数据结构基础约瑟夫环.docx

《数据结构基础约瑟夫环.docx》由会员分享，可在线阅读，更多相关《数据结构基础约瑟夫环.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学号： 我隆理了火挈琢住报百（数据结构基础）题目约瑟夫环学院自动化专 业电气工程及其自动化班级姓名指导教师李晓红2022年 11月 22 日能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。8参考文献谭浩强 程序设计北京：清华大学出版社，严蔚敏，吴伟民 数据结构北京清华大学出版社，严蔚敏，吴伟民数据结构北京：清华大学出版社，数据结构（用面向对象方法与 描述），殷人昆等，清华大学出版社。算法与数据结构习题精解和实验指导，宁正元等，清华大学出版社本科生课程大作业成绩评定表学院：自动化姓名：任海亮专业班级：电气1403学号：序号评分项目满分实得分1学习态度认真、遵守纪律102

2、算法设计分析合理性103数据结构设计正确性、可行性204设计结果正确性405设计报告的规范性106设计验收10总得分指导教师签名:2022年11月22日目录1选题描述3.2算法设计3 .3算法分析4.4程序源码6 .5试算截屏图8.6分析与总结9.7参考文献9 .1选题描述约瑟夫环:编号为1, 2, n的n个人按顺时针方向围坐一圈，每人持有一 个密码（正整数）。一开始任选一个正整数作为报数的上限值m,从第一个人开 始按顺时针方向自1开始顺序报数，报到m时住手报数，报m的人出列，将他 的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此 下去，直至所有人全部出列为止，设计一个程序

3、求出出列顺序。基本要求：1、利用单循环链表作为存储结构摹拟此过程；2、键盘输入总人数、初始报数上限值m及各人密码；3、按照出列顺序输出各人的编号。2算法设计2.1 数据结构设计输入人数N和报 数上限值M调用input函数 摹拟n个人围成 的圈，并赋予每 个人密码调用output函数输出出列序列子函数功能介绍：创建循环单链表，摹拟个人围成的圈输出出列顺序2.2 约瑟夫环算法设计1 ,输入人数N和报数上限值M,调用函数摹拟n个人围成的圈，并赋予每 个人密码，从第一个人开始按顺时针方向自1开始顺序报数，报到m时住手报 数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个 开始重新从1

4、报数，如此下去，直至所有人全部出列为止，调用output函数输出 出列序列结点结构单元模块一一定义单向循环链表的结点结构。2 .各模块之间的调用关系如下：结点结构单元模块单向循环链表单元模块I约瑟夫环单元模块I主程序模块3约瑟夫环算法分析LinkList s;int n,m;请输入总人数请输入上线数输入人数和限定值请输入d个人的密码s=input(n);LinkList input(int n) int i ;LinkList tail,head;head = tail = (LinkList)malloc(sizeof(LNode); 生成新节点 tail-num = 1;请输入第1个人的密

5、码for(i = 2;i num = i;请输入第0个人的密码tail-next = p; tail = p;tail-next = head;return tail;定义指针p用以循环链表，定义变量i计数，指针p每挪移一次，i加1,直到 i=m时，输出指针p所指向的节点序号，也就是令这个“人”出列，q指向该 节点上一节点，令上一节点next域指向该节点下一节点，然后删除该节点，令 头节点L指向该节点下一节点作为再次报数初始“人”，再令i归0,继续循环。 知道q=p时，表示所有“人”出列完毕，删除最后的节点后跳出循环。序号 密码output(s,m,n);void output(LinkLis

6、t L,int keyjnt n)int i;LinkList q;while( n0) (for (i = 1; i next;q =L-next;第|个人出列，密码L-next =q-next;key = q-password;free(q);n-；报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人 开始重新从1报数，如此下去，直到所有人全部出列为止。4程序源码#include#includetypedef struct LNode /建立一个结构体typedef类型定义(int password; / 密码int num;/编号 数据域struct LNode *next;

7、 指针域 LNode,*LinkList;线性表的单链表存储结构LinkList input(int n) int i ;LinkList tail,head;head = tail = (LinkList)malloc(sizeof(LNode); 生成新节点 tail-num = 1;请输入第1个人的密码for(i = 2;i num = i;请输入第1个人的密码tail-next = p; tail = p;tail-next = head;return tail;void output(LinkList L,int keyjnt n)int i;LinkList q;while( n0

8、)(for (i = 1; i next;)q =L-next;第|个人出列，密码L-next =q-next;key = q-password;free(q);n-；)void main()LinkList s;int n,m;请输入总人数请输入上线数请输入d个人的密码s=input(n);序号 密码outputs,m,n);5运行结果及提交结果截图请输入总人数N:搜狗拼音输入法全：图3程序运行截图 请输入总人数N: 10 请输入上线数M： 9 请输入10个人的密码 请输入第1个人的密码：1 请输入第2个人的密码:2 请输入第3个人的密码:3 请揄入第4个人的密相:4 请懒人重5个人的密宿:

9、5 请输入重6个人的密初:6 请输入第7个人的密码:7 请扁入第8个人的密柿:8 请瑜入童9个人的密祜：9 请输入第10个人的密码:10序号密码第孙人出列，密码9 第8个人出列，密码8 第7个人出列，密码7 第6个人出列，密码6 第5个人出列，密码5 第4个人出列，密码4 第3个人出列，密码3 第2个人出列，密码2 第1个人出歹密码1 第人出列，密码10 . Press any key to continue图4提交截图6体味与总结通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以 说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题 目自己根本不能把程序完整

10、地编写出来，所以这次课程设计最大的收获就在于对 循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除 链表中的一个结点，增加一个结点等。在这次课程设计过程中需要我们一边设 计一边探索，这这个过程之中我发现自己在数据结构方面知识掌握不够深入，对 一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这 是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才干 充分地结合起来。在程序的输入的时候，因为自己对键盘的不熟练，代码又不少 很繁琐，往往会产生抛却的念头，从中我也感受到惟独坚持到底，胜利才会浮现。 在调试程序的时候我也有所体味，虽然约瑟夫环问题不是很难，但调试的时候还 是会浮现不少错误，因此我们不能认为容易就不认真对待。在以后的学习中，要