哈夫曼编码的C语言程序

以下是哈夫曼编码的C语言程序：

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

#define MAX 1000

//赫夫曼树结点
typedef struct {
    int weight;//权值
    int parent, lchild, rchild;
}HTNode,*HTTree;

//赫夫曼编码
typedef struct {
    char ch;//结点名称
    char code[10];//结点的编码
}CodeNode,*HuffmanCode;

//选择权值最小的两个结点
void Select(HTTree HT, int n, int *s1, int *s2) {
    int i, min1, min2;
    min1 = min2 = MAX;
    for (i = 1; i <= n; i++) {
        if (HT[i].weight < min1 && HT[i].parent == 0) {
            min2 = min1;
            *s2 = *s1;
            min1 = HT[i].weight;
            *s1 = i;
        }
        else if (HT[i].weight < min2 && HT[i].parent == 0) {
            min2 = HT[i].weight;
            *s2 = i;
        }
    }
}

//构造赫夫曼树
void CreateHuffmanTree(HTTree *HT, int n) {
    int m, i, s1, s2;
    m = 2 * n - 1;
    *HT = (HTTree)malloc((m + 1) * sizeof(HTNode));
    for (i = 1; i <= m; i++) {
        (*HT)[i].parent = 0;
        (*HT)[i].lchild = 0;
        (*HT)[i].rchild = 0;
    }
    for (i = 1; i <= n; i++) {
        scanf("%d", &((*HT)[i].weight));
    }
    for (i = n + 1; i <= m; i++) {
        Select(*HT, i - 1, &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(HTTree HT, HuffmanCode *HC, int n) {
    int i, j, k;
    char *code;
    *HC = (HuffmanCode)malloc((n + 1) * sizeof(CodeNode));
    code = (char*)malloc(n * sizeof(char));
    code[n - 1] = '\0';
    for (i = 1; i <= n; i++) {
        (*HC)[i].ch = i;
        k = i;
        j = n - 1;
        while (HT[k].parent != 0) {
            if (HT[k].parent > n) {
                code[--j] = '1';
            }
            else {
                code[--j] = (HT[HT[k].parent].lchild == k) ? '0' : '1';
            }
            k = HT[k].parent;
        }
        strcpy((*HC)[i].code, &code[j]);
    }
    free(code);
}

//输出赫夫曼编码
void OutPutHuffmanCode(HuffmanCode HC, int n) {
    for (int i = 1; i <= n; i++) {
        printf("%c: %s\n", HC[i].ch, HC[i].code);
    }
}

int main() {
    int n;
    HTTree HT;
    HuffmanCode HC;
    printf("请输入叶子结点的个数：");
    scanf("%d", &n);
    printf("请输入每个叶子结点的权值：");
    CreateHuffmanTree(&HT, n);
    CreateHuffmanCode(HT, &HC, n);
    OutPutHuffmanCode(HC, n);
    return 0;
}