数据结构 课程设计之哈夫曼编码.pdfVIP

哈夫曼编码与解码的实现

一哈夫曼树的设计思想

()

对于一组具有确定权值的叶子结点可以构出多个具有不同带权路径长度的二树，其

中具有最小带权路径长度的二树称作哈夫曼树或者最优二树。

首先给定个权值创个只含根结点的二树，得到一个二树林；再在这二树林

nn

里面找根结点的权值最小和次小的两棵树作成新的二树，其中新的二树的根结点的权值

为摆布子根结点权值之和；最后在二树林中把组合过的二树删除，再重复第二步，直到

最后就剩一颗二树的时候得到的这棵二树就是哈夫曼树。

(二)哈夫曼编码与解码的设计思想

在数据通讯中，时常要将传送的文字转换为二进制字符和组成的二进制串，称这个

01

过程为编码。与子相对的是解码或者是译码，就是用与编码相同的方式将二进制串转换称编

码前的文字的过程称作解码。在这里是通过哈夫曼树实现编码与解码的，所以称作是哈夫

曼编码与解码。

首先输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二

进制串代替它，这个过程要注意树和编码问题，其中树的问题在上面已经解决，主要看编码

的问题，就是根据我输入的字符串和权值建立相应的树模型，这一步完成那编码就已经完

成为了，最后打印就行了；然后就是解码，完成编码相应的解码就相对简单了，就是先找到

在编码的时候建的那个模型树，将编码中的二进制串再根据权值转换为相应的字符串，这

样一步步解码就行了。

以上就是通过用哈夫曼树进行哈夫曼编码与解码如何实现的主要设计思想。

-1-

哈夫曼编码与解码的实现

(一)哈夫曼树的流程图

开始

初始化哈夫曼链表

二树林

找最小和次小

的二树

组合成新的二树

删除用过的二树

不

是

是不是最后

一个二

树

是

结束

图1哈夫曼树的流程图

(二)编码与解码的流程图

开始开始

找到树的根结点

输入字符串