大数据结构实践报告材料

1、数据结构实践报告学 号： 150906112姓 名： 武锦蓉班 级： NET2 班 指导老师： 田喜平时 间： 2016-12-21实用标准文案项目名称项目构思 程序由三个模块组成： （1）输入模块：无提示语句，直接输入总人数 n 和报数次数 m ，中间用逗 号隔开。（2）处理模块：将元素储存于顺序表中。在主函数中根据报数间隔确定需 要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位 置的值。反复设置并删除直到表空。（3 ）输出模块：分别在 DOS 下和文件中， 按移除元素的顺序依次显示其位 置。约瑟夫环问题中的数据是人所在的位置， 而这种数据是存在 “第一元素、 最后元素”，

2、并且存在“唯一的前驱和后继的” ，符合线性表的特点。由于需 要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序 的输出。核心算法主要分为两步：1、确定需要删除的位置， 2、设置并删除该位置。已知报数间隔 m ，我们可以把当前位置加上 m 获得需要删除的位置， 如 果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际 长度来修正（即模拟环状计数） 。然后把顺序表中的当前指向位置设置为该精彩文档实用标准文案位置，继而删掉该位置。反复进行上述确定位置和删除位置的操作，直到顺序表为空 程序主要功能模块1 、输入的形式和输入值的范围：每一次输入的值为两个正整数，中间用逗号隔

3、开 若分别设为 n,m ，则输入格式为：“n,m ”。 不对非法输入做处理，即假设输入都是合法的。2 、输出的形式：输出格式 1 ：在字符界面上输出这 n 个数的输出序列输出格式 2 ：将这 n 个数的输出序列写入到文件中3 、程序所能达到的功能：对于输入的约瑟夫环长度 n 和间隔 m ，输出约瑟夫环的出列顺序。4、测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果正确：输入：10,3输出：3 6 9 2 7 1 8 5 10 4输入：41,3输出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32精彩文档实用标准文

4、案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数据对象：整形数据关系：线性关系，即 (0 an) 。基本操作：bool remove(int &elem)/ 移除一个元素，被移除的元素赋给 elem/ 如果操作成功，返回 true, 否则返回 falsebool isEmpty()/ 判断数组的元素是否

5、清空，空返回 true, 否则返 回 falsebool setPos(int place)/ 设置当前元素的位置，设置成功返回精彩文档实用标准文案true, 否则返回 falseint getLength()/ 获取数组的实际长度2、各程序模块之间的层次(调用)关系：主函数会按设计的方法调用顺序表中“获取实际长度” 、“设置需要删除元素 的位置”、“移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次 出列，并正确结束程序。用整形存储用户输入的整数。用顺序表实现线性表：class AListprivate:int *listArray;/ 指向数组的指针int realSize;/

6、数组中含有元素的实际长度int fence;/ 指向当前元素下标public:精彩文档实用标准文案AList(int s)/ 构造函数，初始化数组listArray=new ints;for(int i=0;is;i+)listArrayi=i+1;/ 数组值等于数组下标 +1realSize=s;fence=0;/ 指向首元素bool remove(int &elem)/ 移除一个元素if(isEmpty()return false;/ 如果数组为空返回 false elem = listArrayfence;从当前位置开始循环向前赋值for(int i=fence;i=0&place=re

7、alSize)fence=place;return true;return false;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);/ 创建顺序表对象while(!alist.isEmpty()/ 如果顺序表不为空，继续删除 m=m%alist.getLength();/ 调整计

8、数的长度/ 设置偏移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 ;/ 文件输出四、测试结果(截图显示)五、遇到的问题及解决方法1、初始化部分为循环赋值，时间复杂度为 (n) 。2、处理部分，我为了提高效率没有采用循环寻找的方法，直接

9、利用数学关 系通过当前位置获得下一位置，因此对于长度为 n 的约瑟夫环，只做了 n 次定 位，每次定位的复杂度为 (1) ，所以时间复杂度为 (n)。但是用顺序表实现时， 每次其移除的方法是时间复杂度为 (k)的 (k 与实际长精彩文档实用标准文案度有关)，所以处理部分总的结果是 (1 2n)n )的，化简后时间复杂度仍然为 (n2)。综上，该算法的时间代价为 (n2)。(PS：如果是用循环查找，在 n 次定位中每次都使用了 m 次的循环，至少 是(n*m) ，然后再用顺序表的移除方法，总的复杂度应该是 (m*n 2)的。)事实上要用线性表来完成这道题，其复杂度最好也是(n2)的，毕竟对于 n个数据，每个都要进行时间复杂度为 (n) 的删除工作。欲到达 (n)的效率除非 不用线性表来实现。六、体会输入人数 n,报数间