哈夫曼编码

1. 相关概念:

1. 定长编码:
   1. 类似于ASCII码这种, 每个字符都是定长的编码
2. 变长编码:
   1. 每个字符的编码每个字符的编码长度不相同
3. 前缀码:
   1. 每个字符的编码都不可能是其他字符的前缀

2. 梗概:

1. 用根结点到叶结点的路径表示一个编码对象
   1. 从根结点到叶结点的所走分支的顺序=编码从左到右的顺序
   2. 习惯上规定分支表示的码:
      1. 往左走为0
      2. 往右走为1

3. 哈夫曼编码的特点:

1. 前缀码
2. 没有二义性
3. 频率越高, 编码越短

4. 哈夫曼编码在C语言中的实现:

4.1. 梗概:

1. 一个一个叶结点地编码
   1. 从叶结点倒推回根结点
      1. 这样路径才唯一, 才找的出来
         1. 因为往上看, 根结点唯一; 而往下看, 叶结点不唯一
   2. 需要申请一个临时保存当前叶结点编码的工作空间
2. 获得对应结点(权值)的编码
   1. HuffmanCode[对应结点在哈夫曼数组中的下标]

4.2. 代码实现:

typedef char* HuffmanCode[N+1];
void CrtHuffmanCode (HuffmanTree ht, HuffmanCode hc, int n){
    //hc为二维数组,储存每个叶结点对应编码
    //n为叶结点数
    int i,start,c,p;
    /*cd数组用于临时保存当前叶结点的编码*/
    char *cd;
    /*叶结点编码最长不超过总叶结点数量*/
    cd = (char*)calloc(n,sizeof(char));
    /*因为从叶结点倒退根结点,故从右往左编码*/
    cd[n-1]='\0';
    for(i=1;i<=n;i++){
        /*当前编码的左边界*/
        start = n-1;
        /*倒退根结点*/
        c=i;p=ht[i].parent;
        for(;p!=0;){
            --start;
            /*习惯规定左为0,右为1*/
            if(ht[p].LChild==c)cd[start]='0';
            else cd[start]='1';
            c=p;p=ht[p].parent;
        }
        /*当前叶结点编码完毕,复制保存编码结果*/
        hc[i]=(char*)calloc(n-start,sizeof(char));
        strcpy(hc[i],&cd[start]);
    }
    /*为下一个叶结点编码做准备*/
    free(cd);
}