霍夫曼編碼實戰：C 語言實現文件壓縮與解壓縮完整教程

編輯：關於C語言

前言

霍夫曼編碼是一種基於字元出現頻率的貪婪演算法，構建最優二元樹，讓高頻字元使用較短編碼，廣泛應用於資料壓縮（如 ZIP、JPEG、MP3）。本文示範以 C 語言在 VC++ 6.0 環境下實現完整的壓縮/解壓縮程式。

核心資料結構

#define MAXCHAR 30000
#define MAXNODE 300
#define MAXNUM  150

typedef char InfoType;

struct HtNode {
    long weight;          // 權重（頻率）
    char info;            // 字元
    int parentIndex;      // 父節點索引
    int llinkIndex;       // 左子節點索引
    int rlinkIndex;       // 右子節點索引
};

struct HtTree {
    struct HtNode ht[MAXNODE];
    int rootIndex;
};
typedef struct HtTree* PHtTree;

採用陣列儲存樹節點，葉節點數 m，內部節點 m-1，總節點 2m-1。

演算法流程

統計頻率：掃描檔案或使用預設頻率表（針對 C 原始碼、文字等不同類型可預訓練頻率表以提高壓縮率）。
建立霍夫曼樹：重複 m-1 次選取兩個最小權重且無父節點的節點合併。
生成編碼表：從葉節點向根回溯，將各字元對應的編碼與長度存入 HaffCode codeList[128]，索引即 ASCII 值，查找 O(1)。
壓縮寫入：逐字元讀取原檔，按位元寫入編碼至輸出檔（需實作位元流緩衝）。
解壓縮：讀取樹結構（或編碼表），按位元遍歷樹還原字元。

關鍵程式碼片段

建樹函式

PHtTree haffmanAlgorithm(int m, long *w) {
    PHtTree pht = malloc(sizeof(struct HtTree));
    // 初始化葉節點
    for (int i = 0; i < 2*m-1; ++i) {
        pht->ht[i].llinkIndex = pht->ht[i].rlinkIndex = pht->ht[i].parentIndex = -1;
        if (i < m) { pht->ht[i].weight = w[i]; pht->ht[i].info = (char)i; }
        else pht->ht[i].weight = -1;
    }
    // 合併內部節點
    for (int i = 0; i < m-1; ++i) {
        // 找出兩個最小權重無父節點的節點
        // ... 略 ...
        pht->ht[first].parentIndex = m+i;
        pht->ht[second].parentIndex = m+i;
        pht->ht[m+i].weight = pht->ht[first].weight + pht->ht[second].weight;
        pht->ht[m+i].llinkIndex = first;
        pht->ht[m+i].rlinkIndex = second;
        pht->rootIndex = m+i;
    }
    return pht;
}

編碼表建立


typedef struct {
    char asciiCode;
    unsigned long haffCode;
    int haffCodeLen;
} HaffCode;

HaffCode codeList[128];
// 遍歷樹填入 codeList，索引 = asciiCode
// 查找：sHaffCode = codeList[inChar].haffCode;