数据结构课程设计-约瑟夫环

《数据结构课程设计-约瑟夫环》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计报告课程设计名称：数据结构课程设计课程设计题目：约瑟夫环院（系）：专业：班级：学号：姓名：指导教师：目录1课程设计介绍11.1课程设计内容11.2课程设计要求12课程设计原理22.1课设题目粗略分析22.2原理图介绍22.2.1功能模块图22.2.2流程图分析33数据结构分析73.1存储结构73.2算法描述74调试与分析84.1调试过程84.2程序执行过程9参考文献12附录（关键部分程序清单）13181课程设计介绍1.1课程设计内容编号为1,2…n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整

2、数）。一开始人选一个正整数作为报数的上限值m，从第一个人开始顺时针方向自1开始顺序报数，报道m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。使用单循环链表作为存储结构。1.2课程设计要求1.参考相应的资料，独立完成课程设计任务。2.交规范课程设计报告和软件代码。182课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为2大模块。此2个模块相互独立，没有嵌套调用的情况，以下是2个模块的大体

3、分析：1.建立初始化单循环链表，将每个结点的座位号及密码给定；2建立伴随指针，将循环进行一边，使跟随指针指向头结点前一个结点。然后进行遍历，循环m-1次时输出此时所指向的结点的座位号，将此结点的密码作为新的m值，删除这个结点，循环至剩下最后一个结点，输出该结点的座位号。2.2原理图介绍2.2.1功能模块图mian()yue_list()init_list()图2.1功能模块图182.2.2流程图分析1.如图2.1通过主函数进行座位号n和初始值m的输入，调用建立单煦暖链表函数init_list和约瑟夫环出列函

4、数yue_list。图2.2主函数main()流程图182.如图2.2，建立单循环链表，并且将链表的座位号赋值给q->info，输入每个座位号的密码给q->code；图2.3建立单循环链表流程图181.如图2.3进行约瑟夫环出列算法，按先后顺序输出座位号。18图2.4进行约瑟夫环出列算法yue_list()流程图183数据结构分析3.1存储结构typedefstructNode{intinfo;//节点的座位数intcode;//节点的密码structNode*next;}*PNode,*LinkList;

5、3.2算法描述1.建立n个结点的单循环链表，简单算法说明如下：定义*p，*q两个结点指针，使头结点的*next指针指向自己，先给第一个结点的密码code，及座位号info赋值；从第二个结点开始用for循环进行建立链表并给链表中结点的code和info赋值。2.进行约瑟夫环算法的循环，将出列的人按顺序输出，简单算法说明如下：定义两个指针，一个为p一个为p的前一个指针pre；先进行一次遍历，使pre的指针指向头结点的前一个位置；进行循环遍历，用while(p!=p->next)判断结点数是否大于1,若大于1，用

6、for循环找到第m个结点，并输出这个结点的座位号，将结点的座位密码赋给m值，并且删除这个结点；如果要删除的结点是头结点，需要将头结点移动到下一个位置。重新进行for循环，直到剩下最后一个结点；跳出循环，输出最后一个结点的座位号，并释放。184调试与分析4.1调试过程在调试程序是主要遇到一下几类问题：问题1：问题描述：当输入m值等于1的时候总是从第二个作为开始输出。问题分析：由于程序遍历的结点先进行了一步，才开始遍历。解决方法：建立伴随指针的时候先将程序遍历一遍，使初始化伴随指针指向头结点的上个位置。问题2：

7、问题描述：先输出第一个结点后总是无法正确输出。问题分析：没有判断输出的是否是头结点。解决方法：判断输出的是否是头结点，如果是把头结点向后移动。问题3：问题描述：输入n,m的时候如果输入的不是正整数，程序无法正常运行。问题分析：没有判断n，m是否是正整数。解决方法：用dowhile循环语句，如果不是正整数需要重新输入。184.2程序执行过程（1）第一次的具体的测试结果如图4.1所示。图4.1第一次测试结果（2）第二次的具体的测试结果如图4.2所示。图4.2第二次测试结果18（3）第三次的具体的测试结果如图4.

8、3所示。图4.3第三次测试结果（4）第四次的具体的测试结果如图4.4所示。图4.4第四次测试结果18（5）第五次的具体的测试结果如图4.5所示。图4.5第五次测试结果系统使用说明：1.输入的数据座位数n，初始值m，密码必须是正整数；2.输入结束后自动输出结果，按任意键退出。18参考文献1.《数据结构》（用面向对象的方法与C++描述），殷人昆等，清华大学出版社，2009。2.《算法与数据结构习题精解和实验指导》，宁