哈夫曼算法详细讲解（算法+源码）

博主介绍：✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦！

🍅文末获取源码联系🍅

👇🏻 精彩专栏推荐订阅👇🏻 不然下次找不到哟

一、哈夫曼算法

二、哈夫曼算法（完整C语言算法）

三、算法优缺点总结

大家点赞、收藏、关注、评论啦！

谢谢哦！如果不懂，欢迎大家下方讨论学习哦。

一、哈夫曼算法

哈夫曼编码是一种可变字长编码（Variable Length Coding）的一种方法，通过根据不同字符出现的频率来构建一颗具有最小编码长度的二叉树。该树的构建和遍历规则使得出现频率高的字符获得较短的编码，而出现频率低的字符获得较长的编码，从而达到对数据进行高效压缩的目的。

以下是哈夫曼编码的基本步骤：

1. 统计字符频率：遍历输入的字符流，统计每个字符出现的频率。

2. 构建哈夫曼树：将每个字符及其频率作为叶子节点，构建一颗二叉树。在每一步中，选择两个最小频率的节点合并，直到只剩下一个根节点。

3. 生成编码：*通过遍历哈夫曼树，从根节点到每个叶子节点的路径上赋予0或1的编码。叶子节点上的编码即为对应字符的哈夫曼编码。

4. 生成编码表：将每个字符及其对应的哈夫曼编码存储在一个编码表中，用于编码和解码。

5. 数据压缩：*使用生成的哈夫曼编码对原始数据进行编码，从而实现数据的压缩。

6. 数据解压：利用编码表对压缩后的数据进行解码，还原为原始数据。

哈夫曼编码的优点在于对频率较高的字符进行了有效的压缩，使得整体的编码长度较短，从而节省了存储空间。这使得哈夫曼编码在数据传输和存储中得到广泛应用，特别是在无损数据压缩领域。

二、哈夫曼算法（完整C语言算法）

#include<stdio.h>
#include<malloc.h>
#include <iostream>

//定义初始化
#define Max 20
#define MaxValue 1000
using namespace std;
typedef struct huffNode
{
    char ch;
    int weight;  //赋以权重 
    int lChild;  //左孩子 
    int rChild;  //右孩子 
    int parent;  //父节点 
    char hCode[Max];   //记录哈夫曼编码 
}huffman;
void init(huffman *huffmanTree,int *w,char *z,int n)
{
    int i;
    //for(i=0;i<2*n-1;i++)
    //    huffmanTree[i]=(huffman *)malloc(sizeof(huffman));

    for(i=0;i<2*n-1;i++)
    {
        huffmanTree[i].ch=z[i];
        huffmanTree[i].weight=w[i];
        huffmanTree[i].parent=-1;
        huffmanTree[i].lChild=-1;
        huffmanTree[i].rChild=-1;
    }
}

void setHuffmanTree(huffman *huffmanTree,int n)
{
    int m,m1,m2,x1,x2,i,j;
    m=2*n-1;
    for(i=n;i<m;++i)
    {
        m1=m2=MaxValue;
        x1=x2=0;
        for(j=0;j<i;++j)
        {
            if(huffmanTree[j].parent==-1&&huffmanTree[j].weight<m1)
            {
                m2=m1;x2=x1;m1=huffmanTree[j].weight;x1=j;
            }
            else if (huffmanTree[j].parent==-1&&huffmanTree[j].weight<m2)
            {    m2=huffmanTree[j].weight;x2=j;
            }
        }
        huffmanTree[x1].parent=i;
        huffmanTree[x2].parent=i;
        huffmanTree[i].lChild=x1;
        huffmanTree[i].rChild=x2;
        huffmanTree[i].weight=m1+m2;
    }
}
void huffmanTreeCode(huffman *huffmanTree,int n)
{
    char hc[Max];
    int hcLen;
    int i,j,k,parent,p;
    for(i=0;i<n;i++)
    {
        hcLen=0;
        parent=huffmanTree[i].parent;//待编码字符的双亲结点下标
        p=i;
        while(parent!=-1)//未到达根结点
        {
            if(huffmanTree[parent].lChild==p)//是左孩子
                hc[hcLen]='0',hcLen++;
            else if(huffmanTree[parent].rChild==p)//是右孩子
                hc[hcLen]='1',hcLen++;
                p=parent;
                parent=huffmanTree[parent].parent;//继续向根结点查找
    }
    for(j=0,k=hcLen-1;j<hcLen;j++,k--)//将编码写入相应字符数组
        huffmanTree[i].hCode[j]=hc[k];
        huffmanTree[i].hCode[j]='\0';//加上字符串结束符
    }

    return;
}
int main()
{
    int n,i;

    char z,*Z;
    int w,W[Max];
    huffman huffmanTree[Max];
    
    printf("请输入叶子个数：\n");
    scanf("%d",&n);
   //W=(int *)malloc(n*sizeof(int));
    Z=(char *)malloc(n*sizeof(char));
    printf("请输入%d个字符和权值。\n",n);
    for(i=0;i<n;i++)
    {
        printf("请输入第%d个字符:\n",i+1);
        //scanf("%c",&z);
        cin>>z;
        Z[i]=z;
        printf("请输入第%d个字符的权:\n",i+1);
        //scanf("%d",&w);
        cin>>w;
        W[i]=w;
    }
    
    init(huffmanTree,W,Z,n);
    setHuffmanTree(huffmanTree,n);
    huffmanTreeCode(huffmanTree,n);
    for(i=0;i<n;i++)
    {
        printf("%c:%s\n",huffmanTree[i].ch,huffmanTree[i].hCode);
    }
    return 0;
}

代码执行结果：