线性表实验报告

1、北京邮电大学通信工程数据结构实验题目（ 2019 年春季） 约瑟夫环院系：信息与通信工程学院班级：学号：姓名：完成时间： 2019 年 3 月 19 日线性表实验报告题目： 2.4 约瑟夫问题人员：完成时间： 2019 年 3 月 19 日1需求分析：（ 1）题目概括：约瑟夫问题如下：已知 n 个人（ n>=1 ）围坐一圆桌周围，从1 开始顺序编号。从序号为 1 的人开始报数，顺时针数到 m 的那个人出列；他的下一个人又从1 开始报数，数到 m 的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。建立循环链表，通过两层循环嵌套，内循环次数达到 m 进行一个节

2、点的删除，外层循环实现只剩余一个后进行输出。（ 2）输入的形式和输入值的范围： 输入一个正整数n 代表人数， 一个正整数m 作为出圈的判断周期。 （ n,m 均为正整数）（ 3）输出的形式：输出一个正整数表示最后一个出列的人的编号。（ 4）程序所能达到的功能：利用循环链表实现约瑟夫问题的求解。5）测试数据：输入：103输出：4输入：62输出：5输入：124输出：1输入：83输出：72概要设计定义结构类型，使其储存编号，并含有指针以便形成链式结构。主程序：连续定义n 个对象，并形成环状结构，从首节点向后移动m-1 次，然后删除后方的节点。继续循环此操作，至只剩余一个对象。输出其编号。3详细设计定

3、义结构类型person ， 内含整型 num 储存其编号， person 的指针类型*next 指向环中紧邻的下一个person 。主程序：输入 n,m 并判断是否合理，若合理，以 head 为头节点，连续定义n 个 person的对象，依次递增进行编号，利用指针成员指向下一个成员，并将尾节点的next 指针指向head->next 形成循环链。在两层循环嵌套结构中，利用计数器进行循环，循环m 次之后，delete 对应的对象，并保持循环链，并将计数器清零，直至只剩余一个对象。将该对象的 num 输出。后释放剩余的动态内存空间。伪代码：struct 节点的结构类型定义int 编号；指针

4、指向下一个节点； 将该指针初始化为NULL；int main（）定义头节点，尾节点，用来申请动态内存的 s节点，用来删除某一结点的用头节点申请动态内存空间，并让尾节点背附为头节点；定义整型变量n,m,j,j为计数器，初值赋为0;输入n,m;tryIf(n或m输入不合理)throw特定字符表示输入错误类型；catch(一个字符)对该字符进行判断输出错误类型并终止程序；for(int i=0;i<n;i+)用s节点来申请动态内存空间；填写s节点的编号值；将s节点连接在尾节点后；调整新的尾节点；将尾节点指向头结点的下一个节点，形成环型链表；while(j<(n -1)for(int i=

5、0;i<m -1;i+)将尾节点后移；将todelete赋为尾节点的下一个节点，即要被删除的节点；是尾节点连接todelete的下一个节点，保证删除操作不会使环形链表断开;将todelete对应的节点删除；计数器计数；输出尾节点的编号值；此时环形链表只剩余一个节点将剩余未释放的动态内存释放；4.调试分析todelete ;定义结构类型II 以下为主程序创建结构类型指针：head,now,newperson,todelete整型变量：n,m,j=0申请动态内存空间,并连接到尾节点形成环状(1)在使用线性表时出现已经去除的对象仍占据表中的位置，因此为 了实现灵活删除对象，改用链表结构进行存储

6、。在实现删除的过程中想要实 现删除特定对象且不破坏链表连接，需要额外创建对象指向被删对象的前一 个，过于繁琐且不易实现，于是将移动位置从移动m位，改为m-1位，可 使得循环条件简化。（ 2）当前算法中最复杂的模块为两层循环嵌套，为实现删除n-1 个对象需要进行n-1 次的内循环，为了删除指定的对象，需要移动操作位置m-1次，时间复杂度为 O（ m*n ） 。空间复杂度为 O（ n） ，创建 n 个对象实现环形链表，其余变量空间复杂度为 O（ 1 ）（ 3）若不使用链表结构或许可降低空间复杂度5用户使用说明只需要输入两个正整数表示 总人数和淘汰的周期长度。6测试结果输入： 103 输出： 4输入

7、：62输出：5输入：124输出：1输入：83输出：77附录#include <iostream>#include <string>using namespacestd;struct person / 定义结构类型int num;person *next;person()next = NULL;int main()person *head, *now, *newperson,*todelete; /*head 为头指针， *now 为当下进行操作的对象，*newperson 为动态申请的空间 ,*todelete 为将要删除的对象head = new person ;no

8、w = head;int n, m,j=0; /n为人数，m为报数是需要出圈的位置编号，j为计数器删除n-1个人cout << "输入总人数和淘汰的周期长度" << endl;cin >> n >> m;try/ 判断输入的数据是否合理，并进行分类，若为异常数据则中断程序if (n <= 0&&m<=0) throw 'b' ;else if (n <= 0) throw 'n' ;else if (m <= 0) throw 'm' ;c

9、atch ( char a)switch (a)case 'b' :cout << " 总人数和淘汰的周期长度异常" << endl;return 0;break ;case 'n' :cout << " 总人数异常" << endl;return 0;break ;case 'm' :cout << " 淘汰的周期长度异常" << endl;return 0;break ;for ( int i = 0; i &l

10、t; n; i+)newperson = new person ;newperson->num = i + 1;/ 给每一个人进行编号，以便输出now->next = newperson; / 连接新增的节点now = newperson; / 将 now变为链表的尾节点 now->next = head->next; / 形成环形链表while (j < (n - 1)for ( int i = 0; i < m-1; i+)now = now->next;/ 将所要操作的节点后移 m-1 次，此时 now 的位置下一个节点为应该删除的节点todelete = now->next;now->next = todelete->next; / 删除节点并保证原本的环形链式结构delete todelete;j+