数据结构实践报告

数据结构实践报告 学 号 150906112 姓 名 武锦蓉 班 级 NET2 班 指导老师 田喜平 时 间 2016 12 21 项目名称 一 一 项目构思 程序由三个模块组成 1 输入模块 无提示语句 直接输入总人数 n 和报数次数 m 中间用逗 号隔开 2 处理模块 将元素储存于顺序表中 在主函数中根据报数间隔确定需 要删除的元素的位置 在顺序表中设置该位置并删除该位置 同时输出该 位置的值 反复设置并删除直到表空 3 输出模块 分别在 DOS 下和文件中 按移除元素的顺序依次显示其 位置 约瑟夫环问题中的数据是人所在的位置 而这种数据是存在 第一元素 最后元素 并且存在 唯一的前驱和后继的 符合线性表的特点 由于 需要模拟约瑟夫环的出列问题 可以采用顺序表来实现线性表 完成出列 顺序的输出 核心算法主要分为两步 1 确定需要删除的位置 2 设置并删除该位置 已知报数间隔 m 我们可以把当前位置加上 m 获得需要删除的位置 如果获得的位置超过顺序表中实际元素的总长度 则可以通过减去数组的 实际长度来修正 即模拟环状计数 然后把顺序表中的当前指向位置设置 为该位置 继而删掉该位置 反复进行上述确定位置和删除位置的操作 直到顺序表为空 程序主要功能模块 1 输入的形式和输入值的范围 输入的形式和输入值的范围 每一次输入的值为两个正整数 中间用逗号隔开 若分别设为 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 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 a n 基本操作 bool remove int 指向数组的指针 int realSize 数组中含有元素的实际长度 int fence 指向当前元素下标 public AList int s 构造函数 初始化数组 listArray new int s for int i 0 i s i listArray i i 1 数组值等于数组下标 1 realSize s fence 0 指向首元素 bool remove int 如果数组为空返回 false elem listArray fence for int i fence i 0 return true return false int getLength 获取数组长度 return realSize 在主函数中调用上述模块的方法 ofstream fout 文件流 fout open C Josephus txt 设置文件路径 int n m elem point 0 scanf d d 获得用户输入 AList alist n 创建顺序表对象 while alist isEmpty 如果顺序表不为空 继续删除 m m alist getLength 调整计数的长度 if m 0 m alist getLength if point m 1 alist getLength point point m 1 设置偏移位置 else point point m alist getLength 1 alist setPos point 设置当前需要删除的位置 alist remove elem 删除元素 cout elem DOS 输出 fout elem 文件输出 四 测试结果 截图显示 五 遇到的问题及解决方法 1 初始化部分为循环赋值 时间复杂度为 n 2 处理部分 我为了提高效率没有采用循环寻找的方法 直接利用数学关 系通过当前位置获得下一位置 因此对于长度为 n 的约瑟夫环 只做了 n 次定 位 每次定位的复杂度为 1 所以时间复杂度为 n 但是用顺序表实现时 每次其移除的方法是时间复杂度为 k 的 k 与实际 长度有关 所以处理部分总的结果是 的 化简后时间复杂度仍然为 2 1 nn n2 综上 该算法的时间代价为 n2 PS 如果是用循环查找 在 n 次定位中每次都使用了 m 次的循环 至少 是 n m 然后再用顺序表的移除方法 总的复杂度应该是 m n2 的 事实上要用线性表来完成这道题 其复杂度最好也是 n2 的 毕竟对于 n 个数据 每个都要进行时间复杂度为 n 的删除工作 欲到达 n 的效率除 非不用线性表来实现 六 体会 主程序 输入和输出的格式 输入和输出的格式 输