数据结构实践报告

1、本文格式为word版，下载可任意编辑数据结构实践报告 20xx 报 告 汇 编 compilation of reports 数据结构实践报告 学 号： 150906112 姓 名： 武锦蓉 班 级： net2 班 指导老师： 田喜平 时 间： 2021-12-21 报告文档借鉴学习 word 可编辑有用文档 项目名称 一、 项目构思 程序由三个模块组成： （1）输入模块：无提示语句，直接输入总人数 n 和报数次数 m，中间用逗号隔开。 （2）处理模块：将元素储存于挨次表中。在主函数中依据报数间隔确定需要删除的元素的位置，在挨次表中设置该位置并删除该位置，同时输出该位置的值。反复设置并删除直到

2、表空。 （3）输出模块：分别在 dos 下和文件中，按移除元素的挨次依次显示其位置。 约瑟夫环问题中的数据是人所在的位置，而这种数据是存在"第一元素、最终元素'，并且存在"唯一的前驱和后继的'，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采纳挨次表来实现线性表，完成出列挨次的输出。 核心算法主要分为两步： 1、确定需要删除的位置，2、设置并删除该位置。 已知报数间隔 m，我们可以把当前位置加上 m 获得需要删除的位置，假如获得的位置超过挨次表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把挨次表中的当前指向位置设置为

3、该位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到挨次表为空。 程序主要功能模块 1 、输入的形式和输入值的范围： 每一次输入的值为两个正整数，中间用逗号隔开。 若分别设为 n,m，则输入格式为："n,m'。 不对非法输入做处理，即假设输入都是合法的。 2 、输出的形式： 输出格式 1：在字符界面上输出这 n 个数的输出序列 输出格式 2：将这 n 个数的输出序列写入到文件中 3 、程序所能达到的功能： 对于输入的约瑟夫环长度 n 和间隔 m，输出约瑟夫环的出列挨次。 4 、测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 正确： 输入：1

4、0,3 输出：3 6 9 2 7 1 8 5 10 4 报告文档借鉴学习 word 可编辑有用文档 输入：41,3 输出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31 错误： 输入：10 3 输出：6 8 7 1 3 4 2 9 5 10 二、 程序清单 1 、 抽象数据类型的定义： 为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。线性表 adt 定义如下： adt list 数据对

5、象：整形 数据关系：线性关系，即ai,ai+1(0an)。 基本操作： bool remove(int elem)/移除一个元素，被移除的元素赋给 elem /假如操作胜利，返回 true,否则返回 false bool isempty()/推断数组的元素是否清空，空返回 true,否则返回false bool setpos(int place)/设置当前元素的位置，设置胜利返回 true,否则返回 false int getlength()/猎取数组的实际长度 2 、各程序模块之间的层次（调用）关系： 主函数会按设计的方法调用挨次表中"猎取实际长度'、"设置需要删

6、除元素的位置'、"移除该位置元素'和"推断是否为空表'四种方法方法，使元素依次出列，并正确结束程序。 用整形存储用户输入的整数。 用挨次表实现线性表： class alist private: int *listarray;/指向数组的指针 int realsize;/数组中含有元素的实际长度 报告文档借鉴学习 word 可编辑有用文档 int fence;/指向当前元素下标 public: alist(int s)/构造函数，初始化数组 listarray=new ints; for(int i=0;is;i+) listarrayi=i+1;/数

7、组值等于数组下标+1 realsize=s; fence=0;/指向首元素 bool remove(int elem)/移除一个元素 if(isempty()return false;/假如数组为空返回 false elem = listarrayfence; for(int i=fence;irealsize-1;i+)/从当前位置开头循环向前赋值 listarrayi=listarrayi+1; realsize-; return true; bool isempty()/推断数组的元素是否清空 if(realsize=0)return true; else return false; b

8、ool setpos(int place)/设置当前元素的位置 if(place=0place=realsize) fence=place; return true; return false; 报告文档借鉴学习 word 可编辑有用文档 int getlength()/猎取数组长度 return realsize; ; 在主函数中调用上述模块的方法： ofstream fout;/文件流 fout.open(c:josephus.txt);/设置文件路径 int n,m,elem,point=0; scanf(%d,%d,n,m);/获得用户输入 alist alist(n);/创建挨次表对

9、象 while(!alist.isempty()/假如挨次表不为空，连续删除 m=m%alist.getlength();/调整计数的长度 if(m=0)m=alist.getlength(); if(point+m-1alist.getlength()point=point+m-1; /设置偏移位置 elsepoint=point+m-alist.getlength()-1; alist.setpos(point);/设置当前需要删除的位置 alist.remove(elem);/删除元素 coutelem ;/dos 输出 foutelem ;/文件输出 四、测试结果（截图显示） 报告文档

10、借鉴学习 word 可编辑有用文档 五、遇到的问题及解决方法 1、初始化部分为循环赋值，时间简单度为(n)。 2、处理部分，我为了提高效率没有采纳循环查找的方法，直接利用数学关系通过当前位置获得下一位置，因此对于长度为 n 的约瑟夫环，只做了 n 次定位，每次定位的简单度为(1)，所以时间简单度为(n)。 但是用挨次表实现时，每次其移除的方法是时间简单度为(k)的(k 与实际长度有关)，所以处理部分总的结果是(2) 1 ( n n +)的，化简后时间简单度仍旧为(n 2 )。 综上，该算法的时间代价为(n 2 )。 （ps：假如是用循环查找，在 n 次定位中每次都使用了 m 次的循环，至少是(n*m)，然后再用挨次表的移除方法，总的简单度应当是(m*n 2 )的。） 事实上要用线性表来完成这道题，其简单度最好也是(n 2 )的，究竟对于 n个数据，每个都要进行时间简单度为(n)的删除工作。欲到达(n)的效率除非不用线性表来实现。 六、体会 输入人数 n,报数间隔 m