哈夫曼树编码及哈夫曼树组问题案例

已知四个字符权值。

（1）建立相应的哈夫曼编码树，构造哈夫曼编码表，

（2）在此基础上对压缩文件进行压缩。

输出要求：

（1）输出哈夫曼数组；字符的哈夫曼编码；

（2）文件原文；压缩后的编码

案例代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TREE_HT 100

/* 定义哈夫曼树的节点结构 */
struct MinHeapNode {
    char data;
    unsigned freq;
    struct MinHeapNode *left, *right;
};

/* 定义哈夫曼编码表的节点结构 */
struct HuffmanCode {
    char data;
    char *code;
};

/* 定义哈夫曼树的堆结构 */
struct MinHeap {
    unsigned size;
    unsigned capacity;
    struct MinHeapNode **array;
};

/* 创建一个新的哈夫曼树节点 */
struct MinHeapNode* newNode(char data, unsigned freq) {
    struct MinHeapNode* node = (struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));
    node->left = node->right = NULL;
    node->data = data;
    node->freq = freq;
    return node;
}

/* 创建一个新的哈夫曼树的堆 */
struct MinHeap* createMinHeap(unsigned capacity) {
    struct MinHeap* minHeap = (struct MinHeap*) malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct MinHeapNode**) malloc(minHeap->capacity * sizeof(struct MinHeapNode*));
    return minHeap;
}

/* 交换两个节点 */
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {
    struct MinHeapNode* t = *a;
    *a = *b;
    *b = t;
}

/* 维护堆的性质 */
void minHeapify(struct MinHeap* minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
        smallest = left;
    if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
        smallest = right;
    if (smallest != idx) {
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

/* 判断堆是否只剩一个节点 */
int isSizeOne(struct MinHeap* minHeap) {
    return (minHeap->size == 1);
}

/* 取出堆中最小的节点 */
struct MinHeapNode* extractMin(struct MinHeap* minHeap) {
    struct MinHeapNode* temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

/* 插入一个新的节点到堆中 */
void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = minHeapNode;
}

/* 判断是否为叶子节点 */
int isLeaf(struct MinHeapNode* root) {
    return !(root->left) && !(root->right);
}

/* 创建一个新的哈夫曼树 */
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {
    struct MinHeapNode *left, *right, *top;
    struct MinHeap* minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        insertMinHeap(minHeap, newNode(data[i], freq[i]));
    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

/* 将哈夫曼编码表中的节点插入到数组中 */
void storeCodes(struct MinHeapNode* root, char* codes[], int top, struct HuffmanCode huffmanCode[]) {
    if (root) {
        if (root->left) {
            codes[top] = (char*) malloc(MAX_TREE_HT * sizeof(char));
            strcpy(codes[top], "0");
            storeCodes(root->left, codes, top + 1, huffmanCode);
        }
        if (root->right) {
            codes[top] = (char*) malloc(MAX_TREE_HT * sizeof(char));
            strcpy(codes[top], "1");
            storeCodes(root->right, codes, top + 1, huffmanCode);
        }
        if (isLeaf(root)) {
            huffmanCode[root->data].data = root->data;
            huffmanCode[root->data].code = (char*) malloc(MAX_TREE_HT * sizeof(char));
            huffmanCode[root->data].code[0] = '\0';
            for (int i = 0; i < top; ++i)
                strcat(huffmanCode[root->data].code, codes[i]);
        }
    }
}

/* 压缩文件 */
void compressFile(FILE* fpIn, FILE* fpOut, struct HuffmanCode huffmanCode[]) {
    char c, code[MAX_TREE_HT];
    int i = 0;
    while ((c = fgetc(fpIn)) != EOF) {
        strcpy(code, huffmanCode[c].code);
        for (i = 0; code[i]; ++i)
            fputc(code[i], fpOut);
    }
}

/* 释放哈夫曼编码表中的内存空间 */
void freeHuffmanCode(struct HuffmanCode huffmanCode[], int size) {
    for (int i = 0; i < size; ++i)
        free(huffmanCode[i].code);
}

/* 主函数 */
int main() {
    char data[] = {'a', 'b', 'c', 'd'};
    int freq[] = {7, 5, 2, 4};
    int size = sizeof(data) / sizeof(data[0]);
    struct MinHeapNode* root = buildHuffmanTree(data, freq, size);
    struct HuffmanCode huffmanCode[size];
    char* codes[MAX_TREE_HT];
    int top = 0;
    memset(codes, 0, sizeof(codes));
    memset(huffmanCode, 0, sizeof(huffmanCode));
    storeCodes(root, codes, top, huffmanCode);
    FILE* fpIn = fopen("example.txt", "r");
    FILE* fpOut = fopen("compressed.txt", "w");
    compressFile(fpIn, fpOut, huffmanCode);
    fclose(fpIn);
    fclose(fpOut);
    freeHuffmanCode(huffmanCode, size);
    return 0;
}

在以上示例中，使用了C语言实现了构建哈夫曼树、生成哈夫曼编码表、压缩文件等功能。在主函数中，定义了字符权值数组，调用buildHuffmanTree函数构建哈夫曼树，调用storeCodes函数生成哈夫曼编码表，最后调用compressFile函数对文件进行压缩。

运行以上代码，即可得到对示例文件进行哈夫曼压缩的结果。