中南民族大学管理学院学生实验报告
中南民族大学管理学院学生实验报告
实用标准文档
实用标准文档
中南民族大学管理学院
学生实验报告
实验项目:
约瑟夫问题
课程名称：
数据结构
年 级:
专 业：
信息管理与信息系统
指导教师:
实验地点：
管理学院综合实验室
完成日期:
小组成员:
2012 学年至2013 学年度第 丄学期
文案大全
?、实验目的
（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）构造单向循环链表。
（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=fro nt-> next;
4） 、修改头结点的指针域，将新节点加入到链表中： fron t-> next=s;
时间复杂度为：1；
（2）、删除：首先通过 p指针查找到所要删除的节点的前一个节点，继而通
过q=p->next 简单地删除掉。假设所要查找的为第 i个元素。
伪代码阐释如下：
1 ）、在堆中建立新节点 p,通过循环查找到i-1，将此节点的地址赋给 p。
2 ）、设 q 指向第 i 个节点：若 p=rear ，贝U q=front->next; 否^U, q=p->next;
3） 、摘链，即将 q从链表中摘除：若 q=rear，贝U p->next=front->next ;
否则，贝U p-next=q->next.
4） 、保存q元素的数据：x=q->data ;
5） 、释放 q 元素：delete q ;
时间复杂度为：1 ;
（3 ）、约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实
现了循环查找到节点。一个关键部分就是删除节点后进行链表的链接， 从而
保证链表的循环性。在查找方面上，我利用了一个for循环来计数所查找过 的节点。其中查找的时间复杂度也为 1 ;
（二）概要设计
开始测试主函数流程：
开始
流程图如下：
输入m和n
创建Clinklist 类的对象,
首先建立循环链表，之后 调用Josef函数。
删除该节点，并从该节点的直接 后继结点重新计数。此时要判断 P和q是否存在恰好为rear指针 的情况
详细设计
#in clude<iostream>
using n amespace std;
con st int d=50000;
struct Node
{
int data;
struct Node*next; // 声明 next 指针
}；
class Cli nklist
{
public:
Clinklist(int a[],int n);
void Josef( int m,i nt n);
private:
Node *rear; // 声明 rear 和 front 指针
Node *front;
int n;
};
Clinklist::Clinklist(int a[],int n)
{
rear=new Node;
front=new Node;
front->n ext=rear;〃 构造空单链表
rear->n ext=fr ont;
rear->data=a[ n-1];
for(i nt i=n-2;i>=0;i--)
{
Node*s=new Node; //循环插入元素来建立链表
s_>data=a[i];
s->n ext=fr ont->n ext;
front->n ext=s;
}
}
void Cli nklist::Josef( int m,i nt n)
{
Node* p=front;
int j=0;
while(fro nt-> next!=fro nt)
{
int i=0;
while(i!=m-1) //实现第 m-1个节点的查找
{
if(p==rear)
p=front->n ext;
else p=p->n ext;
i++；
}
Node* q=p->n ext;
if(p==rear) //排除p恰好为rear节点的情况
{q=fro nt_>n ext;
front->n ext=q->n ext;
p->n ext=fr ont->n ext;
}
else
if(q==rear)II排除
if(q==rear)
II排除q恰好为rear节点的情况
p->next=front->next; // 完成摘链
else
p->next=q->next; // 完成摘链
}
int x=q->data; // 保留 q 点数据
delete q; //完成q节点的删除
j++；
if( j==n)cout<<" 所出的最后一个人的编号是 ："<<x<<endl;
}
}
int mai n()
{
int m,n;
cout<<"请输入人数(1<=n<=50000):"<<endl;
cin?n;
//建立数组
//建立数组
for(i nt i=0;i <n ;i++)
member[i]=i+1;
}
cout<<"请输入要按那个数进行计算 (m>=1):"<<e ndl;
cin?m;
if(n <=0||m<=0)throw" 所输入的数不符合要求！"；
Clinklist pro(member,n); // 构造 Clinklist 类的对象
pro.Josef( m,n);
return 0;
}
调试分析
调试时出现的问题及解决的方法
1、 早期程序只写了约瑟夫的实现部分，没有对输入的数据进行筛选，测试 时会出错。
2、 在先前的程序循环过程中没有进行优化，导致循环次数过多，浪费了一 定的时间。
3、 为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数
字，但是做的是一个循环。在约瑟夫的实现在程序中，为 for循环，时间复
杂度为o(m%n-1)当n=1时，复杂度为 0(1)。
4、 在调试时一开始用的是模板类，调试时就总会遇到“无法解析的外部指 令”之类的问题。由于无法解决，对模板类的理解不好，所以就去掉了模板 类的应用。Templete<T> 还需要再次加强。
5、 “ rear指针找不到声明”，这个的解决方案是参照别的线性表例子，加上 了如下struct类型的语句，才得以运行正常：
struct Node
{
int data;
struct Node* next;
}；
6、 这个是最严重的逻辑错误，就是编译的时候没有任何问题，在程序运行
时会出现乱码或者出错的情况。 这个完全靠一点点的逻辑判断了， 又用了最
笨的方法：在纸上画一个循环链表才搞定。
（五）用户手册
1、我们这个程序的运行环境为 VC++6.0操作系统， 2、进入演示程序后即显示文本方式的用户界面:
（六）测试结果
请输入各个人的信息t整数”
你输入旳数is的顺序为三
1 ==> 2 ==> 3 ==> 4 ==〉百 林打賢从富n个人融 请输入幵始号：2
请输入相令陋出列人之间的间淸：3
程序运行后-出列人的顺序为2
3 ==> 5 —> 2 ==> 1 —> 4
Ppets an^p kev to continue_
请輸人嗟桌上人的总數：刘 1
请输入各个人的信息理如
1 2 3 4 5 6 7 8 9 1B 11 12 13 14 15 16 17 18 19 20
你输入的数据的顺序为二
1 ==> 2 ==〉 3 ==> 叫==> 5 ==> 6 ==> 7 ==> 8 ==> 9 ==> ie ==> 11 ==> 12 ==> 13 ” \=> 14 ==> 15 ==、1￡ ==> 1? 18 ==> 15 一一>28
你打算从第几个人开妳请输入开始号；?
请输入桎邻两岀列人之间的间隔；8
程序运行后，岀列人的顺序为；
16 呻—> 12 1 —> LS 20 丄丄—> 3 —> 15 8 —> 5 1? 1
B —> 2 —> 7 --> 14 —> 13 —> 6 —> 17 —> 9
Press ein_y kep to continue
（七）心得体会
数据结构的课程设计， 相对来说还是一个较大的工程， 我们小组各个成
员相互合作，虽然里面的内容不是很完备，但总体上还是一个比较能要体现 数据结构的知识点能力的程序了，这个设计让我们在课堂中学到的理论知 识，解决相应的实际问题， 深入理解和灵活掌握所学的内容， 使我们在实践
的过程中收获匪浅，认真去做，踏踏实实，静静思考，慢慢进步，会有收获 的。
（八）团队介绍
小组成员基本情况介绍 组长：雷灵组员：涂伍雨小组成员分工情况
组长 雷灵花，选择的实验设计为第一模块的约瑟夫问题，完成了第一个实
验的程序设计和最终实验报告的总结。
组员 涂艺，完成了第二个实验的程序设计和实验报告的撰写工作，选择的
程序设计为第一模块的城市链表实验。
组员 伍宇豪，在进行实验当中查阅了大量的相关资料，给出了实验的程序
设计和源代码上的文件资料和指导。
小组成员任务完成情况
程序一和程序二的调试工作完成情况良好， 各个结果都能运行，组长实验一
的程序和实验报告完成符合老师要求格式， 组员涂艺程序和实验报告完成情
况基本一致，组员伍宇豪也提供了很多的资料和技术支持。 总体来说，团队
意识很好，一起共同完成学习任务。
附录：源程序清单
源程序文件名清单：
#in clude<iostream>
using n amespace std;
con st int d=50000;
struct Node
{
int data;
struct Node*next; // 声明 next 指针
}；
class Cli nklist
{
public:
Clinklist(int a[],int n);
void Josef( int m,i nt n);
private:
Node *rear; // 声明 rear 和 front 指针
Node *front; int n;
};
Clinklist::Clinklist(int a[],int n) {
rear=new Node;
front=new Node;
front->n ext=rear;// 构造空单链表 rear->n ext=fr ont;
rear->data=a[ n-1];
for(i nt i=n-2;i>=0;i--)
{
//循环插入元素来建立链表
//循环插入元素来建立链表
}void Cli nklist::Josef( int m,i nt n) {Node* p=front; int j=0;while(fro nt-> next!=fro nt) {int i=0; while(i!=m-1) {if(p==rear) p=front->n ext; else p=p->n ext; i++;
}
void Cli nklist::Josef( int m,i nt n) {
Node* p=front; int j=0;
while(fro nt-> next!=fro nt) {
int i=0; while(i!=m-1) {
if(p==rear) p=front->n ext; else p=p->n ext; i++;
}
Node* q=p->n ext; if(p==rear) {q=fro nt_>n ext; front->n ext=q->n ext; p->n ext=fr ont->n ext; }
else
{
//实现第m-1个节点的查找
//排除p恰好为rear节点的情况
if(q==rear)
p->n ext=fr ont->n ext; else
p_>n ext=q _>n ext;
//排除q恰好为rear节点的情况
//完成摘链
//完成摘链
//保留
//保留q点数据
//完成q节点的删除
所出的最后一个人的编号是 :"<<x<<e ndl;
}
int x=q->data; delete q;
j++；
if(j==n )cout<<"
}
}
int mai n()
{
int m,n;
cout<<"请输入人数(1<=n<=50000):"<<endl;
cin?n;
int member[d];
for(int i=0;i<n;i++) // 建立数组
{ member[i]=i+1;
}
cout<<"请输入要按那个数进行计算 (m>=1):"<<e ndl;
cin?m;
if(n <=0||m<=0)throw" 所输入的数不符合要求！"；
Clinklist pro(member,n); // 构造 Clinklist 类的对象
pro.Josef( m,n);
return 0;
}
指导教师批阅:
指标
最高分
评分要素
评分
设计技术水平
30
程序的功能设计、数据结构设计及整体结构 设计合理；程序运行情况良好，算法说明清
晰，理论分析与计算正确，实验数据无误
实际动手能力
20
熟练使用开发工具，能够迅速准确的进行调 试、纠错和运行
编程风格
10
良好的编程风格（缩进，注释，变量名、函
数名见名知意等，程序运行界面友好）
报告规范化
10
提交的电子文档及打印文档的书写、存放符
合规范化要求
回答问题
20
能简明扼要地阐述设计的主要内容，能准确
流利地回答各种问题
学习态度
10
端正的学习态度及认真刻苦程度等
总 分
指导教师: