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

约瑟夫环问题设计与实现摘要约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题改进约瑟夫问题的描述是编号为1,2,n的n个人按顺时针方向围坐一圈，每人有一个密码m（整数），留作其出圈后应报到m后出圈，挨次类推，即可求出出列顺序因此约瑟夫环问题如果采用循环链表则能很好的解决循环链表的数据结构，就是将一个链表的最后一个节点指针指向第一个结点出列时，根据密码找到对应的人，打印其编号，将其密码赋值给m后，释放节点，形成新的约瑟夫环，直到所有人出列结束关键字约瑟夫环；循环链表；出列顺序；释放节点；进行下一次循环，最终所有人出列后完成for循环，打印出列顺序，返回大主函数设计和调试分析4调试中遇到的问题

4.11在用scanf函数给普通变量输入数据时，在变量名前漏写地址运算符如:y;2输入数据时的数据形式与要求不符用scanf函数输入数据时，必须注意要与scanf语句中的对应形式匹配如scar血%d%d”,x,y;若按以下形式输入数据24是不合法数据2和4之间应当有逗号3输入、输出时的数据类型与所用格式说明符不匹配例如有以下说明语句int x=l;chya=ra;则运行时执行语句printf%xe,尸％d\n凶y;将给出与原意不符的结果在TURBOC

2.0下运行4对于复合语句，忘记加花括号例如i=l;a=0;while i=10a+=i;i++;printf%泄\n〃,a的;上限值是数组定义时元素个数减15对指针的操作要小心谨慎，比如初始化和赋值等问题值得加以注意经验和体味

4.2通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以幺/火#J0约瑟夫环问题设计与实现°7说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等在这次课程设计过程中需要我们一边设计一边探索，这这个过程之中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的学好基础知识是理论付诸实践的前提，这样理论和实践才干充分地结合起来在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己在程序的输入的时候，因为自己对键盘的不熟练，代码又不少很繁琐，往往会产生抛却的念头，从中我也感受到惟独坚持到底，胜利才会浮现在调试程序的时候我也有所体味，虽然约瑟夫环问题不是很难，但调试的时候还是会浮现不少错误，因此我们不能认为容易就不认真对待在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己用户使用说明51根据正确的提示安装软件2Intel486以上系列、AMDK6以上系列等PC台式机和便携式电脑都可运行3打开该程序系统，根据提示首先输入初始报数上限和约瑟夫环的人数，然后输入各个人的密码，完成输入后，按回车键即可显示约瑟夫环内各人的出列顺序测试数据和测试结果61进入系统界面x■F:\jy\vc

6.0M瑟夫环\Debug\C pp

1.exe-系统提示输入m的值，即报数上限，为测试所给数据，将m的值设为202输入约瑟夫环的人数输入人数后，若输入人数大于30则提示输入错误，重新输入，这里为检测所给数据，设y\vc

6.0\19黑夫不\Debug\Cpp1exe定人数为7约瑟夫环问题要・货加水

77...n3:0r\SJB37203输入7人的密码约瑟夫环问题青人青人青入青人石青—・人青罡人步青第普人青力第密人音第密青董人密人密、根据题目所给数据，7人的密码挨次为3,1,7,2,4,8,4,输入完毕后回车女入二三【人方密」人彳，人主人■露—入人卜主『入耳网—人±「人、人主人年人人4显小结果nX测试的出列顺序为6,1,4,7,2,3,5符合题目要求，与算得的结果一致，证明程序正常运JVI行，能够解决普通的约瑟夫环问题入小干钩的正整数,7RPR*HIUHR•:r.;rtttw7g.g,lmmg.n1234567grg.ATTTTTXn•567iuri.£m.fli•51234-♦^11i.3-fnJn,AIJnJnJttJnB{rlM^.rJTrTPHTHTHTHTHT6664a%111nlnlTiHTi317248431724840参考文献口丁谭浩强.C程序设计（第二版）.北京清华大学出版社，

1999.12⑵［美］Kenneth A.Reek著，徐波译.C和指针.北京；人民邮电出版社

2022.4［3］严蔚敏，吴伟民.数据结构.北京清华大学出版社，1997［4］［美］HMDeiteL PJDeite著1,薛万鹏等译.C语言程序设计教程.北京机械工业出版社，

2000.07附录源程序清单/*约瑟夫环问题设计与实现*///函数头文件〃自定义数据类型typedef intStatus;typedef intElemType;//定义节点结构体typedef struct LNode{ElemType num;ElemType data;struct LNode*next;}LNode,*LinkList;//各人的编号//各人的密码〃函数原型〃指向下一个节点的指针LinkList Data_InPutLinkListL,int k;void Data_OutPutLinkList L,int k,int b;//主函数void mainLinkList L=NULL;int m,n=30;〃m为报数上限，n为人的个数int i=0;〃常用变量约瑟夫环问题请输入m的值要求m=30Mm重新赋值请输入人数〃确定人的个数，即n得值whilen30||n0〃人数异常处理请输入小于30的正整数饿行//调用数据录入函数Data_InPutL,n;//调用数据输出函数Data_OutPutL,n,m;〃数据输入函数LinkList Data_InPutLinkList L,int kLinkList R,P,Q;L=LinkListmallocsizeofLNode;/创建一个节点R二L;forint i=O;ik;i++〃通过for循环录入数据请输入第％€1个人的密码〃挨次输入每一个人的密码R-〉n um=i+1;〃输入每一个人的编号P=LinkListmallocsizeofLNode;/J］建新节点P-next=NULL;；Q=RR-next=P;〃连接新的节点R=P;freeP;〃释放无用结点Q-next=L;return L;//返回循环链表〃调用数据输出函数void Data_OutPutLinkList L,int k,int b出歹叫页序为LinkList R,P,Q;forint i=O;ik;i++〃通过循环输出数据R=L;while-b//通过while循环找到密码做指向的那个人Q=R;〃加入Q方便寻觅出列的人的上一个节点R=R-next;〃指针后移第％1个出列为//输出所找人的编号b=R-data;〃刷新b值，将所找到人的密码赋值给bQ-next=R-next;〃将出列人的前一个节点和后一个节点连接形成新环L=R-next;fireeR;//释放已出列结点忽略此处..Design andRealization of the JosephringABSTRACTThe Josephproblem is the evolutionproposed byancient Romefamous historianJosephusandcome,so oftenreferredtoastheJosephusproblem.ImprovementofJoseph problemdescription is:No.1,2,...N,n individualsaccording toa clockwdirection arounda circle,eachwith apassword ofM integer,keep thering shoureported afterthe Mring,and soon,we cancalculate thecolumnorder.So Josepcircleifusingcirculatinkedlistcan bevery goodsolutionC.irculatioiiistdata structure,isthelast ofa nodeis apointerto alist ofthe pointsto thefirst accordingtothe codeto findthecorrespondingperson,printthe number,the passwordisassigned tom,release thenode,the formationof Josephring,until alpeople outoftheend.Keywords Josephring;circular linkedlist;the columnorder releasenodes;目录1需求分析

11.1课题内容

11.2要求12概要设计13详细设计

23.1程序中的数据类型

23.2函数运行过程详解34设计和调试分析

64.1调试中遇到的问题

64.2经验和体味75用户使用说明76测试数据和测试结果8参考文献10需求分析1火才课题内容

1.11本演示程序中，人数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,5o要求.

1.21源程序要有适当的注释，使程序容易阅读；2函数功能要划分好结构化程序设计；3可以增加新功能模块；4要提供程序测试方案，程序一定要经得起测试，也要能运行起来，不能运行的程序是没有价值的概要设计2该系统采用C语言开辟，主要方法是选择合适的程序结构，灵便使用三种程序设计基本结构、函数等编写程序本程序包含三个模块，对应关系图为

2.11主程序模块；2构造链表并输入每一个人信息模块；

（3）每一个人依序出列打印出列顺序并释放结点模块;艰实现为了实现上述操作，应以

2.2单向循环链表为存储结构基本操作

2.3Data_InPut操作结果构造链表，初始化每一个人的相关信息Data_OutPut操作结果释放指向出列的人的结点，并重新报数详细设计3程序中定义的数据类型

3.1typedef structLNode{ElemType num;//各人的编号ElemType data;//各人的密码structLNode*next;〃指向下一个节点的指针}LNode,*LinkList;火才程序中定义了一个节点的结构体，每次新分配一个节点内存，即为新增一个人，data为人的密码，num是人的编号每一个函数的过程详解

3.

23.

2.1void mainf函数原型void main函数源程序void main{LinkListL=NULL;int m,n=30;//m为报数上限，n为人的个数int i=0;//常用变量约瑟夫环问题请输入m的值要求m=30//Wm重新赋值请输入人数〃确定人的个数，即n得值whilen30||n0〃人数异常处理请输入小于30的正整数椒行//调用数据录入函数Data_InPutL,n;//调用数据输出函数Data_OutPutL,n,m;函数功能及实现此为主函数，先输入m和n的值，即确定初始上限m和人数n,并对人数进行防出错处理，之后调用函数Data」nPutL,n对n个人编号和输入对应密码，再调用函数Data_OutPutL,n,m按照要求对各个人挨次出列，打印相关信息到屏幕上

3.

2.2LinkList Data_InPutLinkList L,int k;函数原型LinkList Data_InPutLinkList L,int k;函数源程序LinkList Data_InPutLinkList L,int kLinkListR,P,Q;L二LinkListmaUocsizeofLNode;/创建一个节点R=L;forint i=O;ik;i++//通过for循环录入数据R-num=i+l;//挨次输入每一个人的密码借俞入每一个人的编号P=LinkListmallocsizeofLNode;/^1］建新节点P-next=NULL;Q=R;R-next=P;〃连接新的节点R二P;freeP;僻放无用结点Q-next=L;return L;//返回循环链表函数功能及实现先定义结构体指针变量R,P,Q,L,创建一个新节点赋值给指针L,并将L赋值给R,通过for循环再创建n个节点，并录入每一个人对应编号，通过scanf函数录入每一^人的密码，因为创建了一个节点并将新创建的节点连到链表尾端，形成一个单链表最后创建的一个节点是多余的，需要删第页共7页10除，所以通过free函数释放最后一个节点之后将单链表的尾指针指向第一个节点，形成一个单循链表最后通过return函数返回循环链表，继续执行主函数；

3.

2.3void Data_OutPutLinkList LJntk,int b函数原型void Data_OutPutLinkList L,int k,；int b函数原程序void Data_OutPutLinkList L,int k,int b出列顺序为LinkListR,P,Q;forint i=0;ik;i++//通过循环输出数据R=L;while—b//通过while循环找到密码做指向的那个人Q=R;〃加入Q方便寻觅出列的人的上一个节点R=R-next;//指针后移第％:1个出列//输出所找人的编号b=R-data;//刷新b值，将所找到人的密码赋值给bQ-next=R-next;〃将出列人的前一个节点和后一个节点连接形成新环L=R-next;freeR;//释放已出列结点}函数功能及实现该函数首先定义了指针变量R,P,Q,L方便对节点的操作通过for循环以确定所有人都会被出列，在while循环中，b的值最初是给定的报数上限，通过自减操作找到所要出列的那个人，打印其编号，将其密码重新赋值给b,并删除代表该人的节点，并释放该节点，形成一个新的约瑟夫环，。