实验六约瑟夫环的实现.docx
- 文档编号:17793302
- 上传时间:2023-08-03
- 格式:DOCX
- 页数:16
- 大小:133.91KB
实验六约瑟夫环的实现.docx
《实验六约瑟夫环的实现.docx》由会员分享,可在线阅读,更多相关《实验六约瑟夫环的实现.docx(16页珍藏版)》请在冰点文库上搜索。
实验六约瑟夫环的实现
浙江大学城市学院实验报告
课程名称数据结构基础
实验项目名称实验六约瑟夫环的实现
学生姓名专业班级学号
实验成绩指导老师(签名)日期
一.实验目的和要求
1、学会通过对问题的分析,设计一种合理的数据结构,并进行定义及操作的实现。
2、掌握利用线性表的各种操作来进行具体的实际应用。
3、加强程序设计的能力。
二.实验内容
1、编写程序,模拟约瑟夫环(josephus)问题:
n个人(编号为1,2,3,……,n(n>0))按顺时针方向围坐一圈,每人持有一个正整数密码。
开始时任意给出两个值:
一个为首先报数的人的编号i(0
接着从编号为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服务器(ftp:
//10.61.14.240:
5000)自己的文件夹下。
同时上交一份书面的实验报告。
三.抽象数据类型定义
(需说明你设计的每个基本操作的功能)
voidInitList(SeqList&L):
初始化线性表
boolInsertList(SeqList&L,ElemTypeitem):
插入数据使线性表中有数据
boolDeleteList(SeqList&L,ElemType&item,intpos):
删除数据模拟人离开
intLengthList(SeqListL):
求线性表的长度,判断人是否为空
ElemTypeGetList(SeqListL,intpos):
根据密码查找下个离开的人
四.两种类型(顺序和链式)的存储结构定义及算法思路
(包括两种存储结构定义及一些重要函数的算法实现思路)
数据类型定义:
typedefstructm
{
intnum,password;
}ElemType;
顺序表:
typedefstructList
{
ElemType*list;
intsize;
intMaxSize;
}SeqList;
voidInitList(SeqList&L):
开辟空间,为size、MaxSize赋初值
boolInsertList(SeqList&L,ElemTypeitem):
在顺序表的最后插入item
boolDeleteList(SeqList&L,ElemType&item,intpos):
删除在顺序表中第pos的值
intLengthList(SeqListL):
返回顺序表的长度
ElemTypeGetList(SeqListL,intpos):
返回第pos位的值
单链表:
typedefstructLNode
{//定义单链表节点类型
ElemTypedata;//存放结点中的数据信息
LNode*next;//指示下一个结点地址的指针
};
voidInitList(LNode*&H):
初始化单链表,建立带表头附加节点的单链表
boolInsertList(LNode*&H,ElemTypeitem):
在单链表末尾增加数据
boolDeleteList(LNode*&H,ElemType&item):
删除与item相同的节点
intLengthList(LNode*H):
通过遍历单链表算出长度
ElemTypeGetList(LNode*H,intpos):
取第pos为上的节点数据
五.实验结果与分析
(包括运行结果截图、结果分析等)
六.心得体会
(记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
)
ElemType类型定义时要小心,尤其在删除插入函数中的具体调用
对于结构体的整体调用判断时,可以利用结构体的某一成员作为标准
【附录----源程序】
test6_Seq.h
typedefstructList{
ElemType*list;
intsize;
intMaxSize;
}SeqList;
voidInitList(SeqList&L)
{//初始化线性表
L.MaxSize=MAXSize;
L.list=(ElemType*)malloc(L.MaxSize*sizeof(SeqList));
if(L.list==NULL)
{
cout<<"初始化失败"< exit (1); } L.size=0; } boolInsertList(SeqList&L,ElemTypeitem) {//按给定条件pos向线性表插入一个元素 if(L.size==L.MaxSize) { L.list=(ElemType*)realloc(L.list,2*L.MaxSize*sizeof(ElemType)); if(L.list==NULL) { printf("空间分配失败\n"); exit (1); } L.MaxSize*=2; } L.list[L.size]=item; L.size++; returntrue; } boolDeleteList(SeqList&L,ElemType&item,intpos) { inti; if(L.size==0){ cout<<"顺序表已空无数据可删! "< returnfalse; } if(pos<-1||pos>L.size){ cout<<"参数pos不合法! "< returnfalse; } //找删除位置,赋值给pos if(pos==0){ for(i=0;i if(item.num==L.list[i].num)break; if(i==L.size)returnfalse; pos=i+1; } elseif(pos==-1)pos=L.size; item=L.list[pos-1];//返回删除元素值 //删除数据元素 for(i=pos;i L.list[i-1]=L.list[i]; L.size--; //若线性表空余空间太多,重新分配压缩 if(float(L.size)/L.MaxSize<0.4&&L.MaxSize>10) { L.list=(ElemType*)realloc(L.list,L.MaxSize*sizeof(ElemType)/2); L.MaxSize=L.MaxSize/2; } returntrue; } intLengthList(SeqListL) {//求线性表长度 returnL.size; } ElemTypeGetList(SeqListL,intpos) {//在线性表L中求序号为pos的元素,该元素作为函数值返回 if(pos<0||pos>=L.size) { printf("pos输入错误\n"); exit (1); } returnL.list[pos]; } test6_Seq.cpp #include #include #include typedefstructshu { intpassword,num; }ElemType; #defineMAXSize20; #include"test6_Seq.h" voidmain(void) { SeqListmyList; ElemTypetemp; intn,no,i,k,count=1; printf("输入人数n: "); scanf("%d",&n); InitList(myList); printf("请继续输入%d组密码\n",n); for(i=0;i { printf("输入第%d组密码: ",i+1); temp.num=i+1; scanf("%d",&temp.password); InsertList(myList,temp); } printf("输入首次报数人编号: "); scanf("%d",&k); printf("初始报数上限值: "); scanf("%d",&no); i=k-1; k=0; while(LengthList(myList)>0) { temp=GetList(myList,i); k++; if(k==no) { printf("第%d个出列的人: %d\n",count,temp.num); count++; no=temp.password; DeleteList(myList,temp,0); k=0; i--; } i++; if(i==LengthList(myList)) i=0; } } test6_Link.h voidInitList(LNode*&H) { H=(LNode*)malloc(sizeof(LNode)); if(! H)exit(0); H->next=NULL; } boolInsertList(LNode*&H,ElemTypeitem) { LNode*newptr,*cp,*ap; newptr=(LNode*)malloc(sizeof(LNode)); newptr->data=item; ap=H; cp=H->next; while(cp! =NULL) { ap=cp; cp=cp->next; } newptr->next=cp; ap->next=newptr; returntrue; } boolDeleteList(LNode*&H,ElemType&item) { if(H->next==NULL) { cout<<"链表为空"< return0; } LNode*cp,*ap; cp=H->next; ap=H; while(cp! =NULL) { if(item.num==cp->data.num) break; else { ap=cp; cp=cp->next; } } if(cp==NULL) { cout<<"没有相应结点可删除! "< returnfalse; } ap->next=cp->next; free(cp); return1; } intLengthList(LNode*H) { inti=0; while(H->next! =NULL) { i++; H=H->next; } returni; } ElemTypeGetList(LNode*H,intpos) { inti=0; if(pos<1) { cout<<"poserror"< exit (1); } while(H->next! =NULL) { i++; if(pos==i)break; H=H->next; } if(H! =NULL) returnH->next->data; else { cout<<"poserror"< exit (1); } } voidTraverseList(LNode*H) { LNode*p; p=H->next; while(p! =NULL) { cout< p=p->next; } cout< } test6_Link.cpp #include #include #include typedefstructm { intnum,password; }ElemType; typedefstructNode {//定义单链表节点类型 ElemTypedata;//存放结点中的数据信息 Node*next;//指示下一个结点地址的指针 }LNode; #include"test6_Link.h" voidmain(void) { LNode*myList; intn,no,i,k,count=1; ElemTypetemp; InitList(myList); printf("请输入人数n: "); cin>>n; printf("请继续输入%d组密码\n",n); for(i=0;i { printf("请输入第%d组密码: ",i+1); temp.num=i+1; cin>>temp.password; InsertList(myList,temp); } printf("输入首次报数人编号: "); cin>>k; printf("初始报数上限值: "); cin>>no; i=k-1; k=0; while(LengthList(myList)>0) { temp=GetList(myList,i+1); k++; if(k==no) { printf("第%d个出列的人: %d\n",count,temp.num); count++; no=temp.password; DeleteList(myList,temp); k=0; i--; } i++; if(i==LengthList(myList)) i=0; } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验六 约瑟夫环的实现 实验 约瑟夫 实现