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

北京邮电大学信息与通信工程学院第2页北京邮电大学电信工程学院第1页数据结构实验报告实验名称：实验一——线性表学生姓名：班级：班内序号：学号：日期：1．实验要求（1）实验目的通过选择下面四个题目之一进行实现，掌握如下内容：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力（2）实验内容利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。2.程序分析2.1存储结构存储结构为单循环链表，线性表简称表，是由零个或多个具有相同类型的数据元素构成的有限序列。链表为了正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这两部分信息构成了实际的存储结构，称为结点。此循环链表只为解决约瑟夫问题，所以有参构造函数让尾指针存储着最后一个元素的数据，然后指向第一个元素，形成单循环链表。如图：a3a2……ana1a3a2……ana1（（rear）2.2关键算法分析1．关键算法约瑟夫问题的实质就是在含n个元素的循环链表中依次删除第m个元素，返回链表中最后一个元素值。即用含那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的指针域指向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，输出剩下一元素的序号，然后删除最后一结点，此为递归结束条件：if(n==1){cout<<”剩下一人的序号：”<<b->next->data<<endl;deleteb;}②判断如果n大于1，则进行自身递归调用，直至遇到结束条件停止:elseif(n>1)Delete(m,b->next,n);③如果n等于0，即一开始链表只有一个结点，输出“无人剩下！”:elseif(n==0) { cout<<"无人剩下!"<<endl; system("pause"); }3．时间复杂度的计算[1]O(n)[2]O(n)[3]O(1)[3.1]O(1)[3.2]O(m)[3.3]O(1)[3.4.1]O(1)[3.4.2]O(n*m)[3.4.3]O(1)2.3其他（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.程序运行结果1．流程流程图如下：开始开始调用单循环表类的删除函数，实参为数组和尾指针的下一结点调用单循环表类的删除函数，实参为数组和尾指针的下一结点定义新结点p，用以存储要删除的结点定义新结点p，用以存储要删除的结点查找第m-1个元素，删除第m查找第m-1个元素，删除第m个元素，指针b后移，人数n减1判断判断人数nn>1n=0n=1n>1n=0n=1进行自身递归调用进行自身递归调用如果n等于0，即一开始链表只有一个结点，输出“无人剩下！”判断如果n等于1，输出剩下一元素的序号，然后删除最后一结点判断如果n等于1，输出剩下一元素的序号，然后删除最后一结点结束结束2．测试条件：人数n和删除数m必须为整数。3.测试结论：4.总结（1）调试时出现的问题及解决方法①在调试时出现了执行错误，在析构函数中设置了断点。在执行时，发现析构函数停不下来，原来在删除函数里已经析构到只剩一个结点，而且尾指针可能已经被删除，所以我去掉了析构函数，而在输出最后一个结点后析构该结点。②在执行时发现剩下一人的序号不对，在删除函数的摘链操作中设置了断点，在执行时，发现每次删除的结点不正确，原来删除函数的实参错误写为了尾指针，该为第一个结点后程序正确。（2）心得体会在本次实验中，熟悉了单循环链表的各种基本操作，特别对插入操作、查找操作和删除操作有了较深的理解。对于数组和指针的用法也更熟练，在程序的调试和异常处理方面有了一定的经验。相信在本次实验中积累的经验、提高的能力将在今后的实验中展现出来。尤其在递归函数的使用方面有了很大的提高，熟悉了递归函数使用条件，了解了要设置递归结束条件。（3）下一步的改进程序有的代码不够简洁，可以写得更简洁，可能还有更好的方法，此程序把尾指针存储了一个元素，违反了尾指针的原意，可以进一步改进。附代码：//ClinkList.h#include<iostream>usingnamespacestd;template<classT>structNode//储存节点的结构{ Tdata; structNode<T>*next;};template<classT>classClinkList//单循环链表类{public: ClinkList(){rear=newNode<T>;rear->next=rear;}//无参构造函数 ClinkList(Ta[],intn);//有参构造函数 voidDelete(intm,Node<T>*b,intn);//删除结点函数 Node<T>*rear;//尾指针};template<classT>ClinkList<T>::ClinkList(Ta[],intn)//头插法{ rear=newNode<T>; rear->next=rear; rear->data=a[n-1]; for(inti=n-2;i>=0;i--) { Node<T>*s=newNode<T>; s->data=a[i]; s->next=rear->next; rear->next=s; }}template<classT>voidClinkList<T>::Delete(intm,Node<T>*b,intn){ Node<T>*p; for(intj=0;j<(m-2+n)%n;j++)//找到要删结点的前一结点 { b=b->next;}p=b->next; b->next=p->next;deletep; n--; if(n==1)//递归结束条件 { cout<<"剩下一人的序号是:"<<b->next->data<<endl; system("pause"); deleteb; } elseif(n>1)Delete(m,b->next,n);//递归函数，递归删除 elseif(n==0) { cout<<"无人剩下!"<<endl; system("pause"); }}//main.cpp#include<iostream>#include"ClinkList.h"usingnamesp