約瑟夫環問題（單循環連結清單實作）

用單循環連結清單解決約瑟夫環問題

大緻思路:

1.利用尾插法建立一個循環連結清單（建表成功後删除頭結點）

2.核心算法：

生成一個work指針，每走到約定的step-1的位置時停止，利用pdel指針标記後繼結點，循環釋放pdel，直到work==work->next停止

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

typedef int ElemType;
typedef struct CLNode{
	ElemType data;
	struct CLNode *next;
}CLNode,*CLinkList;

CLinkList InitList(int n);
bool Josephus_ring(CLinkList L,int step);
bool ShowList(CLinkList L);

int main()
{
	CLNode *Joseph_ring = NULL;
	cout << "Enter a number: ";
	int n;
	cin >> n;
	Joseph_ring = InitList(n);
	cout << "Enter a step: ";
	int step;
	cin >> step;
	ShowList(Joseph_ring);
	Josephus_ring(Joseph_ring,step);
	cout << "Done.\n";
	return 0;
}

CLinkList InitList(int n)
{
	CLNode *temp,*head,*p = NULL;
	int i = 1;
	head = (CLinkList)malloc(sizeof(CLNode));
	if(head == NULL) 
	{
		cout << "Initiae error.\n";
		exit(EXIT_FAILURE);
	}
	p = head;
	if(n != 0)
	{
		while(i <= n){
			temp = (CLinkList)malloc(sizeof(CLNode));
			temp->data = i++;
			p->next = temp;
			p = temp;
		}
	temp->next = head->next;
	}
	delete(head);
	return temp->next;
}

bool Josephus_ring(CLinkList L,int step)
{
	if(L == NULL)
	{
		cout << "Error.\n";
		return false;
	}
	CLNode *work,*pdel;
	work = L;
	while(work != work->next){
		for(int i = 1; i < step-1; i++)
			work=work->next;
		cout << endl << work->next->data << ' '; 
		pdel = work->next;
		work->next = pdel->next;
		delete(pdel);
		work = work->next;
	}
	cout << "\nThe final number is: " << work->data << endl;
	return true;
}

bool ShowList(CLinkList L)
{
	if(L == NULL)
	{
		cout << "Nothing.\n";
		return false;
	}
	CLNode *pshow = L;
	while(pshow->next != L){
		cout << pshow->data << ' ';
		pshow = pshow->next;
	}
	cout << pshow->data;
	return true;
}
           

ShowList函數隻是用來顯示生成的連結清單是否存在結點錯誤以便調試