C++数据结构循环链表约瑟夫问题实验报告.doc

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

1、2009级数据结构实验报告实验名称： 实验一 线性表学生姓名： 班 级： 班内序号： 学 号： 日 期： 2010年11月5日1实验要求一、实验目的通过选择下面4个题目之一进行实现，掌握如下内容：l 熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法；l 学习指针、模板类、异常处理的使用；l 掌握线性表的操作实现方法；l 培养使用线性表解决实际问题的能力。二、实验内容4.题目4利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列。他的下一个人又从1开始报数，数到m的那个人又出列。依次规则重复下

2、去，直到所有人全部出列。请问最后一个出列的人的编号。2. 程序分析2.1 存储结构循环链表。线性表简称表，是由零个或多个具有相同类型的数据元素构成的有限序列。链表为了正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这两部分信息构成了实际的存储结构，称为结点。如果将单链表的终端节点的指针域指向头结点，则整个链表构成一个环，成为单循环链表。如图所示：rearana2a12.2 关键算法分析1关键算法约瑟夫问题的实质就是在含n个元素的循环链表中依次删除第m个元素，返回链表中最后一个元素值。即用含n个元素的数组初始化循环链表，从第一个元素开始查找第m-1个元素

3、，删除第m个元素，然后从第m+1个元素开始继续查找第m-1个元素，删除第m个元素，循环此过程直到链表中只剩下最后一个元素。关键算法伪代码如下：1 用含n个元素的数组初始化循环链表，初始化指针p指向第一个结点；2 判断人数n或报数m是否为1； 2.1 人数n或报数m为1，将人数n赋给x；2.2 当人数不为1时，进入循环； 2.2.1 初始化计数器i=1； 2.2.2 查找第m-1个元素，p指向第m-1个元素； 2.2.3 初始化指针q指向p-next，p的指针域指向q的指针域，第m个元素摘链，删除q，指针p后移； 2.2.4 人数n减1； 2.3 尾指针rear指向最后的结点p，将此结点值赋给x

4、；3 返回x的值。2时间复杂度的计算1 O(n)2 O(1)2.1 O(1) 2.2 O(n) 2.2.1 O(n*m)2.2.2 O(n*m)2.2.3 O(n)2.2.4 O(n)T(n) = n*m2.3 其他在此需要说明的是，在初始化链表时，特使用了尾插法，并对尾插法做了相应的修改。使尾指针rear可以随新插入链表的结点移动。为了保证循环计数的准确，在含参构造函数中，用含n个元素的数组初始化链表后，特将无实际值的头结点删去，这样就可以避免因头结点的存在而导致计数错误，也省去了对头结点的判断。伪代码如下：1 用含n个元素的数组a初始化循环链表；2 初始化指针p使其指向头结点；3 将尾结点

5、rear的指针域指向头结点的下一个结点，即第一个含值的结点；4 删去p，即删除了头结点。3. 程序运行结果1流程（1）用含n个元素的数组a初始化循环链表；（2）计数，查找第m-1个元素，删除第m个元素，人数n减1；（3）循环直到n=1，返回此刻的结点值。流程图如下：开始用含n个元素的数组a初始化单循环链表是人数n或报数m是否等于1否初始化计数器i=1，指针p指向第一个结点是人数n是否等于1否查找第m-1个元素，删除第m个元素，指针p后移，人数n减1尾指针rear指向最后一个结点，将最后一个结点的值赋给x将人数n赋给x返回x的值结束2运行结果4. 总结（1）调试时出现的问题及解决方法在调试时出现

6、了1 个无法解析的外部命令这一错误，在删除了析构函数后问题解决。在执行时，当输入m=1时程序无法继续进行，是因为在查找第m-1个元素时缺少了判断m=1的情况，后增加了当m=1时直接返回人数n的判断，问题解决。（2）心得体会在本次实验中，熟悉了单循环链表的各种基本操作，特别对插入操作、查找操作和删除操作有了较深的理解。对于数组和指针的用法也更熟练，在程序的调试和异常处理方面有了一定的经验。相信在本次实验中积累的经验、提高的能力将在今后的实验中展现出来。（3）下一步的改进程序中不存在析构函数，可能引起程序的错误，需要补上析构函数而不出现“无法解析的外部命令”这一问题，不清楚为什么删除析构函数后此问

7、题解决。在删除结点的过程中，尾结点rear存在指针悬挂的问题，虽然最后又指向了最后的结点，但在程序执行中增加了风险，也需要改进。附录：实验代码#include using namespace std;template struct NodeT data;struct Node *next;template class CLinkListpublic:CLinkList()rear=new Node;rear-next=rear;CLinkList(T a,int n);int Josephus(int m,int n);private:Node *rear;template CLinkList

8、:CLinkList(T a,int n)rear=new Node;rear-next=rear;for (int i=0;in;i+)Node *s=new Node ;s-data = ai;s-next = rear-next;rear-next = s;rear = s;Node *p = rear-next;rear-next = p-next;delete p;template int CLinkList:Josephus(int m,int n)int x,i;Node *p=rear-next;if (n=1|m=1)x=n;elsewhile(n!=1)i=1;while

9、(p&i!=(m-1)p=p-next;i+;Node *q = p-next;p-next = q-next;delete q;p = p-next;n-;rear=p;x=p-data;return x;int main()int M,N,a1024;coutN;if (N=1024)coutError!Please put in a smaller number.;return 0;coutM;if (M=0)coutError!Please put in a positive number:;return 0;for (int i=0;iN;i+)ai = i+1;CLinkList A(a,N);coutthe last number is:A.Josephus(M,N);return 0;