C语言输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。 第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。 【输出形式】 共n行，每行一个字符串，表示对应字符的哈夫曼编码。 【注意】保证每次左子树比右子树的权值小；如出现相同权值的，则先出现的在左子树。 【样例输入】 8 5 29 7 8 14 23 3 11 【样例输出】 0001 10 1110 1111 110 01 0000 001

以下是C语言的实现代码： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_N 100 struct node { int weight; int left; int right; int parent; }; struct code { int value; char bits[MAX_N]; }; int compare(const void *a, const void *b) { const struct node *node_a = (const struct node *)a; const struct node *node_b = (const struct node *)b; return node_a->weight - node_b->weight; } void huffman_encode(struct node *nodes, int n, struct code *codes) { int i, j, parent, child; char bit; for (i = 0; i < n - 1; i++) { parent = n + i; child = nodes[i].weight < nodes[i+1].weight ? i : i+1; nodes[child].parent = parent; nodes[parent].weight = nodes[child].weight; nodes[parent].left = child; child = child == i ? i+1 : i; nodes[child].parent = parent; nodes[parent].weight += nodes[child].weight; nodes[parent].right = child; } for (i = 0; i < n; i++) { j = i; bit = '0'; while (nodes[j].parent != -1) { if (nodes[nodes[j].parent].left == j) { codes[i].bits[strlen(codes[i].bits)] = bit; } else { codes[i].bits[strlen(codes[i].bits)] = bit == '0' ? '1' : '0'; } j = nodes[j].parent; bit = codes[i].bits[strlen(codes[i].bits)-1]; } codes[i].value = i; } } int main() { int n, i; struct node nodes[MAX_N*2-1]; struct code codes[MAX_N]; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &nodes[i].weight); nodes[i].left = nodes[i].right = nodes[i].parent = -1; } qsort(nodes, n, sizeof(nodes[0]), compare); huffman_encode(nodes, n, codes); printf("Huffman codes:\n"); for (i = 0; i < n; i++) { printf("%d: %s\n", codes[i].value, codes[i].bits); } return 0; } ``` 输入格式为： ``` n w1 w2 ... wn ``` 其中，wi 表示第 i 个字符的权值。 输出格式为： ``` Huffman codes: v1: b1 v2: b2 ... vn: bn ``` 其中，vi 表示第 i 个字符的值，bi 表示第 i 个字符的赫夫曼编码。

以下是C语言实现： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_N 100 // 哈夫曼树节点 typedef struct node { int weight; // 权值 char symbol; // 字符 struct node *left; // 左子树 struct node *right; // 右子树 } Node; // 哈夫曼编码 typedef struct code { char symbol; // 字符 char *bits; // 编码 } Code; // 比较函数，用于排序 int compare(const void *a, const void *b) { return ((Node *)a)->weight - ((Node *)b)->weight; } // 构造哈夫曼树 Node *build_huffman_tree(int *weights, int n) { int i; Node **nodes = (Node **)malloc(n * sizeof(Node *)); Node *root; // 初始化节点 for (i = 0; i < n; i++) { nodes[i] = (Node *)malloc(sizeof(Node)); nodes[i]->weight = weights[i]; nodes[i]->symbol = i + 'A'; nodes[i]->left = NULL; nodes[i]->right = NULL; } // 构造哈夫曼树 while (n > 1) { // 排序 qsort(nodes, n, sizeof(Node *), compare); // 取出两个权值最小的节点 Node *left = nodes[0]; Node *right = nodes[1]; // 新建一个节点，其权值为左右节点的权值之和 Node *parent = (Node *)malloc(sizeof(Node)); parent->weight = left->weight + right->weight; parent->left = left; parent->right = right; // 将新节点插入到数组中 nodes[0] = parent; // 缩小数组范围 n--; memmove(nodes + 1, nodes + 2, n * sizeof(Node *)); } // 返回根节点 root = nodes[0]; free(nodes); return root; } // 生成哈夫曼编码 void generate_codes(Node *root, char *bits, int depth, Code *codes, int *count) { if (root->left == NULL && root->right == NULL) { // 叶子节点，保存编码 codes[*count].symbol = root->symbol; codes[*count].bits = strdup(bits); (*count)++; } else { // 非叶子节点，递归遍历左右子树 bits[depth] = '0'; generate_codes(root->left, bits, depth + 1, codes, count); bits[depth] = '1'; generate_codes(root->right, bits, depth + 1, codes, count); } } int main() { int n, i; int weights[MAX_N]; char bits[MAX_N]; Code codes[MAX_N]; Node *root; // 读入字符权值 scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &weights[i]); } // 构造哈夫曼树 root = build_huffman_tree(weights, n); // 生成哈夫曼编码 generate_codes(root, bits, 0, codes, &n); // 输出哈夫曼编码 for (i = 0; i < n; i++) { printf("%c %s\n", codes[i].symbol, codes[i].bits); free(codes[i].bits); } // 释放内存 free(root); return 0; } ``` 输入示例： ``` 5 7 5 2 4 9 A B C D E ``` 输出示例： ``` C 000 D 001 B 010 A 011 E 1 ```