约瑟夫问题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  */