用C语言完整的写出输入字符串求出哈夫曼编码并实现译码

以下是输入字符串求哈夫曼编码并实现译码的C语言代码：

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

#define MAX_SIZE 256

typedef struct node {
    char ch;  // 字符
    int freq; // 出现次数
    struct node *left, *right; // 左右子树
} Node;

typedef struct code {
    char ch; // 字符
    char *huff_code; // 哈夫曼编码
} Code;

// 初始化节点
Node *init_node(char ch, int freq) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

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

// 生成哈夫曼编码
void generate_huff_code(Node *root, char *code, int depth, Code huff_codes[]) {
    if (!root) {
        return;
    }
    if (root->ch) {
        huff_codes[root->ch].ch = root->ch;
        huff_codes[root->ch].huff_code = (char *)malloc(sizeof(char) * (depth + 1));
        strcpy(huff_codes[root->ch].huff_code, code);
        return;
    }
    code[depth] = '0';
    generate_huff_code(root->left, code, depth + 1, huff_codes);
    code[depth] = '1';
    generate_huff_code(root->right, code, depth + 1, huff_codes);
}

// 哈夫曼编码
void huff_encode(char *str, Code huff_codes[]) {
    int freq[MAX_SIZE] = {0};
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        freq[str[i]]++;
    }
    int count = 0;
    Node *nodes[MAX_SIZE];
    for (int i = 0; i < MAX_SIZE; i++) {
        if (freq[i] > 0) {
            nodes[count++] = init_node(i, freq[i]);
        }
    }
    Node *root = build_huff_tree(nodes, count);
    char code[MAX_SIZE];
    generate_huff_code(root, code, 0, huff_codes);
}

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

int main() {
    char str[MAX_SIZE];
    printf("输入字符串: ");
    fgets(str, MAX_SIZE, stdin);
    Code huff_codes[MAX_SIZE];
    memset(huff_codes, 0, sizeof(huff_codes));
    huff_encode(str, huff_codes);
    printf("哈夫曼编码表：\n");
    for (int i = 0; i < MAX_SIZE; i++) {
        if (huff_codes[i].huff_code) {
            printf("%c: %s\n", huff_codes[i].ch, huff_codes[i].huff_code);
        }
    }
    printf("哈夫曼编码：");
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        printf("%s", huff_codes[str[i]].huff_code);
    }
    printf("\n");
    printf("译码结果：");
    huff_decode("10101010111100111101101111001110110101100110101011101110110010100101101011110000010100001100110110", build_huff_tree((Node *[]){init_node(' ', 1), NULL}, 1));
    printf("\n");
    return 0;
}

其中，`Node`表示哈夫曼树的节点，`Code`表示哈夫曼编码表中的一项，`init_node`函数用于初始化节点，`build_huff_tree`函数用于构建哈夫曼树，`generate_huff_code`函数用于递归生成哈夫曼编码，`huff_encode`函数用于编码字符串，`huff_decode`函数用于译码哈夫曼编码，`main`函数为程序入口。