基于单向循环链表的约瑟夫环设计.doc

《基于单向循环链表的约瑟夫环设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、长春建筑学院基于单向循环链表的约瑟夫环设计DesignofJosephringwaycircularlinkedlistbasedon学院：电气信息学院班级：计算机1201班学号：121500140姓名：卢玉琨指导老师:常大俊摘要约瑟夫环问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫环问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,每人有一个密码K（整数），留作其出圈后应报到K后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是

2、约瑟夫环问题的实际场景。约瑟夫环问题如果采用单循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤是：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。【关键词】约瑟夫环；单循环链表；数据结构；删除结点AbstractJosephusringproblemisevolvedbythequestionthatraisedbyJosephus,thefamoushistoricanofancientRome.SOita

3、lwaysbecalledJosephusProblem.ThedescriptionofimprovingJosephusproblemis:peoplewasnumbered1,2,3,...,nsittedasaclockwisedirectionaroundcircle,eachwithapasswordofK(integer),reservedfortheringshouldbereportedKoutofthering.Thereportadaptedthemethodthatchangedalternatelywiththeclockwi

4、seandanticlockwise,theinitialpasswordcanbedetermined.Solvingthenumberofthelastperson.ThisistherealsenseoftheJosephcentralproblems.Josephcentralproblemscanbewell-solvedifitadaptedthecircularlinkedlist.TheconfigurationofthelistisjustpointedtothefirstteamelementswiththeOmotoSopoint

5、er.P->link=head.Thecoreprocesstosolvingtheproblemis:Firstlyestablishedano-head-nodecircularlinkedlistwhichhavenchainnodes.Thendeterminedthelocationofthefirstperson.Andstrikedoutthechainnodesconstantlyuntilthechaintablewasempty.[Keywords]Josephring;circularlinkedlist;datastructur

6、e;deletingnode目录前言1第一章问题分析21.1设计目的21.2设计内容21.3设计要求21.4设计思想第二章逻辑设计42.1循环链表抽象数据类型定义42.2本程序包含的模块设计4第三章详细设计63.1主函数63.2链表的创建73.3出队处理93.4约瑟夫环说明模块103.5菜单模块10第四章程序调试与测试11第五章结论14参考文献15致谢16附录17前言数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。该课程设计的目的是通过课程设计的综合训练，以培养分析和编程等实际动手能力，是系统掌握数据结构这门

7、课程的主要内容。本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接的链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活。约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。通过该课程设计，能运用所学知识，上机解决一些实际问题，了解并初步掌握设计，实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。第一章问题分析1.1设

8、计目的1、掌握单向循环链表的建立。2、掌握单向循环链表的操作。1.2设计内容编号是1,2,……