长春建筑学院
基于单向循环链表的约瑟夫环设计
Design of Joseph ring way circular linked list based on
学 院： 电气信息学院 班 级： 计算机1201班 学 号： 121500140 姓 名： 卢玉琨
指导老师: 常大俊
摘 要
约瑟夫环问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫环问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码K（整数），留作其出圈后应报到K后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景。约瑟夫环问题如果采用单循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head解决问题的核心步骤是：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。
【关键词】约瑟夫环；单循环链表；数据结构；删除结点
Abstract
Josephus ring problem is evolved by the question that raised by Josephus,the famous historican of ancient Rome.SO it always be called Josephus Problem.The description of improving Josephus problem is :people was numbered 1,2,3,...,n sitted as a clockwise direction around circle,each with a password of K(integer),reserved for the ring should be reported K out of the ring .The report adapted the method that changed alternately with the clockwise and anticlockwise, the initial password can be determined.Solving the number of the last person.This is the real sense of the Joseph central problems. Joseph central problems can be well-solved if it adapted the circular linked list .The configuration of the list is just pointed to the first team elements with the Omoto So pointer. P->link=head.The core process to solving the problem is:Firstly established a no-head-node circular linked list which have n chain nodes.Then determined the location of the first person.And striked out the chain nodes constantly until the chain table was empty.
[Keywords] Joseph ring; circular linked list; data structure; deleting node
目 录
前言 ......................................................................................................................................... 5 第一章 问题分析............................................................................................................ 6
1.1 设计目的 ...................................................................................................................... 2 1.2 设计内容 ...................................................................................................................... 2 1.3 设计要求 ...................................................................................................................... 2 1.4 设计思想 ........................................................................................................................
第二章 逻辑设计 ......................................................................................................... 9
2.1 循环链表抽象数据类型定义 .................................................................................... 9 2.2本程序包含的模块设计 .............................................................................................. 9
第三章 详细设计 ....................................................................................................... 11
3.1 主函数 ........................................................................................................................... 11 3.2 链表的创建 .................................................................................................................. 12 3.3 出队处理 ........................................................................................................................ 9 3.4 约瑟夫环说明模块 .................................................................................................... 10 3.5菜单模块 ....................................................................................................................... 10
第四章 程序调试与测试.......................................................................................... 16 第五章 结论 .................................................................................................................... 19 参考文献 ............................................................................................................................ 20 致谢 ....................................................................................................................................... 21 附录 ....................................................................................................................................... 21
前 言
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。该课程设计的目的是通过课程设计的综合训练，以培养分析和编程等实际动手能力，是系统掌握数据结构这门课程的主要内容。
本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接的链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活。约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。
通过该课程设计，能运用所学知识，上机解决一些实际问题，了解并初步掌握设计，实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。