约瑟夫问题大数据结构实验报告材料

1、中南民族大学管理学院学生实验报告实验项目:约瑟夫问题课程名称：数据结构年 级:专业：信息管理与信息系统指导教师:实验地点：管理学院综合实验室完成日期:小组成员:2012 学年至2013 学年度第 丄学期文案大全、实验目的（1）掌握线性表表示和实现；（2）学会定义抽象数据类型；（3）学会分析问题，设计适当的解决方案;二、实验内容【问题描述】：编号为 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 ）。三、实验步骤（一）需求分析对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点 的联系。由于是循环计数，所以才采用循环列表这个线性表方式。程序存储结构利用单循环链表存储结构存储约瑟夫数据（即 n个人的 编码等），模拟约

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

4、为 6，1，4，7，2，3，5）（1 ）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了 front头结点。在每加入一个节点时，都会直接连接在front后面,从而保证一开始就赋值的rear尾节点不用修改。伪代码阐释如下：1）、在堆中建立新节点：Node<T> *s=new Node<T>2）、将ai写入到新节点的数据域：s->data=ai;3）、修改新节点的指针域：s-> next=fro nt-> next;4）、修改头结点的指针域，将新节点加入到链表中：fron t-> next=s;时间复杂度为：1 ；（2）、删除：首

5、先通过 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 ;时间复杂

6、度为：1 ;（3 ）、约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实现了循环查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保证链表的循环性。在查找方面上，我利用了一个for循环来计数所查找过 的节点。其中查找的时间复杂度也为1 ;（二）概要设计开始测试主函数流程：流程图如下：输入m和n创建Clinklist类的对象,首先建立循环链表，之后 调用Josef函数。删除该节点，并从该节点的直接 后继结点重新计数。此时要判断 P和q是否存在恰好为rear指针 的情况(三) 详细设计#in clude<iostream>using n amespace std;con

7、 st int d=50000;struct Nodeint data;struct Node*next; / 声明 next 指针；class Cli nklistpublic: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=

8、fr ont;rear->data=a n-1;for(i nt i=n-2;i>=0;i-)Node*s=new Node;/循环插入元素来建立链表s_>data=ai;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

9、=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;elseif(q=rear)II排除q恰好为rear节点的情况p->next=front->next;/ 完成摘链elsep->next=q->next;/ 完成摘链int x=q->data;/ 保留 q 点数据delete q;/完成q节点的删除j+；if( j=n)cout<<

10、;"所出的最后一个人的编号是："<<x<<endl;int mai n()int m,n;cout<<"请输入人数(1<=n<=50000):"<<endl;cin»n;int memberd;/建立数组for(i nt i=0;i <n ;i+)memberi=i+1;cout<<"请输入要按那个数进行计算(m>=1):"<<e ndl;cin»m;if(n <=0|m<=0)throw"所输入的

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

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

13、序后即显示文本方式的用户界面:（六）测试结果请输入各个人的信息t整数”你输入旳数is的顺序为三1 => 2 => 3 => 4 =百 林打賢从富n个人融 请输入幵始号：2请输入相令陋出列人之间的间淸：3程序运行后-出列人的顺序为23 => 5 > 2 => 1 > 4Ppets anp 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 =>

14、 6 => 7 => 8 => 9 => ie => 11 => 12 => 13 ” => 14 => 15 =、1£ => 1?18 => 15 一一>28你打算从第几个人开妳请输入开始号；?请输入桎邻两岀列人之间的间隔；8程序运行后，岀列人的顺序为；16呻> 121 > LS20丄丄> 3 > 158 > 51?1B > 2 > 7 -> 14 > 13 > 6 > 17 > 9Press ein_y kep to continue（七

15、）心得体会数据结构的课程设计， 相对来说还是一个较大的工程，我们小组各个成员相互合作，虽然里面的内容不是很完备，但总体上还是一个比较能要体现 数据结构的知识点能力的程序了，这个设计让我们在课堂中学到的理论知 识，解决相应的实际问题， 深入理解和灵活掌握所学的内容，使我们在实践的过程中收获匪浅，认真去做，踏踏实实，静静思考，慢慢进步，会有收获 的。（八）团队介绍小组成员基本情况介绍 组长：雷灵花11056024组员：涂艺11056022伍雨豪11056029小组成员分工情况组长 雷灵花，选择的实验设计为第一模块的约瑟夫问题，完成了第一个实验的程序设计和最终实验报告的总结。组员 涂艺，完成了第二个

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

17、ruct Nodeint data;structNode*next;/ 声明 next 指针；class Cli nklistpublic: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->

18、;data=a n-1;for(i nt i=n-2;i>=0;i-)Node*s=new Node; s_>data=ai; 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) if(p=rear) p=front->n ext; else p=p->n ext; i+;No

19、de* 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; elsep_>n ext=q _>n ext;/排除q恰好为rear节点的情况/完成摘链/完成摘链int x=q->data; delete q;j+；if(j=n )cout<<"/保留q点数据/完成q节点