赫夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。
由于赫夫曼树的WPL最小，说明编码所需的比特数最小。
这种编码已经广泛应用于网络通信中。
构建赫夫曼树和赫夫曼编码：
出现的字符：
',','a','b','c','d','e','f','g','h','i','g','k','l','m','n','o','p','q','4','r','s','t','u','v','w','x','y','z'
字符出现的概率：
187,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,13,1,16,1
构建赫夫曼树和赫夫曼编码的方法：--------------------------------------------------------------------------------------------------------------------------------
//设字符集为26个英文字符，其出现频度如下表所示，要求编程实现
#include<stdio.h>
#include<stdlib.h>
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
typedef struct{ //赫夫曼树的结点结构
int weight;
int flag;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree;
typedef struct{
unsigned int bit[MaxN];
int strat;
int weight;
}Code;
//构造赫夫曼树的算法
void HuffmanCoding(int weight[],int n,HTNode HT[]){
int i,j,m1,m2,x1,x2;
if(n<=1) return;
for(i=0;i<2*n-1;i++){ //初始化每一个结点的值
if(i<n)
HT[i].weight=weight[i];
else
HT[i].weight=0;
HT[i].parent=-1;
HT[i].flag=0;
HT[i].lchild=-1;
HT[i].rchild=-1;
}
for(i=0;i<n-1;i++){ //建立赫夫曼树
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++){ //筛选出 weight 最小的两个
if(HT[j].weight<m1 && HT[j].flag==0){
m2=m1;
x2=x1;
m1=HT[j].weight;
x1=j;
}
else if(HT[j].weight<m2 && HT[j].flag==0){
m2=HT[j].weight;
x2=j;
}
}
HT[x1].parent=n+i;
HT[x2].parent=n+i;
HT[x1].flag=1;
HT[x2].flag=1;
HT[n+i].weight=HT[x1].weight+HT[x2].weight;
HT[n+i].lchild=x1;
HT[n+i].rchild=x2;
}
}
//编码的方法有两种，一种是从叶子到根，一种是从根到叶
//设计编码的算法
//从叶子到根你想求每个字符的赫夫曼编码
void HaffCode(HTNode HT[],int n,Code HTCode[]){
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;
for(i=0;i<n;i++){
cd->strat=n-1;
cd->weight=HT[i].parent;
child=i;
parent=HT[child].parent;
while(parent!=-1){
if(HT[parent].lchild==child)
cd->bit[cd->strat]=0;
else
cd->bit[cd->strat]=1;
cd->strat--;
child=parent;
parent=HT[child].parent;
}
for(j=cd->strat+1;j<n;j++)
HTCode[i].bit[j]=cd->bit[j];
HTCode[i].strat=cd->strat+1;
HTCode[i].weight=cd->weight;
}
}
void main(){
int i,j,k,n=27;
char s[]={',','a','b','c','d','e','f','g','h','i','g','k','l','m','n','o','p','q','4','r','s','t','u','v','w','x','y','z'};
int weight[]={187,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,13,1,16,1};
HTNode *myHaffTree=(HTNode *)malloc(sizeof(HTNode)*(2*n+1));
Code *myHaffCode=(Code *)malloc(sizeof(Code)*n);
if(n>MaxN)
{
printf("给出 n 越界，修改McxN");
exit(0);
}
HuffmanCoding(weight,n,myHaffTree);
HaffCode(myHaffTree,n,myHaffCode);
for(i=0;i<n;i++){
printf("字符=%c 权数=%d 赫夫曼编码= ",s[i],myHaffCode[i].weight);
for(j=myHaffCode[i].strat;j<n;j++)
printf("%d",myHaffCode[i].bit[j]);
printf("\n");
}
}
编码的方法有两种，一种是从叶子到根，一种是从根到叶。
与编码与之对应的就是译码了。
赫夫曼树编码的设计过程：
代码转自他人，只供交流学习。