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

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

#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; /*定義一個(gè)全局變量 */

int Create_clist(CNode *clist,int n) //創(chuàng)建含n個(gè)節(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; /*存儲(chǔ)分配失敗 */

p->ID=i;

p->next=clist;

clist=p;

if(i==n)

q=p;/*用q指向鏈表的最后一個(gè)結(jié)點(diǎn) */

}

q->next=clist; /*把鏈表的最后一個(gè)結(jié)點(diǎn)的鏈域指向鏈表的第一個(gè)結(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;/*起始位置錯(cuò) */

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不為空時(shí)，執(zhí)行循環(huán)*/

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

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

q=p->next;

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

if(p->next==p)

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

else { p->next=q->next;/*刪除第K個(gè)節(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請(qǐng)輸入圍坐在圓桌周圍的人數(shù)n：");

scanf("%d",&n);

printf("n請(qǐng)輸入第一次開(kāi)始報(bào)數(shù)人的位置m：");

scanf("%d",&m);

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

scanf("%d",&k);

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

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

Joseph(clist,m,n,k);

getch();

}/*main */