哈夫曼编码（C语言实现）

以下是一个简单的C语言实现哈夫曼编码的例子：

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

#define MAX_TREE_HT 100

// 哈夫曼树结构体
struct HuffmanNode {
    char data;
    unsigned freq;
    struct HuffmanNode *left, *right;
};

// 哈夫曼编码结构体
struct HuffmanCode {
    char data;
    char *code;
};

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

// 建立一个哈夫曼树
struct HuffmanNode* buildHuffmanTree(char data[], int freq[], int size) {
    struct HuffmanNode *left, *right, *top;
    int i;

    // 创建一个最小堆，用于存放节点
    struct MinHeap* minHeap = createMinHeap(size);

    // 将所有节点插入到最小堆中
    for (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 encode(struct HuffmanNode* root, char* code, int top, struct HuffmanCode huffmanCode[]) {
    if (root->left) {
        code[top] = '0';
        encode(root->left, code, top + 1, huffmanCode);
    }

    if (root->right) {
        code[top] = '1';
        encode(root->right, code, top + 1, huffmanCode);
    }

    // 如果是叶子节点，则将其编码存储到哈夫曼编码结构体中
    if (!root->left && !root->right) {
        huffmanCode[root->data].data = root->data;
        huffmanCode[root->data].code = (char*) malloc(sizeof(char) * (top + 1));
        strcpy(huffmanCode[root->data].code, code);
    }
}

// 打印哈夫曼编码
void printHuffmanCodes(struct HuffmanCode huffmanCode[], int size) {
    printf("Huffman Codes:\n");
    for (int i = 0; i < size; ++i) {
        if (huffmanCode[i].code) {
            printf("%c - %s\n", huffmanCode[i].data, huffmanCode[i].code);
        }
    }
}

// 哈夫曼编码主函数
void HuffmanCodes(char data[], int freq[], int size) {
    struct HuffmanNode* root = buildHuffmanTree(data, freq, size);

    // 创建一个哈夫曼编码结构体数组，用于存储每个字符的哈夫曼编码
    struct HuffmanCode huffmanCode[size];

    char code[MAX_TREE_HT];
    int top = 0;

    encode(root, code, top, huffmanCode);
    printHuffmanCodes(huffmanCode, size);
}

int main() {
    char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int freq[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(data) / sizeof(data[0]);

    HuffmanCodes(data, freq, size);

    return 0;
}

以上代码实现了一个简单的哈夫曼编码，它会将给定的字符数组和频率数组作为输入，并输出每个字符的哈夫曼编码。当然，这只是一个基础的实现，实际上哈夫曼编码还有很多优化和扩展。