实验6--约瑟夫环的实现(大作业)

浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验六约瑟夫环的实现学生姓名专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。2、掌握利用线性表的各种操作来进行具体的实际应用。3、加强程序设计的能力。二.实验内容1、编写程序，模拟约瑟夫环（josephus）问题：n个人（编号为1，2，3，……，n(n0)）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i(0i=n)，另一个为起始报数上限值m。接着从编号为i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，……，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。基本要求:（1）人数n、每人的正整数密码、首次报数人编号i、初始报数上限值m均由键盘输入。（2）参照线性表的抽象数据类型定义，设计本实验的抽象数据类型。（3）根据你设计的抽象数据类型，分别用顺序存储结构和链式存储结构实现约瑟夫环问题。并请分别将顺序存储结构的程序存放在文件test6_Seq.h（基本操作函数）、test6_Seq.cpp（主函数）中，链式存储结构的程序存放在文件test6_Link.h（基本操作函数）、test6_Link.cpp（主函数）中。（4）设计测试数据，并调试程序，直到正确运行。2、填写实验报告，实验报告文件取名为report6.doc。3、上传实验报告文件report6.doc及源程序文件test6_Seq.h、test6_Seq.cpp、test6_Link.h、test6_Link.cpp到Ftp服务器（）自己的文件夹下。同时上交一份书面的实验报告。三.抽象数据类型定义（需说明你设计的每个基本操作的功能）1.初始化线性表2.清除线性表3.在线性表中插入某个元素4.删除线性表中的某个元素5．约瑟夫函数四.两种类型（顺序和链式）的存储结构定义及算法思路1.顺序typedefstructList{ElemType*list;intsize;intMaxSize;}SeqList;voidInitList(SeqList&L)；voidClearList(SeqList&L)；boolInsertList(SeqList&L,ElemTypeitem,intpos)；boolDeleteList(List&L,ElemType&item,intpos)2.链式typedefstructLNode{intcode;intnum;structLNode*next;}LNode;voidjosephus(intn,intm,ints)。五.实验结果与分析1.顺序输出结果2.链式输出结果六.心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现2、掌握利用线性表的各种操作来进行具体的实际应用3、加强程序设计的能力，同时对前面所学习的只是进行了回顾，掌握了链表的基本技巧【附录----源程序】1.顺序test6_Seq.cpp#includeiostream.h#includestdio.h#includestdlib.htypedefintElemType;#includetest6_Seq.htypedefstructList{ElemType*list;intsize;intMaxSize;}SeqList;voidmain(){SeqListL;intn,m,i,j;printf(输入人数n,首次报数人编号i,初始报数上限值m:);scanf(%d%d%d,&n,&i,&m);InitList(L);for(j=0;jn;j++)InsertList(L,j+1,0);for(j=0;jn;j++)coutL.list[j]endl;//Josephusintcount=0,k=0,no=1,item;j=i-1;while(countn){if(j=n)j=0;while(jn){if(L.list[j]!=0)k++;if(k==m){printf(No%d:%d\n,no,L.list[j]);k=0;count++;no++;m=L.list[j];L.list[j]=0;DeleteList(L,item,L.list[j]);}j++;}}ClearList(L);}test6_Seq.hvoidInitList(SeqList&L){//初始化线性表L.MaxSize=100;L.list=newElemType[L.MaxSize];if(L.list==NULL){cout动态可分配的存储空间用完，退出运行！endl;exit(1);}L.size=0;}voidClearList(SeqList&L){//清除线性表if(L.list!=NULL){delete[]L.list;L.list=NULL;}L.MaxSize=0;L.size=0;}boolInsertList(SeqList&L,ElemTypeitem,intpos){//按给定条件pos向线性表插入一个元素if(pos-1||posL.size+1){coutpos值无效!endl;returnfalse;}inti;if(pos==0){for(i=0;iL.size;i++)if(itemL.list[i])break;pos=i+1;}elseif(pos==-1)pos=L.size+1;if(L.size==L.MaxSize){intk=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);if(L.list==NULL){cout动态可分配的存储空间用完，退出运行！endl;exit(1);}L.MaxSize=2*L.MaxSize;}for(i=L.size-1;i=pos-1;i--)L.list[i+1]=L.list[i];L.list[pos-1]=item;L.size++;returntrue;}boolDeleteList(List&L,ElemType&item,intpos){if(L.size==0){cout线性表为空，删除无效endl;returnfalse;}if(pos-1||posL.size){coutpos值无效endl;returnfalse;}inti;//根据pos值，确定需删除元素的位置，使下标保存到pos中if(pos==0){//查找删除for(i=0;iL.size;i++)if(item==L.list[i])break;if(i==L.size)returnfalse;pos=i+1;}elseif(pos==-1)pos=L.size;//表尾元素删除item=L.list[pos-1];//被删元素保存返回//从被删元素后开始依次前移，即从下标pos开始移动for(i=pos;iL.size;i++)L.list[i-1]=L.list[i];L.size--;//长度减1//调整线性表空间，空余太多，小于40%时调整if(float(L.size)/L.MaxSize0.4&&L.MaxSize10){intk=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2);L.MaxSize=L.MaxSize/2;//新长度空间}returntrue;}//成功2.链式test6_Link.cpp#includestdio.h#includestdlib.htypedefstructLNode{intcode;intnum;structLNode*next;}LNode;#includetest6_Link.hvoidmain(){intm,n,s;printf(输入人数n,首次报数人编号i,初始报数上限值m:);scanf(%d%d%d,&n,&s,&m);josephus(n,m,s);}test6_Link.hvoidjosephus(intn,intm,ints){structLNode*head;structLNode*p1,*p2;inti,j;p1=(structLNode*)malloc(sizeof(LNode));head=p1;for(i=1;i=n;i++){p1-next=(structLNode*)malloc(sizeof(LNode));printf(输入第%d个人的密码:,i);scanf(%d,&p1-next-code);p1-next-num=i;p1=p1-next;}p1-next=head-next;p2=head-next;deletehead;for(i=1;is;i++){p1=p2;p2=p2-next;if(p2==head){p1=head;p2=head-next;}}printf(出列顺序:);while(p2-next!=p2){for(j=1;jm;j++){p1=p2;p2=p2-next;}printf(%d,p2-code);m=p2-code;p1-next=p2-next;deletep2;p2=p1-next;}printf(%d\n,p2-code);deletep2;}