实验6--约瑟夫环的实现(大作业)备课讲稿.doc

《实验6--约瑟夫环的实现(大作业)备课讲稿.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、起始报数上限值m。接着从编号为i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，……，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。基本要求:收集于网络，如有侵权请联系管理员删除精品文档（1）人数n、每人的正整数密码、首次报数人编号i、初始报数上限值m均由键盘输入。（2）参照线性表的抽象数据类型定义，设计本实验的抽象数据类型。（3）根据你设计的抽象数据类型，分别用顺序存储结构和链式存储结构实现约瑟夫环问题。并请分别将顺序存储结

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.66.28.222:2007）自己的文件夹下。同时上

4、交一份书面的实验报告。三.抽象数据类型定义（需说明你设计的每个基本操作的功能）1.初始化线性表2.清除线性表3.在线性表中插入某个元素4.删除线性表中的某个元素5．约瑟夫函数四.两种类型（顺序和链式）的存储结构定义及算法思路1.顺序收集于网络，如有侵权请联系管理员删除精品文档typedefstructList{ElemType*list;intsize;intMaxSize;}SeqList;voidInitList(SeqList&L)；voidClearList(SeqList&L)；boolInsertList(SeqList&L,ElemTypei

5、tem,intpos)；boolDeleteList(List&L,ElemType&item,intpos)2.链式typedefstructLNode{intcode;intnum;structLNode*next;}LNode;voidjosephus(intn,intm,ints)。五.实验结果与分析1.顺序输出结果收集于网络，如有侵权请联系管理员删除精品文档2.链式输出结果六.心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现2、掌握利用线性

6、表的各种操作来进行具体的实际应用收集于网络，如有侵权请联系管理员删除精品文档3、加强程序设计的能力，同时对前面所学习的只是进行了回顾，掌握了链表的基本技巧【附录----源程序】1.顺序test6_Seq.cpp收集于网络，如有侵权请联系管理员删除精品文档#include#include#includetypedefintElemType;#include"test6_Seq.h"typedefstructList{ElemType*list;intsize;intMaxSize;}SeqList

7、;voidmain(){SeqListL;intn,m,i,j;printf("输入人数n,首次报数人编号i,初始报数上限值m:");scanf("%d%d%d",&n,&i,&m);InitList(L);for(j=0;j=n)j=0;while(j

8、(L.list[j]!=0)k++;if(k==m){printf