-数据结构-树（）

《-数据结构-树（）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第六章树第六节哈夫曼树及其应用应用实例：文件压缩、解压。一、术语路径：连接结点之间的若干分支。路径长度：路径的分支数。结点路径长度：从根到该结点的路径长度。树的路径长度：树中所有叶子结点的路径长度之和。结点带权路径长度：结点路径长度与结点权的积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。哈夫曼树（最优二叉树）:在叶子结点确定的前提下，带权路径长度最小的二叉树。仁5745724WPL二46WPL=36WPL=35经验：①没有度为1的结点。②权值越大的叶子离根越近，树的带权路径长度越小。二、构造哈夫曼树的算法已知：N个结点的权值为Wi,……,W

2、N,构造算法如下：①根据（Wb……，W、）构成森林F二（Tb……,Tx）,每棵二叉树Ti有且只有一个根结点，权为左右子树为空；②在F中选取二棵根的权值最小的树处、Tj,权为Wi、Wj,作为左右子树合成一棵新树Tk,I；的根的权W^Wi+Wj；③在F中删除花、J加入A;④重复②③，循环N-1次，F中只剩一棵树，即为哈夫曼树。示例：0.4,0.2,0.1,0.5示例：0.22,0.3,0.4,0.28三、哈夫曼编码1、信息编码的目标源文件二》目标文件编码目标：目标文件长度尽可能短。2、编码方法定长编码ABCD00011011不定长编码（统计编码）ABcD0

3、10110111统计编码原理：①基于概率分布特性；②编码长度不固定。频率高的符号用较少的位。问题1:A的编码可以为〃1〃吗？B的编码可以为〃11〃吗？前缀编码：任何符号的编码都不是另一符号编码的前缀。统计编码必须是前缀编码！问题2:编码的效率？设SI,S2,…，Sn是被编码的一组符号,Pl,P2,・・・，Pn是各自出现的概率，LI,L2,・・・，Ln是码长，则平均码长：L=工口*Pii=3、哈夫曼树中的哈夫曼编码哈夫曼树的意义：叶子：待编码的符号；权值：待编码的符号的出现频率叶子的路径：符号的哈夫曼编码记：左分支二0,右分支二1。哈夫曼编码的性质：①

4、前缀编码：各个叶子的路径决不会相互包含。②高效编码：树的带权路径长度二平均码长4、压缩/解压软件的思路设压缩单位为字节，压缩模块的设计思路：①统计源文件：0,1,……，255的出现次数二》“频率表”；②根据“频率表”构造哈夫曼树；③读取各字符的哈夫曼编码；④将“频率表”写入压缩文件头；（文件头的格式设计？）⑤翻译源文件，写入压缩文件。解压模块的设计思路：①读压缩文件头，得到“频率表”；②根据“频率表”重构哈夫曼树；③读压缩文件中的〃0/1〃串，从根搜索至叶子，将叶子对应的字符写入“解压文件”；④重复③，直至译完压缩文件。四、哈夫曼算法：建树、计算编码存

5、储结构：顺序？链式？若结点数确定：采用静态链表。若结点数不定：采用动态链表。^defineN4/*需编码的字符数*/^defineM7/*哈夫曼树的结点数二2N-1*/typedefstruct//每个字符及相应权值{charch;floatweight;}CharWeight;typedefstruet{charch;floatweight;intparent,lchild,rchild;//父结点，左、右孩子}HuffNode;typedefstruct//每个字符的编码结构{intstart;intbits[N]:}HuffCode;main()

6、{Char_WeightW[N];HuffNodeHT[M];HuffCodeHC[N];ReadWeight(W)://读入权值Huffman_Create(HT,W);//建树HT[M]Huffman_Coding(HT,HC);//读编码HC[N]voidHuffman_Create(HuffNodeHT[],Char_WeightW[]){for(i=0;i

7、・weight二W[i]・weight;}for(i=N;i

8、1-1-1lchild-1-1-1-1rchild-1-1-1-1完建状态下标0123456c