《2022年2022年哈夫曼编码》由会员分享，可在线阅读，更多相关《2022年2022年哈夫曼编码（6页珍藏版）》请在金锄头文库上搜索。
1、哈夫曼编码I.问题描述哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1 串表示各字符的最优表示方式。II. 问题分析对每一个字符规定一个0,1 串作为其代码， 并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。设 C 为编码字符集，则表示其最优前缀码的二叉树中恰有|C|个叶子， |C|-1 个内部结点。其中，每个叶子对应于字符集中一个字符。二叉树 T 的代价：编码文件需要二进制位数使达到最小的前缀码编码方案称为给定编码字符集C 的最优前缀码。哈夫曼提出构造最优前缀码的贪心算法，由此
2、产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以 |C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。编码字符集中每一字符c 的频率是freq。以 freq 为键值的最小堆优先队列Q 用在贪心选择时有效地确定算法当前要合并的2 棵具有最小频率的树。 一旦 2 棵具有最小频率的树合并后，产生一棵新的树， 其频率为合并的2 棵树的频率之和， 并将新树插入最小堆优先队列Q。经过 n-1 次的合并后，优先队列中只剩下一棵树，即所要求的树T。III .算法描述：HUFFMAN(C) /哈夫曼编码算法n = |C| / 初始化最小优先队列Q
3、INITIALIZE(Q) = BUILD-MIN-HEAP(C) for i=1 to n-1 allocate a new node z z.left = x EXTRACT-MIN(Q) /提取队列 Q 中的最前列结点z.right = y EXTRACT-MIN(Q) z.freq x.freq + y.freq INSERT(Q, z) /在队列 Q 中插入结点z return EXTRACT-MIN(Q) 时间复杂度描述：INITIALIZE(Q) = BUILD-MIN-HEAP(C)的时间复杂度为O（n） ；循环for i=1 to n-1 的时间复杂度为O（n） ；其中，z.
4、left = x EXTRACT-MIN(Q) 和 z.right = y EXTRACT-MIN(Q) 的时间复杂度分别为O(nlogn) ；INSERT(Q, z) 的时间复杂度为O（nlogn） ；最后返回最前列结点return EXTRACT-MIN(Q)的时间复杂度也为O(nlogn) 。所以，这个哈弗曼算法的时间复杂度为T（n）=O(nlogn) 。( ).( )Tc CB Tc freq dc名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - -
5、 - - - - - - IV.程序#include #include #include typedef struct /结点结构体 unsigned int weight; /用来存放各个结点的权值 unsigned int parent,LChild,RChild; /指向双亲、孩子结点的指针 HTNode, *HuffmanTree; /动态分配数组，存储哈夫曼树typedef char *HuffmanCode; /动态分配数组，存储哈夫曼编码/ 选择两个parent为0，且 weight 最小的结点s1和 s2void Select(HuffmanTree *ht,int n,int
6、 *s1,int *s2) int i,min; for(i=1; i=n; i+) if(*ht)i.parent=0) min=i; break; for(i=1; i=n; i+) if(*ht)i.parent=0) if(*ht)i.weight(*ht)min.weight) min=i; *s1=min; for(i=1; i=n; i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - if(*ht)i.pare
7、nt=0 & i!=(*s1) min=i; break; for(i=1; i=n; i+) if(*ht)i.parent=0 & i!=(*s1) if(*ht)i.weight(*ht)min.weight) min=i; *s2=min;/ 构造哈夫曼树ht,w 存放已知的n 个权值void CrtHuffmanTree(HuffmanTree *ht,int *w,int n) int m,i,s1,s2; m=2*n-1; /总共的结点数 *ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(i=1; i=n; i+) /1-n号存放叶
8、子结点，初始化 (*ht)i.weight=wi; (*ht)i.LChild=0; (*ht)i.parent=0; (*ht)i.RChild=0; for(i=n+1; i=m; i+) /非叶子结点的初始化 (*ht)i.weight=0; (*ht)i.LChild=0; (*ht)i.parent=0; (*ht)i.RChild=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - printf(n哈夫曼树为 :
9、n); for(i=n+1; i=m; i+) /创建非叶子结点，建哈夫曼树 /在(*ht)1(*ht)i-1的范围内选择两个parent为0且 weight 最小的结点，其序号分别赋值给s1、 s2 Select(ht,i-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; printf(%d (%d, %d)n,(*ht)i.weight,(*ht)s1.weight,(*ht)s2.w
10、eight); printf(n);/ 从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) char *cd; /定义的存放编码的空间 int a100; int i,start,p,w=0; unsigned int c; hc=(HuffmanCode *)malloc(n+1)*sizeof(char *); /分配 n 个编码的头指针 cd=(char *)malloc(n*sizeof(char); /分配求当前编码的工作空间 cdn-1=0; /从右向左逐位存放编
11、码，首先存放编码结束符 for(i=1; i=n; i+) /求 n 个叶子结点对应的哈夫曼编码 ai=0; start=n-1; /起始指针位置在最右边 for(c=i,p=(*ht)i.parent; p!=0; c=p,p=(*ht)p.parent) /从叶子到根结点求编码 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - if( (*ht)p.LChild=c) cd-start=1; /左分支标 1 ai+; else
12、 cd-start=0; /右分支标 0 ai+; hci=(char *)malloc(n-start)*sizeof(char); /为第 i 个编码分配空间 strcpy(hci,&cdstart); /将 cd 复制编码到hc free(cd); for(i=1; i=n; i+) printf( 权值为 %d的哈夫曼编码为：%sn,(*ht)i.weight,hci); for(i=1; i=n; i+) w+=(*ht)i.weight*ai; printf( 带权路径为： %dn,w);void main() HuffmanTree HT; HuffmanCode HC; int
13、 *w,i,n,wei; printf(*哈夫曼编码 *n ); printf(请输入结点个数： ); scanf(%d,&n); w=(int *)malloc(n+1)*sizeof(int); printf(n输入这 %d个元素的权值 :n,n); for(i=1; i=n; i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - printf(%d: ,i); fflush(stdin); scanf(%d,&wei); wi=wei; CrtHuffmanTree(&HT,w,n); CrtHuffmanCode(&HT,&HC,n);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -
