《数据结构》课程设计报告

数据结构数据结构 课程设课程设 计报告计报告 排序和压缩排序和压缩 排序排序 设计要求 设计要求 编程实现希尔 快速 堆 归并排序算法 要求随机产生 10000 个数据 存入 数据文件 分别采用不同的排序算法进行排序 将结果存入文件中 算法思想 算法思想 首先熟悉四种不同排序的算法编程 然后将它们编写在同一个文件中 调用的 时候就比较方便 1 希尔排序 希尔排序是对直接插入排序的一种改进 它的基本思想是 先将整个待排序记 录序列分割成若干个子序列 在子序列内分别进行直接插入排序 待整个序列 基本有序时 再对全体记录进行一次直接插入排序 2 快速排序 快速排序是对气泡排序的一种改进 其基本思想是 首先选一个轴值 即比较 的基准 将待排序记录分割成独立的两部分 左侧记录的关键码均小于或等于 轴值 右侧记录的关键码均大于或等于轴值 然后分别对这两部分重复上述过 程 直到整个序列有序 3 堆排序 堆排序是简单选择排序的一种改进 其基本思想是 首先将待排序的记录序列 构造成一个堆 此时 选出了堆中所有记录的最大值即堆顶记录 然后将它从 堆中移走 通常将堆顶记录和堆中最后一个记录交换 并将剩余的记录再调整 成堆 这样又找出了次大的记录 依此类推 直到堆中只有一个记录 4 归并排序 归并排序是一种借助 归并 进行排序的方法 其主要思想是 将若干有序序 列逐步归并 最终归并为一个有序序列 程序实现 程序实现 由main cpp sort h和run h三部分组成 sort h头文件中实现了希尔 快速 堆排序 归并排序 run h头文件中有随机产生待排数据 将数据写入文件 从 文件读数据 main cpp主函数调用头文件里的函数 页面菜单 测试结果 测试结果 Run h Main cpp Sort h Shellsort 希尔排序 Quicksort 快速排序 Heapsort 堆排序 Mergesort 归并排序 Generate 随机数产生 Write 写入文件 Read 读文件 功能菜单 调用各个 函数 程序总结 程序总结 这个程序还是比较好实现的 总体就是安排函数的问题 如果把产生随机数 读文件 写文件 几种排序算法全部写在一起 读者就感觉很繁琐 所以我将 产生随机数 读文件 写文件 写在run h里 四种排序算法写在sort h里 然 后在main cpp中调用 增强可读性 压缩软件压缩软件 设计要求 设计要求 设有一个文本文件A 可以是C源程序 统计改文件中各字符频率 对各字符进 行Huffman编码 将该文件翻译成Huffman编码文件B 在将Huffman编码文件译 码成文件C 并对文件A与C进行比较 算法思想 算法思想 1 解压文件 解压文件 压缩文件时要先对源文件进行统计 统计字符的种类及出现的次数 即权值 统计完成之后 建立哈弗曼树 每次选取权值最小且无parent的结点作为左右 孩子 建成一棵二叉树 且设置新的二叉树的根结点的权值为其左右孩子的权 值之和 直至建成含有2 n 1个结点的哈弗曼树 给每种字符进行编码 按照从叶子到根的顺序求其编码 算法和图示如下 for i 0 i n i start n 1 for c i f nodep i parent f 1 c f f nodep f parent start if nodep f lchild c codes start 0 else codes start 1 strcpy nodep i code 编码完成之后 开始对源文件进行压缩 1 从源文件读一个字符 从叶子结点中找出和此字符相同的字符结点 将 其编码写入一个临时字符组 codes 2 当 codes 的长度大于等于 8 时 将其前 8 位转换成字符写入目标文件中 3 重复 1 和 2 此过程 直至读完源文件中的所有字符 4 若 codes 最后还有剩余的不足 8 位的 01 代码 则将其低位补 0 至 8 位 再写入目标文件 同时为了便于解码 将源文件的长度 FileLength 编码区的长度以及叶子结 点的个数 n 每个叶子结点的信息也存入目标文件 存储方式如下图所示 叶子结点信息 FileLength 4B Sumlength 4B 源文件编码 区 叶子数n 4B 字符 值 1B 字符的编 码位数 1B 字符的 编码 1 个结点的信息 sumlength 2 解压文件 解压文件 从被压缩的文件中读出 FileLength n 的值 以及每个叶子结点的信息 字符 字符对应的编码 开始解码 1 从被压缩的文件编码区读出一个字符 将其值转化成二进制形式 不足 8 位的高位要补 0 存入 codes 中 直至 codes 的长度不小于所有叶子结点的 编码的长度 2 用 for 循环查找出第一个和 codes 的 01 字符串匹配的叶子结点编码 将 该叶子结点的字符写入目标文件 并将 codes 的字符串前移 前移位数 该叶子 结点编码的长度 3 重复1和2过程 直至写入的字符数与源文件的长度FileLength相同 程序实现 程序实现 测试结果 测试结果 从上图可以明显看出 2 docx和3 doc的大小时一样大的 而2 zip明显比 2 docx要小很多 同理 4 h和5 h大小是一样的 而4 zip比4 h要小很多 所 Main cpp Compres