哈夫曼编码Word文档下载推荐.docx

1、执行结果 14十一：体会感想 16哈夫曼树给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffman tree）。（1）路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 （2）结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。（3）树的带权路径长度 树的带权路径长度规定为所有叶子结

2、点的带权路径长度之和，记为WPL。哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、wn，则哈夫曼树的构造规则为：（1） 将w1、w2、，wn看成是有n 棵树的森林（每棵树仅有一个结点）；（2） 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；（3）从森林中删除选取的两棵树，并将新树加入森林；（4）重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。哈夫曼编码（Huffman Coding）是一种编码方式，哈夫曼编码是可变字长编码（VLC）的一种。Huffma

3、n于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。哈夫曼算法伪代码1. 数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1；2. 数组huffTree的前n个元素的权值置给定权值wn；3. 进行n-1次合并3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2；3.2 将二叉树i1、i2合并为一棵新的二叉树k；哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代

4、。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 程序功能及输入输出要求：控制台输入需编码的字符个数,分别输入字符符号以及权值后，进行哈夫曼编码，将编码结果输出到txt文件中。编码结束后，可在控制台输入0,1字符串进行解码，若解码成功，输出解码结果。（1）：编程软件 Microsoft Visual Studio 2010（2）：使用C+语言，自定义HuffmanCode类，在头文件HuffmanCode.h中。如下如：自定义类使用的字段，方法以及嵌套类型图1：HuffmanCode类的定义（3）：HuffmanCode类的实现，在HuffmanCod

5、e.cpp文件中，如图图2：HuffmanCode类的实现（4）：HuffmanCode主程序，在HuffmanCodeMain.cpp文件中，如图图3：主程序详细设计如图HuffmanCode类中的公有成员：HuffmanCode（）;主要进行初始化，申请所需内存空间，对字符命名及赋予权值；HuffTree（）;由初始化后的信息构造哈夫曼树；Huff_Encode（）;对字符进行哈夫曼编码；Huff_Decode（）;对二进制信息进行哈夫曼解码；HuffCode（string &CharacterCode）;哈夫曼解码算法，供成员Huff_Decode（）调用；Ele_Path（int n,

6、bool child）;供解码函数调用，返回下一个儿子结点所在下标；HuffmanCode（）; 析构函数，释放内存空间 HuffmanCode类中的私有成员：struct Element string name; int flag; T Ele_Weight; int l_child,r_child,parent; ;用于存放结点信息，即字符名称、标记、权值、左孩子、右孩子、双亲；int Num;字符个数；Element *Elements;一个指向Element结构体的指针；string *Code;所需解码的字符串指针；调试与测试n个字符进行哈夫曼编码，需2n-1个结点，在进行下标遍历时

7、要注意，结点个数是2n-1但最后一个结点的下标是2n-2,否则地址出错，产生不可预测的结果；执行解码时，由输入的0,1字符串判断下一个结点是左孩子还是右孩子，当浏览至叶子结点时，一定要把指针或者下表指向2n-1个结点（根节点）的位置，下表2n-2，否则会出错，导致解码失败；执行n-1次合并时，参与过运算的结点一定要改变标记值，否则下次遍历会再次参与运算，导致结果错误。程序源代码（1）HuffmanCode.h#include using std:string;/HuffmanCode.h 声明类HuffmanCode#ifndef HuffmanCode_H#define HuffmanCod

8、e_Htemplate class HuffmanCodepublic: HuffmanCode（）;/构造函数，HuffTree初始化 void HuffTree（）;/构造哈夫曼树 void Huff_Encode（）;/哈夫曼编码函数 void Huff_Decode（）;/解码函数 void HuffCode（string &/解码算法 int Ele_Path（int n,bool child）;/供解码函数嵌套调用，返回下一个儿子结点下标 /n代表当前结点下标，child代表下一结点所在下标 HuffmanCode（）; /析构函数private: struct Element/编

9、码的字符 /标记/权值/左孩子，右孩子，双亲 int Num; Element *Elements; string *Code;/存放计算出字符哈夫曼编码;#endif（2）HuffmanCode.cpp#include stdafx.h#includeHuffmanCode.h/无参构造函数，确定字符数目n，并初始化2*n-1个结点HuffmanCodeHuffmanCode（） /输入一个大于2的整数 do coutNum; while（Num 2）; /新建2*Num-1个结点 Elements = new Element2*Num-1; for（int i = 0;i 2*Num-1;

10、i+） Elementsi.name = Elementsi.Ele_Weight = 0; Elementsi.flag = 0; Elementsi.parent = -1; Elementsi.l_child = -1; Elementsi.r_child = -1; Num;Please input the name of NO.i+1 characters name:Elementsi.name;Please input weight of NO. character:Elementsi.Ele_Weight; /Text cout coutThe data structure be

11、for compute is:endl;setw（4）Namesetw（10）Weight setw（8）FlagParentsetw（15）Left_childRight_childElementsi.flag;Elementsi.parent;Elementsi.l_child;Elementsi.r_child;templatevoid HuffmanCodeHuffTree（） int i=0, MIN_1,MIN_2, /最小与次小元素下标 MIN_W1,MIN_W2; /最小元素与次小元素的权值 for（ i; iNum-1; i+ ） /n-1次合并 MIN_W1 = MIN_W

12、2 =INT_MAX; / climits 中定义的常量值 MIN_1 = MIN_2 = 0; /下标0开始 /在森林中找两个权值最小的结点 for（int j = 0; j Num+i; j+）/注意：是Num+i 不是Num+1 if（Elementsj.flag = 0） /该点未加入HuffmanTree中 if（Elementsj.Ele_Weight MIN_W1） MIN_W2 = MIN_W1; MIN_2 = MIN_1; MIN_W1 = Elementsj.Ele_Weight; MIN_1 = j; else if（Elementsj.Ele_Weight MIN_W

13、2） MIN_W2 = Elementsj.Ele_Weight; MIN_2 = j; /确定两个最小结点的双亲 ElementsMIN_1.parent = Num+i; ElementsMIN_2.parent = Num+i; /标记已加入HuffTree中 ElementsMIN_1.flag = 1; ElementsMIN_2.flag = 1; ElementsNum+i.Ele_Weight = ElementsMIN_1.Ele_Weight + ElementsMIN_2.Ele_Weight; ElementsNum+i.l_child = MIN_1; Element

14、sNum+i.r_child = MIN_2;Huff_Encode（） /申请编码所需空间并初始化 Code = new stringNum; i+） Codei= /计算第i个结点的HuffMan编码 T Code_Weight = 0; int child = 0; int parent = 0; i+） Code_Weight = Elementsi.Ele_Weight; child = i; parent = Elementsi.parent; /回溯 string temp; while（parent != -1） temp = （Elementsparent.l_child =

15、 child）?01 Codei.insert（0,temp）; child = parent; parent = Elementschild.parent; /输出结果The characters Code Elementsi.name is CodeiHuff_Decode（） /求字符编码最长的长度 string:size_type MAX_Length = 0;Element s size is Codei.size（） MAX_Length） MAX_Length = Codei.size（）;The maximum length of code is MAX_Length /求字符

16、编码最小的长度size_type MIN_Length = MAX_Length; if（Codei.size（） MIN_Length） MIN_Length = Codei.size（）;The minimum length of code is MIN_LengthDecode）;CharacterCode） string temp = int Ele_Num = 2*Num-2;/注意：元素个数是2*Num-1，但根结点下标是2*Num-2，否则参数传递时地址出错 for（string:size_type Length = 0; Length CharacterCode.size（）;

17、 Length+） if（CharacterCodeLength = 0）/该字符为0 Ele_Num = Ele_Path（ Ele_Num, false）; if（ElementsEle_Num.l_child = -1 & ElementsEle_Num.r_child =-1） temp += ElementsEle_Num.name; Ele_Num = 2*Num-2;/返回HuffmanTree的根结点 else if（CharacterCodeLength = 1）/该字符为1 Ele_Num = Ele_Path（ Ele_Num, true）; ElementsEle_Nu

18、m.r_child = -1） else/输入编码中带有0,1以外的字符 cerrThe code have been made wrong. Ele_Num = 0;/这里Ele_Nun可以是任意一个 ！= 2*Num-2的值 break; /译码输出 if（Ele_Num = 2*Num-2）Code CharacterCodetemp else cerr has been wrong.int HuffmanCodeEle_Path（int n , bool child） if（child=false） return Elementsn.l_child; else return Eleme

19、ntsn.r_child;HuffmanCode（） delete Elements; Elements = NULL; delete Code; Code = NULL;（3）HuffmanCodeMain.cpp/ HuffmanCodeMain.cpp : 定义控制台应用程序的入口点。/#includeclimitsiomanipHuffmanCode.cppcin;cerr;cout;setw;int _tmain（int argc, _TCHAR* argv） HuffmanCode a; a.HuffTree（）; a.Huff_Encode（）; a.Huff_Decode（）;

20、 a.HuffmanCode（）; return 0;执行结果（1）如图4，运行主程序，输入字符个数及名称后，指向Element结构体的指针指向一段具有2n-1个结构体的连续内存空间；图4：输入字符个数及名称（2）数据在内存中结构如图5图5：初始化字符个数及名称后的数据结构（3）随后生成哈夫曼树，在内存中结构如图6：图6:生成后的哈夫曼树由哈夫曼树对字符进行编码并输出编码长度等信息：图7：生成编码解决方案输出编码结果到HuffmanCode.txt文件中，如图8；图8：输出编码结果到HuffmanCode.txt文件中（5）：解码，若输入无误，则输出解码结果（注：Ctrl+Z结束解码）图9：哈

21、夫曼解码体会感想经过这次数据结构课程设计，使我更加深刻体会了数据结构在实际应用中的作用，有效地组织好数据结构，可以有效地使系统高效率地执行。而且通过开始的类的设计，程序的流程设计，以及后来类的具体实现，更使我深刻了解了更多C+语言的精妙之处，而且经历多次的调试，更加知道了程序的执行流程。由于这次课程设计很早就得到了自己需要做的题目，因此有很长的时间准备，C+中最重要的指针部分也是我这次调试中问题最多的，但是最终都修改正确。4、参考文献1王红梅数据结构（C+版）清华大学出版社2谭浩强C+程序设计清华大学出版社3王红梅数据结构学习辅导与实验指导清华大学出版社4Stanley B.Lippman Josee La