c语言【问题描述】 输入哈夫曼字符序列，构造哈夫曼树，并计算哈夫曼编码 【输入形式】 第一行输入整数n，表示n个字符(n>1并且不大于10)； 后续输入n行哈夫曼字符及其权值（字符和权值以逗号分隔）。 【输出形式】 输出哈夫曼树的顺序存储形式（数据之间以空格分隔） 输出哈夫曼编码 【样例输入】 7 a,10 c,1 e,15 i,12 s,3 t,4 w,13 【样例输出】 HuffTable: a 10 9 -1 -1 c 1 7 -1 -1 e 15 11 -1 -1 i 12 10 -1 -1 s 3 7 -1 -1 t 4 8 -1 -1 w 13 10 -1 -1 0 4 8 1 4 0 8 9 5 7 0 18 11 8 0 0 25 12 3 6 0 33 12 2 9 0 58 -1 10 11 HuffCode: a:111 c:11010 e:10 i:00 s:11011 t:1100 w:01

以下是C语言实现的代码： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_N 10 // 最大字符数 #define MAX_TREE_SIZE (2 * MAX_N - 1) // 最大哈夫曼树节点数 #define MAX_CODE_LEN 20 // 最大编码长度 // 哈夫曼树节点结构体 typedef struct { int weight; // 权值 int parent; // 双亲节点下标 int left; // 左孩子节点下标 int right; // 右孩子节点下标 } HTNode; // 哈夫曼编码结构体 typedef struct { char ch; // 字符 char code[MAX_CODE_LEN + 1]; // 编码 } CodeNode; void huffmanEncoding(int n, char chList[], int weightList[]); void createHuffmanTree(HTNode huffTree[], int n); void selectTwoMinWeight(HTNode huffTree[], int n, int* pMin1, int* pMin2); void huffmanCoding(HTNode huffTree[], int n, CodeNode codeList[]); void printHuffTable(HTNode huffTree[], int n); void printHuffCode(CodeNode codeList[], int n); int main() { int n, i, weight; char chList[MAX_N]; // 输入n和每个字符的权值 scanf("%d", &n); int weightList[n]; for (i = 0; i < n; i++) { getchar(); // 读入空格 scanf("%c,%d", &chList[i], &weightList[i]); } huffmanEncoding(n, chList, weightList); return 0; } // 哈夫曼编码 void huffmanEncoding(int n, char chList[], int weightList[]) { HTNode huffTree[MAX_TREE_SIZE]; CodeNode codeList[MAX_N]; int i; createHuffmanTree(huffTree, n); huffmanCoding(huffTree, n, codeList); printHuffTable(huffTree, n); printHuffCode(codeList, n); } // 构造哈夫曼树 void createHuffmanTree(HTNode huffTree[], int n) { int i, m, min1, min2; // 初始化哈夫曼树节点 for (i = 0; i < 2 * n - 1; i++) { huffTree[i].weight = 0; huffTree[i].parent = -1; huffTree[i].left = -1; huffTree[i].right = -1; } // 输入每个节点的权值 for (i = 0; i < n; i++) { huffTree[i].weight = weightList[i]; } // 构造哈夫曼树 m = 2 * n - 1; for (i = n; i < m; i++) { selectTwoMinWeight(huffTree, i, &min1, &min2); huffTree[min1].parent = i; huffTree[min2].parent = i; huffTree[i].left = min1; huffTree[i].right = min2; huffTree[i].weight = huffTree[min1].weight + huffTree[min2].weight; } } // 选择权值最小的两个节点 void selectTwoMinWeight(HTNode huffTree[], int n, int* pMin1, int* pMin2) { int i, min1, min2; min1 = min2 = -1; for (i = 0; i < n; i++) { if (huffTree[i].parent == -1) { if (min1 == -1 || huffTree[i].weight < huffTree[min1].weight) { min2 = min1; min1 = i; } else if (min2 == -1 || huffTree[i].weight < huffTree[min2].weight) { min2 = i; } } } *pMin1 = min1; *pMin2 = min2; } // 哈夫曼编码 void huffmanCoding(HTNode huffTree[], int n, CodeNode codeList[]) { int i, j, parent, current; char code[MAX_CODE_LEN + 1]; // 初始化编码表 for (i = 0; i < n; i++) { codeList[i].ch = chList[i]; codeList[i].code[0] = '\0'; } // 从叶子节点向根节点遍历 for (i = 0; i < n; i++) { current = i; parent = huffTree[current].parent; while (parent != -1) { if (huffTree[parent].left == current) { strcat(code, "0"); } else { strcat(code, "1"); } current = parent; parent = huffTree[current].parent; } strrev(code); // 将编码反转 strcpy(codeList[i].code, code); code[0] = '\0'; } } // 输出哈夫曼表 void printHuffTable(HTNode huffTree[], int n) { int i; printf("HuffTable:"); for (i = 0; i < n; i++) { printf(" %c %d %d %d %d", chList[i], huffTree[i].weight, huffTree[i].parent, huffTree[i].left, huffTree[i].right); } printf(" %d %d %d %d %d\n", huffTree[n].weight, huffTree[n].parent, huffTree[n].left, huffTree[n].right, 0); } // 输出哈夫曼编码 void printHuffCode(CodeNode codeList[], int n) { int i; printf("HuffCode:"); for (i = 0; i < n; i++) { printf(" %c:%s", codeList[i].ch, codeList[i].code); } printf("\n"); } ```