相同密码的约瑟夫环.cpp

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

#include<iostream.h>

template <class T>
struct Node
{
	T data;								//编号
	Node<T> *next;
};


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


template <class T>
LinkList<T>::LinkList(T a[],int n)
{
	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];
		p->next=s;
		p=s;
	}
	p->next=first->next;
	
}



template <class T>
void LinkList<T>::Outcycle(int key)			//定义出圈函数
{
	Node<T> *pre,*p,*temp;
    pre=first;
	p=first->next;
	int count=1;
	while(p!=pre)
	{
		if(count==key){						//计数器计满密码后，出圈
			cout<<p->data<<' ';
			temp=p;
			pre->next=p->next;
			p=p->next;
			delete temp;
			count=1;
		}
		else {								//计数器未计满密码后，继续计数
			pre=pre->next;
			p=p->next;
			count++;
		}
	}
	cout<<p->data<<endl;
    delete p;
}


void main()
{
	int n,m;
	cout<<"请输入围成一圈的人数：";
	cout<<endl;
	cin>>n;
	int*a;									
	a=new int[n];								//动态申请数组空间,用来存放n个人的原始顺序
	for(int j=0;j<n;j++)
	{
		a[j]=j+1;								//对n个人编号
	}
	cout<<"出圈前的"<<n<<"个人的次序编号为："<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<' ';						//输出n个人出圈前的顺序
		
	}
	cout<<endl;
	cout<<"请输入密码："<<endl;
	cin>>m;										//设置共同密码
	cout<<n<<"个人的出圈顺序编号为："<<endl;
	LinkList<int> Joseph(a,n);						//对LinkList进行初始化
	Joseph.Outcycle(m);								//出圈
}