数据结构【完整代码】之（C语言实现【哈夫曼编码】）

本文包含两个文件的代码和一张测试效果图：

• HuffmanCD.h文件： 从叶到根逆向求哈夫曼编码
• HuffmanCodingTest.cpp文件： 用于测试
• 效果图：（如下）

效果图：

HuffmanCD.h文件：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
typedef struct{
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;
 
typedef char** HuffmanCode; //动态分配数组存储哈夫曼编码表

void Select(HuffmanTree HT, int n, int &s1, int &s2)
{
    int minum;      // 定义一个临时变量保存最小值?
    for(int i=1; i<=n; i++)     // 以下是找到第一个最小值
    {
        if(HT[i].parent == 0)
        {
            minum = i;
            break;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(HT[i].parent == 0)
            if(HT[i].weight < HT[minum].weight)
                minum = i;
    }
    s1 = minum;
    // 以下是找到第二个最小值，且与第一个不同
    for(int i=1; i<=n; i++)     
    {
        if(HT[i].parent == 0 && i != s1)
        {
            minum = i;
            break;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(HT[i].parent == 0 && i != s1)
            if(HT[i].weight < HT[minum].weight)
                minum = i;
    }
    s2 = minum;
}

void HuffmanInit(HuffmanTree &HT, HuffmanCode &HC, char* ch, int* w, int n){

    //ch存放n个字符，w存放n个字符的权值，构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC
    int m;  
    int i; 
    char* cd; //临时存储每个字符的编码串
    int start; //记录编码在cd中存放的位置，初始指向最后，以便于逆向求编码 
    int c; //记录当前待编码字符的下标i
    int f; //记录前待编码字符的下标i的双亲结点的下标 
    int s1, s2; //记录权值最小两个编码对应下标 
    HuffmanTree p; 
    if(n <= 1){
        return;
    }
    m = 2 * n - 1; //n个叶子结点的哈夫曼树共有2n-1个结点 
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //为了表示方便，0号单元未用
    for(p = HT + 1, i = 1; i <= n; i++, p++, w++){
        (*p).weight = *w;
        (*p).parent = 0;
        (*p).lchild = 0;
        (*p).rchild = 0;
    } 
    for(; i <= m; i++, p++){
        
        (*p).weight = 0;
        (*p).parent = 0;
        (*p).lchild = 0;
        (*p).rchild = 0;
    }
    for(i = n + 1; i <= m; i++){ //建哈夫曼树 
        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;
    }
    //从叶到根逆向求每个字符的哈夫曼编码
    HC = (HuffmanCode)malloc((n + 1) * sizeof(char*)); //分配n个字符编码的头指针
    cd = (char*)malloc(n * sizeof(char)); //分配求编码的工作空间
    cd[n-1] = '\0'; 
    for(i = 1; i <= n; i++){ //求解n个字符的编码，循环n次 
        start = n - 1;
        for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent){ //从叶到根逆向求编码 
            if(HT[f].lchild == c){
                HT[c].weight = 0;
                cd[--start] = '0';
            }
            else{
                HT[c].weight = 1;
                cd[--start] = '1';
            }
        }
        HC[i] = (char*)malloc((n - start) * sizeof(char)); //为第i个字符编码分配空间
        strcpy(HC[i], &cd[start]); //从cd复制编码串到HC 
        printf("%c: ", ch[i-1]);
        puts(HC[i]);
    } 
} 

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, char* input_ch, char* ch, int n){
    int i, j;
    int len = strlen(input_ch);
    printf("%s经哈夫曼编码后为: ", input_ch);
    for(i = 0; i < len; i++){
        for(j = 0; j < n; j++){
            if(input_ch[i] == ch[j]){
                printf("%s", HC[j+1]);
                break;
            }
        }
    }
}

//解码并未完全代码实现出来，只稍微写了点 
//void HuffmanDeCoding(HuffmanTree HT, HuffmanCode HC, char* ch_num, int n){
//  int i;
//  int len = strlen(ch_num);
//  HuffmanTree p = HT + 1;
//  char cd[101];
//  int count = 0;
//  for(i = 0; i < len; i++){
//      if(ch_num[i] == '0' && (*p).lchild != 0){
//          (*p) = (*p).lchild;
//          cd[count] = ch_num[i];
//          count++;
//      }
//      else if(ch_num[i] == '1' && *(p)->rchild != 0){
//          (*p) = (*p).rchild;
//          cd[count] = ch_num[i];
//          count++;
//      }
//      else{
//          puts(cd);
//          p = HT + 1; 
//          char cd[101];
//          int count = 0;
//      }
//  }
//}

HuffmanCodingTest.cpp文件：

#include "HuffmanCD.h"

int main()
{
    HuffmanTree HT;
    char** HC;
    int n = 6, wei;
    char ch[6] = {'A', 'B', 'C', 'D', 'E', 'F'}; 
    int w[6] = {27, 8, 15, 15, 30, 5};
    
    HuffmanInit(HT, HC, ch, w, n);
    printf("\n");
    
    char input_ch[101] = "BADCADFEED";
    HuffmanCoding(HT, HC, input_ch, ch, n);
    printf("\n");
    
//    char input_num[101] = "101100101"; //CBA
//    HuffmanDeCoding(HT, HC, input_num, n);
}