实现哈夫曼树和哈夫曼编码C语言

以下是C语言实现哈夫曼树和哈夫曼编码的示例代码：

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

#define MAX_NODE_NUM 256
#define MAX_CODE_LEN 256

struct huff_node {
    unsigned char ch;           // 字符
    unsigned int freq;          // 频率
    struct huff_node *left;     // 左子节点
    struct huff_node *right;    // 右子节点
};

struct huff_tree {
    struct huff_node *root;     // 根节点
};

// 初始化哈夫曼树节点
struct huff_node *init_node(unsigned char ch, unsigned int freq) {
    struct huff_node *node = (struct huff_node *) malloc(sizeof(struct huff_node));
    node->ch = ch;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 构建哈夫曼树
struct huff_tree *create_huff_tree(unsigned int *freqs) {
    struct huff_node *nodes[MAX_NODE_NUM];
    int node_cnt = 0;
    int i, j;

    for (i = 0; i < MAX_NODE_NUM; i++) {
        if (freqs[i] > 0) {
            nodes[node_cnt++] = init_node(i, freqs[i]);
        }
    }

    while (node_cnt > 1) {
        unsigned int min_freq1 = -1, min_freq2 = -1;
        int min_idx1 = -1, min_idx2 = -1;

        for (i = 0; i < node_cnt; i++) {
            if (nodes[i]->freq < min_freq1) {
                min_freq2 = min_freq1;
                min_idx2 = min_idx1;
                min_freq1 = nodes[i]->freq;
                min_idx1 = i;
            } else if (nodes[i]->freq < min_freq2) {
                min_freq2 = nodes[i]->freq;
                min_idx2 = i;
            }
        }

        struct huff_node *new_node = init_node(0, min_freq1 + min_freq2);
        new_node->left = nodes[min_idx1];
        new_node->right = nodes[min_idx2];
        nodes[min_idx1] = new_node;
        nodes[min_idx2] = nodes[--node_cnt];
    }

    struct huff_tree *tree = (struct huff_tree *) malloc(sizeof(struct huff_tree));
    tree->root = nodes[0];
    return tree;
}

// 释放哈夫曼树节点及其子节点内存
void free_huff_node(struct huff_node *node) {
    if (node != NULL) {
        free_huff_node(node->left);
        free_huff_node(node->right);
        free(node);
    }
}

// 释放哈夫曼树内存
void free_huff_tree(struct huff_tree *tree) {
    free_huff_node(tree->root);
    free(tree);
}

// 计算哈夫曼编码
void calc_huff_code(struct huff_node *node, char **codes, char *buf, int len) {
    if (node->left == NULL && node->right == NULL) {
        buf[len] = '\0';
        codes[node->ch] = strdup(buf);
    } else {
        buf[len] = '0';
        calc_huff_code(node->left, codes, buf, len + 1);
        buf[len] = '1';
        calc_huff_code(node->right, codes, buf, len + 1);
    }
}

// 哈夫曼编码
void huff_encode(unsigned char *src, int src_len, char **codes, unsigned char *dst, int *dst_len) {
    int i, j, k;
    char *code;

    for (i = 0, k = 0; i < src_len; i++) {
        code = codes[src[i]];
        for (j = 0; j < strlen(code); j++) {
            if (code[j] == '0') {
                dst[k / 8] &= ~(1 << (7 - k % 8));
            } else {
                dst[k / 8] |= 1 << (7 - k % 8);
            }
            k++;
        }
    }

    *dst_len = (k + 7) / 8;
}

// 哈夫曼解码
void huff_decode(char *code, int code_len, struct huff_node *root, unsigned char *dst, int *dst_len) {
    int i;
    struct huff_node *node = root;

    for (i = 0; i < code_len; i++) {
        if (code[i] == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == NULL && node->right == NULL) {
            dst[*dst_len] = node->ch;
            (*dst_len)++;
            node = root;
        }
    }
}

int main() {
    unsigned char src[] = "hello, world!";
    int src_len = strlen(src);
    unsigned int freqs[MAX_NODE_NUM] = {0};
    char *codes[MAX_NODE_NUM] = {NULL};
    unsigned char dst[MAX_CODE_LEN] = {0};
    int dst_len;
    int i;

    // 统计字符频率
    for (i = 0; i < src_len; i++) {
        freqs[src[i]]++;
    }

    // 构建哈夫曼树
    struct huff_tree *tree = create_huff_tree(freqs);

    // 计算哈夫曼编码
    char buf[MAX_CODE_LEN];
    calc_huff_code(tree->root, codes, buf, 0);

    // 输出哈夫曼编码表
    for (i = 0; i < MAX_NODE_NUM; i++) {
        if (codes[i] != NULL) {
            printf("%c: %s\n", i, codes[i]);
        }
    }

    // 哈夫曼编码
    huff_encode(src, src_len, codes, dst, &dst_len);

    // 输出哈夫曼编码后的二进制数据
    for (i = 0; i < dst_len; i++) {
        printf("%02x ", dst[i]);
    }
    printf("\n");

    // 哈夫曼解码
    unsigned char decoded[MAX_CODE_LEN] = {0};
    int decoded_len = 0;
    char code[MAX_CODE_LEN];
    for (i = 0; i < dst_len * 8; i++) {
        if (dst[i / 8] & (1 << (7 - i % 8))) {
            code[i] = '1';
        } else {
            code[i] = '0';
        }
    }
    huff_decode(code, dst_len * 8, tree->root, decoded, &decoded_len);

    // 输出解码后的数据
    for (i = 0; i < decoded_len; i++) {
        printf("%c", decoded[i]);
    }
    printf("\n");

    // 释放内存
    for (i = 0; i < MAX_NODE_NUM; i++) {
        free(codes[i]);
    }
    free_huff_tree(tree);

    return 0;
}

该示例代码实现了哈夫曼树的构建、哈夫曼编码的计算、哈夫曼编码的实现和哈夫曼解码的实现。在使用时，只需要将需要编码的数据存放在一个 unsigned char 数组中，并传入该数组的长度，即可获得对应的哈夫曼编码后的二进制数据。在解码时，只需要将哈夫曼编码后的二进制数据转换为对应的字符数组即可。