约瑟夫环C语言实现源代码

首发:http://www.5dkx.com/arch/65.html

前天笔试有个约瑟夫环的问题，怪不得人家没通知我面试，原来我的约瑟夫环做的确实有问题，昨天晚上又重新做了下，下面上源代码：

/

file:osephu.cpp

author:www.5dkx.com

/

#include

using namespace std;

typedef struct Node{

int sort;

struct Node next;

}Link,List;

int Init(List p); //初始化双链表

int Insert(List p,int key); //插入节点

void Print(List p); //打印双链表

void CreateOsep(List p,int n); //初始化约瑟夫环

void osehup(List p,int m,int len,List Re); //计算约瑟夫环出列顺序，并存放在Re链表中

int main()

{

int m,n;

List p,Re;

Init(&p);

Init(&Re);

cout<<"输入环大小: ";

cin>>n;

cout<<"输入地几个人出列: ";

cin>>m;

CreateOsep(p,n);

cout<<"输入为: "<<endl;

Print(p);

osehup(p,m,n,Re);

cout<<"出队顺序为:"<<endl;

Print(Re);

return 1;

}

//初始化

int Init(List p)

{

p = (List)malloc(sizeof(Link));

if(!(p))

{

cout<<"初始化失败!"<\
return 0;\
\
}\
\
else\
\
{\
\
(*p)->next=p;

//(*p)->sort=1;

}

return 1;

}

//插入节点

int Insert(List p,int key)

{

List tmp = (List)malloc(sizeof(Link));

if(!tmp)

{

cout<<"创建节点失败!"<\
return 0;\
\
}\
\
else\
\
{\
\
tmp->sort=key;

tmp->next=(p)->next;

(p)->next=tmp;

p=tmp;

}

return 1;

}

//创建约瑟夫环

void CreateOsep(List p,int n)

{

List tmp=p;

tmp->sort=1;

for(int i=2;i<=n;i++)

Insert(&tmp,i);

}

//约瑟夫环算法

void osehup(List p,int m,int len,List Re)

{

int count=0;

int allc=0;

List tmp1=p;

List tmp2=Re;

List temp;

while(allc\
{\
\
count++;\
\
if(count == m)\
\
{\
\
temp = tmp1->next;

if(allc==0) //如果是第一次出列

tmp2->sort=temp->sort;

else

Insert(&tmp2,temp->sort);

tmp1->next=tmp1->next->next;

// cout<sort<<" ";

free(temp);

temp=NULL;

allc++;

count=0;

}

else

{

tmp1=tmp1->next;

}





}

cout<<endl;

}

//打印链表

void Print(List p)

{

List tmp=p->next;

cout<sort<<" ";

while(tmp!=p)

{

cout<sort<<" ";

tmp=tmp->next;



}

cout<<endl;

}

运行后效果为：

输入环大小: 5

输入地几个人出列: 6

输入为:

1 2 3 4 5

出队顺序为:

2 4 3 1 5

Press any key to continue

非特别说明均为原创文章如转载，请注明：转载自5D开心博客[ http://www.5DKX.com/ ]

原文链接: https://www.cnblogs.com/5dkx/archive/2010/03/20/1690670.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍