循環連結清單 實作 約瑟夫環

【約瑟夫環問題】

已知 n 個人(n>=1)圍坐一圓桌周圍，從 1 開始順序編号，從序号為 1 的人開始報數，順時針數到 m 的那個人出列。下一個人又從 1 開始報數，數到m 的那個人又出列。依此規則重複下去，直到所有人全部出列。請問最後一個出列的人的初始編号。

【要求】

輸入人數 n，所報數 m，輸出最後一個人的初始編号。

【約瑟夫環問題解決思路】

首先因為是圓桌問題，使用連結清單解決的話需要建構循環連結清單。

接着是出列問題，這裡我的設計思路是将指向連結清單的指針移動到需要出列的人的位置，然後根據正常的連結清單删除進行操作即可。

#include <iostream>
using namespace std;

typedef struct node{
	int data;
	node * next;
} LNode, *LinkNode;		// LNode 定義結構體變量， LinkNode 定義結構體指針

int main()
{
	int n, m;
	LinkNode head, p, r;
	cin >> n >> m;
	head = new LNode;	// 先給第一個節點申請存儲空間
	head->data = 1;
	head->next = NULL;
	r = head;
	for(int i=2; i<=n; i++)
	{
		p = new LNode;	// 申請一個新節點
		p->data = i;
		p->next = NULL;	// 後繼為空
		r->next = p;	// 前驅指向目前節點
		r = p;			// 後移指針，始終保持指向最後一個節點

	}
	r->next = head;		// 首位相連
	int num  = 0;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m-2; j++)	// 從一循環到m-2，然後指針移到了應當删除節點的前一個
			r = r->next;
		LinkNode tmp = r->next;		// 儲存要删除的結點
		cout << r->next->data << " ";	// 輸出
		num = r->next->data;		// num留到最後輸出，輸出的是最後一個結點
		r->next = r->next->next;	// 将要被删除的結點的前後結點相連
		r = r->next;	// r 後移 從下一個結點開始下一個循環
		delete tmp;		// 釋放删除節點的空間
	}
	cout << endl;
	cout << num << endl;

	return 0;
}