哈夫曼编码实现最优前（最短期望长度）缀码 的源程序 要用到kiaft不等式约束条件,最优码长的界,

Question

如题所述

Answer 1

哈夫曼编码为最优前缀码
由哈夫曼树求得编码为最优前缀码的原因：
① 每个叶子字符ci的码长恰为从根到该叶子的路径长度li,平均码长(或文件总长)又是二叉树的带权路径长度WPL.而哈夫曼树是WPL最小的二叉树,因此编码的平均码长(或文件总长)亦最小.
② 树中没有一片叶子是另一叶子的祖先,每片叶子对应的编码就不可能是其它叶子编码的前缀.即上述编码是二进制的前缀码.
哈夫曼编码的算法
（1）思想方法
给定字符集的哈夫曼树生成后,求哈夫曼编码的具体实现过程是：依次以叶子T[i](0≤i≤n-1)为出发点,向上回溯至根为止.上溯时走左分支则生成代码0,走右分支则生成代码1.
注意：
① 由于生成的编码与要求的编码反序,将生成的代码先从后往前依次存放在一个临时向量中,并设一个指针start指示编码在该向量中的起始位置（start初始时指示向量的结束位置）.
② 当某字符编码完成时,从临时向量的start处将编码复制到该字符相应的位串bits中即可.
③ 因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符'\0',bits的大小应为n+1.
（2）字符集编码的存储结构及其算法描述
typedef struct {
char ch； //存储字符
char bits[n+1]； //存放编码位串
}CodeNode；
typedef CodeNode HuffmanCode[n]；
void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H)
{//根据哈夫曼树T求哈夫曼编码表H
int c,p,i;//c和p分别指示T中孩子和双亲的位置
char cd[n+1]； //临时存放编码
int start； //指示编码在cd中的起始位置
cd[n]='\0'； //编码结束符
for(i=0,i=0){//直至上溯到T[c]是树根为止
//若T[c]是T[p]的左孩子,则生成代码0；否则生成代码1
cd[--start]=(T[p).1child==C)?'0'：'1'；
c=p； //继续上溯
}
strcpy(H[i].bits,&cd[start])； //复制编码位串
}//endfor
}//CharSetHuffmanEncoding