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

1、课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：约瑟夫环约瑟夫环 院（系）： 专 业： 班 级： 学 号： 姓 名： 指导教师： 目目 录录 1 1 课程设计介绍课程设计介绍.1 1.1 课程设计内容.1 1.2 课程设计要求.1 2 2 课程设计原理课程设计原理.2 2.1 课设题目粗略分析.2 2.2 原理图介绍.2 2.2.1 功能模块图.2 2.2.2 流程图分析.3 3 数据结构分析数据结构分析.7 3.1 存储结构.7 3.2 算法描述.7 4 4 调试与分析调试与分析.8 4.1 调试过程.8 4.2 程序执行过程.9 参考文献参

2、考文献.12 附附 录（关键部分程序清单）录（关键部分程序清单）.13 1 1 课程设计介绍课程设计介绍 1.11.1 课程设计内容课程设计内容 编号为 1,2n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正 整数） 。一开始人选一个正整数作为报数的上限值 m，从第一个人开始顺时针 方向自 1 开始顺序报数，报道 m 时停止报数，报 m 的人出列，将他的密码作 为新的 m 值，从他的顺时针向上的下一个开始重新从 1 报数，如此下去，直 至所有人全部出列为止，设计一个程序求出出列顺序。使用单循环链表作为 存储结构。 1.21.2 课程设计要求课程设计要求 1.参考相应的资料，独立完成课

3、程设计任务。 2.交规范课程设计报告和软件代码。 2 2 课程设计原理课程设计原理 2.12.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求，拟将整体程序分为 2 大模块。此 2 个模块相互独立，没 有嵌套调用的情况，以下是 2 个模块的大体分析： 1.建立初始化单循环链表，将每个结点的座位号及密码给定； 2 建立伴随指针，将循环进行一边，使跟随指针指向头结点前一个结点。然 后进行遍历，循环 m-1 次时输出此时所指向的结点的座位号，将此结点的密码作 为新的 m 值，删除这个结点，循环至剩下最后一个结点，输出该结点的座位号。 2.22.2 原理图介绍原理图介绍 2.2.12.2.1 功

4、能模块图功能模块图 mian() yue_list( )init_list( ) 图 2.1 功能模块图 2.2.22.2.2 流程图分析流程图分析 1. 如图 2.1 通过主函数进行座位号 n 和初始值 m 的输入，调用建立单煦暖链表函 数 init_list 和约瑟夫环出列函数 yue_list。 图 2.2 主函数 main( )流程图 2. 如图 2.2，建立单循环链表，并且将链表的座位号赋值给 q-info，输入每个座 位号的密码给 q-code； 图 2.3 建立单循环链表流程图 3.如图 2.3 进行约瑟夫环出列算法，按先后顺序输出座位号。 图 2.4 进行约瑟夫环出列算法 yu

5、e_list( )流程图 3 数据结构分析数据结构分析 3.1 存储结构存储结构 typedef struct node int info; /节点的座位数 int code; /节点的密码 struct node *next; *pnode, *linklist; 3.2 算法描述算法描述 1. 建立 n 个结点的单循环链表，简单算法说明如下： 定义*p，*q 两个结点指针，使头结点的*next 指针指向自己，先给第一个结 点的密码 code，及座位号 info 赋值； 从第二个结点开始用 for 循环进行建立链表并给链表中结点的 code 和 info 赋值。 2. 进行约瑟夫环算法的循环

6、，将出列的人按顺序输出，简单算法说明如下： 定义两个指针，一个为 p 一个为 p 的前一个指针 pre； 先进行一次遍历，使 pre 的指针指向头结点的前一个位置； 进行循环遍历，用 while (p!=p-next) 判断结点数是否大于 1,若大于 1， 用 for 循环找到第 m 个结点，并输出这个结点的座位号，将结点的座位密码赋给 m 值，并且删除这个结点； 如果要删除的结点是头结点，需要将头结点移动到下一个位置。重新进行 for 循环，直到剩下最后一个结点； 跳出循环，输出最后一个结点的座位号，并释放。 4 4 调试与分析调试与分析 4.14.1 调试过程调试过程 在调试程序是主要遇到

7、一下几类问题： 问题 1： 问题描述：当输入 m 值等于 1 的时候总是从第二个作为开始输出。 问题分析：由于程序遍历的结点先进行了一步，才开始遍历。 解决方法：建立伴随指针的时候先将程序遍历一遍，使初始化伴随指针指向头结 点的上个位置。 问题 2： 问题描述： 先输出第一个结点后总是无法正确输出。 问题分析： 没有判断输出的是否是头结点。 解决方法： 判断输出的是否是头结点，如果是把头结点向后移动。 问题 3： 问题描述：输入 n,m 的时候如果输入的不是正整数，程序无法正常运行。 问题分析：没有判断 n，m 是否是正整数。 解决方法：用 do while 循环语句，如果不是正整数需要重新输

8、入。 4.24.2 程序执行过程程序执行过程 （1）第一次的具体的测试结果如图 4.1 所示。 图 4.1 第一次测试结果 （2）第二次的具体的测试结果如图 4.2 所示。 图 4.2 第二次测试结果 （3）第三次的具体的测试结果如图 4.3 所示。 图 4.3 第三次测试结果 （4）第四次的具体的测试结果如图 4.4 所示。 图 4.4 第四次测试结果 （5）第五次的具体的测试结果如图 4.5 所示。 图 4.5 第五次测试结果 系统使用说明： 1. 输入的数据座位数 n，初始值 m，密码必须是正整数； 2. 输入结束后自动输出结果，按任意键退出。 参考文献参考文献 1.数据结构 （用面向对

9、象的方法与 c+描述） ，殷人昆等，清华大学出版社， 2009。 2.算法与数据结构习题精解和实验指导 ，宁正元等，清华大学出版社， 2007。 3. 谭浩强. .c 程序设计m.北京：清华大学出版社，2005。 附附 录（关键部分程序清单）录（关键部分程序清单） 程序代码程序代码 #include #include #include #define error 0 #define ok 1 typedef struct node int info; /节点的座位数 int code; /节点的密码 struct node *next; *pnode, *linklist; typedef l

10、inklist *plinklist; int init_list(plinklist plist, int n)/建立循环链表，从 1 到 n 输入节点的密码。 struct node *p,*q; int i; q=(pnode)malloc(sizeof(struct node); if (q=null) return error; *plist=q; q-info=1; q-next=q; printf(请输入第 1 个座位的密码:); scanf(%d, if(q-code=0) return error; if (n=1) return ok; for(i=2;icodenext=

11、q-next; q-next=p; q=p; scanf(%d, q-info=i; return ok; void yue_list( plinklist plist,int m) /约瑟夫算法 pnode p,pre; int i; p=*plist; pre =p; p=p-next; while (p!=*plist) pre =p; p=p-next; while (p!=p-next) /当链表中结点个数大于 1 时 for(i=1;inext; printf(输出: %dn,p-info); m=p-code; if (*plist=p) /该结点是第一个结点时，首节点应移向下一

12、个 *plist=p-next; pre-next=p-next; /删除该结点 free(p); p=pre-next; /循环结束，剩下最后一个节点 printf(输出: %d n,p-info); *plist=null; free(p); main( ) linklist y_list; int n,m; / 输入所需各参数的值 do printf(n 输入总座位数 n(n0，否则重新输入):); scanf(%d, while (n0，否则重新输入):); scanf(%d, while (m1); if (init_list( else printf(输入有错误!n); 课程设计总结：课程设计总结： 本次课程设计涉及到的范围很广，让本人能够比较系统的对 c 语言和数据 结构进行一次整理和复习。同时有了很多的体会和经验。 1. 巩固了以前学过的 c 语言的知识，在这次课程设计中我体会到 c 语言超 强的逻辑性，能够熟练使用 vc+的编译环境，也对这两门课程有了新的认识， 他们既有联系，又相互区别，在编写程序过程中要灵活应用。 2. 对数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会 选择不同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案， 所以以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。 3. 此次设计让我意识到程序设