C語言實現霍夫曼編碼：從原理到完整代碼實戰

編輯：關於C語言

C語言實現霍夫曼編碼：從原理到完整代碼實戰

霍夫曼編碼是一種基於字符出現概率的最優前綴編碼，廣泛用於無損數據壓縮（如ZIP、JPEG、MP3）。本文系統講解其構樹原理、編碼規則，並給出完整的C語言實現，包含頻率統計、樹構建、編碼生成、文本壓縮與解碼驗證全流程。

一、霍夫曼樹構建原理

統計頻率：掃描文本，統計每個字符出現次數（權重）。
創建葉子節點：每個字符對應一個節點，權重為頻率。
重複合併：從節點集合中取出權重最小的兩個節點，創建新父節點，權重為兩子節點權重之和，左子樹分配0、右子樹分配1。將新節點放回集合。重複直到只剩一個節點——根節點。
生成編碼：從根到葉子的路徑上0/1序列即為該字符編碼。高頻字編碼短，低頻字編碼長，實現壓縮。

示例：字符F,O,R,G,E,T頻率2,3,4,4,5,7。合併過程：(F,O)→5、(R,G)→8、((F,O),E)→10、((R,G),T)→15、(10,15)→25。最終編碼：E:00, F:010, O:011, R:10, G:110, T:111。

二、核心數據結構

#define MAX_ALPHABET 52   // 大小寫字母
#define MAX_CODE_LEN 100  // 最大編碼長度

// 霍夫曼樹節點
typedef struct HuffNode {
    int weight;                 // 權重/頻率
    char ch;                    // 字符（葉子節點有效）
    struct HuffNode *left, *right;
    struct HuffNode *parent;    // 構樹時用，編碼時回溯用
} HuffNode;

// 編碼表項
typedef struct {
    char bits[MAX_CODE_LEN];    // 編碼位串（反序存儲）
    int start;                  // 有效編碼起始索引
    char ch;                    // 字符
} CodeItem;

HuffNode nodes[2*MAX_ALPHABET]; // 最大 2n-1 個節點
CodeItem codes[MAX_ALPHABET];

三、關鍵算法實現

1. 文件讀取與頻率統計

void readTxtStatistics(const char* filename) {
    FILE* fp = fopen(filename, "r");
    int freq[52] = {0}; // A-Z, a-z
    char buf[1024];
    while (fgets(buf, sizeof(buf), fp)) {
        for (char *p = buf; *p; ++p) {
            if (*p >= 'A' && *p <= 'Z') freq[*p - 'A']++;
            else if (*p >= 'a' && *p <= 'z') freq[*p - 'a' + 26]++;
        }
    }
    fclose(fp);
    // 初始化葉子節點
    int n = 0;
    for (int i = 0; i < 52; ++i) if (freq[i]) {
        char c = (i < 26) ? 'A' + i : 'a' + (i - 26);
        nodes[n].ch = c;
        nodes[n].weight = freq[i];
        nodes[n].left = nodes[n].right = nodes[n].parent = NULL;
        n++;
    }
    // 全局葉子數
    leafCount = n;
}

2. 構建霍夫曼樹（選最小兩個合併）

void buildHuffmanTree() {
    int total = 2 * leafCount - 1;
    // 初始化所有節點 parent=0
    for (int i = 0; i < total; ++i) nodes[i].parent = NULL;

    // 前 leafCount 個已是葉子，後續構建內部節點
    for (int i = leafCount; i < total; ++i) {
        int min1 = -1, min2 = -1;
        // 在 [0, i) 中找親為空且權重最小的兩個
        for (int j = 0; j < i; ++j) if (!nodes[j].parent) {
            if (min1 == -1 || nodes[j].weight < nodes[min1].weight) {
                min2 = min1; min1 = j;
            } else if (min2 == -1 || nodes[j].weight < nodes[min2].weight) {
                min2 = j;
            }
        }
        // 合併
        nodes[min1].parent = &nodes[i];
        nodes[min2].parent = &nodes[i];
        nodes[i].left = &nodes[min1];
        nodes[i].right = &nodes[min2];
        nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
        nodes[i].ch = 0; // 內部節點無字符
        nodes[i].parent = NULL;
    }
    root = &nodes[total - 1];
}

3. 生成編碼表（從葉子回溯到根）

void generateCodes() {
    for (int i = 0; i < leafCount; ++i) {
        CodeItem &cd = codes[i];
        cd.ch = nodes[i].ch;
        cd.start = MAX_CODE_LEN;
        HuffNode *cur = &nodes[i];
        while (cur->parent) {
            cd.bits[--cd.start] = (cur == cur->parent->left) ? '0' : '1';
            cur = cur->parent;
        }
    }
}

4. 編碼壓縮文本

void encodeFile(const char* inFile, const char* outFile) {
    FILE *fin = fopen(inFile, "r"), *fout = fopen(outFile, "wb");
    // 寫入編碼表頭（簡化：這裡略過，實際需序列化 codes 供解碼用）
    char buf[1024];
    unsigned char byte = 0; int bitPos = 0;
    while (fgets(buf, sizeof(buf), fin)) {
        for (char *p = buf; *p; ++p) {
            // 查找編碼
            for (int i = 0; i < leafCount; ++i)
                if (codes[i].ch == *p) {
                    for (int k = codes[i].start; k < MAX_CODE_LEN; ++k) {
                        byte = (byte << 1) | (codes[i].bits[k] - '0');
                        if (++bitPos == 8) { fputc(byte, fout); byte = 0; bitPos = 0; }
                    }
                    break;
                }
        }
    }
    if (bitPos) { byte <<= (8 - bitPos); fputc(byte, fout); }
    fclose(fin); fclose(fout);
}

5. 解碼驗證（從根按位走向葉子）

void decodeFile(const char* inFile, const char* outFile) {
    FILE *fin = fopen(inFile, "rb"), *fout = fopen(outFile, "w");
    int c; HuffNode *cur = root;
    while ((c = fgetc(fin)) != EOF) {
        for (int b = 7; b >= 0; --b) {
            cur = ((c >> b) & 1) ? cur->right : cur->left;
            if (!cur->left && !cur->right) { // 葉子
                fputc(cur->ch, fout);
                cur = root;
            }
        }
    }
    fclose(fin); fclose(fout);
}

四、完整主程序框架

int main() {
    printf("=== 霍夫曼編碼演示 ===\n");
    readTxtStatistics("input.txt");
    buildHuffmanTree();
    generateCodes();
    printf("字符編碼表:\n");
    for (int i = 0; i < leafCount; ++i) {
        printf("%c: ", codes[i].ch);
        for (int k = codes[i].start; k < MAX_CODE_LEN; ++k) putchar(codes[i].bits[k]);
        putchar('\n');
    }
    encodeFile("input.txt", "compressed.bin");
    decodeFile("compressed.bin", "output.txt");
    printf("壓縮解壓完成，驗證 output.txt 與 input.txt 一致。\n");
    return 0;
}