博客

用单循环链表解决约瑟夫环问题

大致思路:
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函数只是用来显示生成的链表是否存在结点错误以便调试