約瑟夫環(huán)

約瑟夫環(huán)是一個數(shù)學的應用問題：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復下去，直到圓桌周圍的人全部出列。
鏈表方法：這個就是約瑟夫環(huán)問題的實際場景，有一種是要通過輸入n,m,k三個正整數(shù)，來求出列的序列。這個問題采用的是典型的循環(huán)鏈表的數(shù)據(jù)結構，就是將一個鏈表的尾元素指針指向隊首元素。 p->link=head 　　解決問題的核心步驟：（程序的基本算法） 　　1.建立一個具有n個鏈結點，無頭結點的循環(huán)鏈表； 　　2.確定第1個報數(shù)人的位置； 　　3.不斷地從鏈表中刪除鏈結點，直到鏈表為空。 　　void JOSEPHUS(int n,int k,int m) //n為總人數(shù)，k為第一個開始報數(shù)的人，m為出列者喊到的數(shù) 　　{ 　　/* p為當前結點 r為輔助結點，指向p的前驅結點 list為頭節(jié)點*/ 　　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é)點*/ 　　/*把當前指針移動到第一個報數(shù)的人*/ 　　for(i=0;ilink; 　　} 　　/*循環(huá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); 　　}