2022年数据结构基础实验参照 .pdf

《2022年数据结构基础实验参照 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构基础实验参照 .pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验六约瑟夫环的实现学生姓名专业班级学号实验成绩指导老师（签名）日期一. 实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。2、掌握利用线性表的各种操作来进行具体的实际应用。3、加强程序设计的能力。二. 实验内容1、编写程序，模拟约瑟夫环（ josephus ）问题： n 个人（编号为 1，2，3，n (n0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i (0i=n)，另一个为起始报数上限值m。接着从编号为 i 的人开始按顺时针方向自1 起顺序报数

2、， 报到 m 时停止报数，且报到 m 的人出列，并将他的密码作为新的m 值，从他在顺时针方向上的下一个人起重新自 1 报数，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。基本要求 : （1）人数 n、每人的正整数密码、首次报数人编号i、初始报数上限值m 均由键盘输入。（2）参照线性表的抽象数据类型定义，设计本实验的抽象数据类型。（3）根据你设计的抽象数据类型， 分别用顺序存储结构和链式存储结构实现约瑟夫环问题。并请分别将顺序存储结构的程序存放在文件test6_Seq.h （基本操作函数）、test6_Seq.cpp（主函数）中，链式存储结构的程序存放在文件

3、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 ）自己的文件夹下。同时上交一份书面的实验报告。三. 抽象数据类型定义（需说明你设计的每个基本操作的功能）名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

4、- - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - Test6_seq 1、/ 清除单链表void ClearList(LNode *&H) 2、/ 求单链表长度int LengthList (LNode*H) 3、/ 判断单链表是否为空表bool EmptyList (LNode *H) 4、/ 取单链表第pos 位置上的元素ElemType GetList (LNode*H, int pos) 5、/ 从单链表中查找是否存在给定值的元素int FindList (LNode*H, ElemType

5、item) 6、/ 向单链表插入一个元素bool InsertList ( LNode*&H, ElemType item, int pos) 7、/ 从单链表中删除一个元素bool DeleteList ( LNode*&H, ElemType &item, int pos) test6_Link 1、/ 初始化线性表void InitList(SeqList &L) 2、/ 判断是否为空bool EmptyList(SeqList L) 3、/ 查找给定值元素的位置int FindList (SeqList L, ElemType item) 4、/ 在线性表 L中求序号为 pos的元素，

6、该元素作为函数值返回ElemType GetList(SeqList L, int pos) 5、/ 求线性表长度int LengthList(SeqList L) 6、/ 按给定条件 pos 向线性表删除一个元素bool DeleteList (SeqList &L, ElemType &item , int pos ) 7、/ 按给定条件 pos 向线性表插入一个元素bool InsertList(SeqList &L, ElemType item, int pos) 四. 两种类型（顺序和链式）的存储结构定义及算法思路（包括两种存储结构定义及一些重要函数的算法实现思路）顺序存储结构：ty

7、pedef int ElemType; typedef struct List ElemType *list; int size; int MaxSize; SeqList; 重要函数的算法实现思路：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - void InitList(SeqList &L) / 初始化线性表int LengthList(SeqList L)/求线性表长度bool EmptyList(SeqList L)

8、/判断是否为空int FindList (SeqList L, ElemType item) /查找给定值元素的位置ElemType GetList(SeqList L, int pos)/ 返回线性表 L 中序号为 pos元素的值bool DeleteList (SeqList &L, ElemType &item , int pos ) /按给定条件 pos向线性表删除一个元素主函数思路：1.先求出线性表长度l 2.再利用 j=(i+m-1)%l 查出要出列的位置3.如果 j=0，则位置在线性表的末尾即j=l; 4.利用 m=GetList(josephus1,j)得出密码作为新的m 值5

9、.接着删除出列的人，长度减少1 6.使 i=j，意思为从出列人的下一个人开始报数7.最后利用函数 FindList (josephus2,m) 输出出列人的编号链式存储结构：typedef int ElemType; struct LNode / 定义单链表节点类型ElemType data; / 存放结点中的数据信息LNode *next; / 指示下一个结点地址的指针; 重要函数的算法实现思路：void InitList (LNode*&H)/ 初始化单链表int LengthList (LNode*H)/ 求单链表长度bool EmptyList(LNode*H)/ 判断是否为空int

10、FindList (LNode*H, ElemType item)/ 查找给定值元素的位置ElemType GetList (LNode*H, int pos)/取单链表第pos 位置上的元素bool InsertList ( LNode*&H, ElemType item, int pos)/向单链表插入一个元素bool DeleteList ( LNode*&H, ElemType &item, int pos) /从单链表中删除一个元素主函数思路：1.建立一个具有 n 个链结点2.找出第 1 个报数人的位置3.利用函数 FindList (josephus2,m) 输出出列人的编号4.得

11、出密码作为新的m 值5.接着删除出列的人，长度减少1 6.使 i=j，意思为从出列人的下一个人开始报数五. 实验结果与分析名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - （包括运行结果截图、结果分析等）六. 心得体会（记录实验感受、 上机过程中遇到的困难及解决办法、遗留的问题、 意见和建议等。）通过实验，我发现我对循坏链表不是很清楚，所以用链表作约瑟夫环的时候我没有用循环链表的方法做【附录 -源程序】Test6_seq.h v

12、oid InitList(SeqList &L) /初始化线性表L.MaxSize =10; L.list = (ElemType *) malloc(L.MaxSize*sizeof(ElemType) ; if (L.list=NULL) cout动态存储空间用完，退出运行endl; exit(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - L.size = 0; /判断是否为空bool EmptyList(Seq

13、List L) return L.size=0; /查找给定值元素的位置int FindList (SeqList L, ElemType item) for (int i=0; iL.size; i+) if (L.listi=item) return i+1; ElemType GetList(SeqList L, int pos) /在线性表 L 中求序号为 pos的元素，该元素作为函数值返回if ( posL.size ) cout参数 pos不合法 endl; exit(1); return L.listpos-1; int LengthList(SeqList L) /求线性表长度

14、return L.size; /按给定条件 pos向线性表删除一个元素bool DeleteList (SeqList &L, ElemType &item , int pos ) int i; if ( L.size = 0 ) cout顺序表已空无数据可删 !endl; return false; if ( pos L.size ) cout参数 pos不合法 !endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - -

15、return false; /找删除位置，赋值给pos if (pos = 0) for ( i=0; i L.size; i+) if ( item = L.listi ) break; if (i = L.size) return false; pos = i+1; else if ( pos = -1 ) pos = L.size; item = L.list pos-1; /返回删除元素值/删除数据元素for ( i = pos; i L.size ; i+) L.listi-1 = L.listi; L.size-; / 若线性表空余空间太多，重新分配压缩if (float (L.s

16、ize) / L.MaxSize 10 ) L.list= (ElemType *) realloc(L.list, L.MaxSize *sizeof(ElemType) / 2 ) ; L.MaxSize = L.MaxSize / 2; return true; /按给定条件 pos向线性表插入一个元素bool InsertList(SeqList &L, ElemType item, int pos) if(posL.size+1) coutpos值无效！ endl;return false; int i; if(pos=0) for(i=0;iL.size;i+) if(itemL.

17、listi) break; pos=i+1; else if(pos=-1) pos=L.size+1; if(L.size=L.MaxSize) int k=sizeof(ElemType); L.list =(ElemType*)realloc(L.list,2*L.MaxSize*k); if(L.list =NULL) cout动态可分配的储存空间用完，退出运行！=pos-1;i-) L.listi+1=L.listi; L.listpos-1=item; L.size+; return true; Test6_seq.cpp #include #include typedef int

18、 ElemType; typedef struct List ElemType *list; int size; int MaxSize; SeqList; #include test6_Seq.h void main() SeqList josephus1; SeqList josephus2; int i,j,m,n,l,x; InitList(josephus1); InitList(josephus2); cout请输入人数 n：n; cout请输入每人的正整数密码：endl; for(j=1;jx; InsertList(josephus1,x,j); InsertList(jose

19、phus2,x,j); coutn 请输入首次报数人编号i 及初始报数上限值mim; while(!EmptyList(josephus1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - l=LengthList(josephus1); /线性表长度j=(i+m-1)%l; /查出要出列的位置if(j=0) /如果 j=0，则位置在线性表的末尾j=l; m=GetList(josephus1,j); /得出下一个上限值Del

20、eteList(josephus1,m,j); /删除出列的人i=j; /从删除人的下一个人开始报数cout出列人的编号是 :; coutFindList (josephus2,m)next; / 保存下一个结点free(cp); cp=np; /使下一个结点成为当前结点 H=NULL; /置单链表为空 /求单链表长度int LengthList (LNode*H) LNode*p=H; /用来遍历链表结点int i=0; /用来统计结点个数while(p!=NULL) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整

21、理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - i+; p=p-next; return i; /判断单链表是否为空表bool EmptyList (LNode *H) return H = NULL; /取单链表第pos 位置上的元素ElemType GetList (LNode*H, int pos) LNode*p=H; /用来遍历链表结点int i=0; /用来统计已查找的结点个数if (pos1) cerr pos is out range!next; if (p!=NULL) return p-data; else /pos值大于表长

22、cerr pos is out range!data=item) return i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - else p=p-next; /向单链表插入一个元素bool InsertList ( LNode*&H, ElemType item, int pos) LNode*newptr, *cp, *ap; if (pos-1) cout 参数不合法 endl; return false; /寻找新

23、结点的插入位置，使得在ap和 cp间插入cp=H; ap=NULL; if (pos = 0) /按值有序插入情况while ( cp != NULL) if ( item data ) break; else ap=cp; cp=cp-next; else if ( pos = -1 ) /在表尾插入情况while ( cp != NULL) ap=cp; cp=cp-next; else /按指定位置插入情况int i=0; while ( cp != NULL) i+; if (i=pos) break; else ap=cp; cp=cp-next; if ( cp=NULL & i+

24、1pos ) cout参数不合法 data = item; if (ap=NULL) /插入到表头newptr-next=H; H=newptr; else /插入到 ap 和 cp结点之间 newptr-next=cp; ap-next=newptr; return true; /从单链表中删除一个元素bool DeleteList ( LNode*&H, ElemType &item, int pos) LNode*cp, *ap; if (H=NULL) cerr 空表，不能删除 ! endl; return false; if (pos-1) cout参数不合法 ! data ) br

25、eak; else ap=cp; cp=cp-next; if (cp=NULL) cout 没有相应结点可删除 !next != NULL) ap=cp; cp=cp-next; else /删除指定位置结点情况int i=0; while ( cp != NULL) i+; if (i=pos) break; else ap=cp; cp=cp-next; if ( cp=NULL) cout参数不合法 !data; if (ap=NULL) H=H-next; /删除表头结点else ap-next=cp-next; /删除非表头结点，即cp所指的结点free(cp); return t

26、rue; Test6_Link.cpp #include #include typedef int ElemType; struct LNode / 定义单链表节点类型ElemType data; / 存放结点中的数据信息LNode *next; / 指示下一个结点地址的指针; #include test6_Link.h void main() LNode *p, *newnode; int x,n,i,j,m,l; InitList ( p); InitList (newnode); cout请输入人数 n：n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

27、- - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - cout请输入每人的正整数密码：endl; for(j=1;jx; InsertList (p, x, j); InsertList (newnode, x,j); coutn 请输入首次报数人编号i 及初始报数上限值mim; while(!EmptyList(p) l=LengthList(p); /线性表长度j=(i+m-1)%l; /查出要出列的位置if(j=0) /如果 j=0，则位置在线性表的末尾j=l; m=GetList(p,j); /得出下一个上限值DeleteList(p,m,j); /删除出列的人i=j; /从删除人的下一个人开始报数cout出列人的编号是 :; coutFindList (newnode,m)endl; / FindList (newnode,m)查找给定值元素的位置 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -