5.2哈夫曼树.ppt

第五章哈夫曼树HuffmanTree 潘理panli hnist 信息与通信工程学院湖南理工学院2020 1 27 2 目标 熟悉哈夫曼树构造方法及熟悉哈夫曼编码译码应用 3 Huffman最优二叉树 Huffman树 n个外部 叶子 结点 权值为 w1 w2 w3 wn 构造一棵二叉树 使得所有外部结点的带权路径长度最小 例 给4个叶子结点 权为 2 3 4 11 53 2 2 11 2 3 2 4 2 40 4 Huffman最优二叉树 Huffman树 n个外部 叶子 结点 权值为 w1 w2 w3 wn 构造一棵二叉树 使得所有外部结点的带权路径长度最小 例 给4个叶子结点 权为 2 3 4 11 11 4 2 3 11 4 2 2 3 3 34 5 Huffman最优二叉树 最优二叉树的特征 权越小的外部结点离根越远 Huffman构造方法 贪心策略 自底向上 6 7 Huffman算法 n个外部结点 初始时 孤立形成n棵树 每次选择根结点权值最小的两棵树 进行合并 权值之和构成合并后的根 每次合并 减少1棵树 故一共需合并n 1次 5 29 7 8 14 23 3 11 8 例题 8个叶子结点 权值W 5 29 7 8 14 23 3 11 构造huffman树 5 29 7 8 14 23 3 11 9 例题 8个叶子结点 权值W 5 29 7 8 14 23 3 11 构造huffman树 3 29 7 8 14 23 5 11 8 10 例题 8个叶子结点 权值W 5 29 7 8 14 23 3 11 构造huffman树 3 29 7 8 14 23 5 11 8 15 11 例题 8个叶子结点 权值W 5 29 7 8 14 23 3 11 构造huffman树 3 29 7 14 23 5 8 15 11 8 19 12 例题 8个叶子结点 权值W 5 29 7 8 14 23 3 11 构造huffman树 3 29 7 23 5 8 15 11 8 19 14 29 13 例题 8个叶子结点 权值W 5 29 7 8 14 23 3 11 构造huffman树 3 29 7 5 8 15 11 8 19 14 29 23 42 14 例题 8个叶子结点 权值W 5 29 7 8 14 23 3 11 构造huffman树 3 29 7 5 8 15 11 8 19 14 29 23 42 58 15 例题 8个叶子结点 权值W 5 29 7 8 14 23 3 11 构造huffman树 3 29 7 5 8 15 11 8 19 14 29 23 42 58 100 16 树的 动态 链式存储结构 17 静态链表存储结构 E A B C D F 下标作为静态指针 孩子为 1表示 父亲为 1表示 18 Huffman树构造算法 5 2 7 3 19 Huffman树构造算法 5 2 7 3 5 20 Huffman树构造算法 5 2 7 3 5 10 21 Huffman树构造算法 5 2 7 3 5 10 17 22 Huffman编码 Huffman编码树例 D A B M W 2 3 5 7 11 13 17 19 23 29 31 37 41 23 Huffman编码树 D A B M W 2 3 5 7 11 13 17 19 23 29 31 37 41 24 Huffman编码 Huffman编码树例 D A M W 2 3 5 7 11 13 17 19 23 29 31 37 41 利用Huffman算法构造出的各字符的二进制编码为 A 1011110B 1011111C 101110D 10110E 0100F 0101G 1010H 000I 001J 011K 100L2 110M 111 通信编码总长最短 L Wili 若di dj 则di不是dj的前缀编码 25 Huffman编码 字符Huffman编码表 A 1011110B 1011111C 101110D 10110E 0100F 0101G 1010H 000I 001J 011K 100L2 110M 111输入正文 ABDEH查找 字符编码表得到编码 10111101011111101100100000 26 Huffman解码 10111101011111101100100000 解码 ABDEH 27 应用举例 明文Acomputerprogramisasequenceofinstructionswrittentoperformaspecifiedtaskwithacomputer Theprogramhasanexecutableformthatthecomputercanusedirectlytoexecutetheinstructions Computersourcecodeisoftenwrittenbycomputerprogrammers Sourcecodemaybeconvertedintoanexecutablefilebyacompilerandlaterexecutedbyacentralprocessingunit 28 Huffman编码 001111010110010110011010110001000011110111011110100011011100111100111011010010101110000111101110010011011101011001111011000001100100101011110100110000011000010010111011111101100000101111100011001001011101110001111110110001111111110110010110111110011101000101110111000001001101110101110010011011101100010110101000110000000010111010011101111010011101111001000110001111100011111100001110010011001011001101011000100001111011101100110011011100100110000101111010001101110011110011101101001010111010000101001110111001000010110011001101011010100001111010010100011100001111010000010011011101011101111100001010011111101111100001011110010110011010110001000011110111011110010101000010110000011101011110101001000110110110101111111100000111011011111001110011001101011010100001111011110111110000101111000010010111011111101100000101111100011001001011101001100110111001010100110101100010000111101110111101110110010000101101010111100101100110100101111000011110111010011000001111011001011000111111011000111111111011001011010100000111011001011001101011000100001111011101111010001101110011110011101101001010110101011101111101001100110111001011100100001011010101111001011001101001011110101010100001110110101000011110010110010010001111000111011111101110100111000010010111110011100100001011001100110101101010000111101001010001110000111101000000001111000011110101000001110110010011001011001101011000100011110000111011110010000101010011101110000100111101110111100110011010110101000011110111010011101010000011101100100110010101100101111101101001110001101000110111001010101111101111010001001011100111100000001000011111001100 29 Huffman译码 Acomputerprogramisasequenceofinstructionswrittentoperformaspecifiedtaskwithacomputer Theprogramhasanexecutableformthatthecomputercanusedirectlytoexecutetheinstructions Computersourcecodeisoftenwrittenbycomputerprogrammers Sourcecodemaybeconvertedintoanexecutablefilebyacompilerandlaterexecutedbyacentralprocessingunit 30 设计思路 生成明文的 字符 权 集构造Huffman树 贪心法 自底向上 利用Huffman树 对明文进行编码利用huffman树 对编码译码为明文 31 设计思路 生成明文的 字符 权 集字符表 包括字符项和权值项 defineN30structcharcode 字符表charc 字符intw 权值 structcharcodectable N 全局变量 明文中出现的字符个数 intnum 0 32 在字符表中查找字符 在字符表中查找字符 成功找到则返回字符位置 不成功返回 1intfind charch inti for i 0 ctable i c 0 i if ctable i c ch 找到字符returni returni 未找到 33 计算字符出现频率 在字符表中查找字符 成功返回字符位置 不成功返回0voidgetweight charch freopen plaintext txt r stdin while ch getchar EOF inti find ch 查找字符位置if ctable i c 若字符表相应位置未存放字符ctable i c ch 存入字符num 字符数加1 ctable i w 权值加1 34 构造huffman树 构造Huffman树Huffman树结构 字符 权 父亲下标 左孩子下标 右孩子下标 structtreenode 静态链表charc charintw weightintf fatherintl leftchildindexintr rightchildindex N个外部结点 总结点不超过2N 1structtreenodehtree 2 N 1 35 按权值排序 使用选择法进行排序 voidsort inti j structcharcodet for i 0 i num i 每次选择最小的权值intm i m记录最小权值的下标for j i 1 j num j if ctable j w ctable m w m j t ctable m ctable m ctable i ctable i t 36 构建huffman树 使用贪心法建立huffman树 每次选择权值最小的根结点voidhuffman inti j k n for i 0 i num i 初始化哈夫曼表htree i c ctable i c htree i w ctable i w htree i l htree i f htree i r 1 j 0 j记录叶子结点的下标k num k记录内部结点的下标for n num n 2 num 1 n 每次选择权值最小intr 0 s 0 htree n l htree n f htree n r 1 37 构建huffman树 while rhtree j w 38 构建huffman树 htree n w s 父亲的权值 39 Huffman编码 Huffman编码 从plaintext txt中读入明文 生成编码 存入telegraph txt中voidencode charch freopen plaintext txt r stdin freopen telegraph txt w stdout while ch getchar EOF inti find ch charstr N getcode i str printf s str 40 Huffman编码 根据字符所在的下标 从叶子结点往上搜索到根节点 然后逆置得到该字符的huffman编码voidgetcode inti char str intn j l 0 for n i htree n f 1 n htree n f 沿着父亲往上搜索intm htree n f if n htree m l str l 0 左