数据结构课程设计报告基于堆的哈夫曼编码问题.docVIP

东北大学信息科学与工程学院数据结构课程设计报告题目 基于堆的哈夫曼编码问题课题组长 黄红清 课题组成员 王帅 邢伟 专业名称 计算机科学与技术班级 计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相关知识（1） STL的二叉树及其操作；（2） STL的堆及其优先队列的设计实现和操作；（3） 基于堆的优先队列概念和哈夫曼树、编码的概念和编程方法；2 需求分析2.1 课题调研使用百度百科了解了什么是基于堆的优先队列，学习力STL编程方法，参考了哈夫曼树和哈夫曼编码的基本原理和知识后，进行程序设计。堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。而我们会用到最小堆：根结点的键值是所有堆结点键值中最小者。而普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出 （largest-in，first-out）的行为特征。基于这样的优先队列，可以实现哈夫曼树的生成吗，进而求得哈夫曼编码。2.2 用户需求分析 哈夫曼树以及哈夫曼编码在计算机和通信领域有着相当重要的应用地位，既是压缩和解压缩的基础方法，又是通信传输的编码方案。而堆又是十分方便和快捷的一种存储结构，堆的优先队列更可以很好地实现最小元素和最大元素的出入队操作。利用优先队列来实现哈夫曼编码是一种可行的方案，对于以后的应用有着深刻的意义和重要的价值。 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统能够对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每段都需要一个完整的编/译系统。所以哈夫曼树和哈夫曼编码的实现，显得尤为需要。3 方案设计3.1 总体功能设计（1） 实现堆的优先队列；（2） 利用堆的优先队列实现哈夫曼树的生成，输出中序、前序（或后序）遍历结果检查哈夫曼树的正确性；（3） 利用生成的哈夫曼树实现哈夫曼编码，进一步检验其正确性；3.2 数据结构设计class MinHeap/最小堆优先队列数据结构设计private:T *heap; /元素数组，0号位置也储存元素 int CurrentSize; /目前元素个数 int MaxSize; /可容纳的最多元素个数 void FilterDown(const int start, 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;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 TreeNodeCount()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;void 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) /自下往上调整 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/判断堆是否已满templatevoid MinHeap:Clear()/清空堆templateBinaryTree:BinaryTree()/二叉树构造函数templateBinaryTree:BinaryTree()/二叉树析构函数templatevoid BinaryTree:Pre_Order()/前序遍历二叉树，调用PreOrdertemplatevoid BinaryTree:In_Order()/中序遍历二叉树，调用InOrdertemplatevoid BinaryTree:Post_Order()/后序遍历二叉树，调用PostOrdertemplateint BinaryTree:TreeHeight()const/求树的深度templateint BinaryTree:TreeNodeCount()const/求树的总结点templatevoid BinaryTree:DestroyTree()/销毁二叉树templatevoid BinaryTree:TreeCoding()/二叉树编码templatevoid BinaryTree:PreOrder(BTNode *r)/前序遍历二叉树templatevoid BinaryTree:Coding(BTNode *r)/二叉树编码templatevoid BinaryTree:InOrder(BTNode *r)/中序遍历二叉树templatevoid BinaryTree:PostOrder(BTNode *r)/后序遍历二叉树templateint BinaryTree:NodeCount(const BTNode *r)const/节点计数templateint BinaryTree:Height(const BTNode *r)const/求二叉树的深度templatevoid BinaryTree:Destroy(BTNode *&r)/销毁二叉树templatevoid BinaryTree:MakeTree(T pData, BinaryTree leftTree, BinaryTree rightTree)/生成二叉树templateBinaryTree HuffmanTree(Type f, int n);/求哈弗曼树3.4 主算法设计3.5 用户界面设计采用命令行界面，提示用户输入字符、权值（频率），然后输出哈夫曼树的前序遍历和中序遍历结果，以及相应的哈夫曼编码。4 方案实现4.1 开发环境与工具采用VS2013进行C+ STL编程。4.2 程序设计关键技术（1） 最小堆优先队列的实现技术。最小堆可以每次筛选出权值最小的结点，而哈夫曼树的构造恰恰需要的就是权值最小的结点，利用最小堆的优先队列可以十分快捷地选取两个权值最小的结点从而组件哈夫曼树。（2） 哈夫曼树的生成算法。4.3 个人设计实现（按组员分工）4.3.1 黄红清设计实现 （1）主函数int main()char cN + 2 = 0 ;char ccN + 1;int fN+1;/下标从1开始 cout 输入6个字符： cc;strcat_s(c, cc);/使c下表从1开始cout 依次输入它们的频率： endl;for (int i = 1; i fi;cout 字符频率： endl;for (int i = 1; i = N; i+)cout ci : fi ;cout endl;BinaryTree t = HuffmanTree(f, N);cout 已生成哈夫曼树。 endl;cout 前序遍历哈夫曼树： endl;t.Pre_Order();cout endl;cout 中序遍历哈夫曼树： endl;t.In_Order();cout endl;cout 按前序遍历输出各点哈夫曼编码： endl;t.TreeCoding();t.DestroyTree();return 0; （2）利用最小堆的优先队列实现生成哈夫曼树 具体实现：templateBinaryTree HuffmanTree(Type f, int n)/生成单节点树 Huffman *w = new Huffmann + 1;BinaryTree z, zero;for (int i = 1; i = n; i+)z.MakeTree(i, zero, zero);wi.weight = fi;wi.tree = z;/建优先队列 MinHeapHuffman Q(n);for (int i = 1; i = n; i+) Q.Insert(wi);/反复合并最小频率树 Huffman x, y;for (int i = 1; in; i+)x = Q.RemoveMin();y = Q.RemoveMin();z.MakeTree(0, x.tree, y.tree);x.weight += y.weight;x.tree = z;Q.Insert(x);x = Q.RemoveMin();delete w;return x.tree;（3） 二叉树编码void BinaryTree:TreeCoding()Coding(root);void BinaryTree:Coding(BTNode *r)static char cN + 1 = ;static int a=N+1;if (r != NULL)strcat_s(c, 0);Coding(r-lChild);int j = 0;for (; cj != 0; j+);cj - 1 = 0;if (r-data&r-data!=a)cout data : c data;strcat_s(c, 1);Coding(r-rChild);int i = 0;for (; ci!=0; i+);ci - 1 = 0;if (r-data&r-data != a)cout data : c data;4.3.2 邢伟的设计实现我进行了最小堆的设计，用STL实现了优先队列及其基本操作：templateclass MinHeapprivate:T *heap; /元素数组，0号位置也储存元素 int CurrentSize; /目前元素个数 int MaxSize; /可容纳的最多元素个数 void FilterDown(const int start, 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();templateMinHeap:MinHeap(int n)MaxSize = n;heap = new TMaxSize;CurrentSize = 0;templateMinHeap:MinHeap()deleteheap;templatevoid MinHeap:FilterUp(int start) /自下往上调整 int j = start, i = (j - 1) / 2; /i指向j的双亲节点 T temp = heapj;while (j0)if (heapi = temp)break;elseheapj = heapi;j = i;i = (i - 1) / 2;heapj = temp;templatevoid MinHeap:FilterDown(const int start, const int end) /自上往下调整，使关键字小的节点在上 int i = start, j = 2 * i + 1;T temp = heapi;while (j = end)if (jheapj + 1)j+;if (temp = heapj)break;elseheapi = heapj;i = j;j = 2 * j + 1;heapi = temp;templatebool MinHeap:Insert(const T &x)if (CurrentSize = MaxSize)return false;heapCurrentSize = x;FilterUp(CurrentSize);CurrentSize+;return true;templateT MinHeap:RemoveMin()T x = heap0;heap0 = heapCurrentSize - 1;CurrentSize-;FilterDown(0, CurrentSize - 1); /调整新的根节点 return x;templateT MinHeap:GetMin()return heap0;templatebool MinHeap:IsEmpty() constreturn CurrentSize = 0;templatebool MinHeap:IsFull() constreturn CurrentSize = MaxSize;templatevoid MinHeap:Clear()CurrentSize = 0;4.3.3王帅的设计实现 我设计的是成员的的创建，添加，删除，组的创建，添加，删除，前序，后序，先序遍历。树的销毁。struct BTNodeT data;BTNode *lChild, *rChild;BTNode()lChild = rChild = NULL;BTNode(const T &val, BTNode *Childl = NULL, BTNode *Childr = NULL)data = val;lChild = Childl;rChild = Childr;BTNode* CopyTree()BTNode *nl, *nr, *nn;if (&data = NULL)return NULL;nl = lChild-CopyTree();nr = rChild-CopyTree();nn = new BTNode(data, nl, nr);return nn;class BinaryTreepublic:BTNode *root;BinaryTree();BinaryTree();void Pre_Order();void In_Order();void Post_Order();int TreeHeight()const;int TreeNodeCount()const;void DestroyTree();void MakeTree(T pData, BinaryTree leftTree, BinaryTree rightTree);void Change(BTNode *r);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;void Coding(BTNode *r);templateBinaryTree:BinaryTree()root = NULL;BinaryTree:BinaryTree()templatevoid BinaryTree:Pre_Order()PreOrder(root);templatevoid BinaryTree:In_Order()InOrder(root);templatevoid BinaryTree:Post_Order()PostOrder(root);templateint BinaryTree:TreeHeight()constreturn Height(root);templateint BinaryTree:TreeNodeCount()constreturn NodeCount(root);templatevoid BinaryTree:DestroyTree()Destroy(root);templatevoid BinaryTree:PreOrder(BTNode *r)if (r != NULL)cout data lChild);PreOrder(r-rChild);void BinaryTree:InOrder(BTNode *r)if (r != NULL)InOrder(r-lChild);cout data rChild);templatevoid BinaryTree:PostOrder(BTNode *r)if (r != NULL)PostOrder(r-lChild);PostOrder(r-rChild);cout data ;templateint BinaryTree:NodeCount(const BTNode *r)constif (r = NULL)return 0;elsereturn 1 + NodeCount(r-lChild) + NodeCount(r-rChild);templateint BinaryTree:Height(const BTNode *r)constif (r = NULL)return 0;elseint lh, rh;lh = Height(r-lChild);rh = Height(r-rChild);return 1 + (lhrh ? lh : rh);templatevoid BinaryTree:Destroy(BTNode *&r)if (r != NULL)Destroy(r-lChild);Destroy(r-rChild);delete r;r = NULL;void BinaryTree:MakeTree(T pData, BinaryTree leftTree, BinaryTree rightTree)root = new BTNode();root-data = pData;root-lChild = leftTree.root;root-rChild = rightTree.root;5 测试与调试5.1 个人测试（按组员分工）5.1.1 黄红清测试 （1）利用前序遍历和中序遍历的结果画图测试了哈夫曼树生成的正确性，通过调试程序，发现错误主要出现在循环控制条件上，导致缺少了结点，于是进行了修改。 （2）进行了哈夫曼编码的测试，直接在树前序遍历的基础上进行修改，遍历的同时完成哈夫曼编码的输出，与（1）相互共同检查了哈夫曼树的正确性。 5.1.2邢伟的测试 （1）用类建立的小顶堆模型，为建立哈夫曼树提供堆顶元素，方便调用。 （2）在建立小顶堆的调整过程，删除元素和插入元素时，需要不同的调整函数，自上而下的调整函数和自下而上的调整函数。 5.1.3王帅的测试 （1）在执行程序时，不可以直接调用类的私用成员函数，必须从公有处调用。（2）树的删除时应先将左右孩子删除后，再将双亲节点释放。5.2 组装与系统测试操作名称操作流程操作结果和输出输入字符从键盘键入相应数目字符字符被保存至字符数组输入权值依次输入相应字符权值，空格分开权值成功输入，显示出字符及其对应权值。并自动进行哈夫曼树和哈夫曼编码。在命令行中显示出哈夫曼树的前序遍历和中序遍历结果，以及哈夫曼编码结果。经校对正确无误。5.3 系统运行测试数据如图所示：首先输入7个结点和他们的权值（频率），此时const N已经设置为7：然后程序输出哈夫曼树遍历结果和编码结果：6 课题总结6.1 课题评价该课题设计难度较大，我们首先一起利用网络查找了有关堆的优先队列、哈夫曼树、哈夫曼编码的相关知识，接触到了一定的算法基础，然后分工合作，最终完成了程序的功能，能够输出正确的结果。但是哈夫曼编码由于时间紧张，并未采用栈来编码，而是在遍历的基础上直接输出编码结果，来检查哈夫曼树的正确与否。6.2 团队协作这次实验分为三个部分：二叉树结构设计和操作、最小堆实现和利用优先队列生成哈夫曼树和编码。我们先一起学习了STL的相关知识，利用它进行编程，二叉树的结构设计和基本操作编程，最小堆部分由组员根据相关知识进行设计，之后由组长整合并完成哈夫曼树的生成和编码。这次课题结果是简单的，但过程是具有挑战性和意义深刻的，在对课题的理解上，我们相互讨论，共同学习，在明确课题是在做什么后，进行了合理的分工，在各成员自我努力和借鉴资料后，成功编完自己的部分，然后组装到一起运行无误，让我们感受到了合作的喜悦。6.3 个人设计小结（按组员分工）6.3.1 黄红清设计小结 （1）这次设计我直接使用了组员设计好的封装好的最小堆类和二叉树类，在此基础上进行编程实现哈夫曼树，感受到了C+封装的方便之处，STL类模板对各种编程更具有普适性。（2）这次编程比较困难的地方是如何把二叉树、哈夫曼树和优先队列联系起来，我参考了网上的相关知识后，才学会了其中的关系，输入各结点的权值实际上只是一个数组，然后将权值一一建立起“小树”（单节点树）来，利用优先队列来存储这些树的结点，然后利用优先队列的相关操作实现哈夫曼树的组建，生成哈夫曼树。让我对各种数据结构通过类模板的相互联系理解更加深刻。 6.3.2邢伟设计小结 （1）将设计小顶堆各种功能放在小顶堆的类中，方便成员函数和成员之间的互相调用，通过此次实验了解类模块化的重要。 （2）对面向对象类编程有一定了解，可以实现封装，知道了面向对象对象的编程，容易分工并且实现代码重复利用。 （3）堆排列可以大大提高程序的效率。6.3.3王帅设计小结（1） 可以用一个树的前序，中序，后序 中的两个将一颗树组建出来。（2） 程序中多次利用函数的递归，使算法更加高效率。7 附录A 课题任务分工A-1 课题程序设计分工学号姓名程序设计函数原型、类功能说明20133982黄红清void BinaryTree:TreeCoding()；void BinaryTree:Coding(BTNode *r)；templateBinaryTree HuffmanTree(Type f, int n);int main()；/调用coding函数为root进行编码/通过前序遍历，当访问到叶子结点时候，输出它的编码/用优先队列生成哈夫曼树/主函数20133994邢伟void FilterDown(const int start, const int end); void FilterUp(int start); MinHeap(int