数据结构约瑟夫环实验报告.doc

一·问题描述
设编号为1，2，…，n个人围坐一圈，约定编号为1的人从1开始报数，数到k的那个人出列，它的下一位又从1开始报数，数到k的那个人又出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。
二·实验描述
该算法可以由三个功能函数实现。main()用做数据的输入和函数调用，creat()做链表的初始化工作，使用Josephus()做删除结点和保存输出顺序的工作，OutRing()完成序列的输出工作。
三·函数设计
#include<iostream.h>
#defineN50
structnode{
intnumber;
node*next;
};
node*creat(intn)
{
node*R,*p,*q;
inti;
R=newnode;
q=R;
for(i=1;i<n;i++){
p=newnode;
q->number=i;
q->next=p;
q=p;
}
p->number=n;
p->next=R;
R=p;
returnR;
}
voidJosephus(node*R,intn,intk,int*quit){
inti,j;
node*p,*q;
p=R;
for(i=0;i<n;i++){
for(j=1;j<=k-1;j++)
p=p->next;
q=p->next;
p->next=q->next;
quit[i]=q->number;
deleteq;
}
}
voidOutRing(intn,int*quit){
inti;
cout<<"新的编码序列为:";
for(i=0;i<n;i++)
cout<<quit[i]<<"";
}
voidmain()
{
intk,n,quit[N];
node*p;
cout<<"请输入总人数:";
cin>>n;
cout<<"请输入出列所需报的数:";
cin>>k;
if(k<1||k>n)
cout<<"输入不符合要求！";
else
{p=creat(n);
Josephus(p,n,k,quit);
OutRing(n,quit);}
}

四·编码实现