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

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

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

#include <stdio.h>

#include <malloc.h>

#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<m;i++)

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

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

{ for(i=1;i<k-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 */