北邮数据结构实验一约瑟夫问题实验报告(递归做法)

《北邮数据结构实验一约瑟夫问题实验报告(递归做法)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验一——线性表学生姓名：班级：班内序号：学号：日期：1．实验要求（1）实验目的通过选择下面四个题目之一进行实现，掌握如下内容：Ø熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法Ø学习指针、模板类、异常处理的使用Ø掌握线性表的操作的实现方法Ø学习使用线性表解决实际问题的能力（2）实验内容利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所

2、有人全部出列。请问最后一个出列的人的编号。2.程序分析2.1存储结构存储结构为单循环链表，线性表简称表，是由零个或多个具有相同类型的数据元素构成的有限序列。链表为了正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这两部分信息构成了实际的存储结构，称为结点。此循环链表只为解决约瑟夫问题，所以有参构造函数让尾指针存储着最后一个元素的数据，然后指向第一个元素，形成单循环链表。如图：a3a2……ana1（rear）2.2关键算法分析1．关键算法约瑟夫问题的实质就是在含n个元素的循环链表中依次删除第m个第6页北京邮电大学信息与通信工程学院元素，

3、返回链表中最后一个元素值。即用含那n个元素的数组初始化循环链表，从第一个元素开始查找第m-1个元素，删除第m个元素，然后从第m+1个元素开始继续查找第m-1个元素，删除第m个元素，循环此过程直到链表中只剩下最后一个元素。关键算法伪代码如下：[1]让用户输入要删第几个元素和总人数n，并给含n个元素的数组赋值；[2]用含n个元素的数组初始化循环链表（头插法）；[3]调用单循环表类的删除函数，实参为数组和尾指针的下一结点（即第一个元素）；[3.1]定义新结点p，用以存储要删除的结点；[3.2]进行循环找到要删除元素的上一结点；[3.3]初始化指针p指向b->next，p的指针域指向

4、b的指针域，第m个元素摘链，删除p，指针b后移，人数n自减1；[3.4.1]判断如果n等于1，输出剩下一元素的序号，然后删除最后一结点，此为递归结束条件；[3.4.2]判断如果n大于1，则进行自身递归调用，直至遇到结束条件停止；[3.4.3]如果n等于0，即一开始链表只有一个结点，输出“无人剩下！”；2.代码详细分析:（1）删除操作的算法步骤：①从第一个结点开始，查找第m-1个元素，设为b指向该结点；②设p指向第i个元素：p=b->next;③摘链，即将b元素从链表中摘除：b->next=p->next;④释放q元素：deleteq;(2)递归调用算法步骤：①判断如果n等于1

5、，输出剩下一元素的序号，然后删除最后一结点，此为递归结束条件：if(n==1){cout<<”剩下一人的序号：”<next->data<1)Delete(m,b->next,n);③如果n等于0，即一开始链表只有一个结点，输出“无人剩下！”:elseif(n==0){cout<<"无人剩下!"<

6、4.1]O(1)[3.4.2]O(n*m)[3.4.3]O(1)2.3其他第6页北京邮电大学信息与通信工程学院（1）在此需要说明的是，在初始化链表时，特使用了头插法，并对头插法做了相应的修改。使尾指针rear存储着最后一个结点。伪代码如下：[1]用含n个元素的数组a[]初始化循环链表；[2]尾指针的data域存储最后一个结点a[n-1]；[3]进行循环初始化新结点s存储a[i];[4]s->next=rear->next;[5]rear指向s:rear->next=s;（2）在这里为了使代码简洁，在删除函数里使用了递归调用，结束条件时只剩一个人时，并输出该人序号。3.程序运行

7、结果1．流程流程图如下：开始调用单循环表类的删除函数，实参为数组和尾指针的下一结点定义新结点p，用以存储要删除的结点查找第m-1个元素，删除第m个元素，指针b后移，人数n减1判断人数nn>1n=0n=1进行自身递归调用如果n等于0，即一开始链表只有一个结点，输出“无人剩下！”判断如果n等于1，输出剩下一元素的序号，然后删除最后一结点结束第6页北京邮电大学信息与通信工程学院2．测试条件：人数n和删除数m必须为整数。3.测试结论：4.总结（1）调试时出现的问题及解决方法①在调试时出现了执行错误，在析构函数中