1、 数据结构课程设计数据结构课程设计档案档案 题题 目目： 约瑟夫环问题 学学 院院： 信息学院 专专 业业： 网络工程 姓姓 名名： 学学 号号： 班班 级级 指导教师指导教师： 职职 称称： 讲 师 完成日期完成日期： 2012 年 12 月 摘 要 约瑟夫环问题是由古罗马著名的史学家 Josephus 提出的问题演变而来， 所以通常称为 Josephus 问题。 改进约瑟夫环问题的描述是： 编号为 1， 2， ， n 的 n 个人按顺时针方向围坐一圈, 每人有一个密码 K（整数） ，留作其出圈 后应报到 K 后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始 密码可任意确定。求最后剩
2、下的人的编号。这个就是约瑟夫环问题的实际场 景。约瑟夫环问题如果采用单循环链表则能很好的解决。循环链表的数据结 构，就是将一个链表的尾元素指针指向队首元素。 p-link=head 解决问题 的核心步骤是：先建立一个具有 n 个链结点，无头结点的循环链表，然后确 定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 【关键词】约瑟夫环；单循环链表；数据结构；删除结点 Abstract Josephus ring problem is evolved by the question that raised by Josephus,the famous historican of an
3、cient 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 metho
4、d 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
5、 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 con
6、stantly until the chain table was empty. Keywords Joseph ring; circular linked list; data structure; deleting node 目目 录录 前言前言.1 第一章第一章 问题分析问题分析.2 第二章第二章 逻辑设计逻辑设计 4 2.1 循环链表抽象数据类型定义 4 2.2 本程序包含的模块设计 .4 第三章第三章 详细设计详细设计 6 3.1 主函数 6 3.2 链表的创建 7 3.3 出队处理 9 3.4 约瑟夫环说明模块 10 3.5 菜单模块 . 10 第四章第四章 程序调试与测试程序调试与测试. 11 第五章第五章 结论结论 14 参考文献参考文献 . 15 致谢致谢. 16 附录附录. 16 1 前前 言言 数据结构是一门研究非数
