83哈夫曼编码

第五章哈夫曼树HuffmanTree信息与通信工程学院湖南理工学院2020/1/292目标熟悉哈夫曼树构造方法及熟悉哈夫曼编码译码应用3Huffman最优二叉树Huffman树：n个外部（叶子）结点，权值为{w1,w2,w3,…,wn}，构造一棵二叉树，使得所有外部结点的带权路径长度最小。例：给4个叶子结点，权为{2,3,4,11}2113441132532*2+11*2+3*2+4*2=404Huffman最优二叉树Huffman树：n个外部（叶子）结点，权值为{w1,w2,w3,…,wn}，构造一棵二叉树，使得所有外部结点的带权路径长度最小。例：给4个叶子结点，权为{2,3,4,11}1142311+4*2+(2+3)*3=345Huffman最优二叉树最优二叉树的特征：权越小的外部结点离根越远。Huffman构造方法：贪心策略+自底向上114233467Huffman算法n个外部结点，初始时，孤立形成n棵树。每次选择根结点权值最小的两棵树，进行合并，权值之和构成合并后的根。每次合并，减少1棵树，故一共需合并n-1次。5297814233118例题8个叶子结点，权值W={5,29,7,8,14,23,3,11}构造huffman树。5297814233119例题8个叶子结点，权值W={5,29,7,8,14,23,3,11}构造huffman树。329781423511810例题8个叶子结点，权值W={5,29,7,8,14,23,3,11}构造huffman树。32978142351181511例题8个叶子结点，权值W={5,29,7,8,14,23,3,11}构造huffman树。3297142358151181912例题8个叶子结点，权值W={5,29,7,8,14,23,3,11}构造huffman树。329723581511819142913例题8个叶子结点，权值W={5,29,7,8,14,23,3,11}构造huffman树。32975815118191429234214例题8个叶子结点，权值W={5,29,7,8,14,23,3,11}构造huffman树。3297581511819142923425815例题8个叶子结点，权值W={5,29,7,8,14,23,3,11}构造huffman树。3297581511819142923425810016树的(动态)链式存储结构左孩子数据右孩子ABCDEFEABCDF17静态链表存储结构EABCDF数据父亲左孩子右孩子0A-1121B0342C05-13D1-1-14E1-1-15F2-1-1下标作为静态指针孩子为-1表示？父亲为-1表示？18Huffman树构造算法5273权父亲左孩右孩05-1-1-112-1-1-127-1-1-133-1-1-14-1-1-15-1-1-16-1-1-119Huffman树构造算法5273权父亲左孩右孩05-1-1-1124-1-127-1-1-1334-1-145-1135-1-1-16-1-1-1520Huffman树构造算法5273权父亲左孩右孩055-1-1124-1-127-1-1-1334-1-145513510-1046-1-1-151021Huffman树构造算法5273权父亲左孩右孩055-1-1124-1-1276-1-1334-1-145513510604617-1255101722Huffman编码Huffman编码树例：D={A,B…,M}W={2,3,5,7,11,13,17,19,23,29,31,37,41}239501143012380152301AB10501C1770D24111301EF134170G23421901HI295301J653101K781374110LMHuffman编码树D={A,B…,M}W={2,3,5,7,11,13,17,19,23,29,31,37,41}24Huffman编码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:1111)通信编码总长最短;（L=∑Wili）2)若di≠dj,则di不是dj的前缀编码。25Huffman编码字符Huffman编码表：A:1011110B:1011111C:101110D:10110E:0100F:0101G:1010H:000I:001J:011K:100L2:110M:111输入正文：ABDEH查找：字符编码表得到编码：1011110101111110110010000026Huffman解码9501143012380152301AB10501C1770D24111301EF134170G23421901HI295301J653101K781374110LM10111101011111101100100000解码：ABDEH27应用举例明文Acomputerprogramisasequenceofinstructionswrittentoperformaspecifiedtaskwithacomputer.Theprogramhasanexecutableformthatthecomputercanusedirectlytoexecutetheinstructions.Computersourcecodeisoftenwrittenbycomputerprogrammers.Sourcecodemaybeconvertedintoanexecutablefilebyacompilerandlaterexecutedbyacentralprocessingunit.28Huffman编码00111101011001011001101011000100001111011101111010001101110011110011101101001010111000011110111001001101110101100111101100000110010010101111010011000001100001001011101111110110000010111110001100100101110111000111111011000111111111011001011011111001110100010111011100000100110111010111001001101110110001011010100011000000001011101001110111101001110111100100011000111110001111110000111001001100101100110101100010000111101110110011001101110010011000010111101000110111001111001110110100101011101000010100111011100100001011001100110101101010000111101001010001110000111101000001001101110101110111110000101001111110111110000101111001011001101011000100001111011101111001010100001011000001110101111010100100011011011010111111110000011101101111100111001100110101101010000111101111011111000010111100001001011101111110110000010111110001100100101110100110011011100101010011010110001000011110111011110111011001000010110101011110010110011010010111100001111011101001100000111101100101100011111101100011111111101100101101010000011101100101100110101100010000111101110111101000110111001111001110110100101011010101110111110100110011011100101110010000101101010111100101100110100101111010101010000111011010100001111001011001001000111100011101111110111010011100001001011111001110010000101100110011010110101000011110100101000111000011110100000000111100001111010100000111011001001100101100110101100010001111000011101111001000010101001110111000010011110111011110011001101011010100001111011101001110101000001110110010011001010110010111110110100111000110100011011100101010111110111101000100101110011110000000100001111100110029Huffman译码Acomputerprogramisasequenceofinstructionswrittentoperformaspecifiedtaskwithacomputer.Theprogramhasanexecutableformthatthecomputercanusedirectlytoexecutetheinstructions.Computersourcecodeisoftenwrittenbycomputerprogrammers.Sourcecodemaybeconvertedintoanexecutablefilebyacompilerandlaterexecutedbyacentralprocessingunit.30设计思路1.生成明文的{字符+权}集2.构造Huffman树（贪心法+自底向上）3.利用Huffman树，对明文进行编码4.利用huffman树，对编码译码为明文31设计思路1.生成明文的{字符+权}集字符表：包括字符项和权值项。#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}ctab