《数据结构课程设计-约瑟夫环.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计-约瑟夫环.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计-约瑟夫环 课程设计报告 学院、系： 专业： 班级： 课程设计科目约瑟夫环 学生姓名： 指导教师： 完成时间：2022年10月-12月 约瑟夫环 一、设计任务与目标 编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止。 该题目要求用单循环链表作为存储结构，进行一个带密码的约瑟夫环的运算问题。而且从键盘输入总人数、初始报数上限值m及各人密码，然
2、后输出出列的人员的编号顺序。 二、方案设计与论证 关于这次题目的设计，根据题目的要求，主要用了一个单循环链表作为存储结构。首先是进行一系列的定义结点，其中就有包括每个人的密码和编号。然后有空链表的创建和循环链表的初始化。在这里，我们将输入每个人密码的步骤放在循环链表的初始化里，在初始化链表时从键盘输入密码和直接给每个人进行编号，而不是在主函数中进行。 然后在主函数里面主要就是实现约瑟夫环的运行，从第一个开始，找到对应上限值的的人，然后输出编号，将头指针指向下一个结点，将该编号人员的密码赋值为新上限值，然后清空该结点的数据，一直这样的运行，直到所有结点都被清空，就完成了约瑟夫环的运行。 在设计的
3、前期，本是设计将密码输入的这一部分放在主函数之中去执行，而建立单循环链表是单独的一个函数，但是无法实现将数据从主函数键入切能被准确使用，于是后改成在初始化链表的时候键入密码，从而达到目标。 三、算法说明 按照题目的要求，要采用单循环链表来作为存储结构，然后在循环链表的基础上去实现约瑟夫环的运行。 在主函数之前，先是定义结点，创建新的空链表，和初始化链表。在初始化循环链表的时候，初始化了每个结点的编号，然后从键盘输入了相对应的密码，从而完成初始化。而约瑟夫环的主要实现的算法就是在主函数里面。 在主函数里，定义完各项之后，我先用一个while的循环语句来实现能够反复进行运算。关于约瑟夫环的运算，先
4、创建一个只有头结点的空链表，然后输入总人数N，和初始的上限值M，用总人数N去初始化循环链表，然后在循环链表里面从键盘输入对应的密码值。 先是设立for循环，确保将所有数据都进行运算，然后从第一个结点开始，一直向下找，直到找到对应上限值M的结点，然后用一个第三方指针p指向该结点，将该结点的密码值（password）赋予初始的上限值M，然后输出该结点的编号值（num），接着指针q指向下一个结点成为头结点，最后清空指针p指向的该对应结点。如此循环，一直到所有的结点都被清空，则已经实现了约瑟夫环的运算。 四、全部源程序清单 源代码： #include #include typedef struct N
5、ode int password; /每个人持有的密码 int num; /人员的编号 struct Node *next; /指向下一个节点 Node,*Link; /创建一个空的链表 void InitList(Link &L) L=(Node *)malloc(sizeof(Node); if(!L) exit(1); L-password=0; L-num=0; L-next=L; /初始化链表，初始化人员编号和输入每个人的密码void Creater(int n,Link &L) Link p,q; q=L; for(int i=1;ipassword); p-num=i; L-ne
6、xt=p; L=p; L-next=q-next; free(q); /主函数，执行约瑟夫环的运行 void main() printf(*约瑟夫环* n); Link L,p,q; int n,m; int a=1; int b=1; /创建一个循环语句，用于在实现约瑟夫环运算结束后是否继续执行 while(b=1) L=NULL; InitList(L); /构造出一个只有头结点的空链表 printf(请输入总人数 N: n); scanf(%d,&n); /输入总共的人数 n while(nnext; q=p-next; m=q-password; /重新赋值给上限值 printf(%d
7、 ,q-num); p-next=q-next; /让下一个节点成为头结点 free(q); printf(n); printf(是否继续重新输入运算 (1.继续 0.退出):n ); scanf(%d,&b); printf(nnn); 五、程序运行的测试与分析 基本界面，关于各项值和密码的输入。 然后得到正确的结果。 同时进行询问判断，是否继续。 如果选择继续，则可以重复输入各项继续进行运算。 如果不选择继续，则输入0后退出。 如果一开始输入的数据有错，则会提示输入的数据有错，要求重新输入。 如果输入的初始上限值有错。也会进行提醒然后要求重新输出。 经过测试，正确地输入数据。就能得出想要的
8、约瑟夫环运算的结果。 六、结论与心得 在这次数据结构的课程设计中，让我进一步地了解单循环链表的用法，也更 清楚地明白关于约瑟夫环的一些内容。在设计的过程中，重点的问题有两个，一个是约瑟夫环该怎么样去实现，还有就是每个人的密码应该如何输入。起初，密码的输入是设计在主函数中去解决，最后在查阅资料和动手实践过之后，决定将密码的输入放在循环链表的初始化过程中，这样的话，能够更条理清晰。 总的来说，关于这次课程设计，我受益不浅。自己动手实践设计关于约瑟夫环，让我对数据结构有进一步的了解，虽然这次的设计只用到链表，没有用到其他结构，但是也对它们有了更深的理解。课程设计，锻炼的是我们的思维能力和动手能力，在今后，我会继续保持自主性的学习和实践，更深入地去学习和应用关于数据结构的知识。 七、参考资料 算法与数据额结构C语言版机械工业出版社陈守孔孟佳娜武秀川 制定人：王钲璇，冯广慧审定人：陈守孔