《数据结构课程设计报告基于堆的哈夫曼编码问题-毕业论文》由会员分享，可在线阅读，更多相关《数据结构课程设计报告基于堆的哈夫曼编码问题-毕业论文（33页珍藏版）》请在金锄头文库上搜索。
1、东北大学信息科学与工程学院数据结构课程设计报告题目 基于堆的哈夫曼编码问题课题组长 黄红清 课题组成员 王帅 邢伟 专业名称 计算机科学与技术班级 计1307指导教师 杨雷2015 年 1月课程设计任务书题目：基于堆的哈夫曼编码问题问题描述：优先队列中的每一个元素都有一个优先级。在优先队列中，按照对象的优先级进行服务。用堆来实现优先队列可以获得较高的效率。在哈夫曼编码中，利用最小堆构造优先队列，一旦当前最小权值的两棵树合并成为一棵新树后，将新树重新插入队列中。设计要求：设计基于堆的优先队列的哈夫曼编码程序。（1）采用STL的堆、向量等数据结构。（2）用堆实现STL的优先队列类。（3）实现优先队
2、列的哈夫曼树和哈夫曼编码。指导教师签字：年月日目录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
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 课题任务【问题
4、描述】优先队列中的每一个元素都有一个优先级。在优先队列中，按照对象的优先级进行服务。用堆来实现优先队列可以获得较高的效率。在哈夫曼编码中，利用最小堆构造优先队列，一旦当前最小权值的两棵树合并成为一棵新树后，将新树重新插入队列中。【设计要求】设计基于堆的优先队列的哈夫曼编码程序。（1）采用STL的堆、向量等数据结构。（2）用堆实现STL的优先队列类。（3）实现优先队列的哈夫曼树和哈夫曼编码。1.2 课题原理利用STL设计基于堆的优先队列，应用二叉树的存储结构，并利用优先队列求得哈夫曼树和哈夫曼编码。1.3相关知识（1） STL的二叉树及其操作；（2） STL的堆及其优先队列的设计实现和操作；（3
5、） 基于堆的优先队列概念和哈夫曼树、编码的概念和编程方法；2 需求分析2.1 课题调研使用百度百科了解了什么是基于堆的优先队列，学习力STL编程方法，参考了哈夫曼树和哈夫曼编码的基本原理和知识后，进行程序设计。堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。而我们会用到最小堆：根结点的键值是所有堆结点键值中最小者。而普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出 （largest-in，first-out）的行为特征。基
6、于这样的优先队列，可以实现哈夫曼树的生成吗，进而求得哈夫曼编码。2.2 用户需求分析 哈夫曼树以及哈夫曼编码在计算机和通信领域有着相当重要的应用地位，既是压缩和解压缩的基础方法，又是通信传输的编码方案。而堆又是十分方便和快捷的一种存储结构，堆的优先队列更可以很好地实现最小元素和最大元素的出入队操作。利用优先队列来实现哈夫曼编码是一种可行的方案，对于以后的应用有着深刻的意义和重要的价值。 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统能够对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道）
7、，每段都需要一个完整的编/译系统。所以哈夫曼树和哈夫曼编码的实现，显得尤为需要。3 方案设计3.1 总体功能设计（1） 实现堆的优先队列；（2） 利用堆的优先队列实现哈夫曼树的生成，输出中序、前序（或后序）遍历结果检查哈夫曼树的正确性；（3） 利用生成的哈夫曼树实现哈夫曼编码，进一步检验其正确性；3.2 数据结构设计class MinHeap/最小堆优先队列数据结构设计private:T *heap; /元素数组，0号位置也储存元素 int CurrentSize; /目前元素个数 int MaxSize; /可容纳的最多元素个数 void FilterDown(const int start
8、, const int end); /自上往下调整，使关键字小的节点在上 void FilterUp(int start); /自下往上调整 public:MinHeap(int n = 1000);MinHeap();bool Insert(const T &x); /插入元素 T RemoveMin(); /删除最小元素 T GetMin(); /取最小元素 bool IsEmpty() const;bool IsFull() const;void Clear();templatestruct BTNode/二叉树结点的数据结构T data;BTNode *lChild, *rChild;
9、BTNode()lChild = rChild = NULL;BTNode(const T &val, BTNode *Childl = NULL, BTNode *Childr = NULL)data = val;lChild = Childl;rChild = Childr;templateclass BinaryTree/二叉树的数据结构public:BTNode *root;BinaryTree();BinaryTree();void Pre_Order();void In_Order();void Post_Order();int TreeHeight()const;int Tree
10、NodeCount()const;void DestroyTree();void MakeTree(T pData, BinaryTree leftTree, BinaryTree rightTree);void TreeCoding();private:void Destroy(BTNode *&r);void PreOrder(BTNode *r);void InOrder(BTNode *r);void PostOrder(BTNode *r);int Height(const BTNode *r)const;int NodeCount(const BTNode *r)const;voi
11、d Coding(BTNode *r);templateclass Huffman/哈夫曼树的数据结构friend BinaryTree HuffmanTree(Type, int);public:operator Type() const/类型转换操作符return weight;/private: BinaryTree tree;Type weight;3.3 函数原型设计templateMinHeap:MinHeap(int n)/最小堆构造函数templateMinHeap:MinHeap()/最小堆析构函数templatevoid MinHeap:FilterUp(int start
12、) /自下往上调整 templatevoid MinHeap:FilterDown(const int start, const int end) /自上往下调整，使关键字小的节点在上 templatebool MinHeap:Insert(const T &x)/插入结点templateT MinHeap:RemoveMin()/删除最小结点templateT MinHeap:GetMin()/获得当前最小结点templatebool MinHeap:IsEmpty() const/判空templatebool MinHeap:IsFull() const/判断堆是否已满templatevo
13、id MinHeap:Clear()/清空堆templateBinaryTree:BinaryTree()/二叉树构造函数templateBinaryTree:BinaryTree()/二叉树析构函数templatevoid BinaryTree:Pre_Order()/前序遍历二叉树，调用PreOrdertemplatevoid BinaryTree:In_Order()/中序遍历二叉树，调用InOrdertemplatevoid BinaryTree:Post_Order()/后序遍历二叉树，调用PostOrdertemplateint BinaryTree:TreeHeight()const/求树的深度templateint BinaryTr
