编写一个c语言程序构建哈夫曼树并生成哈夫曼树

哈夫曼树是一种带权路径长度最小的二叉树，常用于数据压缩和加密等领域。下面是构建哈夫曼树并生成哈夫曼编码的C语言程序：

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

#define MAX_TREE_SIZE 100

// 定义哈夫曼树结点
typedef struct
{
    int weight; // 结点权重
    int parent; // 父结点下标
    int lchild; // 左子结点下标
    int rchild; // 右子结点下标
} HTNode, *HuffmanTree;

// 定义哈夫曼编码结构体
typedef char **HuffmanCode;

// 构建哈夫曼树
void CreateHuffmanTree(HuffmanTree *HT, int n)
{
    if (n <= 1)
    {
        return;
    }

    int m = 2 * n - 1; // 哈夫曼树结点数
    *HT = (HuffmanTree) malloc((m + 1) * sizeof(HTNode)); // 分配哈夫曼树内存空间

    // 初始化哈夫曼树，将前n个结点的权重读入到哈夫曼树的叶子结点中
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &(*HT)[i].weight);
        (*HT)[i].parent = 0;
        (*HT)[i].lchild = 0;
        (*HT)[i].rchild = 0;
    }

    // 构建哈夫曼树，每次找到权重最小的两个结点合并成一个新的结点，直到只剩一个结点
    for (int i = n + 1; i <= m; i++)
    {
        int s1 = 1, s2 = 2;
        while ((*HT)[s1].parent != 0)
        {
            s1++;
        }
        while ((*HT)[s2].parent != 0)
        {
            s2++;
        }

        // 找到权重最小的两个结点s1和s2
        for (int j = 1; j < i; j++)
        {
            if ((*HT)[j].parent == 0)
            {
                if ((*HT)[j].weight < (*HT)[s1].weight)
                {
                    s2 = s1;
                    s1 = j;
                }
                else if ((*HT)[j].weight < (*HT)[s2].weight)
                {
                    s2 = j;
                }
            }
        }

        // 合并s1和s2为新的结点i
        (*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 HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
{
    *HC = (HuffmanCode) malloc((n + 1) * sizeof(char *));
    char *cd = (char *) malloc(n * sizeof(char));
    cd[n - 1] = '\0';

    for (int i = 1; i <= n; i++)
    {
        int start = n - 1;
        int c = i;
        int f = HT[i].parent;

        while (f != 0)
        {
            if (HT[f].lchild == c)
            {
                cd[--start] = '0';
            }
            else
            {
                cd[--start] = '1';
            }

            c = f;
            f = HT[c].parent;
        }

        (*HC)[i] = (char *) malloc((n - start) * sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }

    free(cd);
}

int main()
{
    int n;
    printf("请输入哈夫曼树叶子结点个数：\n");
    scanf("%d", &n);

    HuffmanTree HT;
    HuffmanCode HC;
    printf("请依次输入各个叶子结点的权重：\n");
    CreateHuffmanTree(&HT, n);
    HuffmanCoding(HT, &HC, n);

    printf("哈夫曼编码如下：\n");
    for (int i = 1; i <= n; i++)
    {
        printf("%d: %s\n", HT[i].weight, HC[i]);
    }

    return 0;
}

以上代码通过输入哈夫曼树叶子结点个数和各个叶子结点的权重来构建哈夫曼树，并生成对应的哈夫曼编码。