实习报告
题目：约瑟夫环
班级：031014 姓名：刘嵩学号：03101409 完成日期：2011.11.16
一、需求分析
1.本演示程序中，要求用户输入人数n和初始报数上限的值m。

并依次输入n个人
的密码（password）。

程序输出n个人的出列顺序。

2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之
后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和越算结
果显示在其后。

3.程序执行的命令包括
1）构造链表2）依照题意对链表进行操作，每次删除一个链表的节点并将删
除节点的编号输出3）结束
4. 测试数据
Sample input
7 20
3 1 7 2
4 8 4
Sample output
6 1 4
7 2 3 5
二、概要设计（算法描述）
为实现上述程序功能，应以循环列表表示n个人围坐一圈。

循环列表每个节点所要包含的信息包括：1.每个人的编号 2.每个人的密码 3.指向下一个节点的指针。

建好链表后，从链表的首个节点开始，顺着链表向后移m次，得到一个节点Node。

输出Node的编号，并将Node从链表中删除，然后讲Node的密码值作为新的m。

重复以上步骤，直到所有节点均被从链表中删除为止。

算法复杂度为O(m*n)。

三、详细设计
代码如下:
#include<iostream>
using namespace std;
struct node
{
int id;
int password;
node* next;
};
int main()
{
i nt m,n;
c out<<"Enter the number of people:";
c in>>n;
c out<<"Enter the value of 'm':";
c in>>m;
n ode* p=new node [n+1];
c out<<"Enter the "<<n<<" people's password:"<<endl;
i nt i;
f or(i=0;i<n;i++){cin>>p[i].password;p[i].id=i+1;}
f or(i=0;i<n-1;i++)p[i].next=&p[i+1];
p[n-1].next=&p[0];
n ode* temp=&p[0];
n ode* last=&p[n-1];
w hile(n)
{
for(i=0;i<m-1;i++)
{
if(i==m-2)last=temp;
temp=temp->next;
}
last->next=temp->next;
cout<<temp->id<<" ";
n--;
m=temp->password+1;
}
c out<<endl;
d elet
e [] p;
r eturn 0;
}
四、调试分析
1、刚开始时last指针没有赋初值，会造成应对一些数据时无法输出结果。

五、用户手册
根据提示输入数据即可
六、测试结果
Enter the number of people:7
Enter the value of 'm':20
Enter the 7 people's password:
3 1 7 2
4 8 4
6 1 4
7 2 3 5
Process returned 0 (0x0) execution time : 19.437 s Press any key to continue.。