PAT 甲級 1005 哈夫曼編碼驗證：C語言實現最小加權路徑長度與前綴碼判定

編輯：關於C語言

PAT 1005 Huffman Codes：從構建最優樹到學生提交碼驗證的完整解析

哈夫曼編碼是數據壓縮領域的經典貪心算法。PAT 甲級 1005 題目要求：給定字符頻率，驗證學生提交的編碼是否為合法的哈夫曼編碼（即滿足最小加權路徑長度 WPL 且無前綴碼衝突）。本文提供基於最小堆構建哈夫曼樹、遞歸計算 WPL、暴力檢查前綴碼的完整 C 語言解法，並分析測試點 1 未通過的潛在原因。

一、題目核心要求

輸入 N 個字符及其頻率，構建哈夫曼樹，計算理論最小 WPL。
輸入 M 組學生提交的編碼方案（每組 N 行字符-編碼對）。
判定標準：WPL 等於最小值 且 編碼集無前綴關係（即任一編碼不是另一編碼的前綴）。

二、算法設計與關鍵數據結構

1. 哈夫曼樹節點

typedef struct TreeNode {
    int weight;                 // 權重/頻率
    struct TreeNode *left, *right;
} HuffmanTree, *pHuffmanTree;

2. 最小堆（優先隊列）輔助構建

typedef struct HeapStruct {
    pHuffmanTree *elements; // 動態數組存節點指針
    int size, capacity;
} MinHeap, *pMinHeap;

// 堆操作：Create, Insert, DeleteMin (向上/向下篩選維持最小堆性質)

3. 哈夫曼樹構建流程（貪心）

pHuffmanTree Huffman(pMinHeap H) {
    for (int i = 1; i < H->capacity; i++) {
        pHuffmanTree T = malloc(sizeof(HuffmanTree));
        T->left = DeleteMin(H);   // 取出最小兩棵子樹
        T->right = DeleteMin(H);
        T->weight = T->left->weight + T->right->weight; // 合併權重
        Insert(H, *T);            // 新樹入堆
    }
    return DeleteMin(H); // 最後剩下的即根節點
}

4. WPL 遞歸計算

int getWPL(pHuffmanTree T, int depth) {
    if (!T->left && !T->right) // 葉節點
        return depth * T->weight;
    return getWPL(T->left, depth+1) + getWPL(T->right, depth+1);
}

三、學生提交碼驗證邏輯

// 讀取 M 組提交
for (int i = 0; i < M; i++) {
    int wpl = 0;
    char code[N][MAX_CODE_LEN];
    
    // 讀取 N 行字符與編碼，同時計算該提交的 WPL
    for (int j = 0; j < N; j++) {
        scanf(" %c %s", &ch, code[j]);
        wpl += strlen(code[j]) * freq[j]; // freq 為原始頻率數組
    }
    
    // 1. WPL 檢查
    if (wpl != minWPL) { flag[i] = 0; continue; }
    
    // 2. 前綴碼檢查（暴力 O(N^2 * L)）
    flag[i] = 1;
    for (int j = 0; j < N && flag[i]; j++) {
        for (int k = j+1; k < N; k++) {
            // 檢查 code[j] 是否為 code[k] 前綴，或反之
            if (isPrefix(code[j], code[k]) || isPrefix(code[k], code[j])) {
                flag[i] = 0; break;
            }
        }
    }
}

// 輔助函數：判斷 s1 是否為 s2 前綴
int isPrefix(char *s1, char *s2) {
    return (strncmp(s1, s2, strlen(s1)) == 0);
}

四、完整代碼實現（含詳細註釋）

#include 
#include 
#include 

#define MAXN 64
#define MAXCODE 1000
#define MIN_DATA -1

typedef struct TreeNode {
    int weight;
    struct TreeNode *left, *right;
} HuffmanTree, *pHuffmanTree;

typedef struct HeapStruct {
    pHuffmanTree *elements;
    int size, capacity;
} MinHeap, *pMinHeap;

// ... 堆操作函數：Create, Insert, DeleteMin, Huffman, getWPL (同上) ...

int main() {
    int N;
    scanf("%d", &N);
    int freq[MAXN];
    char ch;
    for (int i = 0; i < N; i++) {
        scanf(" %c %d", &ch, &freq[i]);
    }
    
    // 構建最小堆並生成哈夫曼樹
    pMinHeap H = Create(N);
    for (int i = 0; i < N; i++) {
        pHuffmanTree T = malloc(sizeof(HuffmanTree));
        T->weight = freq[i]; T->left = T->right = NULL;
        Insert(H, *T);
    }
    pHuffmanTree root = Huffman(H);
    int minWPL = getWPL(root, 0);
    
    int M; scanf("%d", &M);
    int flags[MAXN] = {0};
    char codes[MAXN][MAXCODE];
    
    for (int i = 0; i < M; i++) {
        int wpl = 0;
        for (int j = 0; j < N; j++) {
            scanf(" %c %s", &ch, codes[j]);
            wpl += strlen(codes[j]) * freq[j];
        }
        if (wpl != minWPL) continue;
        
        // 前綴檢查
        int ok = 1;
        for (int j = 0; j < N && ok; j++) {
            for (int k = j+1; k < N; k++) {
                if (strlen(codes[j]) < strlen(codes[k])) {
                    if (strncmp(codes[j], codes[k], strlen(codes[j])) == 0) { ok = 0; break; }
                } else {
                    if (strncmp(codes[k], codes[j], strlen(codes[k])) == 0) { ok = 0; break; }
                }
            }
        }
        flags[i] = ok;
    }
    
    for (int i = 0; i < M; i++) {
        printf("%s\n", flags[i] ? "Yes" : "No");
    }
    return 0;
}

五、測試點 1 失敗原因分析與優化方向

變長數組 (VLA) 風險：代碼中 char codes[N][MAXCODE] 依賴 C99 VLA，部分 OJ 編譯器（或舊版 GCC）棧空間有限，大 N 導致棧溢出。修正：改用動態分配 malloc 或靜態最大尺寸 char codes[64][1000]。
頻率數組索引對齊：讀取字符頻率時未建立字符到索引的映射，直接按讀入順序存入 freq[i]，但學生提交碼的字符順序可能不同。修正：用結構體或哈希表存儲 char->freq 映射，驗證時按字符查找頻率。
前綴檢查邏輯漏洞：僅比較長度不同的編碼對，忽略了長度相同但內容相同的情況（雖然題目隱含字符唯一，編碼長度相同且相等即重複，非前綴）。但更嚴謹應用字典樹 (Trie) 統一檢查，O(總長度) 複雜度更優。
內存洩漏：malloc 分配的樹節點與堆數組未 free，雖然程序結束系統回收，但良好習慣應釋放。

六、進階優化：Trie 樹前綴檢查

typedef struct TrieNode {
    struct TrieNode *child[2]; // 0, 1
    int is_end;
} TrieNode;

int checkPrefixTrie(char *codes[], int n) {
    TrieNode *root = calloc(1, sizeof(TrieNode));
    for (int i = 0; i < n; i++) {
        TrieNode *p = root;
        for (int j = 0; codes[i][j]; j++) {
            int bit = codes[i][j] - '0';
            if (!p->child[bit]) p->child[bit] = calloc(1, sizeof(TrieNode));
            p = p->child[bit];
            if (p->is_end) { // 已有編碼是當前編碼前綴
                // 釋放內存略
                return 0;
            }
        }
        if (p->child[0] || p->child[1]) { // 當前編碼是已有編碼前綴
            return 0;
        }
        p->is_end = 1;
    }
    // 釋放 Trie 略
    return 1;
}