哈夫曼树的建立和哈夫曼编码

哈夫曼树中节点的结构体定义

/*
哈夫曼树中每个节点的结构体
x:存放出现的概率
flag:标志当前节点是否有需要编码
data:存放当前数据
lchild:指向左孩子的指针
rchild:指向右孩子的指针
*/
struct Node
{
    float x;   //存放概率
    int flag;  //标志当前节点是否有对应的数据
    char data; //存放数据
    Node *lchild;
    Node *rchild;
};

原理比较简单，代码中全部有注释，应该都可以看懂

PS:以下代码在VScode中配合gdb调试工具能够正常运行，如果使用其他编译器或者IDE可能需要做出修改。

#include <stdio.h>
#include <stdlib.h>
#define N 10


/*
receive:将用户输入的信息录入到数组中
input: 需要编码的元素个数number
       用于存储的数组data[]
*/
void receive(Node *data[], int number)
{
    char no;
    for (int i = 0; i < number; i++)
    {
        scanf("%c", &no); //消除输入过程中的回车
        data[i] = (Node *)malloc(sizeof(Node));
        printf("Please input %dth data:", i);
        scanf("%c", &data[i]->data);
        printf("Rate:");
        scanf("%f", &data[i]->x);
        data[i]->flag = 1;
        data[i]->lchild = data[i]->rchild = NULL;
    }
}

/*
creat:根据存储信息的数组创建哈夫曼树
input: 存储信息的数组data[]
       元素的个数number
return: 哈夫曼树的根节点root
*/
Node *creat(Node *data[], int number)
{
    Node *temp;
    /*循环number-1次，创建哈夫曼树*/
    for (int m = 1; m < number; m++)
    {
        int first = -1;
        int second = -1;
        /*first 指向第一个非NULL元素，second指向第二个非NULL元素*/
        for (int i = 0; i < number; i++)
        {
            if (first == -1 && data[i] != NULL)
            {
                first = i;
                continue;
            }
            if (second == -1 && data[i] != NULL)
            {
                second = i;
                continue;
            }
        }
        if (first != -1 && second != -1)
        {
            /*确保first是最小的，second是第二小的*/
            if (data[first]->x > data[second]->x)
            {
                float temp = first;
                first = second;
                second = temp;
            }
            /*寻找出森林中概率最小的两个结点*/
            for (int j = 0; j < number; j++)
            {
                /*如果小于最小的元素，则first和second都需要更新*/
                if (data[j] != NULL && data[j]->x < data[first]->x)
                {
                    second = first;
                    first = j;
                }
                /*如果只小于第二小的元素，则只更新second的位置*/
                else if (data[j] != NULL && j != first && data[j]->x < data[second]->x)
                {
                    second = j;
                }
            }
            /*利用最小的两个节点构建一个树，并将此放入森林中*/
            temp = (Node *)malloc(sizeof(Node));
            temp->x = data[first]->x + data[first]->x;
            temp->lchild = data[first];
            temp->rchild = data[second];
            temp->flag = 0;   //合成节点并不需要编码
            data[first] = temp;
            data[second] = NULL;
        }
    }
    return temp;
}
/*
show:显示哈夫曼树
input:哈夫曼树的根节点root
*/
void show(Node *root)
{
    if (root != NULL)
    {
        if (root->flag == 1)
        {
            printf("%c", root->data);
        }
        if (root->lchild != NULL)
        {
            printf("(");
            show(root->lchild);
            if (root->rchild != NULL)
            {
                printf(",");
                show(root->rchild);
            }
            printf(")");
        }
    }
}
/*
HuffManCoding:给哈夫曼树编码
input: 哈夫曼树的根节点root
       编码的层次i
*/
void HuffManCoding(Node *root, int i)
{
    static int a[N];
    if (root->flag == 1)
    {
        printf("After coding %c is :", root->data);
        for (int j = 0; j < i; j++)
        {
            printf("%d", a[j]);
        }
        printf("\n");
    }
    else
    {
        /*左边的编码为0，右边编码为1*/
        a[i] = 0;
        HuffManCoding(root->lchild, i + 1);
        a[i] = 1;
        HuffManCoding(root->rchild, i + 1);
    }
}

int main()
{
    int number;
    Node *data[N];
    Node *root;
    printf("Please input the number of data:");
    scanf("%d", &number);
    receive(data, number);
    root = creat(data, number);
    show(root);
    printf("\n");
    HuffManCoding(root,0);
    system("pause");
    return 0;
}