循環鏈表介紹
先不急著看約瑟夫問題是什么，先了解循環鏈表的結構，那什么是循環鏈表？
循環，顧名思義，從鏈表中第一個節點出發，還會遇到第一個節點，形成循環的一環。也就是說鏈表中最后一個節點的下一個節點是第一個節點，但是頭節點也是一個節點，所以最后一個節點的下一個節點應該是頭節點才對。
如下圖，有兩種情況：
其中更大的長方形是節點的數據域，更小的長方形是節點的指針域，指向鏈表中的下一個節點。
循環鏈表的代碼實現
因為解決約瑟夫問題，只需要初始化、插入、打印功能，所以別的功能就沒實現。
節點定義
首先，循環鏈表和普通鏈表節點的結構體定義一模一樣，那就寫出來吧。
typedef struct _LoopLinkList //循環鏈表
{int date;struct _LoopLinkList* next;
}LinkNode,LinkList;?循環鏈表的初始化
初始化循環鏈表，其中函數的參數是一個指向頭節點的指針，如圖所示：
兩個箭頭有些重疊了，不過無傷大雅。
函數參數中的取地址符?& 是引用的意思，為C++特有的，相當于就在使用這個一級指針 L ，無需使用二級指針來接收這個一級指針 L 的地址，如果去掉這個 & ，會發生什么事呢？那就是 L 這個指針所指向的地址無法改變，但是可以改變所指向的變量的值。
bool initLinkList(LinkList *&L)
{L = new LinkNode; //為頭結點申請空間if (!L) return false; // L為空指針,生成頭結點失敗L->next = L; //頭結點指向自己L->date = -1;return true;
}如果上面那段話不太明白，可以先跳過，等寫完所有代碼，然后把初始化函數參數中的 & 去掉，在 IDE 中調試一下即可得出答案。
循環鏈表的插入（尾插法）
其中函數的參數節點指針 node 指向新加節點。
bool InsertBack(LinkList* &L, LinkNode* node)
{if (!L || !node) return false; //如果鏈表頭結點未創建或者傳入的結點指針指向空//分兩種情況,一是鏈表為空,只有頭結點存在if (L->next == L){node->next = L;L->next = node;}else{LinkNode* p = L;while (p->next != L){p = p->next;} //找到最后一個節點p->next = node;node->next = L;}return true;
}循環鏈表的打印
從頭節點開始打印，直到又為頭節點。
bool LinkPrint(LinkList* L)
{if (!L) return false;LinkNode* p = L;p = L ->next;while (p != L){printf("%d ", p->date);p = p->next;}return true;
}
約瑟夫問題
解決了循環鏈表，就開始約瑟夫問題了，哈哈，這故事有很多的分支，我之前聽過的不是下面這種。
據說著名猶太歷史學家Josephus有過以下的故事：在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。問題是，給定了和，一開始要站在什么地方才能避免被處決。Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。
——摘自約瑟夫問題_百度百科
?不過看完這個故事應該大概了解了約瑟夫問題，這個問題可以用循環鏈表解決，每一個人都是鏈表中一個節點，只要某個節點報數報到出圈的那個號碼，就把這個節點從鏈表中刪除。
由于原問題的人數實在太多，我這里就簡化一下，一共 10 人，報數報到 9 的人出圈，并且要求求出第五輪出圈的號碼，還有最后一個出圈的人的號碼，所以添加了兩個整型變量 loops、num來記錄。
首先在進入這個函數之前已經把 10 個節點插入了鏈表，第 n 個節點的值為 n ，例如：第一個節點的數據域為 1 。
代碼實現
其中函數參數 interval 為間隔，也就是出圈的號碼 9 。
bool Joseph(LinkList* &L,int interval)
{if ( !L || L->next == L) return false; // 頭節點未初始化或者是空鏈表if (interval < 1) return false; //報數的間隔也不能小于 1 ， 1 的話還能玩，也就是一報數就死LinkNode* p = L , *q = NULL ; // q 指向要刪除的節點， p 指向要刪除的節點的前一個節點int loops = 0 , num = 0 ; //loops表示進行到第幾輪，num保存著出圈的人的號碼int j = 1;while (L->next != L) //不為空鏈表{while ( j < interval ) //一直報數，除非j等于出圈的數-1，這時候指針p就指向了要刪除的節點的前一個節點{if (p->next != L){j++;} p = p->next;}if (p->next == L) //如果p指向最后一個節點，那肯定不能刪除頭節點，應該刪除第一個節點，所以p賦值為頭節點{p = L;}//刪除q = p->next;num = q->date;p->next = q->next;delete q;j = 1;loops++;cout <<endl<< "這是第"<<loops<<"輪:" ;LinkPrint(L);if (loops == 5){printf("\n第5輪出圈的是:%d", num);}}printf("最后一個出圈的是:%d\n", num);return true;
}?可能有人會想為什么其中循環的條件不是 i <= j 呢？因為在單向鏈表中，你刪除一個節點前，必須要讓刪除節點的上一個節點的next 指針指向刪除節點的下一個節點。
所以指向要刪除的節點的上一個節點就方便很多了
如下圖：
?
完整代碼以及運行結果
#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>using namespace std;
//結點結構體
typedef struct _LoopLinkList
{int date;struct _LoopLinkList* next;
}LinkNode,LinkList;//初始化
bool initLinkList(LinkList* &L)
{ L = new LinkNode;if (!L) return false; L->next = L; //指向自己L->date = -1;return true;
}//尾插法
bool InsertBack(LinkList* L, LinkNode* node)
{if (!L || !node) return false; if (L->next == L) //鏈表為空,只有頭結點{node->next = L;L->next = node;}else{LinkNode* p = L;while (p->next != L){p = p->next;}p->next = node;node->next = L;}return true;
}//打印
bool LinkPrint(LinkList* L)
{if (!L) return false;LinkNode* p = L;p = L ->next;while (p != L){printf("%d ", p->date);p = p->next;}return true;
}//解決joseph問題
bool Joseph(LinkList*& L, int interval)
{if (!L || L->next == L) return false; // 頭節點未初始化或者為空鏈表if (interval < 1) return false; //報數的間隔LinkNode* p = L, * q = NULL; int loops = 0, num = 0; //loops表示進行到第幾輪，num保存著最后一個出圈的人的號碼int j = 1;while (L->next != L) {while (j < interval) {if (p->next != L){j++;}p = p->next;}if (p->next == L) {p = L;}//此時 p 指向要刪除節點的前一個節點（不為最后一個節點）q = p->next;num = q->date;p->next = q->next;delete q;j = 1;loops++;cout << endl << "這是第" << loops << "輪:";LinkPrint(L);if (loops == 5){printf("\n第5輪出圈的是:%d", num);}}printf("最后一個出圈的是:%d\n", num);return true;
}
int main(void)
{LinkList* L = NULL ;LinkNode* e = NULL;//1.初始化循環鏈表initLinkList(L);//2.尾插循環鏈表for (int i = 1; i <= 10; i++){e = new LinkNode;e->date = i;e->next = NULL;InsertBack(L, e);}//3.打印鏈表LinkPrint(L);Joseph(L, 9);return 0;
}---------------------------------------------------------------------------------------------------------------------------------
?
