哈夫曼编码

在远程通讯中，要将待传字符转换成由二进制的字符串。若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少
关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀
哈夫曼编码方法：
①统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）
②利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树，则概率越大的结点，路径越短
③在哈夫曼树中的每个分支上标上0或1：
结点的左分支标0，右分支标1
把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码
为什么哈夫曼编码能够保证是前缀编码？
因为没有一片树叶是另一片树叶的祖先，所以每个叶结点的编码就不可能是其他叶结点编码的前缀
为什么哈夫曼编码能够保证字符编码总长最短？
因为哈夫曼树的带权路径长度最短，故字符编码的总长最短
哈夫曼编码的性质：
①哈夫曼编码是前缀码
②哈夫曼编码是最优前缀码
哈夫曼编码的算法实现：
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC, int n){
//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
HC=new char *[n+1];//分配n个字符编码的头指针矢量
cd=new char [n];//分配临时存放编码的动态数组空间
cd[n-1] = ‘\0’;//编码结束符
for(i=1;i<=n;++i){//逐个字符求哈夫曼编码
start = n-1;c=i;f=HT[i].parent;
while(f!=0){//从叶子结点开始向上回溯，直到根结点
—start;//回溯一次start向前指一个位置
if(HT[f].lchild == c) cd[start] = ‘0’;//结点c是f的左孩子，则生成代码0
else cd[start] = ‘1’;//结点c是f的右孩子，则生成代码1
c=f;f=HT[f].parent;//继续向上回溯
}//求出第i个字符的编码
HC[i] = new char [n-start];//为第i个字符串编码分配空间
strcpy(HC[i],&cd[start]);//将求出的编码从临时空间cd复制到HC的当前行中
}
delete cd;//释放临时空间
}//CreatHuffanCode