哈夫曼编码.doc

哈夫曼编码I.问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。II.问题分析 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。 设C为编码字符集，则表示其最优前缀码的二叉树中恰有|C|个叶子，|C|-1个内部结点。其中，每个叶子对应于字符集中一个字符。二叉树T的代价：编码文件需要二进制位数使 达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。 编码字符集中每一字符c的频率是freq。以freq为键值的最小堆优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入最小堆优先队列Q。经过n-1次的合并后，优先队列中只剩下一棵树，即所要求的树T。 III.算法描述： HUFFMAN(C) /哈夫曼编码算法 n = |C| / 初始化最小优先队列Q 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中插入结点zreturn EXTRACT-MIN(Q)时间复杂度描述：INITIALIZE(Q) = BUILD-MIN-HEAP(C)的时间复杂度为O（n）；循环 for i=1 to n-1的时间复杂度为O（n）； 其中， z.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)。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 *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+) if(*ht)i.parent=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号存放叶子结点，初始化 (*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; printf(n哈夫曼树为: 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.weight); 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; /从右向左逐位存放编码，首先存放编码结束符 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) /从叶子到根结点求编码 if( (*ht)p.LChild=c) cd-start=1; /左分支标1 ai+; else 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 *w,i,n,wei; printf(*哈夫曼编码*n ); printf(请输入结点个数： ); scanf(%d,&n); w=(int *)malloc(n