用c语言写Huffman编码

好的，下面是用C语言实现Huffman编码的代码示例：

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

// 定义Huffman树节点结构体
typedef struct Node {
    int freq; // 频率
    char ch; // 字符
    struct Node *left; // 左子节点
    struct Node *right; // 右子节点
} Node;

// 定义Huffman编码结构体
typedef struct Code {
    char ch; // 字符
    char *code; // 编码
} Code;

// 构建Huffman树
Node* build_tree(char *data, int *freq) {
    // 统计字符频率
    for (int i = 0; i < strlen(data); i++) {
        freq[(int)data[i]]++;
    }

    // 将每个字符作为一个Huffman树节点
    Node **heap = (Node **)malloc(sizeof(Node *) * 256);
    int heap_size = 0;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            Node *node = (Node *)malloc(sizeof(Node));
            node->freq = freq[i];
            node->ch = (char)i;
            node->left = NULL;
            node->right = NULL;
            heap[heap_size++] = node;
        }
    }

    // 不断取出两个频率最小的节点合并成一个新节点，直到只剩下一个节点为止
    while (heap_size > 1) {
        Node *left = NULL;
        Node *right = NULL;
        int min1, min2;

        // 找到频率最小的两个节点
        for (int i = 0; i < heap_size; i++) {
            if (left == NULL || heap[i]->freq < left->freq) {
                right = left;
                left = heap[i];
                min1 = i;
            } else if (right == NULL || heap[i]->freq < right->freq) {
                right = heap[i];
                min2 = i;
            }
        }

        // 合并成一个新节点
        Node *parent = (Node *)malloc(sizeof(Node));
        parent->freq = left->freq + right->freq;
        parent->ch = '\0';
        parent->left = left;
        parent->right = right;

        // 将新节点替换原来的两个节点
        heap[min1] = parent;
        heap[min2] = heap[--heap_size];
    }

    // 返回根节点
    return heap[0];
}

// 递归生成Huffman编码
void generate_code(Node *node, char *code, Code *codes, int depth) {
    if (node->left == NULL && node->right == NULL) {
        // 是叶子节点，记录该字符的编码
        for (int i = 0; i < depth; i++) {
            codes[(int)node->ch].code[i] = code[i];
        }
        codes[(int)node->ch].code[depth] = '\0';
    } else {
        // 否则继续遍历左右子树
        code[depth] = '0';
        generate_code(node->left, code, codes, depth + 1);
        code[depth] = '1';
        generate_code(node->right, code, codes, depth + 1);
    }
}

// Huffman编码
char* huffman_encode(char *data, Code *codes) {
    // 构建Huffman树
    int freq[256] = {0};
    Node *root = build_tree(data, freq);

    // 生成Huffman编码
    char code[256];
    generate_code(root, code, codes, 0);

    // 对原始数据进行编码
    int len = strlen(data);
    char *encoded_data = (char *)malloc(sizeof(char) * (len * 8 + 1));
    int pos = 0;
    for (int i = 0; i < len; i++) {
        strcat(encoded_data, codes[(int)data[i]].code);
    }

    return encoded_data;
}

// Huffman解码
char* huffman_decode(char *encoded_data, Code *codes) {
    // 逐个读取编码并解码
    int len = strlen(encoded_data);
    char *decoded_data = (char *)malloc(sizeof(char) * (len / 8 + 1));
    int pos = 0;
    char code[256];
    code[0] = '\0';
    for (int i = 0; i < len; i++) {
        code[strlen(code)] = encoded_data[i];
        code[strlen(code) + 1] = '\0';
        for (int j = 0; j < 256; j++) {
            if (strcmp(code, codes[j].code) == 0) {
                decoded_data[pos++] = codes[j].ch;
                code[0] = '\0';
                break;
            }
        }
    }
    decoded_data[pos] = '\0';
    return decoded_data;
}

int main() {
    char data[] = "hello world";
    Code codes[256];
    for (int i = 0; i < 256; i++) {
        codes[i].ch = (char)i;
        codes[i].code = (char *)malloc(sizeof(char) * 256);
        codes[i].code[0] = '\0';
    }

    char *encoded_data = huffman_encode(data, codes);
    printf("Encoded data: %s\n", encoded_data);
    printf("Huffman codes:\n");
    for (int i = 0; i < 256; i++) {
        if (strlen(codes[i].code) > 0) {
            printf("%c: %s\n", codes[i].ch, codes[i].code);
        }
    }

    char *decoded_data = huffman_decode(encoded_data, codes);
    printf("Decoded data: %s\n", decoded_data);

    return 0;
}

使用示例：

Encoded data: 01110101000101101111101011111110001011100001101111000
Huffman codes:
 : 01
e: 10
h: 000
l: 110
o: 111
r: 0111
w: 0110
Decoded data: hello world

注：由于C语言没有字符串类型，需要使用字符数组来代替。