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

课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目：约瑟夫环约瑟夫环院（系）：专 业：班 级：学 号：姓 名：指导教师： I 目目 录录1 1 课程设计介绍课程设计介绍.11.1 课程设计内容.11.2 课程设计要求.12 2 课程设计原理课程设计原理.22.1 课设题目粗略分析.22.2 原理图介绍.22.2.1 功能模块图.22.2.2 流程图分析.33 数据结构分析数据结构分析.73.1 存储结构.73.2 算法描述.74 4 调试与分析调试与分析.84.1 调试过程.84.2 程序执行过程.9参考文献参考文献.12附附 录（关键部分程序清单）录（关键部分程序清单）.13 1 1 1 课程设计介绍课程设计介绍1.11.1 课程设计内容课程设计内容 编号为 1,2n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数） 。一开始人选一个正整数作为报数的上限值 m，从第一个人开始顺时针方向自 1 开始顺序报数，报道 m 时停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他的顺时针向上的下一个开始重新从 1 报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。使用单循环链表作为存储结构。1.21.2 课程设计要求课程设计要求1.参考相应的资料，独立完成课程设计任务。2.交规范课程设计报告和软件代码。 2 2 2 课程设计原理课程设计原理2.12.1 课设题目粗略分析课设题目粗略分析根据课设题目要求，拟将整体程序分为 2 大模块。此 2 个模块相互独立，没有嵌套调用的情况，以下是 2 个模块的大体分析：1.建立初始化单循环链表，将每个结点的座位号及密码给定；2 建立伴随指针，将循环进行一边，使跟随指针指向头结点前一个结点。然后进行遍历，循环 m-1 次时输出此时所指向的结点的座位号，将此结点的密码作为新的 m 值，删除这个结点，循环至剩下最后一个结点，输出该结点的座位号。2.22.2 原理图介绍原理图介绍2.2.12.2.1 功能模块图功能模块图mian()yue_list( )init_list( )图 2.1 功能模块图 3 2.2.22.2.2 流程图分析流程图分析1. 如图 2.1 通过主函数进行座位号 n 和初始值 m 的输入，调用建立单煦暖链表函数 init_list 和约瑟夫环出列函数 yue_list。图 2.2 主函数 main( )流程图 4 2. 如图 2.2，建立单循环链表，并且将链表的座位号赋值给 q-info，输入每个座位号的密码给 q-code；图 2.3 建立单循环链表流程图 5 3.如图 2.3 进行约瑟夫环出列算法，按先后顺序输出座位号。 6 图 2.4 进行约瑟夫环出列算法 yue_list( )流程图 7 3 数据结构分析数据结构分析3.1 存储结构存储结构typedef struct Nodeint info; /节点的座位数int code; /节点的密码struct Node *next;*PNode, *LinkList;3.2 算法描述算法描述1. 建立 n 个结点的单循环链表，简单算法说明如下：定义*p，*q 两个结点指针，使头结点的*next 指针指向自己，先给第一个结点的密码 code，及座位号 info 赋值；从第二个结点开始用 for 循环进行建立链表并给链表中结点的 code 和 info赋值。2. 进行约瑟夫环算法的循环，将出列的人按顺序输出，简单算法说明如下：定义两个指针，一个为 p 一个为 p 的前一个指针 pre；先进行一次遍历，使 pre 的指针指向头结点的前一个位置；进行循环遍历，用 while (p!=p-next) 判断结点数是否大于 1,若大于 1，用 for 循环找到第 m 个结点，并输出这个结点的座位号，将结点的座位密码赋给m 值，并且删除这个结点；如果要删除的结点是头结点，需要将头结点移动到下一个位置。重新进行for 循环，直到剩下最后一个结点；跳出循环，输出最后一个结点的座位号，并释放。 8 4 4 调试与分析调试与分析4.14.1 调试过程调试过程在调试程序是主要遇到一下几类问题：问题 1：问题描述：当输入 m 值等于 1 的时候总是从第二个作为开始输出。问题分析：由于程序遍历的结点先进行了一步，才开始遍历。解决方法：建立伴随指针的时候先将程序遍历一遍，使初始化伴随指针指向头结点的上个位置。问题 2：问题描述： 先输出第一个结点后总是无法正确输出。问题分析： 没有判断输出的是否是头结点。解决方法： 判断输出的是否是头结点，如果是把头结点向后移动。问题 3：问题描述：输入 n,m 的时候如果输入的不是正整数，程序无法正常运行。问题分析：没有判断 n，m 是否是正整数。解决方法：用 do while 循环语句，如果不是正整数需要重新输入。 9 4.24.2 程序执行过程程序执行过程（1）第一次的具体的测试结果如图 4.1 所示。图 4.1 第一次测试结果（2）第二次的具体的测试结果如图 4.2 所示。图 4.2 第二次测试结果 10 （3）第三次的具体的测试结果如图 4.3 所示。图 4.3 第三次测试结果（4）第四次的具体的测试结果如图 4.4 所示。图 4.4 第四次测试结果 11 （5）第五次的具体的测试结果如图 4.5 所示。图 4.5 第五次测试结果系统使用说明：1. 输入的数据座位数 n，初始值 m，密码必须是正整数； 2. 输入结束后自动输出结果，按任意键退出。 12 参考文献参考文献1.数据结构 （用面向对象的方法与 C+描述） ，殷人昆等，清华大学出版社，2009。2.算法与数据结构习题精解和实验指导 ，宁正元等，清华大学出版社，2007。3. 谭浩强. .C 程序设计M.北京：清华大学出版社，2005。 13 附附 录（关键部分程序清单）录（关键部分程序清单）程序代码程序代码#include #include #include #define ERROR 0#define OK 1typedef struct Nodeint info; /节点的座位数int code; /节点的密码struct Node *next;*PNode, *LinkList;typedef LinkList *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; 14 *plist=q; q-info=1; q-next=q; printf(请输入第 1 个座位的密码:); scanf(%d,&q-code); if(q-code=0) return ERROR; if (n=1) return OK; for(i=2;icodenext=q-next; q-next=p; q=p; scanf(%d,&q-code); q-info=i; 15 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; 16 printf(输出: %dn,p-info); m=p-code; if (*plist=p) /该结点是第一个结点时，首节点应移向下一个 *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 17 printf(n 输入总座位数 n(n0，否则重新输入):); scanf(%d,&n); while (n0，否则重新输入):); scanf(%d,&m); while (m1);if (init_list(&y_list,n) yue_list(&y_list,m);else printf(输入有错误!n); 18 课程设计总结：课程设计总结：本次课程设计涉及到的范围很广，让本人能够比较系统的对 C 语言和数据结构进行一次整理和复习。同时有了很多的体会和经验。1. 巩固了以前学过的 C 语言的知识，在这次课程设计中我体会到 C 语言超强的逻辑性，能够熟练使用 VC+的编译环境，也对这两门课程有了新的认识，他们既有联系，又相互区别，在编写程序过程中要灵活应用。2. 对数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会选择不同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案，所以以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。3. 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合的，没有平时基础的训练是不会写出高效的算法。4. 此次课程设计时间虽短，但却课设的过程是短暂的，但我所收获的是永恒的。它让我尝到了学习的快乐，成功的喜悦，更让我懂得了不少做人的道理。要完成一项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所畏惧的精神，这对我日后的学习和生活产生了深远一个影响。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩