霍夫曼樹編碼 C 語言完整實作：權重統計、樹建構、編碼生成與輸出

霍夫曼編碼核心流程

1. 統計字元頻率 → 計算權重
2. 建構霍夫曼樹：反覆合併最小權重節點
3. 生成編碼：從葉節點向根回溯，左分支 0、右分支 1
4. 輸出編碼表

資料結構定義

typedef struct {
    unsigned int Weight;   // 權重
    unsigned int Parent;   // 雙親索引
    unsigned int lChild;   // 左孩子索引
    unsigned int rChild;   // 右孩子索引
} HTNode, *HuffmanTree;

typedef char** HuffmanCode;  // 編碼表：HuffmanCode[i] 為第 i 字元編碼

核心函數實作

1. 字元頻率統計

int LookFor(char* str, char letter, int count) {
    for (int i = 0; i < count; ++i)
        if (str[i] == letter) return i;
    return -1;
}

void OutputWeight(char* Data, int Length,
                  char** WhatLetter, int** Weight, int* Count) {
    char* Letter = (char*)malloc(Length);
    int* LetterCount = (int*)malloc(Length * sizeof(int));
    int AllCount = 0;

    for (int i = 0; i < Length; ++i) {
        int idx = LookFor(Letter, Data[i], AllCount);
        if (idx == -1) {
            Letter[AllCount] = Data[i];
            LetterCount[AllCount] = 1;
            ++AllCount;
        } else {
            ++LetterCount[idx];
        }
    }

    *Weight = (int*)malloc(AllCount * sizeof(int));
    *WhatLetter = (char*)malloc(AllCount);
    int Sum = 0;
    for (int i = 0; i < AllCount; ++i) Sum += LetterCount[i];

    for (int i = 0; i < AllCount; ++i) {
        float p = (float)LetterCount[i] / Sum;
        (*Weight)[i] = (int)(1000 * p);  // 權重放大 1000 倍為整數
        (*WhatLetter)[i] = Letter[i];
    }
    *Count = AllCount;
    free(Letter); free(LetterCount);
}

2. 霍夫曼樹建構

void Select(HuffmanTree HT, int Count, int* s1, int* s2) {
    // 從 HT[1..Count] 中找 Parent==0 的最小、次小權重節點
    unsigned int min1 = 0, min2 = 0;
    *s1 = *s2 = -1;
    for (int i = 1; i <= Count; ++i) {
        if (HT[i].Parent == 0) {
            if (min1 == 0 || HT[i].Weight < min1) {
                min2 = min1; min1 = HT[i].Weight;
                *s2 = *s1; *s1 = i;
            } else if (min2 == 0 || HT[i].Weight < min2) {
                min2 = HT[i].Weight;
                *s2 = i;
            }
        }
    }
}

void HuffmanCoding(HuffmanTree* HT, HuffmanCode* HC,
                   int* Weight, int Count) {
    if (Count <= 1) return;
    int Total = 2 * Count - 1;
    *HT = (HuffmanTree)malloc((Total + 1) * sizeof(HTNode));
    HuffmanTree p = *HT;  // 保留陣列起始位址

    // 初始化葉節點
    for (int i = 1; i <= Count; ++i) {
        (*HT)[i].Weight = *Weight++;
        (*HT)[i].Parent = (*HT)[i].lChild = (*HT)[i].rChild = 0;
    }
    // 初始化內部節點
    for (int i = Count + 1; i <= Total; ++i)
        (*HT)[i].Weight = (*HT)[i].Parent = (*HT)[i].lChild = (*HT)[i].rChild = 0;

    // 合併建樹
    for (int i = Count + 1; i <= Total; ++i) {
        int s1, s2;
        Select(*HT, i - 1, &s1, &s2);
        (*HT)[s1].Parent = i;
        (*HT)[s2].Parent = i;
        (*HT)[i].lChild = s1;
        (*HT)[i].rChild = s2;
        (*HT)[i].Weight = (*HT)[s1].Weight + (*HT)[s2].Weight;
    }

    // 生成編碼
    *HC = (HuffmanCode)malloc((Count + 1) * sizeof(char*));
    char* cd = (char*)malloc(Count * sizeof(char));
    cd[Count - 1] = '\0';

    for (int i = 1; i <= Count; ++i) {
        int start = Count - 1;
        for (unsigned int c = i, f = (*HT)[i].Parent; f != 0; c = f, f = (*HT)[f].Parent) {
            cd[--start] = ((*HT)[f].lChild == c) ? '0' : '1';
        }
        (*HC)[i] = (char*)malloc((Count - start) * sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }
    free(cd);
}

主程式測試

int main() {
    HuffmanTree HT;
    HuffmanCode HC;
    char Data[100];
    char* WhatLetter;
    int* Weight;
    int Count;

    printf("Please input the line: ");
    scanf("%s", Data);  // 例：aaaaaaaaaaaaabcccccc

    OutputWeight(Data, strlen(Data), &WhatLetter, &Weight, &Count);
    HuffmanCoding(&HT, &HC, Weight, Count);

    printf(" Letter Weight Code\n");
    for (int i = 0; i < Count; ++i)
        printf(" %c %d %s\n", WhatLetter[i], Weight[i], HC[i + 1]);

    // 記憶體釋放（略）
    return 0;
}

執行範例

輸入：aaaaaaaaaaaaabcccccc
輸出：
 Letter Weight Code
 a 500 0
 b 125 100
 c 375 101

關鍵實作細節

• 靜態陣列實作樹：索引 1 起始，0 不用，雙親/孩子皆用索引引用
• 權重整數化：機率 × 1000 避免浮點運算
• 編碼反向生成：從葉向根回溯，字元陣列尾端放 '\0'，向前填充
• 記憶體管理：所有 malloc 需配對 free，生產碼務必補全

複雜度分析

其中 n = 輸入長度，k = 不同字元數。優化建樹可用最小堆降至 O(k log k)。