資料結構【完整代碼】之（C語言實作【哈夫曼編碼】）

本文包含兩個檔案的代碼和一張測試效果圖：

• HuffmanCD.h檔案： 從葉到根逆向求哈夫曼編碼
• HuffmanCodingTest.cpp檔案： 用于測試
• 效果圖：（如下）

效果圖：

#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;
//      }
//  }
//}      

#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);
}