哈夫曼编码是一种编码方式，属于可变字长编码(VLC)的一种，该编码方式是数学家D.A.Huffman于1952年提出的，是用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式，称之为最佳编码
哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方式，其压缩率通常在20%~90%之间，JPEG就是用哈夫曼编码压缩的
任何一个字符的编码都不能使其他字符编码的前缀，否则译码时将产生二义性
哈夫曼算法的构造思想及设计
1.构造思想
将所要编码的字符作为叶子节点，在文件中使用频率作为叶子节点的权值，以自底向上的方式、通过n-1次的"合并"运算后构造出最终所要求的树
核心思想：让权值大的叶子离根最近
哈夫曼树中节点的存储结构
n个叶子节点的哈夫曼树共有2n-1个节点，并且需要进行n-1次合并操作。为了便于选取根节点权值最小的二叉树以及进行合并操作，树种每个节点的存储结构为：
struct HtNode{
double weight;
int parent,lchild,rchild;
};
其中,weight域表示节点的权值，即为该字符的使用频率，parent域表示节点的双亲节点在数组中的下标；lchild域表示节点的左孩子在数组中的下标；rchild域表示节点的右孩子在数组中的下标
哈夫曼树的存储结构
struct HtTree{
struct HtNode ht[MaxNode];
int root;
};
typedef struct HtTree* PHtTree;
线性结构上实现的Haffman算法
//构造具有n个节点的哈夫曼树
PHtTree Huffman (int n,double w[n])//构造具有n个节点的哈夫曼树
{
PHtTree pht;
//p1,p2用于记录权值最小的两棵树在数组中的位置
int i,j,p1,p2;
//min1,min2用于记录两个最小的权值
double min1,min2;
if(n<=1) return;
//动态分配Haffman树的空间
pht=(PHtTree)malloc(sizeof(struct HtTree));
pht->ht=(struct HtNode*)malloc (sizeof(struct HtMode)*(2*n-1));
//初始化，设置ht数组的初始值
for(i=0;i<2*n-1;i++)
{
pht->ht[i].parent=0;
if(i { pht->ht[i].weight=w[i]; } else { pht->ht[i].weight=-1; } } //执行n-1次合并操作，即构造哈夫曼树的n-1个内部节点 for(i=0;i { p1=p2=0; //相关变量赋初值 min1=min2=∞; for(j=0;j { if(pht->ht[j].parent==0) { if(pht->ht[j].weight { min2=min1; min1=pht->ht[j].weight; p2=p1; p1=j; } else if(pht->ht[j].weight { min2=pht->ht[j].weight; p2=j; } } pht->ht[p1].parent=n+i; pht->ht[p2].parent=n+i; pht->ht[n+i].weight=min1+min2; pht->ht[n+i].lchild=p1; pht->ht[n+i].rchild=p2; } return pht; } //哈夫曼编码算法描述 注:从叶子到根逆向求每个字符的哈夫曼编码算法 void HuffmanCode(char** HC,int n,PHtTree pht) { //每个字符的编码最大长度不会超过n char c[n]; //分配n个字符指针数组的空间 HC=(char**)malloc(n*sizeof(char*)); //第n-1单元存储编码串的结束符 c[n-1]="\0"; //逐个对n个字符求其哈夫曼编码 for(i=1;i<=n;i++) { start=n-1; //k,f是两个工作指针，f指向k的父亲 for(int k=i,f=pht->ht[i].parent;f!=0;k=f,f=pht->ht[k].parent) { //左边分配0,右边分配1 if(pht->ht[f].lchild==k) { c[--start]="0"; } else { c[--start]="1"; } } //为第i个字符编码分配空间 HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&c[start]); } } 其中在选择最小和次小节点时，该代码有错误 编码使用start，统一了字符串的个数，在输出时可能有错误