哈夫曼编码（讲义）

《哈夫曼编码（讲义）》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、哈夫曼编码(讲义)1哈夫曼编码的主要思想信息编码的主要目的是：源文件=》目标文件编码目标：目标文件长度尽可能短。两类二进制编码：（1）等长编码：各个字符的编码长度相等。优点：解码简单。缺点：编码长度可能不最短。（2）不等长编码：各个字符的编码长度不等。优点：编码长度尽可能地短。缺点：解码困难、解码结果可能不唯一。例如：传送电文“ABACCDA”–等长编码•A：00B：01C：10D：11•编码结果00010010101100，长度为14位。•解码方以两位为一字段解码。–不等长编码•原则：出现次数较多的字符编码短，次数

2、较少的字符编码长。•A：0B：00C：1D：01•编码结果000011010，长度为9位。•解码方无法解码，因为解码的结果不唯一。哈夫曼编码（同时满足代码长度短，且解码唯一）–目标：使电文总长最短。–以字符出现的次数为权，构造一棵哈夫曼树；将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列，这样得到的编码称为哈夫曼编码。–哈夫曼解码–从哈夫曼树根开始，从待译码电文中逐位取码。–若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，

3、则译出一个字符；–再重新从根出发，直到电文结束。2哈夫曼编码的算法实现步骤：•构造哈夫曼树•根据哈夫曼树求哈夫曼编码typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表voidCreateHuffmanTree(HuffmanTree&HT,int*w,intn){//w存放n个字符的权值m=

4、2*n-1;//结点个数（n2=n0-1）HT=newHTNode[m+1];//0号单元未用for(p=HT+1,i=1;p<=HT+n,++p,++w)*p={*w,0,0,0};//初始化，叶子结点占1~nfor(i=n+1;i<=m;++i,++p)*p={0,0,0,0};//n+1~m的位置放置中间结点for(i=n+1;i<=m;++i){//建哈夫曼树Select(HT,i-1,s1,s2)//在HT[1..i-1]选择parent为0，且weight//最小两个结点，其序号分别为s1和s2。HT[s

5、1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}}voidCreateHuffmanCode(HuffmanTree&HT,HuffmanCode&hc,intn){HC=newchar*[n+1];//分配n个字符串指针，放每个字符的编码cd=newchar[n];//分配求编码的工作空间for(i=1;i<=n;++i){//逐个字符求哈夫曼编码start=n

6、-1;//编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]=“0”;elsecd[--start]=“1”;}HC[i]=newchar[n-start];//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码到HC}deletecd;}