题解 | #【模板】哈夫曼编码#

用C语言写，超时了，通过用例5/10。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXINT 32676

// 哈夫曼树每一个结点的类型
typedef struct  HuffmanTreeNodeType {
    int weight;                     // 权值
    int parent, lchild, rchild;     // 双亲、左孩子、有孩子的位置
} HuffmanTreeNodeType;

// 找最小的根结点和次小的根结点
void MinSubmin(HuffmanTreeNodeType* HuffmanTree, int len, int* min,
               int* submin) {
    int minval = MAXINT, subminval = MAXINT;
    for (int i = 0; i <= len; i++) {
        if (HuffmanTree[i].weight < minval && HuffmanTree[i].parent == 0) {
            subminval = minval;
            *submin = *min;
            minval = HuffmanTree[i].weight;
            *min = i;
        } else if (HuffmanTree[i].weight < subminval && HuffmanTree[i].parent == 0) {
            subminval = HuffmanTree[i].weight;
            *submin = i;
        }
    }
}

// 创建哈夫曼树
void CreatHuffmanTree(HuffmanTreeNodeType** HuffmanTree, int n) {
    // 先初始化数组，即哈夫曼树的初态
    // 有n个结点，需要n-1次合并，共产生2n-1个结点
    // 每一个结点的四个域均为0
    (*HuffmanTree) = (HuffmanTreeNodeType*)malloc(sizeof(HuffmanTreeNodeType) *
                     (2 * n - 1));
    for (int i = 0; i < 2 * n - 1; i++) {
        (*HuffmanTree)[i].weight = 0;
        (*HuffmanTree)[i].parent = 0;
        (*HuffmanTree)[i].lchild = 0;
        (*HuffmanTree)[i].rchild = 0;
    }
    // 输入前n个元素的weight
    for (int i = 0; i < n; i++)
        scanf("%d", &(*HuffmanTree)[i].weight);
    // 构建哈夫曼树
    int min, submin;
    for (int i = n; i < 2 * n - 1; i++) {
        MinSubmin((*HuffmanTree), i - 1, &min, &submin);
        (*HuffmanTree)[i].lchild = min;
        (*HuffmanTree)[i].rchild = submin;
        (*HuffmanTree)[i].weight = (*HuffmanTree)[min].weight +
                                   (*HuffmanTree)[submin].weight;
        (*HuffmanTree)[min].parent = i;
        (*HuffmanTree)[submin].parent = i;
    }
}

// 构建哈夫曼编码
void CreatHuffmanCode(HuffmanTreeNodeType* HuffmanTree, char*** HuffmanCodeList,
                      int n) {
    (*HuffmanCodeList) = (char**)malloc(sizeof(char*) * n);
    char* code = (char*)malloc(sizeof(char) * n);
    memset(code, '\0', n);
    for (int i = 0; i < n; i++) {
        int start = n - 1;
        int cur = i;
        int par = HuffmanTree[cur].parent;
        while (par != 0) {
            --start;
            if (HuffmanTree[par].lchild == cur)
                code[start] = '0';
            else
                code[start] = '1';
            cur = par;
            par = HuffmanTree[cur].parent;
        }
        (*HuffmanCodeList)[i] = (char*)malloc(sizeof(char) * (n - start));
        strcpy((*HuffmanCodeList)[i], &code[start]);
    }
    free(code);
}

// 求哈夫曼编码的长度
int GetHuffmanCodeLength(HuffmanTreeNodeType* HuffmanTree,
                         char** HuffmanCodeList,
                         int n) {
    int length = 0;
    for (int i = 0; i < n; i++)
        length += HuffmanTree[i].weight * strlen(HuffmanCodeList[i]);
    return length;
}

int main(void) {
    // 定义一棵哈夫曼树
    HuffmanTreeNodeType* HuffmanTree;
    // 定义结点个数
    int n;
    // 读入哈夫曼树的结点个数
    scanf("%d", &n);
    // 创建哈夫曼树
    CreatHuffmanTree(&HuffmanTree, n);
    // 构建哈夫曼编码
    char** HuffmanCodeList;
    CreatHuffmanCode(HuffmanTree, &HuffmanCodeList, n);
    // 求哈夫曼编码的长度
    int HuffmanCodeLength = GetHuffmanCodeLength(HuffmanTree, HuffmanCodeList, n);
    printf("%d\n", HuffmanCodeLength);
    return 0;
}