萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

哈夫曼編碼 C 語言完整實作:樹建構、編碼生成、逐步追蹤

哈夫曼編碼是最佳前綴碼壓縮演算法。本文提供完整 C 語言實作:HuffmanTree() 建構樹、主程式自葉向根回溯生成編碼、陣列模擬樹結構、動態最小權值選擇。

資料結構定義

#define MAXBIT      100
#define MAXVALUE    10000
#define MAXLEAF     30
#define MAXNODE     (MAXLEAF * 2 - 1)

typedef struct {
  int bit[MAXBIT];
  int start;
} HCodeType;   // 編碼結構

typedef struct {
  int weight;
  int parent;
  int lchild;
  int rchild;
} HNodeType;   // 節點結構

樹建構演算法

void HuffmanTree(HNodeType HuffNode[MAXNODE], int n) {
  int i, j, m1, m2, x1, x2;
  
  // 初始化 2n-1 節點
  for (i = 0; i < 2*n-1; i++) {
    HuffNode[i].weight = 0;
    HuffNode[i].parent = -1;
    HuffNode[i].lchild = -1;
    HuffNode[i].rchild = -1;
  }
  
  // 輸入 n 個葉節點權值
  for (i = 0; i < n; i++) {
    printf("Please input weight of leaf node %d: ", i);
    scanf("%d", &HuffNode[i].weight);
  }
  
  // n-1 輪合併
  for (i = 0; i < n-1; i++) {
    m1 = m2 = MAXVALUE;
    x1 = x2 = 0;
    
    // 找無父節點且權值最小的兩個節點
    for (j = 0; j < n+i; j++) {
      if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1) {
        m2 = m1; x2 = x1;
        m1 = HuffNode[j].weight; x1 = j;
      } else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1) {
        m2 = HuffNode[j].weight; x2 = j;
      }
    }
    
    // 建立父節點
    HuffNode[x1].parent = n + i;
    HuffNode[x2].parent = n + i;
    HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
    HuffNode[n+i].lchild = x1;
    HuffNode[n+i].rchild = x2;
    
    printf("Round %d: merge %d(%d) + %d(%d) -> %d(%d)\n",
           i+1, x1, m1, x2, m2, n+i, HuffNode[n+i].weight);
  }
}

編碼生成 (自葉向根回溯)

int main() {
  HNodeType HuffNode[MAXNODE];
  HCodeType HuffCode[MAXLEAF], cd;
  int i, j, c, p, n;
  
  printf("Please input n: ");
  scanf("%d", &n);
  HuffmanTree(HuffNode, n);
  
  for (i = 0; i < n; i++) {
    cd.start = n - 1;           // 編碼從陣列尾端向前填
    c = i;
    p = HuffNode[c].parent;
    
    while (p != -1) {           // 向上追溯至根
      if (HuffNode[p].lchild == c)
        cd.bit[cd.start--] = 0; // 左分支 = 0
      else
        cd.bit[cd.start--] = 1; // 右分支 = 1
      c = p;
      p = HuffNode[c].parent;
    }
    
    // 輸出編碼 (start+1 到 n-1)
    printf("Leaf %d (w=%d): ", i, HuffNode[i].weight);
    for (j = cd.start + 1; j < n; j++)
      printf("%d", cd.bit[j]);
    printf("\n");
    
    HuffCode[i] = cd;           // 保存
  }
  return 0;
}

執行範例

Input n: 5
Weights: 5 15 40 30 10

Round 1: merge 0(5) + 4(10) -> 5(15)
Round 2: merge 5(15) + 1(15) -> 6(30)
Round 3: merge 3(30) + 6(30) -> 7(60)
Round 4: merge 7(60) + 2(40) -> 8(100)

Leaf 0 (w=5):  1110
Leaf 1 (w=15): 110
Leaf 2 (w=40): 0
Leaf 3 (w=30): 10
Leaf 4 (w=10): 1111

演算法複雜度

階段時間複雜度空間複雜度
建樹 (簡單線性搜尋)O(n²)O(n)
建樹 (最小堆優化)O(n log n)O(n)
編碼生成O(n h) ≈ O(n log n)O(n h)

關鍵細節

  • 陣列索引 0 ~ n-1 為葉節點,n ~ 2n-2 為內部節點。
  • parent = -1 表示未加入樹 (可用於尋找候選節點)。
  • 編碼反向生成 (從葉到根),故用 start 從高索引向前填入。
  • 左子樹 = 0、右子樹 = 1 為慣例,亦可相反,只要編解碼一致即可。

工程化建議

  • 使用優先佇列 (最小堆) 取代線性搜尋,大幅提升大規模符號集效能。
  • 位元級寫入輸出位串流 (BitOutputStream) 而非字元 '0'/'1'。
  • 標準化檔頭儲存符號表/樹結構,支援解碼端重建。
  • 參考成熟庫:zlib (DEFLATE=哈夫曼+LZ77)、huffman (獨立庫)。

此實作完整展示哈夫曼演算法核心邏輯,是資料壓縮、編碼理論教學與嵌入式系統輕量壓縮的優秀基礎代碼。

copyright © 萬盛學電腦網 all rights reserved