约瑟夫问题C语言代码实现过程

约瑟夫问题:N个人围成一圈,从第M个位置开始按1.2.3...报数报到K的就出圈,请问出圈的人的顺序.请用链表实现该功能。约瑟夫问题可以用循环单链表解决，循环单链表的特点是链表中最后一个节点的指针域不再是NULL，而是指向整个链表的第一个节点，从而使链表形成一个环。

本题用到链表的建立，删除链表中的节点等知识：

#include

#include

#define NULL 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

typedef struct Cnode

{ int ID;

struct Cnode next;

}CNode;

CNode joseph; /定义一个全局变量 /

int Create_clist(CNode clist,int n) //创建含n个节点的循环单链表

{ CNode p,q;

int i;

clist=NULL;

for(i=n;i>=1;i--)

{ p=(CNode )malloc(sizeof(CNode));

if(p==NULL)

return OVERFLOW; /存储分配失败 /

p->ID=i;

p->next=clist;

clist=p;

if(i==n)

q=p;/用q指向链表的最后一个结点 /

}

q->next=clist; /把链表的最后一个结点的链域指向链表的第一个结点，构成循环链表 /

joseph=clist; /把创建好的循环链表头指针赋给全局变量 /

return OK;

} /end /

int Josephus(CNode clist,int m,int n,int k)

{ int i;

CNode p,q;

if(m>n) return ERROR;/起始位置错 /

if(!Create_clist(clist,n))

return ERROR; /循环链表创建失败 /

p=joseph; /p指向创建好的循环链表 /

for(i=1;i

p=p->next; /p指向m位置的结点 /

while(p) /当p不为空时，执行循环/

{ for(i=1;i

p=p->next; / 找出第k个结点q /

q=p->next;

printf("%d ",q->data);/输出应出列的结点 /

if(p->next==p)

p=NULL; /删除最后一个结点 /

else { p->next=q->next;/删除第K个节点/

p=p->next;

free(q);/这句很重要/

}

} / end while /

clist=NULL;

} / end /

void main( )

{ int m,n,k,i;

CNode clist;

clist=NULL;/初始化clist /

printf("\n请输入围坐在圆桌周围的人数n：");

scanf("%d",&n);

printf("\n请输入第一次开始报数人的位置m：");

scanf("%d",&m);

printf("\n你希望报数到第几个数的人出列?");

scanf("%d",&k);

Create_clist(clist,n);/创建一个有n个结点的循环链表clist /

printf("\n出列的顺序如下：\n");

Joseph(clist,m,n,k);

getch();

}/main /