顺序存储的约瑟夫环.cpp

数据结构课程设计--约瑟夫环问题.有三种方法可以实现.

#include <iostream.h> 
#include<stdlib.h>

const int MaxSize=100;  
template <class T>     
class SeqList
{ 
public:    
   SeqList(int n);      
   ~SeqList();                               
   void Delete(int i);			//出圈、使其后的人前移
   void Get(int key,int n);		//获取下一个出圈者的位置
private:
   T data[MaxSize];				//记录约瑟夫环中每个人的编号
   int length;            
};

template <class T> 
SeqList<T>::SeqList(int n)
{
	if(n>MaxSize||n<=0){
		cout<< "参数非法"<<endl;
		exit(0);
	}
  for (int i=0; i<n; i++)
  {
	  data[i+1]=i+1;                      //对每个人编号后输出
	  cout<<data[i+1]<<" ";
  }
  length=n;
}

template <class T> 
SeqList<T>::~SeqList()
{
}

template <class T>
void SeqList<T>::Delete(int i)			//出圈函数
{ 
	int temp,j;
	if (length==0){
		cout<<"下溢";
	    exit(0);
	}
	if (i<1 || i>length){
	    cout<< "位置异常";
	    exit(0);
	}
	temp=data[i];
	cout<<temp<<' ';					//出圈后，将出圈者后面的人前移	
	for (j=i; j<=length;j++)
	{
		data[j]=data[j+1]; 
	}
	length--;
}

template <class T>
void SeqList<T>::Get(int key,int n)			//确定出圈者位置
{
	int p=key;			
	while(length)
	{
		Delete(p);							//出圈
		if(length!=0)p=(key+p-1)%length;	//计算出下一个出圈的人所在的位置
		if(p==0)p=length;   		 		//当p=0时，圈中最后一个人出圈
	}
	cout<<endl;
}

void main()
{
	int n,key;
	cout<<"请输入围成一圈的人数："<<endl;
	cin>>n;
	cout<<"出圈前人的编号顺序为:"<<endl;
	SeqList<int> Joseph(n);
	cout<<endl;
	cout<<"请输入密码：";
	cin>>key;
	cout<<"出圈的顺序为:"<<endl;
	Joseph.Get(key,n);				
}