《约瑟夫问题数据结构实验报告要点.pdf》由会员分享，可在线阅读，更多相关《约瑟夫问题数据结构实验报告要点.pdf（13页珍藏版）》请在三一文库上搜索。
1、中南民族大学管理学院 学生实验报告 实验项目 : 约瑟夫问题 课程名称：数据结构 年级： 专业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员： 2012 学年至 2013 学年度第1 学期 中南民族大学管理学院学生实验报告 一、实验目的 （1）掌握线性表表示和实现； （2）学会定义抽象数据类型； （3）学会分析问题，设计适当的解决方案； 二、实验内容 【问题描述】：编号为1,2, ,n的 n 个人按顺时针方向围坐一圈，每人 持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从 第一个人开始按顺时针方向自1 开始顺序报数， 报到m 时停止报数。
2、报 m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开 始重新从1 报数，如此下去，直至所有人全部出列为止。试设计一个程序 求出出列顺序。 【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序 印出各人的编号。 【测试数据】：m 的初值为20；密码： 3，1，7，2，4，8，4（正确的结 果应为6，1，4， 7，2，3， 5）。 三、实验步骤 （一） 需求分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点 的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构
3、利用单循环链表存储结构存储约瑟夫数据（即 n 个人的编 码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为 1,2, ,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码 （正整数） 。 一开始任选一个正整数作为报数上限值 m， 从第一个人开始按顺时针方向自 1 开始顺序报数， 报到 m 时停止报数。 报 m 的人出列， 将他的密码作为新 的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去， 直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用 单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环
4、链表。 （2）按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20 ；密码： 3， 1，7，2，4，8，4（正确的结果 应为 6 ，1， 4，7，2，3，5） （1） 、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我 保留了 front头结点。在每加入一个节点时，都会直接连接在front后面， 从而保证一开始就赋值的rear 尾节点不用修改。 伪代码阐释如下： 中南民族大学管理学院学生实验报告 1) 、在堆中建立新节点：Node *s=new Node; 2) 、将 ai写入到新节点的数据域：s-data=ai; 3) 、修改新节点的指针域：s-next=front-n
5、ext; 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
6、) 、保存 q 元素的数据：x=q-data ； 5） 、释放 q 元素： delete q； 时间复杂度为：1； （3） 、约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实现 了循环查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保 证链表的循环性。在查找方面上， 我利用了一个for 循环来计数所查找过的 节点。其中查找的时间复杂度也为1； （二）概要设计 测试主函数流程： 流程图如下： 否 是 开始 输入 m和 n 创建 Clinklist类的对象， 首先建立循环链表，之后 调用 Josef 函数。 判断 m、 n 是 否符合要求 中南民族大学管理学院学生实验报告 跳出
7、函数 否 是 否 （三）详细设计 #include using namespace std; const int d=50000; struct Node int data; 判断所要删除节点 是否为最后一个 删除该节点，并从该节点的直接 后继结点重新计数。此时要判断 P和 q 是否存在恰好为rear 指针 的情况 输出 m的位置 结束 循环查找到所要删除节点 的前一个节点。 判 断 链 表 是否为空 中南民族大学管理学院学生实验报告 struct Node*next; /声明 next 指针 ; class Clinklist public: Clinklist(int a,int n);
8、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-next=rear;/ 构造空单链表 rear-next=front; rear-data=an-1; for(int i=n-2;i=0;i-) Node*s=new Node; /循环插入元素来建立链表 s-data=ai; s-next=front-next; front-ne
9、xt=s; void Clinklist:Josef(int m,int n) Node* p=front; int j=0; while(front-next!=front) int i=0; 中南民族大学管理学院学生实验报告 while(i!=m-1) /实现第 m-1 个节点的查找 if(p=rear) p=front-next; else p=p-next; i+; Node* q=p-next; if(p=rear) /排除 p恰好为 rear 节点的情况 q=front-next; front-next=q-next; p-next=front-next; else if(q=re
10、ar) /排除 q恰好为 rear 节点的情况 p-next=front-next; /完成摘链 else p-next=q-next; /完成摘链 int x=q-data; /保留 q 点数据 delete q; /完成 q 节点的删除 j+; if(j=n)coutn; int memberd; for(int i=0;i=1):“m; if(n 还需要再次加强。 5、 “ rear 指针找不到声明” ，这个的解决方案是参照别的线性表例子，加上 了如下 struct类型的语句，才得以运行正常： struct Node int data; 中南民族大学管理学院学生实验报告 struct N
11、ode*next; ; 6、这个是最严重的逻辑错误，就是编译的时候没有任何问题，在程序运行 时会出现乱码或者出错的情况。这个完全靠一点点的逻辑判断了，又用了最 笨的方法：在纸上画一个循环链表才搞定。 （五）用户手册 1、我们这个程序的运行环境为 VC+6.0 操作系统， 2、进入演示程序后即显示文本方式的用户界面： （六）测试结果 中南民族大学管理学院学生实验报告 （七）心得体会 数据结构的课程设计，相对来说还是一个较大的工程，我们小组各个成 员相互合作， 虽然里面的内容不是很完备，但总体上还是一个比较能要体现 数据结构的知识点能力的程序了，这个设计让我们在课堂中学到的理论知 识，解决相应的实
12、际问题，深入理解和灵活掌握所学的内容，使我们在实践 的过程中收获匪浅，认真去做，踏踏实实，静静思考，慢慢进步，会有收获 的。 （八）团队介绍 小组成员基本情况介绍组长：雷灵花11056024 组员：涂艺11056022 伍雨豪 11056029 中南民族大学管理学院学生实验报告 小组成员分工情况 组长雷灵花，选择的实验设计为第一模块的约瑟夫问题，完成了第一个实 验的程序设计和最终实验报告的总结。 组员涂艺，完成了第二个实验的程序设计和实验报告的撰写工作，选择的 程序设计为第一模块的城市链表实验。 组员伍宇豪，在进行实验当中查阅了大量的相关资料，给出了实验的程序 设计和源代码上的文件资料和指导。
13、 小组成员任务完成情况 程序一和程序二的调试工作完成情况良好，各个结果都能运行，组长实验一 的程序和实验报告完成符合老师要求格式，组员涂艺程序和实验报告完成情 况基本一致， 组员伍宇豪也提供了很多的资料和技术支持。总体来说， 团队 意识很好，一起共同完成学习任务。 （九）附录：源程序清单 源程序文件名清单： #include using namespace std; const int d=50000; struct Node int data; struct Node*next; /声明 next指针 ; class Clinklist public: Clinklist(int a,int
14、 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-next=rear;/ 构造空单链表 rear-next=front; rear-data=an-1; for(int i=n-2;i=0;i-) Node*s=new Node; /循环插入元素来建立链表 s-data=ai; s-next=f
15、ront-next; front-next=s; void Clinklist:Josef(int m,int n) Node* p=front; int j=0; while(front-next!=front) int i=0; while(i!=m-1) /实现第 m-1个节点的查找 if(p=rear) p=front-next; else p=p-next; i+; Node* q=p-next; if(p=rear) /排除 p恰好为 rear节点的情况 q=front-next; front-next=q-next; p-next=front-next; else if(q=re
16、ar) /排除 q恰好为 rear节点的情况 p-next=front-next; /完成摘链 else p-next=q-next; /完成摘链 int x=q-data; /保留 q点数据 delete q; /完成 q节点的删除 j+; if(j=n)coutn; 中南民族大学管理学院学生实验报告 int memberd; for(int i=0;i=1):“m; if(n=0|m=0)throw“ 所输入的数不符合要求!“; Clinklist pro(member,n); /构造 Clinklist 类的对象 pro.Josef(m,n); return 0; 指导教师批阅： 指标最高分评分要素评分 设计技术水平 30 程序的功能设计、数据结构设计及整体结构 设计合理；程序运行情况良好，算法说明清 晰，理论分析与计算正确，实验数据无误 实际动手能力 20 熟练使用开发工具，能够迅速准确的进行调 试、纠错和运行 中南民族大学管理学院学生实验报告 编程风格 10 良好的编程风格（缩进，注释，变量名、函 数名见名知意等，程序运行界面友好） 报告规范化 10 提交的电子文档及打印文档的书写、存放符 合规范化要求 回答问题 20 能简明扼要地阐述设计的主要内容，能准确 流利地回答各种问题 学习态度 10 端正的学习态度及认真刻苦程度等 总分 指导教师： 年月日