哈夫曼编码 C语言代码

哈夫曼编码是一种基于权值的自适应数据压缩算法，通过构建一棵二叉树来实现对字符的高效编码。每个字符的频率越高，其在树中的路径就越短，对应的编码也就越短。下面是一个简单的C语言实现哈夫曼编码的例子：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

typedef struct Node {
    char data;
    int freq;
    struct Node* left, *right;
} Node;

Node* newNode(char data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->freq = 0;
    node->left = node->right = NULL;
    return node;
}

// 插入节点到最小堆
void insert(Node** heap, char data) {
    Node* newNode = newNode(data);
    if (*heap == NULL || (*heap)->freq > newNode->freq) {
        newNode->freq += (*heap)->freq;
        *heap = newNode;
    } else {
        Node* temp = *heap;
        while (temp != NULL) {
            if (newNode->freq < temp->freq) {
                if (temp->left == NULL) {
                    temp->left = newNode;
                    break;
                } else if (newNode->freq <= temp->left->freq) {
                    temp = temp->left;
                } else {
                    newNode->freq += temp->freq;
                    *heap = temp;
                    temp->freq = 0;
                    temp->left = newNode;
                    break;
                }
            } else {
                if (temp->right == NULL) {
                    temp->right = newNode;
                    break;
                } else if (newNode->freq <= temp->right->freq) {
                    temp = temp->right;
                } else {
                    newNode->freq += temp->freq;
                    *heap = temp;
                    temp->freq = 0;
                    temp->right = newNode;
                    break;
                }
            }
        }
    }
}

// 构建哈夫曼树并生成编码
void buildHuffmanTree(Node** root, Node** codes) {
    // ...这里会实现二叉树的构建和遍历过程...
}

int main() {
    Node* root = NULL;
    Node** codes = NULL; // 用于存储每个字符及其编码
    // 先统计字符频率，然后插入到堆里，最后构建哈夫曼树
    // ...在这里填充实际的字符和频率...

    buildHuffmanTree(&root, &codes);

    // 对每个字符应用生成的编码
    for (/* 每个字符的数据和编码 */)

    free(root); // 释放内存

    return 0;
}