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

《约瑟夫问题数据结构实验报告23938.pdf》由会员分享，可在线阅读，更多相关《约瑟夫问题数据结构实验报告23938.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、中南民族大学管理学院 学生实验报告 实验工程:约瑟夫问题 课程名称：数据构造 年 级：专 业：信息管理与信息系统 指导教师：实验地点：管理学院综合实验室 完成日期：小组成员：2012 学年至 2013 学年度第 1 学期 一、实验目的 1掌握线性表表示和实现；2学会定义抽象数据类型；3学会分析问题，设计适当的解决方案；二、实验容-.z【问题描述】：编号为 1,2,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码正整数。一开场任选一个正整数作为报数上限值 m，从第一个人开场按顺时针方向自 1 开场顺序报数，报到 m 时停顿报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向

2、上的下一个人开场重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【根本要求】：利用单向循环链表存储构造模拟此过程，按照出列的顺序印出各人的编号。【测试数据】：m 的初值为 20；密码：3，1，7，2，4，8，4正确的结果应为 6，1，4，7，2，3，5。三、实验步骤（一）需求分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到 m时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。程序存储构造 利用单循环链表存储构造存储约瑟夫数据即 n 个人的编码等，模拟约瑟夫的显示过程，按照

3、出列的顺序显示个人的标号。编号为 1,2,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码正整数。一开场任选一个正整数作为报数上限值 m，从第一个人开场按顺时针方向自 1 开场顺序报数，报到 m 时停顿报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开场重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。根本要利用单向循环链表存储构造模拟此过程，按照出列的顺序印出各人的编号。程序执行的命令1构造单向循环链表。2按照出列的顺序引出各个人的标号。测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4正确的结果应为 6，1，4

4、，7，2，3，5 1、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保存了 front 头结点。在每参加一个节点时，都会直接连接在 front 后面，从而保证一开场就赋值的 rear 尾节点不用修改。伪代码阐释如下：1)、在堆中建立新节点：Node*s=new Node;2)、将 ai写入到新节点的数据域：s-data=ai;3)、修改新节点的指针域：s-ne*t=front-ne*t;4)、修改头结点的指针域，将新节点参加到链表中：front-ne*t=s;时间复杂度为：1；(2)、删除：首先通过 p 指针查找到所要删除的节点的前一个节点，继而通-.z 过 q=p-ne*t 简

5、单地删除掉。假设所要查找的为第 i 个元素。伪代码阐释如下：1、在堆中建立新节点 p,通过循环查找到 i-1，将此节点的地址赋给 p。2、设q指向第i个节点：假设p=rear，则q=front-ne*t;否则，q=p-ne*t;3)、摘链，即将 q 从链表中摘除：假设 q=rear，则 p-ne*t=front-ne*t；否则，则 p-ne*t=q-ne*t.4)、保存 q 元素的数据：*=q-data；5、释放 q 元素：delete q；时间复杂度为：1；3、约瑟夫问题的根本思想：在这个循环查找问题中，通过循环链表实现了循环查找到节点。一个关键局部就是删除节点后进展链表的，从而保证链表的循

6、环性。在查找方面上，我利用了一个 for 循环来计数所查找过的节点。其中查找的时间复杂度也为 1；（二）概要设计 测试主函数流程：流程图如下：否 是 跳出函数 否 是 否 三详细设计#include using namespace std;const int d=50000;struct Node 开场 输入 m 和 n 创立 Clinklist 类的对象，首先建立循环链表，之后调用 Josef 函数。判断所要删除节点是否为最后一个 删除该节点，并从该节点的直接后继结点重新计数。此时要判断 P和q是否存在恰好为rear指针的情况 输出 m 的位置 完毕 循环查找到所要删除节点的前一个节点。判断

7、链表是否为空 判断 m、n 是否符合要求-.z int data;struct Node*ne*t;/声明 ne*t 指针;class Clinklist public:Clinklist(int a,int n);void Josef(int m,int n);private:Node*rear;/声明 rear 和 front 指针 Node*front;int n;Clinklist:Clinklist(int a,int n)rear=new Node;front=new Node;front-ne*t=rear;/构造空单链表 rear-ne*t=front;rear-data=an

8、-1;for(int i=n-2;i=0;i-)Node*s=new Node;/循环插入元素来建立链表 s-data=ai;s-ne*t=front-ne*t;front-ne*t=s;void Clinklist:Josef(int m,int n)Node*p=front;int j=0;while(front-ne*t!=front)int i=0;while(i!=m-1)/实现第 m-1 个节点的查找 -.z if(p=rear)p=front-ne*t;else p=p-ne*t;i+;Node*q=p-ne*t;if(p=rear)/排除 p 恰好为 rear 节点的情况 q=

9、front-ne*t;front-ne*t=q-ne*t;p-ne*t=front-ne*t;else if(q=rear)/排除 q 恰好为 rear 节点的情况 p-ne*t=front-ne*t;/完成摘链 else p-ne*t=q-ne*t;/完成摘链 int*=q-data;/保存 q 点数据 delete q;/完成 q 节点的删除 j+;if(j=n)cout所出的最后一个人的编号是:*endl;int main()int m,n;cout请输入人数(1=n=50000):n;int memberd;for(int i=0;in;i+)/建立数组 memberi=i+1;cou

10、t=1):m;if(n=0|m=0)throw所输入的数不符合要求!;Clinklist pro(member,n);/构造 Clinklist 类的对象-.z pro.Josef(m,n);return 0;四调试分析 调试时出现的问题及解决的方法 1、早期程序只写了约瑟夫的实现局部，没有对输入的数据进展筛选，测试时会出错。2、在先前的程序循环过程中没有进展优化，导致循环次数过多，浪费了一定的时间。3、为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是一个循环。在约瑟夫的实现在程序中，为 for 循环，时间复杂度为 o(m%n-1)当 n=1 时，复杂度为 o(1)

11、。4、在调试时一开场用的是模板类，调试时就总会遇到无法解析的外部指令之类的问题。由于无法解决，对模板类的理解不好，所以就去掉了模板类的应用。Templete还需要再次加强。5、rear 指针找不到声明，这个的解决方案是参照别的线性表例子，加上了如下 struct 类型的语句，才得以运行正常：struct Node int data;struct Node*ne*t;6、这个是最严重的逻辑错误，就是编译的时候没有任何问题，在程序运行时会出现乱码或者出错的情况。这个完全靠一点点的逻辑判断了，又用了最笨的方法：在纸上画一个循环链表才搞定。五用户手册 1、我们这个程序的运行环境为 VC+6.0 操作系

12、统，2、进入演示程序后即显示文本方式的用户界面：六测试结果 七心得体会 数据构造的课程设计，相对来说还是一个较大的工程，我们小组各个成员相互合作，虽然里面的容不是很完备，但总体上还是一个比拟能要表达数据构造的知识点能力的程序了，这个设计让我们在课堂中学到的理论知识，解决-.z 相应的实际问题，深入理解和灵活掌握所学的容，使我们在实践的过程中收获匪浅，认真去做，踏踏实实，静静思考，慢慢进步，会有收获的。八团队介绍 小组成员根本情况介绍 组长：雷灵花 11056024 组员：涂艺 11056022 伍雨豪 11056029 小组成员分工情况 组长 雷灵花，选择的实验设计为第一模块的约瑟夫问题，完成

13、了第一个实验的程序设计和最终实验报告的总结。组员 涂艺，完成了第二个实验的程序设计和实验报告的撰写工作，选择的程序设计为第一模块的城市链表实验。组员 伍宇豪，在进展实验当中查阅了大量的相关资料，给出了实验的程序设计和源代码上的文件资料和指导。小组成员任务完成情况 程序一和程序二的调试工作完成情况良好，各个结果都能运行，组长实验一的程序和实验报告完成符合教师要求格式，组员涂艺程序和实验报告完成情况根本一致，组员伍宇豪也提供了很多的资料和技术支持。总体来说，团队意识很好，一起共同完成学习任务。九附录：源程序清单 源程序文件名清单：#include using namespace std;const

14、 int d=50000;struct Node int data;struct Node*ne*t;/声明ne*t指针;class Clinklist public:Clinklist(int a,int n);void Josef(int m,int n);private:Node*rear;/声明rear和front指针-.z Node*front;int n;Clinklist:Clinklist(int a,int n)rear=new Node;front=new Node;front-ne*t=rear;/构造空单链表 rear-ne*t=front;rear-data=an-1

15、;for(int i=n-2;i=0;i-)Node*s=new Node;/循环插入元素来建立链表 s-data=ai;s-ne*t=front-ne*t;front-ne*t=s;void Clinklist:Josef(int m,int n)Node*p=front;int j=0;while(front-ne*t!=front)int i=0;while(i!=m-1)/实现第m-1个节点的查找 if(p=rear)p=front-ne*t;else p=p-ne*t;i+;Node*q=p-ne*t;if(p=rear)/排除p恰好为rear节点的情况 q=front-ne*t;f

16、ront-ne*t=q-ne*t;p-ne*t=front-ne*t;else if(q=rear)/排除q恰好为rear节点的情况 p-ne*t=front-ne*t;/完成摘链 else p-ne*t=q-ne*t;/完成摘链 int*=q-data;/保存q点数据 delete q;/完成q节点的删除 j+;if(j=n)cout所出的最后一个人的编号是:*endl;-.z int main()int m,n;cout请输入人数(1=n=50000):n;int memberd;for(int i=0;in;i+)/建立数组 memberi=i+1;cout=1):m;if(n=0|m=

17、0)throw所输入的数不符合要求!;Clinklist pro(member,n);/构造Clinklist类的对象 pro.Josef(m,n);return 0;指导教师批阅：指标 最高分 评分要素 评分 设计技术水平 30 程序的功能设计、数据构造设计及整体构造设计合理；程序运行情况良好，算法说明清晰，理论分析与计算正确，实验数据无误 实际动手能力 20 熟练使用开发工具，能够迅速准确的进展调试、纠错和运行 编程风格 10 良好的编程风格缩进，注释，变量名、函数名见名知意等，程序运行界面友好 报告规化 10 提交的电子文档及打印文档的书写、存放符合规化要求 答复下列问题 20 能简明扼要地阐述设计的主要容，能准确流利地答复各种问题 学习态度 10 端正的学习态度及认真刻苦程度等 总分 -.z 指导教师：年 月 日