約瑟夫環(huán)

約瑟夫環(huán)是一個(gè)數(shù)學(xué)的應(yīng)用問題：已知n個(gè)人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報(bào)數(shù)，數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。
鏈表方法：這個(gè)就是約瑟夫環(huán)問題的實(shí)際場景，有一種是要通過輸入n,m,k三個(gè)正整數(shù)，來求出列的序列。這個(gè)問題采用的是典型的循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個(gè)鏈表的尾元素指針指向隊(duì)首元素。 p->link=head 　　解決問題的核心步驟：（程序的基本算法） 　　1.建立一個(gè)具有n個(gè)鏈結(jié)點(diǎn)，無頭結(jié)點(diǎn)的循環(huán)鏈表； 　　2.確定第1個(gè)報(bào)數(shù)人的位置； 　　3.不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表為空。 　　void JOSEPHUS(int n,int k,int m) //n為總?cè)藬?shù)，k為第一個(gè)開始報(bào)數(shù)的人，m為出列者喊到的數(shù) 　　{ 　　/* p為當(dāng)前結(jié)點(diǎn) r為輔助結(jié)點(diǎn)，指向p的前驅(qū)結(jié)點(diǎn) list為頭節(jié)點(diǎn)*/ 　　LinkList p,r,list; /*建立循環(huán)鏈表*/ 　　for(int i=0；idata=i; 　　if(list==NULL) 　　list=p; 　　else 　　r->link=p; 　　r=p; 　　} 　　p->link=list; /*使鏈表循環(huán)起來*/ 　　p=list;　/*使p指向頭節(jié)點(diǎn)*/ 　　/*把當(dāng)前指針移動(dòng)到第一個(gè)報(bào)數(shù)的人*/ 　　for(i=0;ilink; 　　} 　　/*循環(huán)地刪除隊(duì)列結(jié)點(diǎn)*/ 　　while(p->link!=p) 　　{ 　　for(i=0;ilink; 　　} 　　r->link=p->link; 　　printf("被刪除的元素：%4d ",p->data); 　　free(p); 　　p=r->link; 　　} 　　printf("\n最后被刪除的元素是：%4d",P->data); 　　}