约瑟夫问题大数据结构实验报告材料x
时间:2020-11-03 17:01:01 来源:勤学考试网 本文已影响 人
中南民族大学管理学院学生实验报告
中南民族大学管理学院学生实验报告
实用标准文档
实用标准文档
中南民族大学管理学院
学生实验报告
实验项目:
约瑟夫问题
课程名称:
数据结构
年 级:
专 业:
信息管理与信息系统
指导教师:
实验地点:
管理学院综合实验室
完成日期:
小组成员:
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
端正的学习态度及认真刻苦程度等
总 分
指导教师: