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

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

2、夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。流程图：算法:主函数Huffmantree(HuffmanTree&HT,int*w,int'n,char*e)*hc,CHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intJoutputHuffman(HuffmanTreeHT,intm)<Jselect(HuffmanTree*ht,intn,int*s1,int*s2)<J模块：在分析了实验要求和算法分析之后，将

3、程序分为四个功能函数，分别如下：首先建立一个哈夫曼树和哈夫曼编码的存储表小：typedefstruct(intweight;intparent,lchild,rchild;charelem;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedefchar*HuffmanCode;/动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree*ht,int*w,intn):w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。构造哈夫曼树：开始叶子初始化非叶子初始化调用select函数选择权值最小的两个这两个权

4、值最小的两个字符非别作为同一个结点的左右孩子，其父母的权值为两个字符的权值之和结束for(i=n+1;i<=m;+i)(/在HT1i选择parent为0且weight最小的两个Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTSelect(HuffmanTree&HT,intn,int*s1,int*s2):在所给的权值中，选择出权值最小的两个值。inti,min;for(i=1;i<=n;i+)if(

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

6、重要的是：for(inti=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=newcharn-star;/为第i个编码分配空间strcpy(HCi,&cdstar);/从cd复制编码串到HCoutputHuffman(HuffmanTreeHT,intm):显小出哈夫曼树的编码和字符以及权重，与二义

7、树的遍历相似：if(m!=0)(cout<<HTm.elem<<""<<HTm.weight<<endl;outputHuffman(HT,HTm.lchild);outputHuffman(HT,HTm.rchild);三、测试数据测试一：字符为：ABC权重：10128测试数据二：字符为：ABCDEFG权重为：788121596四、结果调试调试一：调试二:1入入入入JA1A彖月2-7BLDi值宜值值值直权权权权权权向A白B巨C白D付E国F向G-*.-3-.-素符素寥符素符素符素符需言兀字元空兀字无字元字元字一兀字一f个个f个

8、个*个个丰1122334455667?一言与WR®豪入入入入入A-A-入入入入入兀入五. 土个充豢的=i个字符，n2个兀素的权值：122个字符,B3个元素的极值：83个字符7总结在进行这个程序的编写的时候，其实有点毫无头绪，只是知道在书上的算法就可以编写成功。但是在一次乂一次的过程，还是一次乂一次的错误，最后在进行理解才稍微理解了哈夫曼树的编码过程，但是选择权值最小的过程还是不太理解，进行了调试才明白也一些，但是还是没有明白透彻。在这次的实验过程中，我明白了调试的重要性，不要在自己遇到问题的时候就去问同学，因为那样会养成自己的依赖性，在自己不会的时候，不会进行深层次的了解就去问，那样

9、对自己没有太大的提高，只有自己理解和同学的讲解相结合，才能有所提高。六、附录：#include<iostream.h>#include<string.h>typedefstruct(intweight;intparent,lchild,rchild;charelem;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedefchar*HuffmanCode;/动态分配数组存储赫夫曼编码表/求赫夫曼编码voidSelect(HuffmanTree&HT,intn,int*s1,int*s2)(inti,min;for(i=1;i<=n;

10、i+)(if(HTi.parent=0)(min=i;i=n+1;for(i=1;i<=n;i+)(if(HTi.parent=0)(if(HTi.weight<HTmin.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(HTi.parent=0&&i!=*s1)(if(HTi.weight<HTmin.weight)min=i;*s2=min;/voidHuffmantree(Huffman

11、Tree&HT,int*w,intn,char*e)(/w存放n个字符的权值，构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCintm,i,s1,s2;if(n<=1)return;m=2*n-1;/总的结点HT=newHTNodem+1;for(i=1;i<=n;+i)(/*1-n号放叶子结点，初始化*/HTi.weight=wi;HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.elem=ei;for(i=n+1;i<=m;+i)/*非叶子结点初始化*/HTi.weight=0;HTi.lchild=0;HTi.rchild=0

12、;HTi.parent=0;HTi.elem=0;for(i=n+1;i<=m;+i)/充HT1i彼择parent为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;/voidCHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn)char*cd;intc,f,star;HC=newchar*n+1;cd=newch

13、arn;cdn-1='0'/编码结束符for(inti=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=newcharn-star;/为第i个编码分配空间strcpy(HCi,&cdstar);/从cd复制编码串到HCdeletecd;/释放工作空间for(i=1;i<=n;

14、i+)cout<<HTi.elem<<""<<HTi.weight<<”:"<<HCi<<endl;/voidoutputHuffman(HuffmanTreeHT,intm)if(m!=0)cout<<HTm.elem<<""<<HTm.weight<<endl;outputHuffman(HT,HTm.lchild);outputHuffman(HT,HTm.rchild);voidmain()HuffmanTreeHT;HuffmanCodeHC;int*w;char*e;charc;inti,n,m,wei;cout<<"请输入赫夫曼树的带权数目："cin>>n;w=newintn+1;e=newcharn+1;for(i=1;i<=n;i+)cout<&