约瑟夫问题 - 线性表部分 数据结构实验报告

北京邮电大学信息与通信工程学院

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 *s=new Node; 2)、将a[i]写入到新节点的数据域：s->data=a[i]; 3)、修改新节点的指针域：s->next=front->next;

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还需要再次加强。 B、 “rear指针找不到声明”，这个的解决方案是参照别的线性表例子，加上了如下

struct类型的语句，才得以运行正常：

struct Node {

int data;

struct Node*next; };

C、这个是最严重的逻辑错误，就是编译的时候没有任何问题，在程序运行时会出现乱码或者出错的情况。这个完全靠一点点的逻辑判断了，又用了最笨的方法：在纸上画一个循环链表才搞定。

2、 心得体会

这次实验首先遇到的问题是用类来完成单链表的操作时，不知道该用什么样的格式来写，比如，上述的B类编译错误，一开始就完全不知所云。逐渐把格式搞定后，接下来最大的问题就是逻辑的判断。这个也花费了我最多的时间去解决。 才认识到循环列表的厉害之处，在插入元素时就废了很大时间，头结点和尾节点的移动关系也需要理解。

3、 下一步的改进

第5页

本文来源：https://www.bwwdw.com/article/ny52.html