数据结构基础约瑟夫环

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

23.…算法分析

34.…程序源码

46.…试算截屏图

58.・・.分析与总结

69.…参考文献

79.…选题描述1约瑟夫环:编号为的个人按顺时针方向围坐一圈，每人持有一个密码1,2,,n n（正整数）一开始任选一个正整数作为报数的上限值从第一个人开始按顺时针方m,向自开始顺序报数，报到时住手报数，报的人出列，将他的密码作为新的1m m m值，从他的顺时针方向上的下一个开始重新从报数，如此下去，直至所有人全部出1列为止，设计一个程序求出出列顺序基本要求、利用单循环链表作为存储结构摹拟此过程；

1、键盘输入总人数、初始报数上限值及各人密码；2m、按照出列顺序输出各人的编号3算法设计2调用函数摹输入人数和报input调用函数N output拟个人围成的n数上限值输出出列序列M圈，并赋予每个人密码数据结构设计

2.1子函数功能介绍创建循环单链表，摹拟个人围成的圈输出出列顺序约瑟夫环算法设计

2.2,输入人数和报数上限值调用函数摹拟个人围成的圈，并赋予每个人密1N M,n码，从第一个人开始按顺时针方向自开始顺序报数，报到时住手报数，报1m m的人出列，将他的密码作为新的值，从他的顺时针方向上的下一个开始重新m从报数，如此下去，直至所有人全部出列为止，调用函数输出出列序列1output结点结构单元模块一一定义单向循环链表的结点结构.各模块之间的调用关系如下2结点结构单元模块单向循环链表单元模块I约瑟夫环单元模块I主程序模块约瑟夫环算法分析3LinkList s;int n,m;请输入总人数请输入上线数----------------------输入人数和限定值------------------请输入个人的密码％ds=inputn;LinkList inputint n{int i;LinkList tail,head;〃生成新节点head=tail=LinkListmallocsizeofLNode;tail-num=1;请输入第个人的密码1fori=2;i=n;i++LinkList p;〃指针变量p=LinkListmallocsizeofLNode;pp-num=i;请输入第％个人的密码0tail-next=p;tail=p;}tail-next=head;return tail;｝定义指针用以循环链表，定义变量计数，指针每挪移一次，加直到时，p ip i1,i==m输出指针所指向的节点序号，也就是令这个“人”出列，指向该节点上一节点，p q令上一节点域指向该节点下一节点，然后删除该节点，令头节点指向该节点下next L一节点作为再次报数初始“人”，再令归继续循环知道时，表示所有“人”i0,q==p出列完毕，删除最后的节点后跳出循环序号密码outputs,m,n;void outputLinkListL,int keyjntnint i;LinkList q;while n0for i=1;ikey;i++L=L-next;}q=L-next;第％£|个人出列，密码L-next=q-next;key=q-password;freeq;n-；｝报的人出列，将他的密码作为新的值，从他在顺时针方向的下一个人开始mm重新从报数，如此下去，直到所有人全部出列为止1程序源码4#includestdio.h#includemalloc.h建立一个结构体类型定义typedef struct LNode//typedef//密码int password;//编号数据域int num;〃指针域structLNode*next;}LNode,*LinkList;〃线性表的单链表存储结构LinkList inputintn{int i;LinkList tail,head;〃生成新节点head=tail=LinkListmallocsizeofLNode;tail-num=1;请输入第个人的密码1fori=2;i=n;i++LinkList p;〃指针变量p=LinkListmallocsizeofLNode;pp-num=i;请输入第％€个人的密码1tail-next=p;tail=p;}tail-next=head;return tail;}void outputLinkListL,int keyjntnint i;LinkList q;while n0for i=1;ikey;i++L=L-next;q=L-next;第％£|个人出列，密码L-next=q-next;key=q-password;freeq;n-；}void mainLinkLists;intn,m;请输入总人数请输入上线数请输入个人的密码％ds=inputn;序号密码outputs,m,n;}运行结果及提交结果截图5请输入总人数N:搜狗拼音输入法全图3程序运行截图请输入总人数N:10请输入上线数M9请输入10个人的密码请输入第1个人的密码1请输入第2个人的密码:2请输入第3个人的密码:3请揄入第4个人的密相:4请懒人重5个人的密宿: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 anykey tocontinue图提交截图4体味与总结6通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等在这次课程设计过程中需要我们一边设计一边探索，这这个过程之中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的学好基础知识是理论付诸实践的前提，这样理论和实践才干充分地结合起来在程序的输入的时候，因为自己对键盘的不熟练，代码又不少很繁琐，往往会产生抛却的念头，从中我也感受到惟独坚持到底，胜利才会浮现在调试程序的时候我也有所体味，虽然约瑟夫环问题不是很难，但调试的时候还是会浮现不少错误，因此我们不能认为容易就不认真对待在以后的学习中，要。