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