回圈鏈表
把鏈表的兩頭連接，使其成為了一個環狀鏈表，通常稱為回圈鏈表，
和它名字的表意一樣，只需要將表中最后一個結點的指標指向頭結點，鏈表就能成環兒，下圖所示，
需要注意的是，雖然回圈鏈表成環狀，但本質上還是鏈表，因此在回圈鏈表中，依然能夠找到頭指標和首元節點等，回圈鏈表和普通鏈表相比，唯一的不同就是回圈鏈表首尾相連，其他都完全一樣，
回圈鏈表實作約瑟夫環
約瑟夫環問題，是一個經典的回圈鏈表問題，題意是：已知 n 個人（分別用編號 1，2，3，…，n 表示）圍坐在一張圓桌周圍，從編號為 k 的人開始順時針報數，數到 m 的那個人出列；他的下一個人又從 1 開始，還是順時針開始報數，數到 m 的那個人又出列；依次重復下去，直到圓桌上剩余一個人，
如下圖所示，假設此時圓周周圍有 5 個人，要求從編號為 3 的人開始順時針數數，數到 2 的那個人出列：
出列順序依次為：
編號為 3 的人開始數 1，然后 4 數 2，所以 4 先出列；
4 出列后，從 5 開始數 1，1 數 2，所以 1 出列；
1 出列后，從 2 開始數 1，3 數 2，所以 3 出列；
3 出列后，從 5 開始數 1，2 數 2，所以 2 出列；
最后只剩下 5 自己，所以 5 勝出，
約瑟夫環問題有多種變形，比如順時針轉改為逆時針等，雖然問題的細節有多種變數，但解決問題的中心思想是一樣的，即使用回圈鏈表，
通過以上的分析，我們可以嘗試撰寫 C 語言代碼，完整代碼如下所示：
————————————
typedefstruct node{ int number; structnode * next; }person; person * initLink(int n){ person * head=(person*)malloc(sizeof(person)); head->number=1; head->next=NULL; person * cyclic=head;for(inti=2; i<=n; i++) { person * body=(person*)malloc(sizeof(person)); body->number=i; body->next=NULL; cyclic->next=body; cyclic=cyclic->next; } cyclic->next=head;//首尾相連return head; }voidfindAndKillK(person * head,intk,int m){ person * tail=head;//找到鏈表第一個結點的上一個結點，為洗掉操作做準備while(tail->next!=head) { tail=tail->next; } person * p=head;//找到編號為k的人while(p->number!=k) { tail=p; p=p->next; }//從編號為k的人開始，只有符合p->next==p時，說明鏈表中除了p結點，所有編號都出列了，while(p->next!=p) {//找到從p報數1開始，報m的人，并且還要知道數m-1de人的位置tail，方便做洗掉操作，for(inti=1; i tail=p; p=p->next; } tail->next=p->next;//從鏈表上將p結點摘下來printf("出列人的編號為:%d\n",p->number);free(p); p=tail->next;//繼續使用p指標指向出列編號的下一個編號，游戲繼續} printf("出列人的編號為:%d\n",p->number);free(p); }int main() { printf("輸入圓桌上的人數n:");int n; scanf("%d",&n); person * head=initLink(n); printf("從第k人開始報數(k>1且k<%d)：",n);int k; scanf("%d",&k); printf("數到m的人出列：");int m; scanf("%d",&m); findAndKillK(head, k, m);return0; }
————————————
看到這里你是不是對C語言又有了一點新的認知呢~
如果你喜歡這篇文章的話，動動小指，點個贊再走~
如果你想學編程，小編推薦一個C語言/C++編程學習基地【點擊進入】！
一個活躍、高逼格、高層次的編程學習殿堂；編程入門只是順帶，思維的提高才有價值！
涉及：編程入門、游戲編程、網路編程、Windows編程、Linux編程、Qt界面開發、黑客等等...
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/166738.html
標籤：C
上一篇：十大經典排序演算法（動圖演示）