2022年约瑟夫环 .pdf

《2022年约瑟夫环 .pdf》由会员分享，可在线阅读，更多相关《2022年约瑟夫环 .pdf（11页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、软 件 学 院课程设计报告书课程名称数据结构课程设计设计题目 Joseph环专业班级软件 09-5 学号 0920010521 姓名杨龙博指导教师孙宁2010 年12 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 目录(一) 设计时间 3 (二) 设计目的 3 (三) 设计任务 3 (四) 设计内容 3-10 (五) 总结与展望 10 (六) 参考文献 .11 名师资料总结 - - -精品资料欢迎下载 - - - - -

2、- - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 1 设计时间 12月 27 日-12 月 31 日2 设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的

3、训练，将起到显著的促进作用。3 设计任务编号是 1，2， ,n 的 n 个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数） 。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1 开始顺序报数，报到 m时停止报数。报 m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1 报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。4 设计内容设计一个程序，以人机交互的方式执行，用户指定约瑟夫环游戏的总人数n 和初始的报数上限 m ，然后输入每个人所持有的密码key。模拟约瑟夫环，从头开始报数，直到所有人出列。系统按照出列顺序给出编号及该人所持有

4、的密码。4.1 需求分析1、程序所能达到的功能： 用户指定约瑟夫环游戏的总人数n 和初始的报数上限m ，然后输入每个人所持有的密码key。模拟约瑟夫环，从头开始报数，直到所有人出列。系统按照出列顺序给出编号及该人所持有的密码。2、输入的形式为一个在 -21474836482147483648之间的整数数值。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 3、测试数据正确输入结果：参加的人数为 :3 起始报数上线值 :2 输入第

5、 1 个人的密码： 4 输入第 2 个人的密码： 5 输入第 3 个人的密码： 6 输出结果为 : 第 1 个出列的人的编号是： 2 密码是： 5 第 2 个出列的人的编号是： 3 密码是： 6 最后一个出局的人的编号是：1 密码是： 4 错误的结果：若输入的内容格式不符合要求，则会出现乱码。4.2 总体设计1、本程序中用到的所有抽象数据类型的定义为：创建一个循环链表struct LNode* CreateList_L( LinkList *L, int z) 对循环链表进行操作 Operate(LinkList L,int h, int n) 找到第 m 个元素将其删除并且将其 data 域

6、的值赋给下一个m值继而进行循环。2、主程序的流程为：输入起始参加约瑟夫循环的人数以及起始上限m 值，建立一个循环链表，之后对循环来表进行操作，实现目的。3、各程序模块之间的调用关系。主函数调用CreateList_L( LinkList *L, int z) 函数和Operate(LinkList L,int h, int n) 。4.3 详细设计1、struct LNode*CreateList_L( LinkList *L,int z) (*L)=(LinkList) malloc ( sizeof(LNode); q=(*L); q-next=NULL; 名师资料总结 - - -精品资料

7、欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - for(i=1;inext=p; p-next=NULL; p-data=i; printf( 输入第 %d个人的密码： ,i); scanf(%d,&key); p-password =key; q=p; *L=(*L)-next; p-next=*L ；return L; /创建约瑟夫环Operate(LinkList L, int h,int n) int i=1,j; LinkList J; for (

8、i = 1; in; i+) for (j = 1; j next; J-next = L-next; printf(第%d个出列的人的编号是： %d 密码是： %dn,i,L-data,L-password); h=L-password; L=L-next; i =L-password; j=L-data; printf(最后一个出局的人的编号是：%d 密码是： %dn,j,i); /对单循环链表进行操作main() k=CreateList_L(& I,n); I=*k; Operate(I,m,n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

9、- - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 2、struct LNode *CreateList_L( LinkList *L,int z) (*L)=(LinkList) malloc ( sizeof(LNode);/定义一个 LinkList型的指针q=(*L); q-next=NULL; for(i=1;inext=p; p-next=NULL; p-data=i;/ 赋值printf( 输入第 %d个人的密码： ,i); scanf(%d,&key); p-password=key;/输入之后赋值

10、q=p; / 将循环链表中的 data和password依次赋值*L=(*L)-next; p-next=*L；/ 将尾指针赋给头指针，使其变为一个循环链表return L; / 创建约瑟夫环Operate(LinkList L, int h,int n) int i=1,j; LinkList J; for (i = 1; in; i+) for (j = 1; j next; / 找出第 m个元素J-next = L-next;/ 将其删除printf( 第%d个出列的人的编号是： %d 密码是： %dn,i,L-data,L-password); h=L-password;/重新赋给 h

11、 L=L-next;/ 让L指向下一个循环链表中的指针i =L-password; j=L-data; printf(最后一个出局的人的编号是：%d 密码是： %dn,j,i); / 对单循环链表进行操作main() k=CreateList_L( &I,n); I=*k; Operate(I,m,n);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 3、 函数的调用关系图为：是否是否开始建立单链表， 使其成为循环链表输入人数

12、和起始上限值inext=*L 使 p 指向头结点返回头指针进行 Operate 函数p-next=*L i 总人数 n jnext 输出此人所持有的密码，并将其付给下一个 n 输出最后一个人的密码结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 4.4 测试与分析4.4.1 测试参加的人数为 :3 起始报数上线值 :2 输入第 1 个人的密码： 4 输入第 2 个人的密码： 5 输入第 3 个人的密码： 6 输出结果为 :

13、第 1 个出列的人的编号是： 2 密码是： 5 第 2 个出列的人的编号是： 3 密码是： 6 最后一个出局的人的编号是：1 密码是： 4 4.4.2 分析1、当初试图仅仅应用一个指针来指向循环链表，发现不行，采用两个指针，通过建立节点之处，通过复制是一个指针指向表头，赋完值之后，进行让位指针指向头指针，从而构建循环链表，在对循环链表进行操作的时候，发现最后一个元素不能通过循环链表将其输出，只能通过再一个输出语句来输出最后一个元素。2、用单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点的指针，用三大主要的函数来实现功能，包括创建链表的函数、输出链表信息的函数、删除结点也就是出栈

14、的函数、主函数等函数。4.5 附录#include #include typedef structLNode int data; int password; struct LNode * next; LNode, *LinkList; struct LNode*CreateList_L( LinkList *L,int z) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - int key,i; LinkList p,q; (*

15、L)=(LinkList) malloc ( sizeof(LNode); q=(*L); q-next=NULL; for(i=1;inext=p; p-next=NULL; p-data=i; printf( 输入第 %d个人的密码： ,i); scanf(%d,&key); p-password =key; q=p; *L=(*L)-next; p-next=*L; return L; /创建约瑟夫环Operate(LinkList L, int h,int n) int i=1,j; LinkList J; for (i = 1; in; i+) for (j = 1; j next;

16、 J-next = L-next; printf(第%d个出列的人的编号是： %d 密码是： %dn,i,L-data,L-password); h=L-password; L=L-next; i =L-password; j=L-data; printf(最后一个出局的人的编号是：%d 密码是： %dn,j,i); /对单循环链表进行操作void main() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - int n,m;

17、 LinkList I, *k; printf(参加的人数为 :); scanf(%d,&n); printf(起始报数上线值 :); scanf(%d,&m); k=CreateList_L(&I,n); I=*k; printf(输出结果为 :n); Operate(I,m,n); 5 总结与展望课程设计的过程，需要创建一个循环链表，这个循环链表是在单链表的基础上改造得来，途中遇到指针值传错的问题，需创建两个指针， p -next =*L; 实现了单链表的循环，在程序运行的过程中，调用的两个函数并未完全运行，而自己有需要查找问题所在，运用一个简单的printf函数即可知道程序运行到哪里，书

18、上提示的只是算法，不能直接在电脑上运行，缺点在程序运行过程中一旦输入错误，无法返回。从这次课程设计的实践中认识到自己还有很多的不足，发现自己眼高手低的毛病，经过这次课程设计，我对自己的实践方面进行了加强，虽然在课程设计的过程中遇到了很多错误，但是自己还是逐一克服， 相信自己在今后的学习中， 能够更好了解自己， 完成任务。通过这次课设我把以前以为没有实际用处的书本知识转化为了实际问题来解决，很有意思，也觉得课设这种动手能力更高的学习方法有助于我们把兴趣放在学习上。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 参考文献1 数据结构（ C语言版） ，北京：清华大学出版社，2002 2 数据结构课程设计，北京，机械工业出版社，2004 3C 语言程序设计教程，上海，高等教育出版社，2006 成绩评定成绩教师签字名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -