北京邮电大学信息与通信工程学院
2010级数据结构实验报告
实验名称： 实验一——线性表（约瑟夫问题） 学生姓名： 在这我就不写了 班 级： ** 班内序号： ** 学 号：日 期：
**
2010年11月4日第1页
北京邮电大学信息与通信工程学院
1．实验要求
一、实验目的
通过实现约瑟夫问题，掌握如下内容：
1、 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法； 2、 学习指针、模板类、异常处理的使用； 3、 掌握线性表的操作实现方法；
4、 培养使用线性表解决实际问题的能力。 二、实验内容
利用循环链表实现约瑟夫问题的求解。
约瑟夫问题如下：有n个人(n>=1)围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，顺时针数到m的那个人出列，他的下一个然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列。请问最后一个出列的人的编号。
2. 程序分析
对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。
在这个程序中解决了存储问题后，之后最大的难点就是关于出列节点的逻辑判断。由于我插入元素时是将rear指针中也存入了元素值，又增加了一个front指针，实际上是front指针始终存在而rear指针有可能消除。这样遇到的问题就是，假设p本身就是rear指针，那当移到下一位时就应该移动两位来跳过front这一个空节点。这个是程序实现中容易发生逻辑错误的地方。
2.1 存储结构
本实验中所用的存储结构为单链表。 以下即为单链表的存储结构示意图：
front
（1） 空单循环链表 a1 a2 ? an front rear （2）非空单循环链表
2.2 关键算法分析
1、 关键算法：
第2页
北京邮电大学信息与通信工程学院
（1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。
伪代码阐释如下：
1)、在堆中建立新节点：Node
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)、保存q元素的数据：x=q->data； 5）、释放q元素：delete q；
时间复杂度为：1； （3）、约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实现了循环查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保证链表的循环性。在查找方面上，我利用了一个for循环来计数所查找过的节点。 其中查找的时间复杂度也为1；
2.3 其他
在程序运行结果中，虽然编译没有任何错误，在运行过程中也没有逻辑错误，可以得到正确结果，但在运行即将结束时会有“程序已停止执行”的窗口。这是一个我没有解决好的debug。我自己感觉可能是由于在我所建立的链表中可以删除掉rear指针，但是还是不明白。
3. 程序运行结果
测试主函数流程： 流程图如下：
第3页
北京邮电大学信息与通信工程学院
开始 输入m和n
m n 是 否 判断、 否符合要求
是 创建Clinklist类的对象， 首先建立循环链表，之后 调用Josef函数。
断 链 表 跳出函数 判 是否为空
否 循环查找到所要删除节点 的前一个节点。 判断所要删除节点是否为最后一个 是
否 删除该节点，并从该节点的直接 后继结点重新计数。此时要判断 P和q是否存在恰好为rear指针 的情况
输出m的位置
结束
第4页
北京邮电大学信息与通信工程学院
例如，当n=189，m=23时的结果为如下所示：
测试结论：程序功能正常，能完成实验要求的输出结果。
4. 总结
1、 调试时出现的问题及解决的方法
A、 在调试时一开始用的是模板类，调试时就总会遇到“无法解析的外部指令”之
类的问题。由于无法解决，对模板类的理解不好，所以就去掉了模板类的应用。Templete
struct类型的语句，才得以运行正常：
struct Node {
int data;
struct Node*next; };
C、这个是最严重的逻辑错误，就是编译的时候没有任何问题，在程序运行时会出现乱码或者出错的情况。这个完全靠一点点的逻辑判断了，又用了最笨的方法：在纸上画一个循环链表才搞定。
2、 心得体会
这次实验首先遇到的问题是用类来完成单链表的操作时，不知道该用什么样的格式来写，比如，上述的B类编译错误，一开始就完全不知所云。逐渐把格式搞定后，接下来最大的问题就是逻辑的判断。这个也花费了我最多的时间去解决。 才认识到循环列表的厉害之处，在插入元素时就废了很大时间，头结点和尾节点的移动关系也需要理解。
3、 下一步的改进
第5页
北京邮电大学信息与通信工程学院
首先是想解决我的“.exe已停止工作”的问题，这个一直不能改掉的问题。其次要改进的我的逻辑算法，总感觉写的很乱，比如在判断是否到达rear的问题上，就觉得写的有些不简明了。最应该做的改进就是认真的理解线性表的各种基本操作。比如最简单的建立一个线性表都应该加强理解和掌握。
附录源代码：
#include
class Clinklist { public: };
Clinklist::Clinklist(int a[],int n) { }
void Clinklist::Josef(int m,int n) {
Node* p=front; int j=0; rear=new Node; front=new Node;
front->next=rear;//构造空单链表 rear->next=front; rear->data=a[n-1]; for(int i=n-2;i>=0;i--) { }
Node*s=new Node; //循环插入元素来建立链表 s->data=a[i]; s->next=front->next; front->next=s; Clinklist(int a[],int n); void Josef(int m,int n);
Node *rear; //声明rear和front指针 Node *front; int n; int data;
struct Node*next; //声明next指针
private:
第6页
北京邮电大学信息与通信工程学院
}
while(front->next!=front) {
int i=0; {
if(p==rear)
p=front->next; else p=p->next; i++; }
while(i!=m-1) //实现第m-1个节点的查找
Node* q=p->next;
if(p==rear) //排除p恰好为rear节点的情况
{q=front->next; front->next=q->next; p->next=front->next; } { }
if(q==rear) //排除q恰好为rear节点的情况 p->next=front->next; //完成摘链 p->next=q->next; //完成摘链
else
else
int x=q->data; //保留q点数据 delete q; //完成q节点的删除 j++; }
if(j==n)cout<<\所出的最后一个人的编号是:\< int main() { int m,n; cout<<\请输入人数(1<=n<=50000):\< for(int i=0;i cout<<\请输入要按那个数进行计算(m>=1):\< if(n<=0||m<=0)throw\所输入的数不符合要求!\; Clinklist pro(member,n); //构造Clinklist类的对象 pro.Josef(m,n); member[i]=i+1; 第7页 北京邮电大学信息与通信工程学院 } return 0; 第8页
