《数据结构（C语言描述）（第2版）》教学课件4-15构造哈夫曼编码的算法

1、2016数据结构Data structure讲授：刘斌构造哈夫曼编码的算法常州信息职业技术学院02教学目标12哈夫曼编码算法的算法思想03哈夫曼编码算法的算法实现三、链表的插入04构造哈夫曼编码的算法1.5哈夫曼树及哈夫曼编码五、求哈夫曼编码的算法思想方法给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子Ti(0in-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。cb100554525301312defa1614950110010101三、链表的插入05构造哈夫曼编码的算法1.5哈夫曼树及哈夫曼编码五、求哈夫曼编码的算法注意：（i）由于生成

2、的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时向量中，并设一个指针start指示编码在该向量中的起始位置（start初始时指示向量的结束位置）。（ii）当某字符编码完成时，从临时向量的start处将编码复制到该字符相应的位串bits中即可。（iii）因为字符集大小为n，故变长编码的长度不会超过n，加上一个结束符0，bits的大小应为n+1。06构造哈夫曼编码的算法1.5字符集编码的描述 typedef struct char ch;/存储字符char bitsn+1;/存放编码位串CodeNode;typedef CodeNode HuffmanCoden;07构造哈夫曼编码

3、的算法1.5void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H)/根据哈夫曼树T求哈夫曼编码表Hint c,p,i;/c和p分别指示T中孩子和双亲的位置char cdn+1; /临时存放编码int start;/指示编码在cd中的起始位置cdn=0;/编码结束符for(i=0;i=0) /*直至上溯到Tc是树根为止，若Tc是Tp的左孩子，则生成代码0；否则生成代码1*/ cd-start=(Tp.lchild=c)?0:1; c=p; /继续上溯 strcpy(Hi.bits,&cdstart); /复制编码位串 具体算法08构造哈夫

4、曼编码的算法1.56文件的编码和解码 有了字符集的哈夫曼编码表之后，对数据文件的编码过程是：依次读入文件中的字符c，在哈夫曼编码表H中找到此字符，若Hi.ch=c，则将字符c转换为Hi.bits中存放的编码串。cb100554525301312defa1614950110010101a：0b：100c：101d：110e：1110f：1111 待编码字符串：bcadef编码后二进制串：10010101101110111109构造哈夫曼编码的算法1.56文件的编码和解码 对压缩后的数据文件进行解码则必须借助于哈夫曼树T，其过程是：依次读入文件的二进制码，从哈夫曼树的根结点（即Tm-1）出发，若当前读入0，则走向左孩子，否则走向右孩子。一旦到达某一叶子Ti时便译出相应的字符Hi.ch。然后重新从根出发继续译码，直至文件结束。cb100554525301312defa1614950110010101a：0b：100c：101d：110e：1110f：1111 待解码二进制串：100101011011101111解码后字符串：bcadef10构造哈夫曼编码的算法1.5【课堂实践】假设通信电文使用的字符集为a，b，c，d，e，f，g，h，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，请为这8个字符设计哈夫曼编码。