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