数据结构课设用哈夫曼实现软件压缩.doc

南京师范大学 《数据结构》课程设计报告 姓 名： 学 号： 学 院： 计算机科学与技术学院 题 目： 排序算法比较与压缩软件的实现 指导教师： 二〇一四年九月一日 目录 TOC \o "1-3" \h \z \u 必做题 3 一、 设计内容 3 二、 设计思想描述 3 1 希尔排序 3 2 快速排序 3 3 堆排序 4 4 二路归并排序 7 三、 程序结构 8 1 类设计 8 2 主程序设计 8 3 流程图 9 四、 系统环境与程序测试案例 9 五、 设计中遇到的问题及解决方案 12 1 测时间的函数不准确 12 其他测试运行时间的方式： 13 2什么是“真随机”，什么是“伪随机”？ 14 3 如何根据文档结构图生成目录 14 六、 参考文献 15 选做题 15 一、 设计内容 15 二、 设计思想描述 15 1 Huffman树与Huffman编码 15 2 Huffman算法的思想 15 3 现有的压缩软件及其压缩比 16 三、 程序结构 17 1 类设计 17 2 主程序设计 18 3 流程图 20 四、 系统环境与程序测试案例 20 五、 设计中遇到的问题及解决方案 23 六、 收获与体会 24 七、 参考文献 24 必做题 设计内容 编程实现希尔、快速、堆排序、归并排序算法。要求随机产生10000个数据存入磁盘文件，然后读入数据文件，分别采用不同的排序方法进行排序，并将结果存入文件中。 设计思想描述 1 希尔排序 希尔排序是对直接插入排序的改进。基本思想是先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组，所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。 举例 已知数据序列为（12， 5， 9， 20， 6， 31， 24），对该数据序列进行希尔排序： 12 12 5 9 20 6 31 24 12 5 9 20 6 31 24 5 6 9 12 20 24 31 初始键值序列 第一趟排序结果（d1=3） ） 第二趟排序结果（d2=1） ） 具体代码见 Sort代码.txt！ 2 快速排序 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 举例 已知数据序列为（12， 5， 9， 20， 6， 31， 24），对该数据序列进行快速排序： 一次划分 12 12 5 9 20 6 31 24 12 5 9 20 6 31 24 12 5 9 20 6 31 24 6 5 9 20 12 31 24 6 5 9 20 12 31 24 6 5 9 20 12 31 24 6 5 9 12 20 31 24 对轴值两侧分别进行快速排序 6 6 5 9 6 5 9 5 6 9 5 9 20 31 24 20 31 24 31 24 24 24 31 3 堆排序 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父结点。 举例 已知数据序列为（12， 5， 9， 20， 6， 31， 24），对该数据序列进行堆排序： 初始：5 初始： 5 12 9 24 20 6 31 1 1 调整成小根堆 6 5 9 24 20 12 31 2 5 2 5与24换 6 24 9 5 20 12 31 3 调整成小根堆 12 6 9 5 20 24 31 12 311 9 5 20 24 6 5 调整成小根堆 12 9 31 5 20 24 6 4 6与31换 12 12 241 9 5 20 31 6 7