hnust 2184: huffman编码（1）

hnust 2184: huffman编码（1）

题目描述
给定n个字符的权值(权值均是大于0的正整数)，构造赫夫曼树HT，并求出这n个字符的赫夫曼编码HC。
注意：构造赫夫曼树HT时，在将2棵二叉树合并成一棵新的二叉树时，将根结点权值小的用作左子树！
输入
先输入权值的个数n（n>1）。
然后依次输入n个权值（权值均是大于0的正整数）
输出
与输入的n个权值相对应，依次输出对应的编码。
编码时，左孩子分支编码为0，右孩子分支编码为1。
样例输入 Copy
8
5 29 7 8 14 23 3 11
样例输出 Copy
0001
10
1110
1111
110
01
0000
001
提示
参考人邮版教材137－142页。

解题过程

代码解析

这段C++代码实现了赫夫曼编码的生成过程，包括构建赫夫曼树和生成对应的赫夫曼编码。

1. 结构定义

• HTNode：定义了赫夫曼树的节点，包含权重 weight，父节点 parent，左孩子 lchild，右孩子 rchild。
• HuffmanTree：赫夫曼树的类型定义，指向 HTNode 的指针。
• HuffmanCode：赫夫曼编码的类型定义，指向字符指针数组的指针。

2. 函数 Select

• 作用：在赫夫曼树中选择两个权重最小且没有父节点的节点。
• 输入参数：赫夫曼树 HT，树的长度 len，以及两个节点序号的引用 s1 和 s2。
• 过程：遍历赫夫曼树，找到两个权重最小且没有父节点的节点，并更新 s1 和 s2。

3. 函数 CreatHuffmanTree

• 作用：构造赫夫曼树。
• 输入参数：赫夫曼树的引用 HT 和叶子节点个数 n。
• 过程：
  • 初始化赫夫曼树的节点。
  • 读取每个叶子节点的权重。
  • 通过不断选择、合并节点来构建赫夫曼树。

4. 函数 CreadHuffmanCode

• 作用：根据赫夫曼树生成赫夫曼编码。
• 输入参数：赫夫曼树 HT，赫夫曼编码的引用 HC，叶子节点个数 n。
• 过程：
  • 为每个叶子节点分配一个字符数组来存储编码。
  • 从叶子节点开始，向上遍历到根节点，根据左右孩子的不同，添加 ‘0’ 或 ‘1’ 到编码字符串。

5. 主函数 main

• 读取叶子节点个数 n。
• 调用 CreatHuffmanTree 函数构造赫夫曼树。
• 调用 CreadHuffmanCode 函数生成赫夫曼编码。
• 打印每个叶子节点的赫夫曼编码。

博客：赫夫曼编码生成过程解析

问题分析

赫夫曼编码是一种基于字符出现频率的前缀编码方法，用于数据压缩。构建赫夫曼编码的核心是生成赫夫曼树，树的构建过程是一个贪心算法。

赫夫曼树构建

1. 初始化：创建一个包含所有叶子节点的森林，每个叶子节点包含一个字符和对应的权重（字符出现频率）。
2. 选择：在森林中选择两个权重最小的节点，这些节点没有父节点。
3. 合并：创建一个新的内部节点，将选出的两个节点作为新节点的子节点，新节点的权重是两个子节点权重的和。
4. 迭代：重复选择和合并步骤，直到森林中只剩下一个节点，这个节点就是赫夫曼树的根节点。

赫夫曼编码生成

1. 遍历：从赫夫曼树的叶子节点开始，向上遍历到根节点。
2. 编码：对于每个节点，如果是左孩子则添加 ‘0’，如果是右孩子则添加 ‘1’。
3. 存储：到达根节点后，得到的字符串就是叶子节点的赫夫曼编码。

代码分解

1. 节点定义：定义赫夫曼树的节点结构，包含权重、父节点和左右孩子。
2. 选择函数：实现选择两个最小权重节点的逻辑。
3. 构建树函数：实现赫夫曼树的构建过程，包括初始化、权重读取、节点选择和合并。
4. 生成编码函数：根据赫夫曼树生成每个叶子节点的赫夫曼编码。
5. 主函数：整合以上步骤，从用户输入到输出赫夫曼编码。

总结

赫夫曼编码是一种有效的数据压缩方法，通过构建赫夫曼树来实现。本代码实现了赫夫曼编码的生成过程，包括树的构建和编码的生成。这种方法在信息论和数据压缩领域有着广泛的应用。

注意事项

• 确保输入的权重数据是有效的，并且叶子节点个数正确。
• 在构建赫夫曼树和生成编码时，注意内存管理，避免内存泄漏。
• 赫夫曼编码的生成依赖于树的结构，确保树构建过程的正确性。

AC代码

#include<iostream>
#include<cstring>
using namespace std;
typedef struct
{
    int weight;
    int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
  
void Select(HuffmanTree HT,int len,int &s1,int &s2)//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点，并返回它们在HT中的序号s1和s2
{
    /****在此下面完成代码***************/
    int min1=200,min2=200;
    for(int i=1; i<=len; i++)//找出s1
    {
        if(HT[i].weight<min1&&HT[i].parent==0)//左边负责找最小，右边负责审核是否已被合成
        {
            min1=HT[i].weight;
            s1=i;
        }
    }
    for(int i=1; i<=len; i++)
    {
        if(i!=s1&&HT[i].weight<min2&&HT[i].parent==0)
       //相较于上一个循环，此处为了避免上面的s1再次被选中，加了i!=s1;
        {
            min2=HT[i].weight;
            s2=i;
        }
    }
  
  
    /***********************************/
}
  
//用算法5.10构造赫夫曼树
void CreatHuffmanTree(HuffmanTree &HT,int n)
{
    //构造赫夫曼树HT
    int m,s1,s2,i;
    if(n<=1)return;
    m=2*n-1;
    HT=new HTNode[m+1];        //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点
    for(i=1; i<=m; ++i)         //将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
    {
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    //cout<<"请输入叶子结点的权值：\n";
    for(i=1; i<=n; ++i)         //输入前n个单元中叶子结点的权值
        cin>>HT[i].weight;
    /*――――――――――初始化工作结束，下面开始创建赫夫曼树――――――――――*/
    for(i=n+1; i<=m; ++i)
    {
        //通过n-1次的选择、删除、合并来创建赫夫曼树
        Select(HT,i-1,s1,s2);
        //在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,
        // 并返回它们在HT中的序号s1和s2
        HT[s1].parent=i;
        HT[s2].parent=i;
        //得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
        HT[i].lchild=s1;
        HT[i].rchild=s2 ;                          //s1,s2分别作为i的左右孩子
        HT[i].weight=HT[s1].weight+HT[s2].weight;  //i 的权值为左右孩子权值之和
    }                                              //for
}
void CreadHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
    HC = new char*[n+1];//此处负责为HC分配n+1个char数组，每一个数组存对应字符的编码
    char *cd;
    cd = new char[n];
    cd[n-1] = '\0';
    int start, c, f;
    for(int i=1; i<=n; i++)
    {
        start = n-1;
        c = i;
        f = HT[i].parent;
        while(f!=0)//从叶子节点不断找爹，直到找到祖先（祖先没有爹了，停下）
        {
            --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]);
    }
    delete cd;
}                                        // CreatHuffmanTree
int main()
{
    HuffmanTree HT;
    HuffmanCode HC;
    int n;
    cin>>n;                                          //输入赫夫曼树的叶子结点个数
    CreatHuffmanTree(HT,n);
    CreadHuffmanCode(HT, HC, n);
    for(int i=1; i<=n; i++)cout<<HC[i]<<endl;
    return 0;
}