数据结构-自顶向下的赫夫曼编码 （C语言代码）

解题思路:

    练写。

注意事项:

    同题1700，见代码114行，,构建的哈夫曼树要与题目一致。

参考代码:

#include<stdio.h>
#include<string.h>
#include<malloc.h>
 
typedef struct HTNode{
    int weight; // 权重
    int parent; // 父结点的下标
    int lchild, rchild; // 左右孩子的下标
} HTNode, *HuffTree;
 
typedef char **HuffCode; // 动态二维数组，存放哈夫曼编码
 
// 创建哈夫曼树 --------------------- 权重数组 - 字符数
void CreateHuffmanTree(HuffTree *htree, int *w, int n);
 
// 选择最小权重的两个字符 --- 当前结点数 - 权重最小的两个结点下标 
void SelectHTNode(HuffTree htree, int n, int *s1, int *s2);
 
// 哈夫曼编码 ------------------ 传入动态二维数组地址
void HuffmanCode(HuffTree htree, HuffCode *hcode, int n);
 
// 打印哈夫曼编码 ------------------- 字符数
void PrintHuffmanCode(HuffCode hcode, int n);
 
int main()
{
    int n, i, *w;
    HuffTree htree = NULL;
    HuffCode hcode = NULL;
     
    scanf("%d", &n); // 需编码字符数
    w = (int *)malloc(sizeof(int) * (n + 1)); // 权重数组，0号位置不用
    for(i = 1, w[0] = 0; i <= n; i++){
        scanf("%d", w + i);
    }
     
    CreateHuffmanTree(&htree, w, n);
    HuffmanCode(htree, &hcode, n);
    PrintHuffmanCode(hcode, n);
     
    free(w);
    free(htree);
     
    return 0;
}
 
 
void CreateHuffmanTree(HuffTree *htree, int *w, int n){
     
    if(n <= 1) return;
     
    int m = 2 * n - 1; // 最终哈夫曼树的结点数
    int i, s1, s2; // s1，s2为当前未建树最小权重结点的下标
     
    *htree = (HuffTree)malloc(sizeof(HTNode) * (m + 1)); // 0号位置不用
    // --- 初始化结点数据 --- //
    for(i = 1; i <= n; i++){
         
        (*htree)[i].weight = w[i];
        (*htree)[i].parent = 0;
        (*htree)[i].lchild = 0;
        (*htree)[i].rchild = 0;
    }
    for(i = n + 1; i <= m; i++){
         
        (*htree)[i].weight = 0;
        (*htree)[i].parent = 0;
        (*htree)[i].lchild = 0;
        (*htree)[i].rchild = 0;
    }
     
    for(i = n + 1; i <= m; i++){ // 进行n - 1次循环构建哈夫曼树
         
        SelectHTNode(*htree, i - 1, &s1, &s2);
        (*htree)[i].lchild = s1;
        (*htree)[i].rchild = s2;
        (*htree)[s1].parent = (*htree)[s2].parent = i;
        (*htree)[i].weight = (*htree)[s1].weight + (*htree)[s2].weight;
    }
}
 
 
void SelectHTNode(HuffTree htree, int n, int *s1, int *s2){
     
    int i;
     
    for(i = 1, *s1 = 0; i <= n; i++){
         
        if(!htree[i].parent && *s1 == 0){
             
            *s1 = i;
            continue;
        }
        if(!htree[i].parent){ // 先找到两个未建树的结点
             
            *s2 = i;
            break;
        }
    }
     
    for(i = *s2; i <= n; i++){ // i从s2开始，第一次循环是s2与s1的比较，使得s1 < s2
         
        if(!htree[i].parent){
             
            if(htree[i].weight < htree[*s1].weight){ // 如果比当前最小权重还小
                 
                *s2 = *s1; // 使s1成为次小
                *s1 = i; // s1始终为最小
            }
            else if(htree[i].weight < htree[*s2].weight){ // 如果仅比次小的小
                 
                *s2 = i; // i取代s2
            }
        }
    }
     
    // 进行到这，s1、s2分别为当前未建树的最小、次小权重的结点下标
    // 但观察题目，s1、s2不以权重值来划分左右孩子结点，而是下标。
     
    if(*s1 > *s2){ // 故一定要加上判断！！！
         
        int t = *s1;
        *s1 = *s2;
        *s2 = t;
    }
}
 
 
void HuffmanCode(HuffTree htree, HuffCode *hcode, int n){
     
    *hcode = (HuffCode)malloc(sizeof(char *) * (n + 1)); // 0号位置不用
    char *cd = (char *)malloc(sizeof(char) * n); // 临时存放编码串
    
    int m = 2 * n - 1; // 总结点数
    int i, cdlen = 0; // 当前编码串长度
    
    for(i = 1; i <= m; i++){
        
        htree[i].weight = 0; // 权重置0，用于访问标记
    }
    
    while(m){ // 当回退到树根"父结点"，编码完毕，退出循环
        
        if(htree[m].weight == 0){ // 当结点标记为0，未访问
            
            htree[m].weight = 1; // 标记访问一次
            if(htree[m].lchild){ // 若有左孩子
                
                m = htree[m].lchild; // 向左继续访问
                cd[cdlen++] = '0'; // 记录编码‘0’
            }
            else if(!htree[m].rchild){ // 若没有左右孩子，为叶子结点，该字符编码完成
                
                (*hcode)[m] = (char *)malloc(sizeof(char) * (cdlen + 1));
                cd[cdlen] = '\0';
                strcpy((*hcode)[m], cd);
            }
        }
        else if(htree[m].weight == 1){ // 标记为1，证明左孩子访问过
            
            htree[m].weight = 2; // 标记访问两次
            if(htree[m].rchild){ // 若有右孩子
                
                m = htree[m].rchild; // 向右一步
                cd[cdlen++] = '1'; // 记录编码‘1’
            }
        }
        else{ // 标记为2，说明左右孩子都访问过(或者没有左右孩子)
            
            //htree[m].weight = 0;
            m = htree[m].parent; // 回退到父结点
            cdlen--; // 编码串长度--
        }
    }
    
    free(cd);
}
 
 
void PrintHuffmanCode(HuffCode hcode, int n){
     
    for(int i = 1; i <= n; i++){
         
        printf("%s\n", hcode[i]);
        free(hcode[i])
    }
    
    free(hcode);
}