实验报告
题目：约瑟夫环
班级：
一．需求分析
1． 本演示程序中，人数n应为任意的，首先应输入一个值赋给初始报数上限m，程序应能自动保存出列人的序号和将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。
2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。
3． 程序执行的命令包括：
（1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。
4． 测试数据
（1）n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。
二．概要设计
为了实现上述操作，应以循环链表为存储结构。
本程序包含三个模块：
（1） 主程序模块；
（2） 构造链表并输入每个人信息模块；
（3） 释放结点模块；
三、程序实现：
#include <iostream.h>
#include <malloc.h>
struct node{
int num;
int code;
node *next;
};//定义一个节点，有一个号码，一个密码，一个指向下一节点的指针
struct cir_link{
node *head;
node *tail;
};//定义一个循环连表
void init_cir_link(cir_link &a,int length){
cout<<"And what are their codes?"<<endl;
a.head=a.tail=(node *)malloc(sizeof(node));
a.head->num=1;
cin>>a.head->code;
int i;
for(i=2;i<=length;i++){
node *q;
if(i==2)
a.head->next=q;
q=(node *)malloc(sizeof(node));
q->num=i;
cin>>q->code;
a.tail->next=q;
a.tail=q;
if(i==length)
q->next=a.head;
}
cout<<"the cir_link created successfully!"<<endl;
}//建立连表，由你来输入人数和每人的密码
void showlink(cir_link a,int length){
for(int i=1;i<=length;i++){
cout<<a.head->num;
a.head=a.head->next;
}
}//一个用来检测连表是否循环的函数，可以不编译
void findhead(cir_link &a){
int n;
cout<<"please input the start number:"<<endl;
cin>>n;
for(int i=1;i<n;i++)
a.head=a.head->next;
cout<<"the start number is "<<a.head->num<<endl;
}//设定起始位置
void joseph(cir_link &a){
node *temp=NULL;
int flag;
flag=a.head->code-1;//第一轮从设定的人开始数
while(1){
for(int i=0;i<flag-1;i++)
a.head=a.head->next;
temp=a.head->next;
if(a.head==temp){
cout<<a.head->num;
return;
}
a.head->next=a.head->next->next;
cout<<temp->num<<"\t";
flag=temp->code;
free(temp);}
}
void main(){
cir_link taitai;
cout<<"How many codes are there?"<<endl;
int num;
cin>>num;
init_cir_link(taitai,num);
findhead(taitai);
joseph(taitai);
cout<<endl<<"end"<<endl;
cin.get();
}
四．调试说明
（1）本程序的运行环境为WIN2.0。
(2) 进入演示程序后即显示提示信息：
How many codes are there?
(输入人数)
And what are their codes?
（输入密码）
the cie_link created successfully!
Please input the start number:
（输入初始数）
he start number is_
_____________
end
Press any key to continue
(3)注意输入程序时中英文状态
五、测试结果：
How many codes are there?
7
And what are their codes?
3
1
7
2
4
8
4
the cie_link created successfully!
Please input the start number:
20
the start number is 6
6 1 4 7 2 3 5
end
Press any key to continue
评论0