约瑟夫环课程设计报告

00C++课程设计报告课题:约瑟夫环专业班级：学号：姓名：指导教师:目录评阅意见：评定成绩：指导老师签名：年月日11课程设计的目的和意义...............................................................................................................22需求分析.......................................................................................................................................33系统（项目）设计.......................................................................................................................4(包括总体设计和详细设计)............................................................................................................4一、设计思路及方案.......................................................................................................................4二、模块的设计及介绍...................................................................................................................4（2）创建单循环链表函数流程图.................................................................................................6（3）删除结点函数（出队函数）程序流程图.............................................................................74系统实现.......................................................................................................................................85系统调试.....................................................................................................................................11参考文献.........................................................................................................................................15附录源程序...................................................................................................................................1621课程设计的目的和意义数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。本次课程设计的内容是用单循环链表模拟约瑟夫环游戏，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。32需求分析该程序所做的工作是约瑟夫环游戏，有以下内容和要求：1．本程序设计中，从键盘输入约瑟夫环游戏的总人数n和初始的报数上限m，然后给每个人输入所持有的密码key。用单循环链表模拟约瑟夫环，从队头开始从1报数，报到m的人出列，再把此人的密码赋给m，继续下一轮的报数，直到所有的人出列。2．演示程序以用户和计算机对话方式进行，根据提示信息由用户从键盘输入数据，以“回车符“为结束标志，运行后输出的结果是约瑟夫环的相关信息和经过报数后出队的人的序列号及相关信息。结果出来后再选择输入一数字，输入1继续新一轮的游戏，输入0结束，退出此游戏。3．程序执行的命令包括：（1）构造单循环链表；（2）输出循环链表的信息；（3）按照出列的顺序输出各人的编号4．测试数据总人数n=5，初始报数上限m=6，5个人的密码依次为2，5，4，6，7，正确的输出序列为2，4，5，3，1。43系统（项目）设计(包括总体设计和详细设计)一、设计思路及方案用单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点的指针，用三大主要的函数来实现功能，包括创建链表的函数、输出链表信息的函数、删除结点也就是出队的函数、主函数等函数。二、模块的设计及介绍（1）主程序模块Voidmain（）{初始化；do{接受命令；处理命令；}while（“命令”=“退出”）；}（2）创建链表模块Staticvoidcreatlist（行参）{初始化；For{接受命令；处理命令}}（3）输出链表信息模块staticvoidPrntList(参数){定义变量并初始化；输出命令；}（4）删除结点也就是出队模块staticvoidStatGame(参数){定义变量并初始化；5While{开始报数；输出结果；}}三、主要模块程序流程图（1）主函数程序流程图开始输入n，m创建单循环链表输出链表信息开始游戏输入aa=1？结束否是6（2）创建单循环链表函数流程图开始i=n?输入每人所持有的密码创建结点结束是否7（3）删除结点函数（出队函数）程序流程图84系统实现各模块关键代码及算法的解释：（1）主函数模块代码circularlistpHead=NULL;intmain(void){intn,m，iflag=1while(iflag=1){printf(请输入总人数n=);scanf(%d,&n);printf(\n再请输入初始报数上限m=);scanf(%d,&m)；CreatList(&pHead,n);printf(\n输出所有人的信息如下:\n);PrntList(pHead);printf(\n按照出列顺序输出每个人的编号:\n);StatGame(&pHead,m);printf(\n约瑟夫环的游戏完成!\n);printf(输入1开始建环做游戏，输入0退出该游戏，请选择!);scanf(%d,&i);}return0;}程序解释：该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入总人数和初始的报数上限，再调用创建链表的函数建环，后输出单循环链表的信息，再调用StatGame（）函数，报到上限的那个结点从表中删除既出队，然后再选择输入一个数确定是否继续游戏，输入1继续，输入0退出。（2）创建单循环链表函数模块代码staticvoidCreatList(circularlist*ppHead,constintn){inti,ikey;Node*pNew,*pCur;for(i=1;i=n;i++)9{printf(请输入第%d个人所持有的密码:,i);scanf(%d,&ikey);pNew=GetNode(i,ikey);if(*ppHead==NULL){*ppHead=pCur=pNew;pCur-next=*ppHead;}else{pNew-next=pCur-next;pCur-next=pNew;pCur=pNew;}}程序解释：用一个for循环来给链表的每个结点分配空间，并从键盘输入每人所持有的密码，如果头结点的值为空，使其指向新生成的一个结点，新结点的next指针指向头结点，如果不是，则当前结点的next的值赋给新结点的next，然后当前结点的next值指向新结点，再当前结点的指针指向新结点，实现链表的建立。（3）删除结点函数代码staticvoidStatGame(circularlist*ppHead,intikey){intiCounter,iFlag=1;Node*pPrv,*pCur,*pDel;pPrv=pCur=*ppHead;while(iFlag)!*/{for(iCounter=1;iCounter=ikey;iCounter++){pPrv=pCur;pCur=pCur-next;}if(pPrv==pCur)iFlag=0;10pDel=pCur;Prv-next=pCur-next;pCur=pCur-next;ikey=pDel-key;printf(第%d个人出列,所持有密码是:%d\n,pDel-id,pDel-key);free(pDel);}ppHead=NULL;}程序解释：设立一个标签，值为1执行循环语句，值为0跳出循环。循环语句里的for循环实现报数功能，也就是结点移动的功能，移动ikey个结点，再删除第ikey个结点，并把该结点的密码值赋给ikey，再从该结点的下一个结点移动，重复上面的过程，结点全都删除后使标签的值为0，结束while循环，游戏结束。115系统调试1、运行程序后，初界面：图5.1初界面2、输入总人数之后的界面：3、输入初始报数上限后的界面：4、输入所有人所持有的密码后的界面：125、输入1之后的界面：136、继续新一轮的游戏，结束后的界面：7、输入0之后的界面：14小结通过一周的课程设计之后，培养了我选用参考书，查阅手册及文献资料的能力，培养独立思考，深入研究，分析问题、解决问题的能力，提高综合运用本课程所学知识的能力，还对设计的基本过程的设计方法、步骤、思路、有一定的了解与认识，并对存储结构，比如线形表、链表、循环链表、树、图等存储结构，特别是对单循环链表理解的更深。也使我认识到《数据结构》这门课程是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重要的地位。同时也使我知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。本次课程设计的主题是用单循环链表来模拟约瑟夫环游戏，由于刚开始对循环链表的理解不够，也没理请约瑟夫环的基本思路，做起来有点难，但通过反复的修改，最终还是能够理解。我学到了很多的东西，通过实际编译系统的分析设计、编程调试，也掌握了一些工程设计方法。现在也能够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制程序框图。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。在这次课程设计中我遇到许多问题和麻烦。比如，表建成之后，不能输出表中的信息，说明指针