数据结构-joseph环

////joseph环
//时间：05/07/04
//程序：张建波

//输入 n=7 // 3,1,7,2,4,7,4 //输出6 7 4 1 5 3 2


#include <iostream.h>
#include "key.h"

typedef struct person
{ int pwd; //密码
int num; //人数
struct person *next; //指向结构体的指针
}PERSON;



void OutPut(int *a,int n);//输出结果
int CreatPersonList(PERSON *head);// 创建一张链表
int Fx_PersonList(PERSON *head,int n,int *a);//模拟报数


int _f4_main() //函数入口
{

PERSON *head; //定义链表头

cout<<"joseph环 问题模拟!"<<endl;

head=new person; //新建PERSON,并分配内存

int n=CreatPersonList(head); // 创建一张链表,同时返回人数 n

int *a=new int[20]; //保存输出的结果

int x=Fx_PersonList(head,n,a); //模拟报数,同时返回出队人数 count

OutPut(a,x); //输出序列

InitKey();//键盘中断

return 0;
}


int CreatPersonList(PERSON *head){
int n,m,i;
PERSON *p,*q;
cout<<"\n请输入 n=";
cin>>n;
p=head; //p指向表头
for(i=1;i<=n;i++){ //建立链表
cout<<"\n请输入第"<<i<<"的人的报数密码m=";
cin>>m;
p->pwd=m;
p->num=i;
q=new person;
if(i==n)p->next=head; //当 i==n时,循环结束把p1指向表头
else
{
p->next=q;
p=q;
}

}
return n;

}


int Fx_PersonList(PERSON *head,int n,int *a){
PERSON *p1,*p0,*p;
int tm; //临时变量,保存上一密码值
int m; //报数密码 m
int count=1; //出队计数

p0=p1=head; //使p0,p1都指向head头

cout<<"\n请输入 M 的 起始值 m=";
cin>>m;
while(count<=n-1)
{
for(int i=1;i<m;i++)
{ //把 m 重新作为报数上限值
p1=p0;
p0=p0->next;
tm=p0->pwd;
}
m=tm;
p=p0->next;
a[count++]=p0->num; //把每次出队的序号保存在a[x]中
p1->next=p0->next;
delete p0;
p0=p;
}
a[count]=p0->num; //把每次出队的序号保存在a[x]中
p1->next=p0->next;
delete p0;

return count;
}

void OutPut(int *a,int n)
{
cout<<"正确的输出序列为:";
for(int i=1;i<=n;i++) cout<<a[i]<<" ";

}