哈夫曼編碼完整實現：C/C++ 文本壓縮解壓驗證全流程（大學數據結構作業標準解）

作業需求拆解

1. 讀取 source.txt（≥1000 英文字符），統計字符頻率輸出概率表。
2. 構建哈夫曼樹，生成編碼表 codebook1。
3. 按編碼表將源文本轉二進制寫入 code.dat。
4. 讀取 code.dat 解碼還原為 target.txt。
5. 對比 source.txt 與 target.txt，異位報告位置。

核心數據結構

#define MAX_CHAR 256
#define MAX_NODES (2 * MAX_CHAR)

typedef struct {
    char ch;
    int freq;
    char code[100];  // 編碼串
} HuffNode;

typedef struct {
    HuffNode nodes[MAX_NODES];
    int size;
} HuffTree;

關鍵算法步驟

1. 統計頻率

void count_freq(const char *filename, int freq[]) {
    FILE *fp = fopen(filename, "rb");
    int ch;
    while ((ch = fgetc(fp)) != EOF) freq[(unsigned char)ch]++;
    fclose(fp);
}

2. 構建哈夫曼樹（最小堆/優先隊列）

void build_tree(HuffTree *tree, int freq[]) {
    // 初始化葉子節點
    for (int i = 0; i < MAX_CHAR; i++) 
        if (freq[i]) { tree->nodes[tree->size++] = (HuffNode){.ch=i, .freq=freq[i]}; }
    
    // 簡化：選擇排序法（教學足夠），工程用最小堆 O(n log n)
    for (int i = 0; i < tree->size - 1; i++) {
        // 選兩個最小 freq 節點合併
        int min1 = -1, min2 = -1;
        for (int j = 0; j < tree->size; j++) {
            if (tree->nodes[j].freq >= 0) {
                if (min1 == -1 || tree->nodes[j].freq < tree->nodes[min1].freq) {
                    min2 = min1; min1 = j;
                } else if (min2 == -1 || tree->nodes[j].freq < tree->nodes[min2].freq) {
                    min2 = j;
                }
            }
        }
        // 合併
        HuffNode parent = {.ch=0, .freq = tree->nodes[min1].freq + tree->nodes[min2].freq};
        tree->nodes[min1].freq = -1;  // 標記已合併
        tree->nodes[min2].freq = -1;
        tree->nodes[tree->size++] = parent;
    }
    // 遞歸生成編碼（根節點在最後）
    gen_codes(tree, tree->size - 1, "");
}

3. 生成編碼（遞歸遍歷）

void gen_codes(HuffTree *tree, int idx, const char *prefix) {
    if (idx < 0 || idx >= tree->size) return;
    if (tree->nodes[idx].ch != 0) {  // 葉子節點
        strcpy(tree->nodes[idx].code, prefix);
        return;
    }
    // 內部節點：左 0 右 1（需維護左右子節點索引，此處簡化）
    // 完整版需存 left/right 指針或索引
}

4. 壓縮寫入（位流操作）

void compress(const char *src, const char *dst, HuffTree *tree) {
    FILE *in = fopen(src, "rb"), *out = fopen(dst, "wb");
    unsigned char buffer = 0; int bit_cnt = 0;
    int ch;
    while ((ch = fgetc(in)) != EOF) {
        char *code = tree->nodes[ch].code;
        for (int i = 0; code[i]; i++) {
            buffer = (buffer << 1) | (code[i] - '0');
            if (++bit_cnt == 8) { fputc(buffer, out); buffer = 0; bit_cnt = 0; }
        }
    }
    if (bit_cnt) { buffer <<= (8 - bit_cnt); fputc(buffer, out); }
    fclose(in); fclose(out);
}

5. 解壓還原

void decompress(const char *src, const char *dst, HuffTree *tree) {
    FILE *in = fopen(src, "rb"), *out = fopen(dst, "wb");
    int node_idx = tree->size - 1;  // 根節點
    int ch;
    while ((ch = fgetc(in)) != EOF) {
        for (int bit = 7; bit >= 0; bit--) {
            int b = (ch >> bit) & 1;
            node_idx = b ? tree->nodes[node_idx].right : tree->nodes[node_idx].left;
            if (tree->nodes[node_idx].ch != 0) {
                fputc(tree->nodes[node_idx].ch, out);
                node_idx = tree->size - 1;
            }
        }
    }
    fclose(in); fclose(out);
}

6. 文件對比驗證

void verify(const char *f1, const char *f2) {
    FILE *fp1 = fopen(f1, "rb"), *fp2 = fopen(f2, "rb");
    int c1, c2, pos = 0;
    while ((c1 = fgetc(fp1)) != EOF && (c2 = fgetc(fp2)) != EOF) {
        if (c1 != c2) printf("差異位置: %d (0x%X vs 0x%X)\n", pos, c1, c2);
        pos++;
    }
    if (c1 != EOF || c2 != EOF) printf("長度不一致\n");
    fclose(fp1); fclose(fp2);
}

完整可運行代碼倉庫

參考博客完整實現：哈夫曼編碼完整代碼（含測試數據）

工程化提示

• 編碼表需隨壓縮文件存儲（文件頭），解壓時先讀編碼表重建樹。
• 大文件分塊壓縮，避免單樹深度過大。
• 位流讀寫用 fread/fwrite 批量操作提升 IO 性能。

哈夫曼編碼是「貪心 + 堆 + 位操作」的綜合訓練場，把五個步驟各個擊破，數據結構作業輕松拿 A+。