约瑟夫问题数据结构实验报告.doc

中南民族大学管理学院
学生试验汇报
试验项目: 约瑟夫问题
课程名称：　　数据结构　　
年　 级：　　　
专　 业：信息管理和信息系统
指导老师：　　　　　
试验地点：管理学院综合试验室
完成日期：　
小组组员：　　
　　　
　　　　
年至 年度第 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<T> *s=new Node<T>;
2)、将a[i]写入到新节点数据域：s->data=a[i];
3)、修改新节点指针域：s->next=front->next;
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函数。
判定链表是否为空
跳出函数
否
循环查找到所要删除节点前一个节点。