资源描述：
《哈夫曼算法详解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、构造Huffman树的方法——Huffman算法构造Huffman树步骤根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例w={5,29,7,8,14,23,3,11}514297823
2、31114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100Huffman算法实现Ch5_8.c一棵有n个叶子结点的Huffman树有2n-1个结点采用顺序存储结构——一维结构数组结点类型定义typedefstruct{intweight;intparent,lchild,rchild;}HTNode;75
3、24weightparentlchildrchild1234567a7b5c2d461118例a7b5c2d4ht[i]abcdfor(p=HT+1,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0};for(;i<=m;++I,++p)*p={0,0,0,0};7000500020004000000000000000weightparentlchildrchild1234567a7b5c2d461118ht[i]abcdfor(i=n+1;i<=m;i++){//建哈夫曼树Select(HT,i-
4、1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}7000500025004500603400000000weightparentlchildrchild123456770005600250045006634110250000weightparentlchildrchild1234567a7b5c2d461118abcdabcd770056
5、002500450066341172518016weightparentlchildrchild1234567a7b5c2d461118abcdHuffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列例要传输的字符集D={C,A,S,T,;}字符出现频率w={2,4,2,3,3}CS3364224814T;A0011011
6、0T:00;:01A:10C:110S:111译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束例电文是{CAS;CAT;SAT;AT}其编码“11010111011101000011111000011000”电文为“1101000”译文只能是“CAT”CS3364224814T;A00110110T:00;:01A:10C:110S:111
