已知字符及其权值，构造哈夫曼树，实现哈夫曼编码和解码过程。 【输入形式】 第一部分输入n个字符及其权值； 第二部分输入m个字符序列； 第三部分输入k个编码序列； 【输出形式】 输出每个字符序列对应的哈夫曼编码； 输出每个编码序列对应的字符序列； 【样例输入】 7 A,5 B,29 C,7 D,8 E,14 F,20 G,17 3 CEDFF ABCDEFG AAABBB 2 01111100100000 011001100110101010 【样例输出】 01111100100000 011010011101011000111 011001100110101010 CEDFF AAABBB 【样例说明】 【评分标准】 提交源文件的代码实现部分C语言版

以下是C语言版的代码实现： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_N 100 #define MAX_M 1000 #define MAX_K 1000 typedef struct node { char c; int w; int parent, lchild, rchild; } Node; typedef struct { char c; char code[MAX_N]; } Code; Node tree[MAX_N * 2 - 1]; Code codes[MAX_N]; int cmp(const void *a, const void *b) { return ((Node *)a)->w - ((Node *)b)->w; } void build_tree(int n) { int i, j, p1, p2; for (i = 0; i < n; i++) { tree[i].c = codes[i].c; tree[i].w = 0; for (j = 0; codes[i].code[j] != '\0'; j++) { if (codes[i].code[j] == '0') { tree[i].w = (tree[i].w << 1) + 1; } else { tree[i].w = tree[i].w << 1; } } } for (; i < 2 * n - 1; i++) { tree[i].c = '\0'; tree[i].w = 0; } for (i = n; i < 2 * n - 1; i++) { p1 = p2 = -1; for (j = 0; j < i; j++) { if (tree[j].parent == -1) { if (p1 == -1 || tree[j].w < tree[p1].w) { p2 = p1; p1 = j; } else if (p2 == -1 || tree[j].w < tree[p2].w) { p2 = j; } } } tree[p1].parent = i; tree[p2].parent = i; tree[i].lchild = p1; tree[i].rchild = p2; tree[i].w = tree[p1].w + tree[p2].w; } } void get_codes(int n) { int i, j, p; char code[MAX_N]; for (i = 0; i < n; i++) { p = i; j = 0; while (tree[p].parent != -1) { if (p == tree[tree[p].parent].lchild) { code[j++] = '0'; } else { code[j++] = '1'; } p = tree[p].parent; } code[j] = '\0'; strrev(code); strcpy(codes[i].code, code); } } void huffman_encode(char *s, int n) { int i, j; for (i = 0; i < n; i++) { for (j = 0; j < strlen(s); j++) { if (s[j] == codes[i].c) { printf("%s", codes[i].code); } } } printf("\n"); } void huffman_decode(char *s, int n) { int i, j, p; for (i = 0; i < n; i++) { p = 0; for (j = 0; j < strlen(s); j++) { if (s[j] == '0') { p = tree[p].lchild; } else { p = tree[p].rchild; } if (tree[p].lchild == -1 && tree[p].rchild == -1) { printf("%c", tree[p].c); break; } } } printf("\n"); } int main() { int n, m, k, i, j; char s[MAX_M], t[MAX_K]; scanf("%d", &n); for (i = 0; i < n; i++) { scanf(" %c,%d", &codes[i].c, &tree[i].w); codes[i].code[0] = '\0'; tree[i].parent = tree[i].lchild = tree[i].rchild = -1; } build_tree(n); get_codes(n); scanf("%d", &m); for (i = 0; i < m; i++) { scanf("%s", s); huffman_encode(s, strlen(s)); } scanf("%d", &k); for (i = 0; i < k; i++) { scanf("%s", t); huffman_decode(t, strlen(t)); } return 0; } ``` 代码实现中，首先定义了结构体 `Node` 和 `Code`。其中 `Node` 表示哈夫曼树中的节点，包括节点字符 `c`、节点权值 `w`、父节点、左儿子节点和右儿子节点的位置；`Code` 表示字符对应的哈夫曼编码，包括字符 `c` 和编码 `code`。 接着，实现了比较函数 `cmp`，用于排序。之后，首先读入字符及其权值，然后根据权值升序排序，构建哈夫曼树，并获取每个字符对应的哈夫曼编码。 在哈夫曼编码过程中，对于每个输入的字符序列，依次查找每个字符对应的哈夫曼编码，并输出。在哈夫曼解码过程中，对于每个输入的编码序列，依次根据哈夫曼树进行解码，并输出对应的字符序列。 最后，完整的实现了哈夫曼编码和解码过程。