基于单向循环链表的约瑟夫(Joseph)环设计

《基于单向循环链表的约瑟夫(Joseph)环设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、长春建筑学院《数据结构》课程设计（论文）基于单向循环链表的约瑟夫(Joseph)环设计Basedonone-waycircularlinkedlistofJoseph(Joseph)ringdesign年级:学号:姓名:专业:指导老师:二零一三年十二月约瑟夫问题是由古罗马著名的史学家Josephus捉出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1,2,…，n的n个人按顺时针方向围坐一，每人冇一个密码Ki（整数），留作其出圈后应报到Ki后出圈。报数方法采用顺吋针报数和逆吋针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题

2、的实际场景，后来老师要求我们对要求中的每人所持冇的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构,就是将一个链表的尾元索指针指向队首元索。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。关键词：约瑟夫环；双向循环链表；数据结构；删除结点AbstractJosephproblemisputforwardbyfamousancientRomanhistorianJosephusproblemhasevolved,

3、sooftenreferredtoasJosephusproblem.ImprovedJosephadescriptionoftheproblemis:Numbersfor1,2,…，nnindividualssittingaroundaclockwisecircle,EachwithapasswordKi(integer),reservedfortheoneswithreportshouldKiafterones.Countoffmethodthenumberoffclockwiseandcounterclockwisecountoffalternates,initialpassw

4、ordcanbearbitrary.Finallytheserialnumberoftherestofthepeople.ThisistheactualsceneofJosephringproblem,thentheteacheraskedustorequesteachheldbythepasswordandthelimitonthenumberoffofthefirsttimetouserandomnumberisgenerated・SoJosephringproblemifthebidirectionalcircularlinkedlistcanbeaverygoodsoluti

5、on.Circularlinkedlistdatastructureisalistofthetailelementpointertothefirstelement.P->link=headthecorestepstosolvetheproblem:first,setupachainofnnodes,theheadlessnodesofcircularlinkedlist,andthendeterminethepositionofthefirstpersontocountoff,andconstantlytodeletechainnodefromthelist,untilthelist

6、isempty.Keywords:Josephring;Thebidirectionalcircularlinkedlist;Datastructure;Deletenodes目录摘要IABSTRACTII第1章绪论-1-1.1设计目的：-1-1-2设计内容-1-1.3设计耍求-1-1.4设计思想-2-第2章系统总体设计・3・2.1基木理论-3-2.2概要设计・3・2・3类LinkList・3・2.4类Joseph2.5类界常处理-4-第3章详细设计-5-3.1创建结点Node-5-3.2创建双向循环链表-6-3.3从链表屮删除结点-7-第四章流程分析图-8-4.1函数生成过程-8-

7、4.2主要功能模块设计-10-4.3函数主耍调用关系图-11-第5章系统测试-12-5.1调试分析-12-5.2实验结果-12-结论-14-致谢-15-参考文献-15-第1章绪论引言：木次选做的课程设计是改进约瑟夫（Joseph）环问题。约瑟夫环问题是-•个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表，同样也能方便地解决。1.1设计目的：1、掌握单向循环链表的建立。