迴圈鏈表是一種特殊的單鏈表， 其最後一個結點的指標域指向鏈表的頭結點或者直接指向第一個元素結點。
約瑟夫環是一個數學的應用問題：已知n個人（以編號1， 2， 3...n分別表示）圍坐在一張圓桌周圍。 從編號為k的人開始報數， 數到m的那個人出列；他的下一個人又從1開始報數， 數到m的那個人又出列；依此規律重複下去， 直到圓桌周圍的人全部出列。
約瑟夫環運作如下：
1、一群人圍在一起坐成 環狀；
2、從某個編號開始報數（如：K）；
3、數到某個數（如：M）的時候， 此人出列， 下一個人重新報數；
4、一直迴圈， 直到所有人出列 ， 約瑟夫環結束。
傳說， 39個猶太人與Josephus及他的朋友躲到一個洞中， 39個猶太人決定寧願死也不要被敵人抓。 於是決定了自殺方式， 41個人排成一個圓圈， 由第1個人開始報數， 每報數到第3人該人就必須自殺。 然後下一個重新報數， 直到所有人都自殺身亡為止。 然而Josephus和他的朋友並不想遵從，
這是一個典型的迴圈鏈表題目。 我們需要創建一個迴圈鏈表， 依照遊戲規則， 依次進行刪除結點操作。 直至鏈表為空， 列印出的元素順序即為出局順序！
下面用C語言寫出約瑟夫環問題的程式， 創建鏈表， 添加資料， 依次刪除結點操作， 直到鏈表為空表，
原始程式碼如下：
我們可以任意設置個數n， 以及間隔m。 下圖為一個實例的運行結果， 類比了經典的約瑟夫問題， 41人， 間隔3人， 最後就是16號和31號逃脫！
如果是10人，
間隔3，
則是如下效果：
較複雜的約瑟夫問題：
已知n個人（以編號1， 2， 3...n分別表示， 另外每個人手上都有一個密碼數p）圍坐在一張圓桌周圍。 從編號為k的人開始報數， 順時鐘方向數到m的那個人出列， 並將手中的密碼作為新的報數上限M， 從他的順時鐘方向的下一個人又從1開始報數，
最簡單的解法就是使用一個不帶頭結點的迴圈鏈表來存儲約瑟夫環中每個人的編號和手中的密碼， 然後按照規則進行報數和出列的動作。 其中報數對應迴圈鏈表的迴圈遍歷操作，出列對應的是迴圈鏈表的刪除結點操作。
在main函數中，首先調用CreatJosephRing創建一個包含n個結點的約瑟夫環並用指標list指向其第一個元素的結點，然後設置指標p和q分別指向迴圈鏈表的第一個結點和它的前驅結果。這樣便構成了一個初始狀態，如下圖所示：
接下來就可以動態地執行“報數→出列”的動作，每出列一個成員，實際上就是迴圈鏈表中刪除一個結點，並輸出該結點的編號id作為出隊序列，同時將結點的密碼key作為下一次的報數上限M。這個過程可以通過下面的程式片段來實現：
當指針p不等於q時表明該迴圈鏈表中不只有一個結點，所以迴圈繼續。每次迴圈過程中，指標p和q都順序後移m-1次，最終指標p指向要出列的成員結點，指標q指向其前驅結點。然後通過指針q從鏈表中刪除該結點，通過指針p讀出出列成員結點的id和key。將id輸出作為出列序列，將key賦值給m作為下一次迴圈的報數上限。
當迴圈鏈表只剩下一個結點時，指標p和q指向同一結點，如下圖所示：
此時約瑟夫環中只剩下一個成員，其他成員都已出列，那麼這個成員手中的密碼也沒有用了，於是輸出該結點的成員編號id即可。
運行效果：
附源碼1：
#include
typedef struct node
{
int data;
struct node *next;
}node;
node *create(node *head,int n)
{
int i=1;
node *s,*p=head;
while(i<=n)
{
s=(node *)malloc(sizeof(node));
s->data=i++;
p->next =s;
p=p->next;
}
p->next=head->next;
free(head);
return p->next;
}
int main()
{
int i,n,m,j=1;
node *head,*newstart,*h,*t;
head=(node *)malloc(sizeof(node));
printf("請輸入資料長度n、資料間隔m，如：41,3 ");
scanf("%d,%d",&n,&m);
newstart = create(head,n);
h=newstart;
while(h!=h->next)
{
for(i=1;i { h=h->next; } t=h->next; printf(" %d→",h->next->data); if(j%3==0) printf(" "); h->next=t->next; h=t->next; j++; free(t); } printf("%d",h->data); printf(" "); system("pause"); return 0; } 附源碼2： #include "stdio.h" #include "malloc.h" typedef struct node{ int id;/*成員編號*/ int key; /*密碼*/ struct node *next ;/*指針域*/ }LNode,*LoopLinkList; LoopLinkList CreatJosephRing(int n) { LoopLinkList list,p,r; int e; int i; scanf("%d",&e); /*得到第一個元素結點數據*/ r = list = (LoopLinkList) malloc(sizeof(LNode));/*創建第一個結點*/ list->next = list;/*指標指向自身*/ list->key = e;/*複製第一個結點的資料元素*/ list->id = 1; for(i=2;i<=n;i++) { /*迴圈創建後續的n-1個結點*/ scanf("%d",&e); p=(LoopLinkList)malloc(sizeof(LNode)); p->key = e; p->id = i; p->next = list;/*指向鏈表第一個結點*/ r->next = p;/*將新結點連入迴圈鏈表*/ r = r->next;/*指針r後移*/ } return list; } main() { LoopLinkList list=NULL,p=NULL,q=NULL; int n,m,i; printf("Input the number of the people in Joseph Ring "); scanf("%d",&n); printf("Input the password of the people "); list = CreatJosephRing(n); printf("Input the first Maximum Number M "); scanf("%d",&m); printf("The order of leaving Joseph Ring "); q = p = list; while(q->next!=list) { q = q->next;/*q指向p的前驅結點*/ } while(p!=q) { for(i=0;i { p = p->next; q = q->next; } printf("%3d",p->id);/*輸出出隊者的編號*/ m = p->key;/*下一次的報數上限*/ q->next = p->next;/*刪除結點*/ free(p);/*釋放刪除的結點空間*/ p = q->next; } printf("%3d",p->id); free(p); list = p = q = NULL; printf(" "); system("pause"); } －End－ 在main函數中，首先調用CreatJosephRing創建一個包含n個結點的約瑟夫環並用指標list指向其第一個元素的結點，然後設置指標p和q分別指向迴圈鏈表的第一個結點和它的前驅結果。這樣便構成了一個初始狀態，如下圖所示： 接下來就可以動態地執行“報數→出列”的動作，每出列一個成員，實際上就是迴圈鏈表中刪除一個結點，並輸出該結點的編號id作為出隊序列，同時將結點的密碼key作為下一次的報數上限M。這個過程可以通過下面的程式片段來實現： 當指針p不等於q時表明該迴圈鏈表中不只有一個結點，所以迴圈繼續。每次迴圈過程中，指標p和q都順序後移m-1次，最終指標p指向要出列的成員結點，指標q指向其前驅結點。然後通過指針q從鏈表中刪除該結點，通過指針p讀出出列成員結點的id和key。將id輸出作為出列序列，將key賦值給m作為下一次迴圈的報數上限。 當迴圈鏈表只剩下一個結點時，指標p和q指向同一結點，如下圖所示： 此時約瑟夫環中只剩下一個成員，其他成員都已出列，那麼這個成員手中的密碼也沒有用了，於是輸出該結點的成員編號id即可。 運行效果： 附源碼1： #include typedef struct node { int data; struct node *next; }node; node *create(node *head,int n) { int i=1; node *s,*p=head; while(i<=n) { s=(node *)malloc(sizeof(node)); s->data=i++; p->next =s; p=p->next; } p->next=head->next; free(head); return p->next; } int main() { int i,n,m,j=1; node *head,*newstart,*h,*t; head=(node *)malloc(sizeof(node)); printf("請輸入資料長度n、資料間隔m，如：41,3 "); scanf("%d,%d",&n,&m); newstart = create(head,n); h=newstart; while(h!=h->next) { for(i=1;i { h=h->next; } t=h->next; printf(" %d→",h->next->data); if(j%3==0) printf(" "); h->next=t->next; h=t->next; j++; free(t); } printf("%d",h->data); printf(" "); system("pause"); return 0; } 附源碼2： #include "stdio.h" #include "malloc.h" typedef struct node{ int id;/*成員編號*/ int key; /*密碼*/ struct node *next ;/*指針域*/ }LNode,*LoopLinkList; LoopLinkList CreatJosephRing(int n) { LoopLinkList list,p,r; int e; int i; scanf("%d",&e); /*得到第一個元素結點數據*/ r = list = (LoopLinkList) malloc(sizeof(LNode));/*創建第一個結點*/ list->next = list;/*指標指向自身*/ list->key = e;/*複製第一個結點的資料元素*/ list->id = 1; for(i=2;i<=n;i++) { /*迴圈創建後續的n-1個結點*/ scanf("%d",&e); p=(LoopLinkList)malloc(sizeof(LNode)); p->key = e; p->id = i; p->next = list;/*指向鏈表第一個結點*/ r->next = p;/*將新結點連入迴圈鏈表*/ r = r->next;/*指針r後移*/ } return list; } main() { LoopLinkList list=NULL,p=NULL,q=NULL; int n,m,i; printf("Input the number of the people in Joseph Ring "); scanf("%d",&n); printf("Input the password of the people "); list = CreatJosephRing(n); printf("Input the first Maximum Number M "); scanf("%d",&m); printf("The order of leaving Joseph Ring "); q = p = list; while(q->next!=list) { q = q->next;/*q指向p的前驅結點*/ } while(p!=q) { for(i=0;i { p = p->next; q = q->next; } printf("%3d",p->id);/*輸出出隊者的編號*/ m = p->key;/*下一次的報數上限*/ q->next = p->next;/*刪除結點*/ free(p);/*釋放刪除的結點空間*/ p = q->next; } printf("%3d",p->id); free(p); list = p = q = NULL; printf(" "); system("pause"); } －End－