哈夫曼編碼是最佳前綴碼壓縮演算法。本文提供完整 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 從高索引向前填入。BitOutputStream) 而非字元 '0'/'1'。zlib (DEFLATE=哈夫曼+LZ77)、huffman (獨立庫)。此實作完整展示哈夫曼演算法核心邏輯,是資料壓縮、編碼理論教學與嵌入式系統輕量壓縮的優秀基礎代碼。