请用算法模拟实现哈夫曼编码,要求输入一个关键词的频率表,输出相应的每个关键词的编码。c

下面是哈夫曼编码的C语言实现，包括构建哈夫曼树和生成哈夫曼编码的过程：

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

#define MAX_NODE_NUM 10000
#define MAX_CODE_LEN 100

typedef struct node {
    int freq;           // 权值
    char ch;            // 关键词
    struct node *left;  // 左子节点
    struct node *right; // 右子节点
} Node;

typedef struct {
    char ch;            // 关键词
    int freq;           // 频率
    char code[MAX_CODE_LEN]; // 编码
} Code;

// 构建哈夫曼树
Node* build_huffman_tree(Code code_table[], int n) {
    Node *nodes[MAX_NODE_NUM];
    int i, j, k, heap_size = 0;

    // 将每个关键词构造成一个叶子节点
    for (i = 0; i < n; i++) {
        nodes[i] = (Node*)malloc(sizeof(Node));
        nodes[i]->ch = code_table[i].ch;
        nodes[i]->freq = code_table[i].freq;
        nodes[i]->left = nodes[i]->right = NULL;
        heap_size++;
    }

    // 将节点按照权值从小到大排序，构造成小根堆
    for (i = heap_size / 2 - 1; i >= 0; i--) {
        k = i;
        while (2 * k + 1 < heap_size) {
            j = 2 * k + 1;
            if (j + 1 < heap_size && nodes[j + 1]->freq < nodes[j]->freq) {
                j++;
            }
            if (nodes[k]->freq <= nodes[j]->freq) {
                break;
            }
            Node *tmp = nodes[k];
            nodes[k] = nodes[j];
            nodes[j] = tmp;
            k = j;
        }
    }

    // 依次取出堆顶的两个节点，合并成一个新的节点，然后将其插入堆中
    while (heap_size > 1) {
        Node *p1 = nodes[0];
        nodes[0] = nodes[heap_size - 1];
        heap_size--;
        k = 0;
        while (2 * k + 1 < heap_size) {
            j = 2 * k + 1;
            if (j + 1 < heap_size && nodes[j + 1]->freq < nodes[j]->freq) {
                j++;
            }
            if (nodes[k]->freq <= nodes[j]->freq) {
                break;
            }
            Node *tmp = nodes[k];
            nodes[k] = nodes[j];
            nodes[j] = tmp;
            k = j;
        }
        Node *p2 = nodes[0];
        nodes[0] = (Node*)malloc(sizeof(Node));
        nodes[0]->freq = p1->freq + p2->freq;
        nodes[0]->left = p1;
        nodes[0]->right = p2;
        k = 0;
        while (2 * k + 1 < heap_size) {
            j = 2 * k + 1;
            if (j + 1 < heap_size && nodes[j + 1]->freq < nodes[j]->freq) {
                j++;
            }
            if (nodes[k]->freq <= nodes[j]->freq) {
                break;
            }
            Node *tmp = nodes[k];
            nodes[k] = nodes[j];
            nodes[j] = tmp;
            k = j;
        }
    }

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

// 生成哈夫曼编码
void generate_huffman_code(Node *root, char *code, int len, Code code_table[]) {
    if (root->left == NULL && root->right == NULL) {
        int i;
        for (i = 0; i < len; i++) {
            code_table[root->ch].code[i] = code[i];
        }
        code_table[root->ch].code[len] = '\0';
        return;
    }
    code[len] = '0';
    generate_huffman_code(root->left, code, len + 1, code_table);
    code[len] = '1';
    generate_huffman_code(root->right, code, len + 1, code_table);
}

int main() {
    int n, i;
    Code code_table[MAX_NODE_NUM];
    Node *root;
    char code[MAX_CODE_LEN];

    // 输入关键词的频率表
    printf("请输入关键词的数量：");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        printf("请输入第%d个关键词和它的频率（用空格分隔）：", i + 1);
        scanf("%s %d", &code_table[i].ch, &code_table[i].freq);
    }

    // 构建哈夫曼树，并生成哈夫曼编码
    root = build_huffman_tree(code_table, n);
    generate_huffman_code(root, code, 0, code_table);

    // 输出每个关键词的编码
    printf("关键词\t频率\t编码\n");
    for (i = 0; i < n; i++) {
        printf("%c\t%d\t%s\n", code_table[i].ch, code_table[i].freq, code_table[i].code);
    }

    return 0;
}

在上述代码中，我们首先定义了一个 `Node` 结构体，表示哈夫曼树的节点，其中包含了关键词的权值、字符值以及左右子节点的指针。为了方便生成编码，我们还定义了一个 `Code` 结构体，其中包含了关键词的频率和编码。

在 `build_huffman_tree` 函数中，我们首先将所有关键词构造成叶子节点，并将它们按照权值从小到大排序，构造成一个小根堆。然后我们依次取出堆顶的两个节点，合并成一个新的节点，并将其插入堆中。重复这个过程，直到堆中只剩下一个节点，即根节点，这个节点就是哈夫曼树的根。

在 `generate_huffman_code` 函数中，我们利用递归的方式遍历哈夫曼树，对于每个叶子节点，将它的编码存储到相应的 `Code` 结构体中。在递归过程中，我们使用一个字符数组 `code` 来存储当前路径的编码，`len` 表示当前已经编码的位数。

最后在 `main` 函数中，我们输入关键词的频率表，然后调用 `build_huffman_tree` 函数构建哈夫曼树，再调用 `generate_huffman_code` 函数生成哈夫曼编码，最后输出每个关键词的编码。