约瑟夫环数据结构课程设计

约瑟夫环问题设计与实现第1页共10页CHANGSHAUNIVERSITYOFSCIENCE&TECHNOLOGY课程设计（论文）题目：约瑟夫环学生姓名：江元学号：201153100121班级:信息与计算科学11-01班所在院部:数学与计算科学学院指导教师：龚红仿2013年6月约瑟夫环问题设计与实现第2页共10页约瑟夫环学生姓名：江元学号：201153100121班级：信计11-01班指导教师：龚红仿完成日期:2013年6月27日约瑟夫环问题设计与实现第3页共10页约瑟夫环问题设计与实现摘要约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,每人有一个密码m（整数），留作其出圈后应报到m后出圈，依次类推，即可求出出列顺序。因此约瑟夫环问题如果采用循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的最后一个节点指针指向第一个结点。出列时，根据密码找到对应的人，打印其编号，将其密码赋值给m后，释放节点，形成新的约瑟夫环，直到所有人出列结束。关键字：约瑟夫环；循环链表；出列顺序；释放节点；约瑟夫环问题设计与实现第4页共10页DesignandRealizationoftheJosephringABSTRACTTheJosephproblemistheevolutionproposedbyancientRomefamoushistorianJosephusandcome,sooftenreferredtoastheJosephusproblem.ImprovementofJosephproblemdescriptionis:No.1,2,...N,nindividualsaccordingtoaclockwisedirectionaroundacircle,eachwithapasswordofM(integer),keeptheringshouldbereportedaftertheMring,andsoon,wecancalculatethecolumnorder.SoJosephcircleifusingcircularlinkedlistcanbeverygoodsolution.Circulationlistdatastructure,isthelastofanodeisapointertoalistofthepointstothefirstnode.Out,accordingtothecodetofindthecorrespondingperson,printthenumber,thepasswordisassignedtom,releasethenode,theformationofJosephring,untilallthepeopleoutoftheend.Keywords:Josephring;circularlinkedlist;thecolumnorderreleasenodes;约瑟夫环问题设计与实现第5页共10页目录1需求分析………………………………………………………………11.1课题内容…………………………………………………………11.2要求………………………………………………………………12概要设计…………………………………………………………………13详细设计…………………………………………………………………23.1程序中的数据类型………………………………………………23.2函数运行过程详解………………………………………………34设计和调试分析…………………………………………………………64.1调试中遇到的问题………………………………………………64.2经验和体会………………………………………………………75用户使用说明……………………………………………………………76测试数据和测试结果……………………………………………………8参考文献……………………………………………………………………10约瑟夫环问题设计与实现第6页共10页1需求分析1.1课题内容：（1）本演示程序中，人数n应为任意的，首先应输入一个值赋给初始报数上限m，程序应能自动保存出列人的序号和将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。（2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。（3）程序执行的命令包括：（1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。（4）测试数据n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。1.2要求：（1）源程序要有适当的注释，使程序容易阅读；（2）函数功能要划分好（结构化程序设计）；(3)可以增加新功能模块；(4)要提供程序测试方案，程序一定要经得起测试，也要能运行起来，不能运行的程序是没有价值的。2概要设计该系统采用C语言开发，主要方法是选择合适的程序结构，灵活使用三种程序设计基本结构、函数等编写程序。约瑟夫环问题设计与实现第7页共10页2．1本程序包含三个模块，对应关系图为：（1）主程序模块；（2）构造链表并输入每个人信息模块；（3）每个人依序出列打印出列顺序并释放结点模块；2.2为了实现上述操作，应以单向循环链表为存储结构。2.3基本操作：Data_InPut()操作结果：构造链表，初始化每个人的相关信息Data_OutPut()操作结果：释放指向出列的人的结点，并重新报数3详细设计3.1程序中定义的数据类型调用函数Data_InPut创建链表并输入每个人的编号和密码调用函数Data_OutPut按特定的顺序让每个人出列，并释放已出列的节点结束开始执行主函数的内容，开始程序数据next数据next数据next数据next约瑟夫环问题设计与实现第8页共10页typedefstructLNode{ElemTypenum;//各人的编号ElemTypedata;//各人的密码structLNode*next;//指向下一个节点的指针}LNode,*LinkList;程序中定义了一个节点的结构体，每次新分配一个节点内存，即为新增一个人，data为人的密码，num是人的编号。3.2每个函数的过程详解3.2.1voidmain()；函数原型：voidmain()函数源程序：voidmain(){LinkListL=NULL;intm,n=30;//m为报数上限，n为人的个数inti=0;//常用变量printf(\t约瑟夫环问题\n\n);printf(请输入m的值（要求m=30）：);scanf(%d,&m);//将m重新赋值printf(请输入人数n:);scanf(%d,&n);//确定人的个数，即n得值while(n30||n0)//人数异常处理{printf(请输入小于30的正整数：);scanf(%d,&n);}printf(\n);//换行//调用数据录入函数约瑟夫环问题设计与实现第9页共10页Data_InPut(L,n);//调用数据输出函数Data_OutPut(L,n,m);}函数功能及实现：此为主函数，先输入m和n的值，即确定初始上限m和人数n，并对人数进行防出错处理，之后调用函数Data_InPut(L,n)对n个人编号和输入对应密码，再调用函数Data_OutPut(L,n,m)按照要求对各个人依次出列，打印相关信息到屏幕上。3.2.2LinkListData_InPut(LinkList&L,intk);函数原型：LinkListData_InPut(LinkList&L,intk);函数源程序：LinkListData_InPut(LinkList&L,intk){LinkListR,P,Q;L=(LinkList)malloc(sizeof(LNode));//创建一个节点R=L;for(inti=0;ik;i++)//通过for循环录入数据{scanf(%d,&R-data);//依次输入每个人的密码R-num=i+1;//输入每个人的编号P=(LinkList)malloc(sizeof(LNode));//创建新节点P-next=NULL;Q=R;R-next=P;//连接新的节点R=P;}free(P);//释放无用结点Q-next=L;return(L);//返回循环链表约瑟夫环问题设计与实现第10页共10页}函数功能及实现：先定义结构体指针变量R，P，Q，L，创建一个新节点赋值给指针L，并将L赋值给R，通过for循环再创建n个节点，并录入每个人对应编号，通过scanf函数录入每个人的密码，因为创建了一个节点。并将新创建的节点连到链表尾端，形成一个单链表。最后创建的一个节点是多余的，需要删除，所以通过free函数释放最后一个节点。之后将单链表的尾指针指向第一个节点，形成一个单循链表。最后通过return函数返回循环链表，继续执行主函数。3.2.3voidData_OutPut(LinkList&L,intk,intb)；函数原型：voidData_OutPut(LinkList&L,intk,intb)；函数原程序：voidData_OutPut(LinkList&L,intk,intb){printf(\n出列顺序为:\n);LinkListR,P,Q;for(inti=0;ik;i++)//通过循环输出数据{R=L;while(--b)//通过while循环找到密码做指向的那个人{Q=R;//加入Q方便寻找出列的人的上一个节点R=R-next;//指针后移}printf(第%d个出列%d\n,i+1,R-num);//输出所找人的编号b=R-data;//刷新b值，将所找到人的密码赋值给bQ-next=R-next;//将出列人的前一个节点和后一个节点连接形成新环L=R-next;free(R);//释放已出列结点约瑟夫环问题设计与实现第11页共10页}函数功能及实现：该函数首先定义了指针变量R，P，Q，L方便对节点的操作。通过for循环以确定所有人都会被出列，在while循环中，b的值最初是给定的报数上限，通过自减操作找到所要出列的那个人，打印其编号，将其密码重新赋值给b，并删除代表该人的节点，并释放该节点，形成一个新的约瑟夫环，进行下一次循环，最终所有人出列后完成for循环，打印出列顺序，返回大主函数。4设计和调试分析4.1调试中遇到的问题（1）在用scanf函数给普通变量输入数据时，在变量名前漏写地址运算符&。如:scanf(″％d％d″,x,y);（2）输入数据时的数据形式与要求不符。用scanf函数输入数据时，必须注意要与scanf语句中的对应形式匹配。如：scanf(″％d,％d″,&x,&y);若按以下形式输入数据：24是不合法。数据2和4之间应当有逗号。（3）输入、输出时的数据类型与所用格式说明符不匹配。例如有以下说明语句：intx=1;chary=’a’;则运行时执行语句printf(″x=％c,y=％d＼n″,x,y);将给出与原意不符的结果：(在TURBOC2.0下运行)（4）对于复合语句，忘记加花括号。例如：i=1;a=0;while(i＜=10)a+=i;i++;约瑟夫环问题设计与实现第12页共10页printf(″a=％d＼n″,a);的上限值是数组定义时元素个数减1。（5）对指针的操作要小心谨慎，比如初始化和赋值等问题值得加以注意。4.2经验和体会通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的