中南民族大学管理学院
学生实验报告
实验项目: 约瑟夫问题 课程名称： 数据结构 年 级：
专 业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员：
2012 学年至2013 学年度第 1 学期
中南民族大学管理学院学生实验报告
一、实验目的
（1）掌握线性表表示和实现； （2）学会定义抽象数据类型；
（3）学会分析问题，设计适当的解决方案；
二、实验内容
【问题描述】：编号为 1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
【测试数据】：m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5）。
三、实验步骤
（一） 需求分析
对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构 利用单循环链表存储结构存储约瑟夫数据（即n个人的编码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为 1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环链表。
（2）按照出列的顺序引出各个人的标号。
测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5） （1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下：
中南民族大学管理学院学生实验报告
1)、在堆中建立新节点：Node
4)、修改头结点的指针域，将新节点加入到链表中：front->next=s; 时间复杂度为：1；
(2)、删除：首先通过p指针查找到所要删除的节点的前一个节点，继而通过q=p->next简单地删除掉。假设所要查找的为第i个元素。 伪代码阐释如下： 1）、在堆中建立新节点p,通过循环查找到i-1，将此节点的地址赋给p。 2）、设q指向第i个节点：若p=rear，则q=front->next; 否则，q=p->next; 3)、摘链，即将q从链表中摘除：若q=rear，则p->next=front->next；否则，则p-next=q->next.
4)、保存q元素的数据：x=q->data； 5）、释放q元素：delete q； 时间复杂度为：1； （3）、约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实现了循环查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保证链表的循环性。在查找方面上，我利用了一个for循环来计数所查找过的节点。其中查找的时间复杂度也为1；
（二）概要设计
测试主函数流程： 流程图如下： 开始 输入m和n
m n 是 否 判断、 否符合要求
是 创建Clinklist类的对象， 首先建立循环链表，之后 调用Josef函数。