给我一份C语言的哈夫曼编码例程

以下是一个简单的C语言哈夫曼编码的例程：

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

// 哈夫曼树节点结构体
typedef struct
{
    int weight; // 权重
    int parent; // 父节点
    int lchild; // 左子节点
    int rchild; // 右子节点
}HuffmanNode, *HuffmanTree;

// 哈夫曼编码结构体
typedef struct
{
    int bit[100]; // 编码位串
    int start; // 起始位置
}HuffmanCode, *HuffmanCodeTable;

// 选择两个权值最小的节点
void select(HuffmanTree ht, int n, int *s1, int *s2)
{
    int i, j;
    int min1 = 0x7fffffff, min2 = 0x7fffffff; // 定义最小值为无穷大

    for(i = 0; i < n; i++)
    {
        if(ht[i].parent == -1 && ht[i].weight < min1) // 如果找到更小的权值节点
        {
            min2 = min1; // 原最小值变为次小值
            *s2 = *s1; // 原最小值节点变为次小值节点
            min1 = ht[i].weight; // 更新最小值
            *s1 = i; // 更新最小值节点
        }
        else if(ht[i].parent == -1 && ht[i].weight < min2) // 如果找到次小的权值节点
        {
            min2 = ht[i].weight; // 更新次小值
            *s2 = i; // 更新次小值节点
        }
    }
}

// 构建哈夫曼树
void createHuffmanTree(HuffmanTree *ht, int n, int *w)
{
    if(n <= 1) // 如果只有一个节点，则无需构建
        return;

    int m = 2 * n - 1; // 哈夫曼树节点数

    *ht = (HuffmanTree)malloc(m * sizeof(HuffmanNode)); // 分配空间

    int i;
    for(i = 0; i < n; i++) // 初始化叶子节点
    {
        (*ht)[i].weight = w[i];
        (*ht)[i].parent = -1;
        (*ht)[i].lchild = -1;
        (*ht)[i].rchild = -1;
    }

    for(; i < m; i++) // 初始化非叶子节点
    {
        (*ht)[i].weight = 0;
        (*ht)[i].parent = -1;
        (*ht)[i].lchild = -1;
        (*ht)[i].rchild = -1;
    }

    int s1, s2; // 最小值和次小值节点
    for(i = n; i < m; i++) // 构建哈夫曼树
    {
        select(*ht, i, &s1, &s2); // 选择两个权值最小的节点
        (*ht)[s1].parent = i; // 最小值节点成为新节点的左子节点
        (*ht)[s2].parent = i; // 次小值节点成为新节点的右子节点
        (*ht)[i].lchild = s1;
        (*ht)[i].rchild = s2;
        (*ht)[i].weight = (*ht)[s1].weight + (*ht)[s2].weight; // 新节点的权值为左右子节点权值之和
    }
}

// 生成哈夫曼编码
void createHuffmanCode(HuffmanTree ht, int n, HuffmanCodeTable *hct)
{
    *hct = (HuffmanCodeTable)malloc(n * sizeof(HuffmanCode)); // 分配空间

    int i, j, c, p;
    for(i = 0; i < n; i++) // 逐个生成编码
    {
        (*hct)[i].start = n - 1; // 起始位置
        c = i;
        p = ht[c].parent;
        while(p != -1) // 逆序求出编码位串
        {
            if(ht[p].lchild == c)
                (*hct)[i].bit[--(*hct)[i].start] = 0;
            else
                (*hct)[i].bit[--(*hct)[i].start] = 1;
            c = p;
            p = ht[c].parent;
        }
    }
}

int main()
{
    int w[] = {5, 6, 8, 7, 15}; // 权值数组
    HuffmanTree ht;
    createHuffmanTree(&ht, 5, w); // 构建哈夫曼树
    HuffmanCodeTable hct;
    createHuffmanCode(ht, 5, &hct); // 生成哈夫曼编码

    int i, j;
    for(i = 0; i < 5; i++) // 输出编码
    {
        printf("%d: ", w[i]);
        for(j = hct[i].start; j < 100; j++)
            printf("%d", hct[i].bit[j]);
        printf("\n");
    }

    return 0;
}