哈夫曼编码C/C++代码实现-蒲公英云

哈夫曼编码C/C++代码实现

哈夫曼编码的特点：

因为哈夫曼树的特点是：叶子结点权值越大的，离根越近。又因为构造不等长编码的原则是：字符使用频率越高，编码越短，故采用哈夫曼树进行编码可以得到最优前缀编码。
约定左分支标记为0, 右分支标记为 1

求哈夫曼编码:

为不浪费存储空间，动态分配一个长度为n(字符编码长度一定小于n) 的一维数组cd, 用来临时存放当前正在求解的第i个字符的编码，当第i个字符的编码求解完毕后，根据数组cd的字符串长度分配HC[i]的空间，然后将数组cd中的编码复制到HC[i]中。

依照上一篇文章的哈夫曼树：
在这里插入图片描述
哈夫曼编码表HC：

注意：由于哈夫曼树不唯一，故哈夫曼编码也不唯一。

代码如下：

#include<stdio.h>
#include<iostream>
//哈夫曼树定义
typedef struct {
    int weight;
    int parent, lchild, rchild;
}HTNode, *HuffmanTree;
//选择两个双亲域为0且权值最小的结点，并返回在HT中的序号s1，s2
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
{
    //寻找第一个双亲域为0且权值最小的结点
    int min;
    for (int i = 1; i <= n; i++)    //找到第一个双亲域为0的，下标暂存到min
    {
        if (HT[i].parent == 0)
        {
            min = i;
            break;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0)
        {
            if (HT[i].weight < HT[min].weight)
            {
                min = i;
            }
        }
    }
    s1 = min;
    //寻找第二个双亲域为0且权值最小的结点
    for (int i = 1; i <= n; i++)    //找到第一个双亲域为0的，下标暂存到min
    {
        if (HT[i].parent == 0 && i != s1)
        {
            min = i;
            break;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0 && i != s1)
        {
            if (HT[i].weight < HT[min].weight)
            {
                min = i;
            }
        }
    }
    s2 = min;
}
//输出
void println(HuffmanTree &HT, int m)
{
    printf("==============================\n");
    for (int i = 1; i <= m; i++)
    {
        printf("%d，   ", i);
        printf("%d   ", HT[i].weight);
        printf("%d   ", HT[i].parent);
        printf("%d  ", HT[i].lchild);
        printf("%d   \n", HT[i].rchild);
        printf("---------------------------\n");
    }
}
//创建哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT,int n, int *ht)
{
    //初始化
    int i, m = 2 * n - 1, s1, s2;        //m为所有结点的个数
    if (n <= 1) return;
    HT = new HTNode[m + 1];                //0号不用从1开始，多申请一行，前1~n存放叶子结点
    for (i = 1; i <= m; ++i)            //遍历每一个结点并赋值为0
    {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    //创建树
    for (i = 1; i <= n; ++i)            //把叶子结点权值放入表中
    {
        HT[i].weight = ht[i - 1];
    }
    printf("\nHT的初态\n");
    println(HT, m);
    for (int 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;
    }
    printf("\nHT的终态\n");
    println(HT, m);
}
//哈夫曼编码
typedef char **HuffmanCode;        //哈夫曼编码表，指针数组
char *cd;                        //用来临时存放当前正在求解的第i个字符的编码
int start;                        //cd数组的下标指针
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
    int i, c, f;
    HC = new char*[n + 1];
    cd = new char[n];
    cd[n - 1] = '\0';
    for (i = 1; i <= n; ++i)
    {
        start = n - 1;
        c = i;                        //当前结点
        f = HT[i].parent;            //双亲结点
        while (f != 0)                //因为cd数组的start指针从后往前，所以哈夫曼树从下往上即从叶子到根结点进行比较，
        {
            if (HT[f].lchild == c) cd[--start] = '0';
            else                   cd[--start] = '1';
            c = f;
            f = HT[f].parent;
        }
        HC[i] = new char[n - start];
        strcpy(HC[i], &cd[start]);
        //输出
        printf("第%d组--->", i);
        for (int j = start; j <= n - 1; ++j)
        {
            printf("%c ", cd[j]);
        }
        printf("\n");
    }
    delete cd;
}
int main() {
    HuffmanTree HT;                        //构造哈夫曼
    HuffmanCode HC;                        //哈夫曼编码
    int n = 8;                            //n为叶子节点的个数
    int ht[8] = {
     5,29,7,8,14,23,3,11 };
    CreateHuffmanTree(HT, n, ht);
    CreatHuffmanCode(HT, HC, n);
}