新建文本文档.txt

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

实验报告

题目：约瑟夫环
班级：
一．需求分析
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