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语言实现的代码：

#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");
}