《数据结构课程设计报告-约瑟夫环问题.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-约瑟夫环问题.docx（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计报告-约瑟夫环问题 华北科技学院 课程设计说明书 班级: 姓名:_ 设计题目: 约瑟夫环 设计时间:_2022-2-28 至_2022-3-11 指导教师: 评语:_ _ _ _ _ 评阅成绩:评阅教师: 一、设计题目与要求 设计题目：约瑟夫环 问题描述： 编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。 一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 基本
2、要求： 1、利用单循环链表作为存储结构模拟此过程； 2、键盘输入总人数、初始报数上限值m及各人密码； 3、显示游戏中队形及各人密码变化过程； 4、按照出列顺序输出各人的编号。 二、概要设计 实验设计思路： 1以无头结点的单循环链表为存储结构模拟此过程。 2键盘录入各各同学所持密码，存储在一维数组a中。 3单循环链表初始化时，将密码和编号存入结构体中。 4进行单链表删除操作，直到链表为空，输出的编号存入数组b中 5依次输出b中的元素。 程序结构： 本程序是单文件程序，构成的函数有 LinkedList LinkedListInit(int n,int a) 初始化循环单链表 void Linke
3、dListTraverse(LinkedList L) 遍历单链表 void Play(LinkedList L,int m,int b,int n) 单循环链表的删除 void main() 主函数，输出出队序列 其中，void Play()是最主要的函数，初始化单链表后，开始执行该函数，指针按给定的密码值m依次后移m次删除定位后的结点，输出编号，同时获得新的m 值，继续循环，直到该链表为空。 三、算法设计 结构体类型 int num, code; struct LNode *next; LNode,*LinkedList; num存放编号，code存放密码值，next为指向下一个结点的指针
4、。 流程图 初始化循环单链表流程图： 约瑟夫环主要函数流程图：（单循环链表的删除） 说明：此函数中，采用p和s两个指针一前一后来完成删除结点的操作，以m来计指针移动的步数，将符合的结点的编号返回给bi。当m=1时做特殊情况的处理。 四、程序调试 1.前期初始化单循环链表时，语法没错但运行总是报错。经老师指出，原来是把p-next=s写成s=p-next了，此时才明白这两个语句不是等价的，等号是把后者赋给前者，前后写反了会导致根本性的错误。 2.最初按照常规的单链表遍历，结果出现死循环，因为链表是循环的。我定义了一个标志变量flag=1,当指针p一轮结束又回到第一个结点时，flag=-1,循环结
5、束，这样就克服了这个问题。 3.单循环链表结点的删除。写完函数后发现总有重复的编号被输出，经过我手工操作后发现问题出在前后指针的位差上，s、p本应在定位后只有一位位差，但循环中让p移动m位，s移动m-1位，删除结点后，又有p=p-next的语句，这使p、s间有两位的位差了。因此，我在最后增加了s=p的语句。但经过大量数据测试，发现某些测试时还是会出现问题。问题出在特殊情况：下一个密码m=1。当m=1时，p、s 指针没有后移，而上一句s=p使s、p没有位差，这就造成了删除操作的错误。只需用if语句处理这一特殊情况即可。 五、数据测试和运行结果 数据测试： 第一组 : n=6；6个人的密码依次为：
6、5，3，4，7，6，9；m 的初值为15； 出列顺序为3，1，2，6，4，5。 第二组： n=7；7个人的密码依次为：3，1，7，2，4，8，4；m 的初值为20； 出列顺序为6，1，4，7，2，1，3，5。 运行结果图一： 运行结果图二： 五、总结体会 通过这次课程设计，让我对数据结构中的单循环链表有了更深的体会。以前上课的时候都是照着指导书敲的，没有真正的自己编代码，这次课程设计的代码都是我自己写的，编写的过程中遇到了很多问题，通过问老师问同学和自己反复研究都得到了解决。这次设计的具体收获如下： 1.掌握了单循环链表的初始化，创建，删除，遍历等操作。 2.在调试程序的时，可以逐块地检查，将非相关的代码暂时隐去，需要跟踪某 个变量时，可以在函数适当的位置加入输出语句，查看变量的值的变化情况。 3.遇到程序报错时，可以手工操作模拟程序的运行，看看是在哪一步出错了， 这次设计时我深有体会，某个问题看了很久都不知道哪错了，手工试一遍就 发现了问题。 4.并不是每个函数都必须自己重新再敲一遍，一些类似的功能只需将以前写的 函数搬过来稍加修改即可。比如，课程设计中单循环链表的遍历函数就是我 将以前的单链表遍历函数拿过来修改了一下。