約瑟夫問題:N個人圍成一圈,從第M個位置開始按1.2.3...報數(shù)報到K的就出圈,請問出圈的人的順序.請用鏈表實現(xiàn)該功能。約瑟夫問題可以用循環(huán)單鏈表解決，循環(huán)單鏈表的特點(diǎn)是鏈表中最后一個節(jié)點(diǎn)的指針域不再是NULL，而是指向整個鏈表的第一個節(jié)點(diǎn)，從而使鏈表形成一個環(huán)。

本題用到鏈表的建立，刪除鏈表中的節(jié)點(diǎn)等知識：

#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) //創(chuàng)建含n個節(jié)點(diǎn)的循環(huá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指向鏈表的最后一個結(jié)點(diǎn) */

}

q->next=clist; /*把鏈表的最后一個結(jié)點(diǎn)的鏈域指向鏈表的第一個結(jié)點(diǎn)，構(gòu)成循環(huán)鏈表 */

joseph=clist; /*把創(chuàng)建好的循環(huán)鏈表頭指針賦給全局變量 */

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; /*循環(huán)鏈表創(chuàng)建失敗 */

p=joseph; /*p指向創(chuàng)建好的循環(huán)鏈表 */

for(i=1;i<m;i++)

p=p->next; /*p指向m位置的結(jié)點(diǎn) */

while(p) /*當(dāng)p不為空時，執(zhí)行循環(huán)*/

{ for(i=1;i<k-1;i++)

p=p->next; /* 找出第k個結(jié)點(diǎn)q */

q=p->next;

printf("%d ",q->data);/*輸出應(yīng)出列的結(jié)點(diǎn) */

if(p->next==p)

p=NULL; /*刪除最后一個結(jié)點(diǎn) */

else { p->next=q->next;/*刪除第K個節(jié)點(diǎn)*/

p=p->next;

free(q);/*這句很重要*/

}

} /* end while */

clist=NULL;

} /* end */

void main( )

{ int m,n,k,i;

CNode *clist;

clist=NULL;/*初始化clist */

printf("n請輸入圍坐在圓桌周圍的人數(shù)n：");

scanf("%d",&n);

printf("n請輸入第一次開始報數(shù)人的位置m：");

scanf("%d",&m);

printf("n你希望報數(shù)到第幾個數(shù)的人出列?");

scanf("%d",&k);

Create_clist(clist,n);/*創(chuàng)建一個有n個結(jié)點(diǎn)的循環(huán)鏈表clist */

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

Joseph(clist,m,n,k);

getch();

}/*main */