哈夫曼编码和译码c语言

以下是哈夫曼编码和译码的 C 语言代码：

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

// 定义哈夫曼树节点
typedef struct huffman_node {
    char ch; // 当前节点表示的字符
    int weight; // 当前节点的权重
    struct huffman_node *left; // 左子节点指针
    struct huffman_node *right; // 右子节点指针
} huffman_node;

// 定义哈夫曼编码表节点
typedef struct huffman_code {
    char ch; // 当前节点表示的字符
    char *code; // 当前节点的哈夫曼编码
} huffman_code;

// 计算字符出现的频率
void calc_freq(char *str, int *freq)
{
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        freq[(int)str[i]]++;
    }
}

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

// 构建哈夫曼树
huffman_node *build_tree(int *freq)
{
    huffman_node *nodes[256];
    int node_count = 0;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            nodes[node_count++] = init_node((char)i, freq[i]);
        }
    }
    while (node_count > 1) {
        int min1 = 0, min2 = 1;
        if (nodes[min1]->weight > nodes[min2]->weight) {
            int temp = min1;
            min1 = min2;
            min2 = temp;
        }
        for (int i = 2; i < node_count; i++) {
            if (nodes[i]->weight < nodes[min1]->weight) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->weight < nodes[min2]->weight) {
                min2 = i;
            }
        }
        huffman_node *new_node = init_node('\0', nodes[min1]->weight + nodes[min2]->weight);
        new_node->left = nodes[min1];
        new_node->right = nodes[min2];
        nodes[min1] = new_node;
        nodes[min2] = nodes[--node_count];
    }
    return nodes[0];
}

// 生成哈夫曼编码表
void gen_codes(huffman_node *node, char *code, int depth, huffman_code *codes, int *code_count)
{
    if (node->left == NULL && node->right == NULL) {
        codes[*code_count].ch = node->ch;
        codes[*code_count].code = (char *)malloc((depth + 1) * sizeof(char));
        memcpy(codes[*code_count].code, code, depth);
        codes[*code_count].code[depth] = '\0';
        (*code_count)++;
    } else {
        code[depth] = '0';
        gen_codes(node->left, code, depth + 1, codes, code_count);
        code[depth] = '1';
        gen_codes(node->right, code, depth + 1, codes, code_count);
    }
}

// 哈夫曼编码
void huffman_encode(char *str, huffman_code *codes, int code_count)
{
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < code_count; j++) {
            if (str[i] == codes[j].ch) {
                printf("%s", codes[j].code);
                break;
            }
        }
    }
}

// 哈夫曼译码
void huffman_decode(char *str, huffman_node *root)
{
    huffman_node *node = root;
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (str[i] == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == NULL && node->right == NULL) {
            printf("%c", node->ch);
            node = root;
        }
    }
}

int main()
{
    char str[100];
    printf("请输入字符串：");
    scanf("%s", str);
    int freq[256] = {0};
    calc_freq(str, freq);
    huffman_node *root = build_tree(freq);
    char code[256] = {0};
    huffman_code codes[256];
    int code_count = 0;
    gen_codes(root, code, 0, codes, &code_count);
    printf("哈夫曼编码结果：");
    huffman_encode(str, codes, code_count);
    printf("\n");
    printf("哈夫曼译码结果：");
    huffman_decode("11011101001001101011011101111110011110100110001011110100011111001011011011101101100101101010101101001101001110100011001001001111010011110101110111111110101111001000001110111110000001101100000111101101000010110010011001010111010010101011101110010", root);
    printf("\n");
    return 0;
}

这是一个简单的哈夫曼编码和译码的实现，可以直接运行，输入字符串后会输出哈夫曼编码和译码的结果。