约瑟夫环实验报告

数据结构课程设计报告题目：约瑟夫环实验班级：成员：指导教师：完成日期：第1页共24页1目录：实习报告要求..............................................................2约瑟夫环实验描述.......................................................3课程设计报告正文.................................4一．需求分析..............................................................4二．概要设计..............................................................4三．详细设计..............................................................61．各模块关键代码及算法的解释：.............62．函数的调用关系图.........................8四．调试分析............................................................11五．用户使用说明.....................................................12六．测试结果............................................................13七．小结.....................................................................3八．附录，带注释的源程序.........................................4第2页共24页2实习报告要求实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：1.需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定:(1)输入的形式和输入值的范围；(2)输出的形式；(3)程序所能达到的功能；(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2.概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。3.详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数的调用关系图。4.调试分析内容包括：(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；(3)经验和体会等。5.用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。6.测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。7.附录带注释的源程序。可以只列出程序文件名的清单。实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然也可以应该最后用实验报告纸誉清或打印)。第3页共24页3约瑟夫环实验描述【问题描述】约瑟夫(Joseph)问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。【测试数据】m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6(正确的出列顺序应为6，1，4，7，2，3，5)。【实现提示】程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。【选作内容】向上述程序中添加在顺序结构上实现的部分。第4页共24页4课程设计报告正文一．需求分析1．输入的形式和输入值的范围本程序中，输入人数n(n小于等于30)和初始密码m（m大于等于1），然后给每个人输入所持有的密码key，均限定为正整数。用单循环链表模拟约瑟夫环，从队头开始从1报数，报到m的人出列，再把此人的密码赋给m，继续下一轮的报数，直到所有的人出列。结果出来后再选择输入一数字，输入1继续新一轮的游戏，输入0结束，退出此游戏。演示程序以用户和计算机对话方式进行，根据提示信息由用户从键盘输入数据，输入的形式为一个以“回车符”为结束标志的正整数。2．输出的形式在计算机终端上显示提示信息之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。运行后输出的结果是约瑟夫环的相关信息和经过报数后出队的人的序列号及相关信息。程序执行的命令包括：（1）输入人数和初始密码（2）输入所有人的密码（3）显示输入的所有人的编号及相应的密码（4）输出出列密码及编号（5）结束即：（1）构造单循环链表；（2）输出循环链表的信息；（3）按照出列的顺序输出各人的编号3．程序功能提供用户从键盘输入，Joseph约瑟夫环的必要数据，并从屏幕显示出列顺序。4．测试数据（1）n=7,m=20（常规数据）,7个人的密码依次为3，1，7，2，4，8，4，正确的输出序列为6，1，4，7，2，3，5.（2）n=5，m=6（常规数据），5个人的密码依次为2，5，4，6，7，正确的输出序列为1,3,4,2,5。（3）n=31,m=3（错误数据），“这个人数太大了，请重新输入”。（4）n=0,m=3（错误数据），“这个约瑟夫环里没有人！”。（5）n=1,m=4,（边缘数据），正确的输出序列为1。（6）n=3,m=1,（边缘数据），正确的输出序列为1，3，2。第一组为常规数据，中间两组为错误数据，后面两组为边缘数据。5．设计思路及方案用单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点的指针，用三大主要的函数来实现功能，包括创建链表的函数、输出链表信息的函数、删除结点也就是出队的函数、主函数等函数。二．概要设计1．抽象数据类型的定义第5页共24页5为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为：ADTLinkList{数据对象：D={ai|ai∈termset,i=1,2,……n,n=0}，termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,……n}基本操作：LinkListEvaluList(intn);//对单向循环链表进行尾插入赋值intsize(LinkListL);//求链表的节点个数StatusScanList(LinkListL);//遍历单向循环链表StatusJoseph(LinkList&L,intm);//约瑟夫环的实现}此抽象数据类型中的一些常量如下：#defineTRUE1#defineFALSE0#defineOK1typedefintStatus;typedefdoubleElemType;单向循环链表中节点的定义如下所示：typedefstructLNode{intnumber;intdata;structLNode*next;}LNode,*LinkList;2．主程序的流程voidmain(){初始化；输入数据；执行功能；显示结果；}3．模块的设计及介绍（1）主程序模块Voidmain（）{初始化；do{接受命令；处理命令；}while（“命令”=“退出”）；}（2）创建链表模块Staticvoidcreatlist（行参）{第6页共24页6初始化；For{接受命令；处理命令}}（3）输出链表信息模块staticvoidPrntList(参数){定义变量并初始化；输出命令；}（4）删除结点也就是出队模块staticvoidStatGame(参数){定义变量并初始化；While{开始报数；输出结果；}}4．各程序模块之间的层次(调用)关系。本程序包含以下模块：（1）主程序模块：（2）各功能模块——实现顺序表的各项功能。各模块的调用关系：主程序↓各功能模块三．详细设计1．各模块关键代码及算法的解释：（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退出该游戏，请选第7页共24页7择!);scanf(%d,&i);}return0;}程序解释：该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入总人数和初始的报数上限，再调用创建链表的函数建环，后输出单循环链表的信息，再调用StatGame（）函数，报到上限的那个结点从表中删除既出队，然后再选择输入一个数确定是否继续游戏，输入1继续，输入0退出。（2）创建单循环链表函数模块代码staticvoidCreatList(circularlist*ppHead,constintn){inti,ikey;Node*pNew,*pCur;for(i=1;i=n;i++){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;pDel=pCur;Prv-next=pCur-next;第8页共24页8pCur=pCur-next;ikey=pDel-key;printf(第%d个人出列,所持有密码是:%d\n,pDel-id,pDel-key);free(pDel);}ppHead=NULL;}程序解释：设立一个标签，值为1执行循环语句，值为0跳出循环。循环语句里的for循环实现报数功能，也就是结点移动的功能，移动ikey个结点，再删除第ikey个结点，并把该结点的密码