约瑟夫环问题

问题描述：设编号为1,2,…,n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，抱m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数；如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。

基本要求：

（1）初始报数上限值m和测试数据在程序中确定；

（2）用带头结点的单循环链表作数据元素的存储结构；

（3）把带头结点的单循环链表作为抽象数据类型设计。

测试数据：

n = 7，七个人的密码依次为3,1,7,2,4,8,4

初始报数上限值m = 20

#include<iostream.h>

typedef struct LNode{
int data,code;
struct LNode *next;
}LNode,*LinkList;

void main()
{

int m,n,i;
cout<<"输入初始报数上限值m: "<<endl;
cin>>m;
cout<<"输入人数n: "<<endl;
cin>>n;
cout<<"输入各人密码："<<endl;
LinkList p,head,q;
head=new LNode;
head->data=1;
cin>>head->code ;
p=head;

//初始化单向循环链表
for(i=2;i<=n;i++)
{
struct LNode *s=new LNode;
s->data=i;
cin>>s->code;
p->next=s;
p=p->next;
}
p->next=head;
cout<<"出列顺序为： "<<endl;

//处理出列顺序
while(n!=1)
{
for(i=1;i<m;i++)
{
p=p->next;
}
q=p->next;
p->next=q->next;
m=q->code;
cout<<q->data<<' ';
delete q;
n--;
}
cout<<p->data<<endl;
}