不同密码的约瑟夫环.cpp

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

#include<iostream.h>

template <class T>
struct Node
{
	T data;
	T key;						//密码
	Node<T> *next;
};

template <class T>
class LinkList 
{
	public:
		LinkList(T a[],int n,T mima[]);
	    void Outcycle();
	private:
		Node<T> *first;
};


template <class T>
LinkList<T>::LinkList(T a[],int n,T mima[])
{
	first=new Node<T>;
	first->next=NULL;
	Node<T> *p;
	p=first;
	for(int i=0;i<n;i++)
	{
		Node<T> *s;					//初始化连表
		s=new Node<T>;
		s->data=a[i];				//记录每个人的编号
		s->key=mima[i];				//记录下每个人所持有的密码
		p->next=s;
		s->next=NULL;
		p=s;
	}
	p->next=first->next;
}

template <class T>
void LinkList<T>::Outcycle()			//出圈函数
{
	T CurentKey;			//当前密码
	Node<T> *pre,*p,*temp;
   	pre=first;
	p=first->next;
	int count=1;
	CurentKey=p->key; 
	while(p!=pre)
	{
		if(count==CurentKey){
			cout<<p->data<<' ';
			temp=p;
			pre->next=p->next;			 //出队列
			p=p->next;         
			CurentKey=temp->key;         //获取新密码
			delete temp;
			count=1;				//出圈后，计数器重新计数
		}
		else {
			pre=pre->next;			//还为计数到出圈者的位置，指针后移，继续向后数
			p=p->next;
			count++;		
		}
	}
	cout<<p->data<<endl;				 //最后一个人出圈
    delete p;
}


void main()
{
	int n,p;
	cout<<"请输入围成一圈的人数：";
	cout<<endl;
	cin>>n;
	int*num,*mima;
	num=new int[n];
	mima=new int[n];
	cout<<"请输入对应的密码："<<endl;
	cout<<"编号"<<'\t'<<"密码"<<endl;
	for(int j=0;j<n;j++)
	{
		num[j]=j+1;
		cout<<num[j]<<'\t';
		cin>>p;
		mima[j]=p;
	}
	cout<<"循环前的"<<n<<"个人的次序和密码为："<<endl;
	cout<<"次序"<<'\t'<<"密码"<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<num[i]<<'\t';
		cout<<mima[i]<<endl;
	}
	cout<<n<<"个人的出圈顺序为："<<endl;
	LinkList<int> Joseph(num,n,mima);
	Joseph.Outcycle();
}