约瑟夫环课程设计报告

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：约瑟夫环院（系）：专业：班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告I目录1课程设计介绍............................................................................................................11.1课程设计内容........................................................................................................11.2课程设计要求........................................................................................................12课程设计原理............................................................................................................22.1课设题目粗略分析..............................................................................................22.2原理图介绍..........................................................................................................22.2.1功能模块图（如图2.1）...............................................................................22.2.2流程图分析.....................................................................................................33数据结构分析............................................................................................................53.1存储结构..............................................................................................................53.2算法描述..............................................................................................................54调试与分析................................................................................................................64.1调试过程..............................................................................................................64.2程序执行过程......................................................................................................6参考文献..........................................................................................................................8附录（关键部分程序清单）....................................................................................9沈阳航空航天大学课程设计报告11课程设计介绍1.1课程设计内容编号为1,2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。使用单循环链表作为存储结构分析：由题意可以将每个人看做链表上的一个节点，每个人持有的密码即为每个节点所存储的数据；相邻的人之间存在连结关系，即链表的两个相邻节点之间由指针来进行关联；最后一个人和第一个人也存在连结关系，即链表的末尾节点和头结点相连构成了单循环链表存储结构。执行报数过程可以看做一个单独指针依次指向每一个节点，有人出列即删除掉链表中相应的节点。1.2课程设计要求1.参考相应的资料，独立完成课程设计任务。2.交规范课程设计报告和软件代码。沈阳航空航天大学课程设计报告22课程设计原理2.1课设题目粗略分析根据课设题目要求，程序应该分为两大部分：1、单循环链表储存结构的建立：建立所需的单循环链表数据存储结构，对每个节点输入所需的密码、序号数据并通过指针连接成单循环链表。2、实现约瑟夫环数据出列顺序的算法：依照题目要求按照报数上限对节点进行查找和删除操作，按顺序输出出列的节点序号，依照每次出列的节点存储的密码修改报数上限循环操作直到全部节点出列完毕程序运行结束。2.2原理图介绍2.2.1功能模块图（如图2.1）图2.1功能模块图建立单循环链表输出出列顺序约瑟夫环沈阳航空航天大学课程设计报告32.2.2流程图分析1.主程序图，如图2.2：首先建立单循环链表作为数据存储结构并存储数据，然后如果执行报数。如果链表中剩余节点数大于1，执行报数操作，得到节点的序号数据并输出；若链表中只剩一个节点，输出节点的序号数据，程序运行结束。图2.2主程序图开始构建单循环链表；选定报数上限m；链表中节点数大于1报数并保存数据删除节点选定新的报数上限m为删除节点储存的密码是否结束输出结果沈阳航空航天大学课程设计报告42.构建单循环链表流程图，如图2.3：首先为链表存储空间，然后判断节点数是否达到上限，若没有到达上限，构建新节点；若已到达上限，将末尾节点的指针指向头结点形成单循环链表并结束建立链表操作。图2.3构建单循环链表流程图开始分配存储空间节点数达到最大构建新节点末尾节点指向表头结束是否沈阳航空航天大学课程设计报告53数据结构分析3.1存储结构typedefstructLNode{intdata;//每个人持有的密码intnum;//每个人的编号structLNode*next;//指向下一个节点的指针}LNode,*LinkList;//定义一个结构体为一个持有密码的人3.2算法描述1.构建单循环链表：首先定义结构体节点指针节点p，链表L，头指针head。使head指向L的头结点，p指向L。对结构体p的数据部分进行输入赋值作为L的一个节点然后向后移一位。循环此步操作形成单链表。最后将末尾节点的指针指向头结点形成单循环链表。2.约瑟夫环出列操作：首先定义指针J和K，指针J指向单循环链表的第一个节点，随机生成一个报数上限m值。将指针p向后拨m-1次，此时p所指向节点的下一个节点即为要出列的节点，使指针K指向该节点，将这个节点从链表中删除，然后读取其中存储的序号数据输出，读取其中存储的密码作为新的m值。然后继续反复执行拨指针p，出列节点，读取数据操作，直到链表中只剩下一个节点停止循环操作，此时输出最后一个节点中的序号数据完成全部出列操作。沈阳航空航天大学课程设计报告64调试与分析4.1调试过程调试过程中出现errorC2065：’rand’:undeclaredidentifier报错，在添加预处理命令#includes“time.h”后正常执行；在执行过程中出现极大数据，发现构建循环链表时将末尾指针指向了头结点，改为指向头结点的下一个节点之后正常运行；4.2程序执行过程1.如图4.1所示，当输入人数为5，每个人所持有的密码依次为2、4、6、8、10时，输出结果：出列顺序为：1-3-2-5-4，程序运行正确。图4.1当人数为5时的程序运行结果沈阳航空航天大学课程设计报告72.如图4.2所示，当输入人数为10，每个人所持有的密码依次为9、1、5、7、3、6、8、2、4、10时，输出结果：出列顺序为：8-10-2-3-9-6-1-7-5-4，程序运行正确。图4.2当人数为10时的程序运行结果沈阳航空航天大学课程设计报告8参考文献[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007.[2]张长海，陈娟.C程序设计[M].北京：高等教育出版社，2004.[3]谭浩强.C程序设计[M].北京：清华大学出版社，2005.[4]苏士华，黄学俊.数据结构解析.习题.课程设计[M].合肥：中国科学技术大学出版社，2009.[5]张瑞军.数据结构[M].北京：清华大学出版社，2009.[6]刘怀亮.数据结构习题解析与实验指导[M].北京：冶金出版社，2009.[7]王敬华，林萍，张清国.C语言程序设计教程（第二版）[M].背景：清华大学出版社，2005.沈阳航空航天大学课程设计报告9附录（关键部分程序清单）#includestdafx.h#includestdio.h#includestdlib.h#includestring.h#includemalloc.h#includemath.h#includetime.htypedefstructLNode{intdata;intnum;structLNode*next;}LNode,*LinkList;voidcreatelist(LinkList&L,intn){LinkListp,head;inti,a;L=(LinkList)malloc(sizeof(LNode));沈阳航空航天大学课程设计报告10head=L;for(i=0;in;i++){p=(LinkList)malloc(sizeof(LNode));printf(请输入第%d个人的密码\n,i+1);scanf(%d,&a);p-data=a;p-num=i+1;L-next=p;p-next=NULL;L=p;}p-next=head-next;}voidmain(){intn,m,x,k,l;LinkListJ,L,K;printf(请输入人数：\n);scanf(%d,&n);createlist(L,n);沈阳航空航天大学课程设计报告11J=L;srand((unsigned)time(NULL));m=rand()%n;printf(出列顺序为：);for(l=0;ln-1;l++){for(k=0;km-1;k++){J=J-next;}K=J-next;J-next=K-next;x=K-num;printf(%d-,x);m=K-data;free(K);}x=J-num;printf(%d\n,x);}沈阳航空航天大学课程设计报告12课程设计总结：在老师让我们在课设题目中选择一道时，我看到这道题的条件似乎很有思考的价值，有点类似于ACM比赛题目便选择了这道题目。在完成了课程设计的过程中我并没有遇到太大的阻碍，一开始就对题目的理解