学位论文_数据结构报告基于堆的哈夫曼编码问题.doc

东北大学信息科学与工程学院 数据结构课程设计报告 题目 基于堆的哈夫曼编码问题 课题组长 黄红清 课题组成员 王帅 邢伟 专业名称 计算机科学与技术 班级 计1307 指导教师 杨雷 2015 年 1月 课程设计任务书 题目： 基于堆的哈夫曼编码问题 问题描述： 优先队列中的每一个元素都有一个优先级。在优先队列中，按照对象的优先级进行服务。用堆来实现优先队列可以获得较高的效率。在哈夫曼编码中，利用最小堆构造优先队列，一旦当前最小权值的两棵树合并成为一棵新树后，将新树重新插入队列中。 设计要求： 设计基于堆的优先队列的哈夫曼编码程序。 （1）采用STL的堆、向量等数据结构。 （2）用堆实现STL的优先队列类。 （3）实现优先队列的哈夫曼树和哈夫曼编码。 　　　　　　　　　　　　 指导教师签字： 年　　月　　日 目录 1 课题概述 4 1.1 课题任务 4 1.2 课题原理 4 1.3 相关知识 4 2 需求分析 5 2.1 课题调研 5 2.2 用户需求分析 5 3 方案设计 6 3.1 总体功能设计 6 3.2 数据结构设计 6 3.3 函数原型设计 8 3.4 主算法设计 10 3.5 用户界面设计 11 4 方案实现 12 4.1 开发环境与工具 12 4.2 程序设计关键技术 12 4.3 个人设计实现（按组员分工） 4.3.1 黄红清设计实现 12 4.3.2 邢伟设计实现 15 4.3.3 王帅设计实现 18 5 测试与调试 24 5.1 个人测试（按组员分工） 26 5.1.1 黄红清测试 24 5.1.2 邢伟测试 24 5.1.3 王帅测试 24 5.2 组装与系统测试 24 5.3 系统运行 24 6 课题总结 26 6.1 课题评价 26 6.2 团队协作 26 6.3 个人设计小结（按组员分工） 26 6.3.1 黄红清设计小结 26 6.3.2 邢伟设计小结 26 6.3.3 王帅设计小结 27 7 附录A 课题任务分工 28 A-1 课题程序设计分工 28 A-2 课题报告分工 30 附录B 课题设计文档（光盘） 31 B-1课程设计报告（电子版） 31 B-2源程序代码（*.H，*.CPP） 31 B-3工程与可执行文件） 31 B-4屏幕演示录像文件（可选） 31 附录C 用户操作手册（可选） 32 C.1 运行环境说明 32 C.2 操作说明 32 1 课题概述 1.1 课题任务 【问题描述】 优先队列中的每一个元素都有一个优先级。在优先队列中，按照对象的优先级进行服务。用堆来实现优先队列可以获得较高的效率。在哈夫曼编码中，利用最小堆构造优先队列，一旦当前最小权值的两棵树合并成为一棵新树后，将新树重新插入队列中。 【设计要求】 设计基于堆的优先队列的哈夫曼编码程序。 （1）采用STL的堆、向量等数据结构。 （2）用堆实现STL的优先队列类。 （3）实现优先队列的哈夫曼树和哈夫曼编码。 1.2 课题原理 利用STL设计基于堆的优先队列，应用二叉树的存储结构，并利用优先队列求得哈夫曼树和哈夫曼编码。 1.3相关知识 STL的二叉树及其操作； STL的堆及其优先队列的设计实现和操作； 基于堆的优先队列概念和哈夫曼树、编码的概念和编程方法； 2 需求分析 2.1 课题调研 使用百度百科了解了什么是基于堆的优先队列，学习力STL编程方法，参考了哈夫曼树和哈夫曼编码的基本原理和知识后，进行程序设计。 堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。而我们会用到最小堆：根结点的键值是所有堆结点键值中最小者。 而普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出 （largest-in，first-out）的行为特征。 基于这样的优先队列，可以实现哈夫曼树的生成吗，进而求得哈夫曼编码。 2.2 用户需求分析 哈夫曼树以及哈夫曼编码在计算机和通信领域有着相当重要的应用地位，既是压缩和解压缩的基础方法，又是通信传输的编码方案。而堆又是十分方便和快捷的一种存储结构，堆的优先队列更可以很好地实现最小元素和最大元素的出入队操作。利用优先队列来实现哈夫曼编码是一种可行的方案，对于以后的应用有着深刻的意义和重要的价值。 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统能够对待传输数据预先编码，在接收端