#include<iostream.h>
template<class ELEM>
class List{
private:
struct ListNode
{
ELEM data;
ELEM num;
ListNode *link;
};
public:
ListNode*first,*last;
List(int n,int max)
{
ListNode *p;
for(int i=1;i<=n;i++)
{
p=new ListNode; //申请新的结点
p->num=i;
cout<<"输入第"<<i<<"位的密码(不能大于"<<max<<"):";
cin>>p->data;
if((p->data)>max)
{
cout<<"输入的密码太大,请重输!"<<endl;
cin>>p->data;
}
if(i==1)
first=p;
p->link=NULL;
if(i!=1)
last->link=p;
last = p;
}
last->link = first; //将头和尾连接起来
}
void print()
{
if(first==NULL)
{
cout<<"没有人员!"<<endl;
}
else
{
ListNode*p;
p=first;
last->link=NULL;
while(p!=NULL)
{
cout<<p->num<<'\t';
cout<<p->data<<endl;
p=p->link;
};
cout<<endl;
last->link=first;
}
}
void Reduce(int i)
{
ListNode*p,*q;
p=first;
if(first==NULL)
{
cout<<"此时链表为空,无法减少结点!"<<endl;
}
else
{
if(i==1)
{
q=p;
last->link=p->link;
first=p->link;
p=first;
first->num=1;
cout<<"退出人员的密码是:"<<(q->data)<<endl;
delete q;
}
else
{
while((p->link->num)!=i)
{
p=p->link;
}
q=p->link;
p->link=q->link;
cout<<"退出人员的密码是:"<<(q->data)<<endl;
delete q;
}
}
p=p->link;
while(p!=first)
{
p->num=p->num-1;
p=p->link;
}
}
void Add(int i,int m)
{
ListNode*p,*q;
p=first;
if(i==1)
{
q=new ListNode;
q->num=i;
q->data=m;
q->link=p;
last->link=q;
first=q;
}
else
{
while((p->num)<(i-1))
{
p=p->link;
}
q=new ListNode;
q->num=i;
q->data=m;
q->link=p->link;
p->link=q;
p=q->link;
}
while(p!=first)
{
p->num=p->num+1;
p=p->link;
}
}
void Move()
{
ListNode *p=first;
first=first->link;
delete p;
last->link=first;
}
void Joseph(int m)
{
while(first!=last)
{
for(int i=1;i!=m;i++) //从1开始报数,报到m就停止
{
first=first->link;
last=last->link;
}
m=first->data; //把要删除的人的密码给m
cout<<"此次出列人员的编号是:"<<first->num<<endl;
cout<<"m重新设置为:"<<m<<endl;
Move(); //从链表中删除
}
cout<<"最后出列人员的编号是:"<<first->num<<endl;
cout<<"它的密码是:"<<first->data<<endl;
Move();
cout<<endl;
first=last=NULL;
}
};
void main()
{
int n,max,m,t;
cout<<"请输入开始需要的总人数:"<<endl;
cin>>n;
if(n>30)
{
cout<<"人数不得超过30人,请重输!"<<endl;
cin>>n;
}
cout<<"请输入要制定的初始报数上限值:"<<endl;
cin>>max;
List<int> L(n,max);
do
{
cout<<"****** 欢迎来到约瑟夫环游戏(单向循环列表法)请选择操作: *******"<<endl;
cout<<"****** 1.删除一个人员的全部信息: *******"<<endl;
cout<<"****** 2.增加一个人员的全部信息: *******"<<endl;
cout<<"****** 3.输出全部人员的全部信息: *******"<<endl;
cout<<"****** 4.游戏开始,进行约瑟夫环游戏: *******"<<endl;
cout<<"****** 5.游戏结束,退出!: *******"<<endl;
cin>>t;
switch(t){
case 1:
int a;
cout<<"请输入要退出人员的编号:"<<endl;
cin>>a;
L.Reduce(a);
break;
case 2:
int bh,mm;
cout<<"请输入要加入人员的编号、密码:"<<endl;
cin>>bh>>mm;
L.Add(bh,mm);
break;
case 3:
cout<<"此时加入游戏的各人编号和密码是:"<<endl;
L.print();
break;
case 4:
cout<<"第一次m的值为:"<<endl;
cin>>m;
L.Joseph(m);
break;
case 5:
cout<<"退出此游戏!"<<endl;
break; }
}while(t!=5);
}
评论0