实验四哈夫曼树与哈夫曼编码

1、实验四 哈夫曼树与哈夫曼编码一、实验内容问题描述已知 n 个字符在原文中出现的频率，求它们的哈夫曼编码。基本要求1. 初始化：从键盘读入 n 个字符，以及它们的权值，建立 Huffman树。（具体算法可参见教材 P147 的算法 6.12 ）2. 编码：根据建立的 Huffman 树，求每个字符的 Huffman 编码。对给定的待编码字符序列进行编码。二、概要设计算法设计：要是实现哈夫曼树的操作， 首先创建一个哈夫曼树， 在创建哈夫 曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在 建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两 个结点的权值和作为新的权值，再选择两个权值最小

2、的作为新的 两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进行编 码，在编码过程中，先找到根，然后遍历，左孩子用 0 标记，右 孩子用 1 标记，最后将编码好的哈夫曼树进行输出，就可以知道 哈夫曼树的编码了流程图:算法:Huffma ntree(Huffma nTree&H T,i nt*w,i nt 切,char *e)*hc, 主函数fCHuffma ncode(Huffma nTree&H T,Huffma node &HC,int丿outputHuffma n(Huffma nTreeHT, i nt m)/ select(Huffma nTree *ht,int n,int *s

3、1, int*s2)I J模块:在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下：首先建立一个哈夫曼树和哈夫曼编码的存储表示：typedef struct int weight;int pare nt,lchild,rchild;char elem;HTNode,*Huffma nTree;/动态分配数组存储赫夫曼树typedef char *Huffma nCode;/动态分配数组存储赫夫曼编码表 CrtHuffmanTree(HuffmanTree *ht , int *w, int n): w 存放n个字符的权值，构造哈夫曼树 HT。先将叶子初始化，再将非叶子结点初始化，

4、然后构造哈夫曼树构造哈夫曼树:for(i=n+1;i=m;+i)为0且weight最小的两个/ 在 HT1 i选择 pare ntSelect(HT,i-1,&s1,&s2);HTs1.pare nt=i;HTs2.pare nt=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HT：在所给的 Select(HuffmanTree &HT,int n,int *s1,int *s2)权值中，选择出权值最小的两个值。int i, min;for(i=1;i=n;i+)if(HTi.parent=0)min=i;i=n+1;for(i=1;

5、i=n;i+)if(HTi.parent=0) if(HTi.weightHTmin.weight)min=i;*s1=min;在选择 s2 的时候和 s1 相似，只有在判断是否为最小的时候就， 要加上一个条件： if(HTi.parent=0&i!=*s1) ，就可以了， 否则，选出来的最小权值和 s1 就相等了， 失去了选择的意义了。 CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n)：从叶子到根逆向求编码：左孩子为 0，右孩子为 1 ，这样一直循环 下去，而最重要的 是：for(int i=1;i=n;+i)star=n-1; / 从右

6、向左逐位存放编码，首先存放编码结束符 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/ 从 叶 子 到根结点求编码if(HTf.lchild=c)cd-star=0; / 左分支标 0elsecd-star=1;/ 右分支标 1HCi=new charn-star; / 为第 i 个编码分配空间 strcpy(HCi,&cdstar);/ 从 cd 复制编码串到 HCoutputHuffman(HuffmanTreeHT, int m):显示出哈夫曼树的编码和字符以及权重，与二叉树的遍历相似：if(m!=0)coutHTm.elemHTm.weighte

7、 ndl;outputHuffma n(HT,HTm.lchild);outputHuffma n(HT,HTm.rchild);三、测试数据测试一：字符为：A B C 权重：10 12 8测试数据二：字符为：ABCDEFG 权重为：7 8 8 12 15 9 6四、结果调试调试一:调试二:IIlf/tM的权值汐 字符沖个元素的权值油孑个元素的权值譚3个字符* C4个元素的权值=加4 个 $g=D个元義的权值曲石5木字舘E6个元素的权值沔6个字隆五.总结在进行这个程序的编写的时候，其实有点毫无头绪，只是知道 在书上的算法就可以编写成功。但是在一次又一次的过程，还是 一次又一次的错误，最后在进行

8、理解才稍微理解了哈夫曼树的编 码过程，但是选择权值最小的过程还是不太理解，进行了调试才 明白也一些，但是还是没有明白透彻。在这次的实验过程中，我 明白了调试的重要性，不要在自己遇到问题的时候就去问同学， 因为那样会养成自己的依赖性，在自己不会的时候，不会进行深 层次的了解就去问，那样对自己没有太大的提高，只有自己理解 和同学的讲解相结合，才能有所提高。六、附录：#include#include typedef struct int weight;int parent,lchild,rchild;char elem;HTNode,*HuffmanTree;/ 动态分配数组存储赫夫曼树 typed

9、ef char *HuffmanCode;/ 动态分配数组存储赫夫曼编码表 / 求赫夫曼编码void Select(HuffmanTree &HT,int n,int *s1,int *s2)int i, min;for(i=1;i=n;i+)if(HTi.parent=0)min=i;i=n+1;for(i=1;i=n;i+)if(HTi.parent=0) if(HTi.weightHTmin.weight) min=i;*s1=min;for(i=1; i=n; i+)if(HTi.parent = 0 & i!=*s1)min = i;i = n+1;for(i=1;i=n;i+)if

10、(HTi.parent=0&i!=*s1) if(HTi.weightHTmin.weight)min=i;*s2=min;/void Huffmantree(HuffmanTree &HT,int*w,int n,char *e)HC /w 存放 n 个字符的权值，构造赫夫曼树HT ，并求出 n 个字符的赫夫曼编码int m,i,s1,s2;if(n=1) return;m=2*n-1;/ 总的结点HT=new HTNodem+1;for(i=1;i=n;+i)/*1-n 号放叶子结点，初始化 */ HTi.weight=wi; HTi.lchild=0; HTi.rchild=0; HTi

11、.parent=0; HTi.elem=ei; for(i=n+1;i=m;+i)/* 非叶子结点初始化 */ HTi.weight=0; HTi.lchild=0; HTi.rchild=0; HTi.parent=0; HTi.elem=0;for(i=n+1;i=m;+i)/在HT1 i选择pare nt为0且weight 最小的两个Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/void CHuffmanc

12、ode(HuffmanTree &HT,HuffmanCode &HC,int n)char *cd;int c,f,star;HC=new char*n+1;cd=new charn;cdn-1=0;/ 编码结束符for(int i=1;i=n;+i)star=n-1; / 从右向左逐位存放编码，首先存放编码结束符 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/ 从叶子到根结点 求编码if(HTf.lchild=c)cd-star=0; /左分支标 0elsecd-star=1;/ 右分支标 1HCi=new charn-star; / 为第 i 个编码分配空间 strcpy(HCi,&cdstar);/ 从 cd 复制编码串到 HC delete cd;/ 释放工作空间for(i=1;i=n;i+)coutHTi.elem HTi.weight:HCiendl;/ / void outputHuffman(HuffmanTree HT, int m)if(m!=0)coutHTm.elem HTm.weightendl; outputHuffman(HT,HTm.lchild);outputHuffman(HT,HTm.rchild);void main()HuffmanTree HT;HuffmanCode HC