输入n个叶子结点的权值构造哈夫曼树；根据哈夫曼树构造哈夫曼编码，并对密文完成解码工作。 用c语言

以下是C语言的实现代码： ``` #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_NODE_NUM 1000 // 最大结点数 // 哈夫曼树结点 typedef struct { int weight; // 权值 int parent, left, right; // 父节点、左子节点、右子节点编号 } HTNode; // 哈夫曼编码结点 typedef struct { char bits[MAX_NODE_NUM]; // 编码位串 int start; // 编码起始位置 } HCode; // 选择权值最小的两个结点 void select(HTNode *ht, int n, int *s1, int *s2) { int i, min1 = 0x7fffffff, min2 = 0x7fffffff; for (i = 1; i <= n; ++i) { if (ht[i].parent == 0) { // 未被选择 if (ht[i].weight < min1) { min2 = min1; min1 = ht[i].weight; *s2 = *s1; *s1 = i; } else if (ht[i].weight < min2) { min2 = ht[i].weight; *s2 = i; } } } } // 构造哈夫曼树 void huffmanTree(HTNode *ht, int n) { int i, s1, s2; for (i = 1; i <= 2 * n - 1; ++i) { ht[i].parent = ht[i].left = ht[i].right = 0; } for (i = n + 1; i <= 2 * n - 1; ++i) { select(ht, i - 1, &s1, &s2); ht[s1].parent = i; ht[s2].parent = i; ht[i].left = s1; ht[i].right = s2; ht[i].weight = ht[s1].weight + ht[s2].weight; } } // 生成哈夫曼编码 void huffmanCode(HTNode *ht, HCode *hc, int n) { int i, j, c, p; for (i = 1; i <= n; ++i) { hc[i].start = n; c = i; p = ht[i].parent; while (p != 0) { --hc[i].start; if (ht[p].left == c) { hc[i].bits[hc[i].start] = '0'; } else { hc[i].bits[hc[i].start] = '1'; } c = p; p = ht[p].parent; } } } // 解码 void huffmanDecode(HTNode *ht, char *code, int n) { int i, p = 2 * n - 1; for (i = 0; code[i] != '\0'; ++i) { if (code[i] == '0') { p = ht[p].left; } else { p = ht[p].right; } if (ht[p].left == 0 && ht[p].right == 0) { printf("%d ", p); p = 2 * n - 1; } } } int main() { int n, i; HTNode ht[MAX_NODE_NUM]; HCode hc[MAX_NODE_NUM]; char code[MAX_NODE_NUM]; printf("请输入叶子结点的个数："); scanf("%d", &n); printf("请输入叶子结点的权值："); for (i = 1; i <= n; ++i) { scanf("%d", &ht[i].weight); } huffmanTree(ht, n); huffmanCode(ht, hc, n); printf("哈夫曼编码为：\n"); for (i = 1; i <= n; ++i) { printf("%d：", i); int j; for (j = hc[i].start; j < n; ++j) { printf("%c", hc[i].bits[j]); } printf("\n"); } printf("请输入哈夫曼编码："); scanf("%s", code); printf("哈夫曼解码结果为：\n"); huffmanDecode(ht, code, n); return 0; } ``` 注意：此代码实现中没有采用优先队列等高效数据结构，仅适用于小规模数据。