约瑟夫环实验报告

1、m388N数据结构课程设计报告题 目：约瑟夫环实验班 级：成 员： 指导教师：完成日期：目录：实习报告要求实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七 个内容：1. 需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么 ?明确规定 :(1) 输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能达到的功能；(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结 果。2. 概要设计说明本程序中用到的所有抽象数据类型的定义、 主程序的流程以及各程序模 块之间的层次 ( 调用) 关系。3. 详细设计实现概要设计中定义的所有数据类型， 对每个操作

2、只需要写出伪码算法； 对 主程序和其他模块也都需要写出伪码算法 (伪码算法达到的详细程度建议为 : 按 照伪码算法可以在计算机键盘直接输入高级程序设计语言程序 ) ；画出函数的调 用关系图。4. 调试分析内容包括：(1) 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分 析；(2) 算法的时空分析 ( 包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想；（3）经验和体会等。5. 用户使用说明 说明如何使用你编写的程序，详细列出每一步的操作步骤。6. 测试结果 列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最 好多于需求分析中所列。7. 附录 带注释

3、的源程序。可以只列出程序文件名的清单。实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写 （当然也可以应该最后用实验报告纸誉清或打印 ）约瑟夫环实验描述【问题描述】约瑟夫 （Joseph） 问题的一种描述是：编号为 1，2， ，n 的n个人按顺 时针方向围坐一 圈，每人持有一个密码 （正整数）。一开始任选一个正整数作为 报数上限值 m，从第一个人开始按顺时针方向自 1开始顺序报数，报到 m时停止 报数。报m的人出列，将他的密码作为新的 m值，从他在顺时针方向上的下一个 人开始重新从 1报数，如此下去，直至所有人全部出列为止。试设计一个程序求 出出列顺序

4、。【基本要求】 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。【测试数据】m 的初值为 20；n=7，7 个人的密码依次为： 3，1，7，2，4，8，4，首 先 m 值为 6（ 正确的出列顺序应为 6，1，4，7，2，3，5） 。【实现提示】程序运行后，首先要求用户指定初始报数上限值， 然后读取各人的密码。可 设n30。此题所用的循环链表中不需要 “头结点”，请注意空表和非空表的 界限。【选作内容】向上述程序中添加在顺序结构上实现的部分。课程设计报告正文一需求分析1输入的形式和输入值的范围本程序中，输入人数 n（n 小于等于 30） 和初始密码 m（m大于等于 1），然后

5、给每个人输入所持有的密码 key，均限定为正整数。 用单循环链表模拟约瑟夫环， 从队头开始从 1 报数，报到 m的人出列，再把此人的密码赋给 m，继续下一轮的 报数，直到所有的人出列。 结果出来后再选择输入一数字， 输入 1 继续新一轮的 游戏，输入 0 结束，退出此游戏。演示程序以用户和计算机对话方式进行，根据 提示信息由用户从键盘输入数据， 输入的形式为一个以“回车符”为结束标志的 正整数。2输出的形式在计算机终端上显示提示信息之后， 有用户在键盘上输入演示程序中规定的 运算命令， 相应的输入数据和运算结果显示在其后。 运行后输出的结果是约瑟夫 环的相关信息和经过报数后出队的人的序列号及相

6、关信息。程序执行的命令包括：（1）输入人数和初始密码 （2）输入所有人的密码 （3） 显示输入的所有人的编号及相应的密码 （4）输出出列密码及编号 （ 5）结束 即：（1）构造单循环链表；（ 2）输出循环链表的信息； （3）按照出列的顺序输出各 人的编号 3程序功能提供用户从键盘输入， Joseph 约瑟夫环的必要数据，并从屏幕显示出列顺 序。4测试数据（1）n=7 ,m=20（常规数据） , 7 个人的密码依次为 3，1，7，2，4，8，4，正 确的输出序列为 6，1，4，7， 2， 3，5.（2）n=5，m=6（常规数据），5 个人的密码依次为 2，5，4，6，7，正确的输出 序列为 1,

7、3,4,2,5 。（ 3） n=31, m=3（错误数据），“这个人数太大了，请重新输入” 。（ 4） n=0, m=3（错误数据），“这个约瑟夫环里没有人！ ”。（ 5） n=1, m=4, （边缘数据），正确的输出序列为 1。（6）n=3, m=1, （边缘数据），正确的输出序列为 1，3，2。 第一组为常规数据，中间两组为错误数据，后面两组为边缘数据。 5设计思路及方案用单循环链表来模拟约瑟夫环， 结点信息包括编号、 密码、 指向下一个结点 的指针，用三大主要的函数来实现功能， 包括创建链表的函数、 输出链表信息的 函数、删除结点也就是出队的函数、主函数等函数。概要设计1抽象数据类型的定

8、义为实现上述功能， 应以有序单向循环链表表示约瑟夫环。 为此， 需要有一个抽象 数据类型。该抽象数据类型的定义为：ADT LinkList数据对象： D= ai | ai termset,i=1,2, n,n=0 ， termset 中每个元素包含编号，密码，和一个指向下一节点的指针 数据关系： R1= | ai-1, ai D , i=2, n基本操作：LinkList EvaluList（int n）;/ 对单向循环链表进行尾插入赋值 int size（LinkList L）;/ 求链表的节点个数 Status ScanList（LinkList L）;/遍历单向循环链表Status Jo

9、seph（LinkList &L,int m）;/约瑟夫环的实现 此抽象数据类型中的一些常量如下： #define TRUE 1 #define FALSE 0#define OK 1 typedef int Status;typedef double ElemType; 单向循环链表中节点的定义如下所示： typedef struct LNodeint number;int data;struct LNode *next;LNode, *LinkList; 2主程序的流程 void main（）初始化；输入数据；执行功能； 显示结果； 3模块的设计及介绍 （1）主程序模块Void main

10、（） 初始化； do 接受命令； 处理命令；while （“命令” =“退出”）；（2）创建链表模块Static void creatlist（行参） 初始化；For 接受命令； 处理命令 （ 3）输出链表信息模块static void PrntList（ 参数 ） 定义变量并初始化； 输出命令；（4）删除结点也就是出队模块 static void StatGame（ 参数 ） 定义变量并初始化；While开始报数；输出结果； 4各程序模块之间的层次 （ 调用）关系。 本程序包含以下模块： （1）主程序模块： （2）各功能模块实现顺序表的各项功能 各模块的调用关系： 主程序 各功能模块三详细设

11、计1各模块关键代码及算法的解释：( 1) 主函数模块代码circularlist pHead=NULL;int main(void) int n, m ， iflag=1while(iflag=1)printf( 请输入总人数 n=);scanf(%d,&n);printf(n 再请输入初始报数上限 m=); scanf(%d,&m) ；CreatList(&pHead,n);printf(n 输出所有人的信息如下 :n);PrntList(pHead);printf(n 按照出列顺序输出每个人的编号 :n);StatGame(&pHead, m);printf(n 约瑟夫环的游戏完成 !n)

12、;printf( 输 入 1 开 始 建 环 做 游 戏 ， 输 入 0 退 出 该 游 戏 ， 请 选 择!);scanf(%d,&i); return 0;程序解释： 该主函数用一个循环语句， 来执行其它的函数的功能。 从键盘输入总 人数和初始的报数上限， 再调用创建链表的函数建环， 后输出单循环链表的信息， 再调用 StatGame()函数，报到上限的那个结点从表中删除既出队，然后再选 择输入一个数确定是否继续游戏，输入 1 继续，输入 0退出。( 2) 创建单循环链表函数模块代码static void CreatList(circularlist * ppHead, const int

13、 n)int i,ikey;Node *pNew, *pCur;for(i=1;inext=*ppHead;elsepNew-next=pCur-next; pCur-next=pNew; pCur=pNew; 程序解释：用一个 for 循环来给链表的每个结点分配空间，并从键盘输入每人所 持有的密码， 如果头结点的值为空， 使其指向新生成的一个结点， 新结点的 next 指针指向头结点，如果不是，则当前结点的 next 的值赋给新结点的 next ，然后 当前结点的 next 值指向新结点，再当前结点的指针指向新结点，实现链表的建 立。(3) 删除结点函数代码static void StatG

14、ame(circularlist * ppHead, int ikey)int iCounter, iFlag=1;Node *pPrv, *pCur, *pDel; pPrv=pCur=*ppHead; while(iFlag) ! */ for(iCounter=1;iCounternext; if(pPrv=pCur) iFlag=0; pDel=pCur; Prv-next=pCur-next; pCur=pCur-next;ikey=pDel-key;printf( 第 %d个人出列 , 所持有密码是 : %dn, pDel-id,pDel-key); free(pDel); ppH

15、ead=NULL;程序解释：设立一个标签，值为 1 执行循环语句，值为 0跳出循环。循环语句里 的 for 循环实现报数功能，也就是结点移动的功能，移动 ikey 个结点，再删除 第 ikey 个结点，并把该结点的密码值赋给 ikey ，再从该结点的下一个结点移动， 重复上面的过程， 结点全都删除后使标签的值为 0，结束 while 循环，游戏结束。2.2 创建单循环链表函数流程图2.3 删除结点函数（出队函数）程序流程图四调试分析1. 调试过程中遇到的问题及解决方法及对设计与实现的回顾讨论和分析 程序的编写和调试基本正常。 遇到的问题有： 指针的指向的边界问题。 当执 行输入人数时，输入 0

16、程序出现了意想不到的错误， 所以再重新设计时加入了对 空节点的处理。 在链表节点的设计上， 最初是仅包含密码和指针， 但是后来考虑 到链表节点删除时会带来一系列的编号变化， 编号难以确定， 所以节点设计上又 加了一个编号。在单向链表的赋值操作时，原本是以一个不变的 L 作为头结点， 但是这种赋值方法带来了诸多变量设计的问题，所以将 L 为节点，赋值完成后， 再让 L 指向头结点。程序原本是没有求节点个数的函数， 但是在约瑟夫环的实现 函数中，节点的个数时时影响着结果的判断，所以加入了该函数。2. 算法的时空分析 在空间复杂度方面第一种算法可以增加一存储出列序列的数据组， 需要辅助 空间，而且与

17、问题的规模 Maxsize有关。第二种算法也可直接对约瑟夫环进行求 解，结果仍然存储在环中，好处是没有增加额外的空间。在时间复杂度方面，第 一种算法可以从中可以看到，报数 m的时间极短 ,问题在出列时 ,由于用顺序表做 删除操作 ,平均移动大约表中一半的元素 , 影响效率 . 但是, 两者都存在二重循环 , 算法中语句重复执行次数的数量级没有发生变化 , 即时间复杂度 O相同。与这两种 算法不同的是， 动态链表实现的算法中， 不需要预先分配足够大的存储空间， 没 有太大的辅助空间的要求，远小于问题规模 Maxsize ，即绝小于第一种算法的辅 助空间，而接近第二种算法。另外，删除结点操作极其方

18、便，比第二种算法移动 元素的少。不过，三者时间复杂度 O均相同。对同一问题，可以有不同的算法。 但仍可以进一步优化。 例如时间问题， 密码可采用对剩余节点取余来减少遍历次 数。3. 经验和体会通过这次的课程设计的综合训练， 培养分析和编程等实际动手能力， 系统掌 握数据结构这门课程的主要内容， 我们对数据结构有了更深的理解。 与以往不同 的是我们自己选定一个研究问题， 对其进行详尽的分析思考， 最终解决。 我们选 择的课程设计的内容是用单循环链表模拟约瑟夫环游戏， 循环链表是一种首尾相 接链表， 其特点是无须增加存储容量， 仅对表的链接方式稍作改变， 使表处理更 加灵活，约瑟夫环问题就是用单循

19、环链表处理的一个实际应用。 通过这个设计实 例，了解单链表和单循环链表的相同与不同之处， 进一步加深对链表结构类型及 链表操作的理解。在此期间遇到了很多困难。 如：当程序大体完成时， 却又在调试过程中发现 出列次序总是错误的， 才想到第一次指向时应该让变化的指针指向尾节点， 这样 可以减少当密码为 1 时程序的设计量。此次课程设计收获相当多，我们不仅对 VC软件更加熟悉，而且学会了能运 用所学知识分析和解决一些实际问题。 了解并初步掌握设计、 实现较大程序的完 整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结 构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

20、本实验采 用数据抽象的与模块化程序设计方法。 思路清晰，实现时调试顺利， 各模块具有 很好的可重用性，得到了一次良好的程序设计训练。 同时在和队友的不断完善中， 许多困难都得到了解决， 从这点我们也认识到团队中合作的重要性。 相信我们以 后会做得更优秀。五用户使用说明1如何使用你编写的程序 首先根据提示输入初始密码和人数， 再输入每个人的密码。 最后输入 1或 0， 选择继续或结束。2每一步的操作步骤 示例：进入演示程序后即显示文本方式的用户界面 ; 欢迎您进入 约瑟夫环 运行界面 请按照提示执行程序 设计者 : 姜密 王轶广 鲍玉凤 1） ，再请输入每个人的 结束。先请输入人数 n（n 小于

21、等于 30） 和初始密码 m（m大于等于 密码。显示出出列顺序。最后输入 1，继续测试。输入 0 如：请输入人数 n（n 小于等于 30）7和初始密人数： 20输入 1 个人的密码： 3输入 2 个人的密码： 1输入 3 个人的密码： 7输入 4 个人的密码： 2输入 5 个人的密码： 4输入 6 个人的密码： 8输入 7 个人的密码： 4后会出现 7 个人的密码为： 3 1 7 2 4 8 4 和出列顺序 6 输入 1 之后的界面：继续测试数据输入 0 之后的界面：结束六测试结果1程序调试，正确2点击运行，进入“约瑟夫环”运行初界面3. 输入总人数之后的界面4输入初始密码后的界面：5. 输入

22、所有人所持有的密码后的界面（继续新一轮的游戏，结束后的界面） 输入所规定范围内的数值。 （第一组，常规数据）6. 输入 1 之后的界面：7.输入 0之后的界面： x1江 * C ADocuient s and SettinsA:?甌拂密码20 输入第1 Am=3 j3 2人的密 Jz 3人的棘：7 4人旳密俘2 4 5人旳费*4 j3 6人的密?删 给入第？人旳挪4 徐成了约瑟夫聃定义J 3 17 2 4 8 4- -1H2 X / UM/UH/UUmnU7 Tt Tt- UTt-Tt Tt TTr 畫密密密密密帘人人人人人人人 个个个个个个个12 3 4 5 6 7 pgRps,F； GR

23、第侄 R EF； GR为为为为为为为 TCr Tt- Tt- Tt. Zf It- Trr12 3 4 5 6 7一 RRfR人人人人人人人6 14 7 2 3 55 555 5.5 Fi s 刘， 1-1-l-8 3 2 4 17 4弄虽1尽码虽1朋 顺密窓窓密密畫密 izszs 的的的：S- tfcfc歹歹歹歹歹歹歹 岀岀出忖出岀出 人人人人人人人6 14 7 2 3 5 RRRR喲就弼題懈决了?眉否址绸Sm?输U继懐a,豌揪1 髓入人鬆(n小干爭諭：尼否绸怨?输比继缆埼人0退岀，W?0rPreSS any key to COntinue8第二次测试， 输入所规定范围内的数值 （第二组，常

24、规数据）。运行结果如下：9当输入的人数值超过范围时，系统会输出“这个人数太大了，请重新输入”第三组，错误数据）运行如下：第四组，错10当输入的人数为 0 时，系统会输出“这个约瑟夫环里没有人” 误数据）程序运行的界面如下：11当输入的人数为 1 时（第五组，边缘数据）运行界面如下：12当输入的密码为 1 时（第六组，边缘数值） ，运行界面如下：七小结通过一周的课程设计之后，培养了我们选用参考书，查阅手册及文献资料 的能力，培养独立思考，深入研究，分析问题、解决问题的能力，提高综合运用 本课程所学知识的能力，还对设计的基本过程的设计方法、步骤、思路、有一定 的了解与认识，并对存储结构，比如线形表

25、、链表、循环链表、树、图等存储结 构，特别是对单循环链表理解的更深。也使我认识到数据结构这门课程是计 算机程序设计的重要理论技术基础， 在我们计算机专业的学习中占据着十分重要 的地位。同时也使我知道，要学好这门课程，仅学习书本上的知识是不够的，还 要有较强的实践能力。 因为我们学习知识就是为了实践。 而只有多实践， 多编写 程序，才能更好的理解与掌握书本上的东西。本次课程设计的主题是用单循环链表来模拟约瑟夫环游戏， 由于刚开始对循 环链表的理解不够， 也没理请约瑟夫环的基本思路， 做起来有点难， 但通过反复 的修改，最终还是能够理解。我学到了很多的东西， 通过实际编译系统的分析设计、 编程调试

26、， 也掌握了 一些工程设计方法。 现在也能够按要求编写课程设计报告书， 能正确阐述设计和 实验结果， 正确绘制程序框图。 课程设计是把我们所学的理论知识进行系统的总 结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能 力，进而加强了我们对知识认识的实践度， 巩固了我们的理论知识， 深化了对知 识的认识，并为走向社会打下一个良好的基础。在这次课程设计中我遇到许多问题和麻烦。 比如，表建成之后， 不能输出表 中的信息， 说明指针的值没传成功， 经过把链表的头指针转为二级指针， 传值成 功。在程序调试过程中，也得到很多同学的帮助，给我及时指出错误，提出许多 宝贵意见。八附录， 带注

27、释的源程序#include#include#define MAX_NODE_NUM 30#define TRUE1U#define FALSE0Utypedef struct NodeType int id;/* 编号 */int cipher; /* 密码 */struct NodeType *next;NodeType;/* 创建单向循环链表 */static void CreaList(NodeType *, const int);/*运行约瑟夫环 问题 */static void StatGame(NodeType *, int);/*打印循环链表 */static void Prnt

28、List(const NodeType *);/*得到一个结点 */static NodeType *GetNode(const int, const int);/* 测试链表是否为空 , 空为 TRUE，非空为 FALSE */static unsigned EmptyList(const NodeType *);int main(void) int n, m; int iflag=1;NodeType *pHead=NULL; printf(n printf(欢迎您进入 约瑟夫环 运行界面n);printf(请按照提示执行程序 n);printf( n);printf( 设计者 : 姜密

29、王轶广 鲍玉凤 n); printf(n while(iflag=1)printf( 请输入人数 n(n 小于等于 %d):,MAX_NODE_NUM); scanf(%d,&n);printf( 和初始密码 m:);scanf(%d,&m); if(nMAX_NODE_NUM)printf( 这个人数太大了，请重新输入 n); continue;CreaList(&pHead,n);printf(nPrntList(pHead); printf(n下列为每个人的密码 n);出列顺序 n);StatGame(&pHead, m);printf(n 约瑟夫环问题 解决了 !n);printf(n

30、n是否继续游戏 ?输入 1 继续，输入 0 退出，请选择 !n);scanf(%d,&iflag); return 0;static void CreaList(NodeType *ppHead, const int n)int i,iCipher;NodeType *pNew, *pCur;for(i=1;inext=*ppHead;else pNew-next=pCur-next; pCur-next=pNew; pCur=pNew; printf(完成了约瑟夫环的定义 n);static void StatGame(NodeType *ppHead, int iCipher)int iCounter, iFlag=1;NodeType *pPrv, *pCur, *pDel;pPrv=pCur=*