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

                                                                       问题描述

  约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

 

就问题来看，需要进行循环删除，在到达尾部后的下一个是头部，而每一次删除都会记录删除删除位置的下一个位置并且把队列给缩短。

因此，我们需要建立一个循环链表来进行解决这个问题。

循环链表简介：

循环链表是一种数据结构，由一些离散数据和连接数据的指针来构成，主要特点是队尾指针执行的是队头，形成一个环状的存储结构

功能：

（1）构造函数-----用于建立空表

（2）析构函数-----用于释放已经申请的内存

（3）添加-----尾插法建立链表，头指针不动，位指针向后移

（4）删除-----删除所输入位置的元素

（5）指向删除-----为了方便约瑟夫环问题解决而建立的

（6）遍历-----输出链表的元素

思路：

根据约瑟夫环游戏进行的过程，每次删除之后下一个开始数数的人为一，所以我建立了一个方法（Todelate（））为了每次删除之后记录删除位置下一个位置为起始点。然后从起始点往后的传入参数个位置进行删除，然后再记录删除后一个位置，如此循环，直到表中只有一个元素为止。

/**循环链表解决约瑟夫环问题=========================>无头指针**/
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
class listnode;
class Link
{
	friend listnode;
private:
	int date;
	Link *link;
};
class listnode
{
private:
	Link *first,*last;
	Link *memorLink;
	int elementsCount;
public :
	//构造
	listnode()
	{
		elementsCount=0;
		first=last=0;
	}
	//析构
	~listnode()
	{
		Link *next=first->link;
		Link *front=first->link;
		do
		{
			front=next->link;
			delete next;
			next=front;
		}while(next!=first);
	}
	//信号设置
	void signSet()
	{
		if(first!=0)
			memorLink=first;
	}
	//加入元素
	void add(int x)
	{
		Link *p=new Link;
		p->date=x;
		if(!first)
		{
			first=last=p;
			last->link=first;
			
		}
		else
		{
			last->link=p;
			last=p;
			last->link=first;
		}
		elementsCount++;
	}

	//删除
	listnode &Delete(int location)
	{
		int index=1;
		Link *p=first;
		while(index<location-1)
		{
			index++;
			p=p->link;
		}
		if(index==1 || p->link==first)
		{
			Link *next=first;
			first=next->link;
			last->link=first;
			delete next;
			return *this;
		}
		else if(p->link==last)
		{
			Link *next=last;
			p->link=next->link;
			last=p;
			delete next;
			return *this;
		}
		else
		{
			Link *next=p->link;
			p->link=next->link;
			delete next;
			return *this;
		}
	}
	//约瑟夫删除
	void Todelete(int location)
	{
		
		Link *p=memorLink;
		int index=1;
		while(index<location-1)
		{
			index++;
			p=p->link;
		}
		if(memorLink==first&&p==first ||p->link==first)
		{
			Link* next=first;
			memorLink=last->link=next->link;
			first=next->link;
			delete next;
		}
		else if(memorLink==last&&p==last || p->link==last)
		{
			Link *next=last;
			Link *front=first;
			for(int i=1;i<elementsCount-1;i++)
			{
				front=front->link;
			}
			memorLink=front->link=next->link;
			last=front;
			delete next;
			
		}
		else
		{
			Link *next=p->link;
			memorLink=p->link=next->link;
			delete next;
			
		}
		elementsCount--;

		

	}
	//获取元素个数
	int getCount()
	{
		return elementsCount;
	}
	//遍历
	void print()
	{
		int count=0;
		Link* p=first;
		if(first->link==first)
		{
			cout<<first->date<<endl;
		}
		else{
			do
			{
				cout<<p->date<<" ";
				p=p->link;
				count++;
			}while(p!=first || count==0);
			cout<<endl;
		}
	}
};
void main()
{
	cout<<"==============================欢迎使用约瑟夫环程序=============================="<<endl;
	listnode list;
	int Juseph;
	int setNumber;
	cout<<"请输入你需要设置的环的大小：";
	cin>>setNumber;
	for(int i=0;i<setNumber;i++)
		list.add(i);
	list.signSet();//至关重要
	cout<<"您设置的环全貌是=======================================》"<<endl;
	list.print();
	cout<<"请输入你需要测试的数据:";
	cin>>Juseph;
	while(list.getCount()!=1)
	{
		list.Todelete(Juseph);
	}
	cout<<"=============================约瑟夫环问题算法结果是============================="<<endl;
	list.print();

	
}