哈夫曼编码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//动态分配数组存储赫夫曼树
typedef struct{
int weight; //字符的权值
int parent,lchild,rchild; //字符的双亲及左右孩子
}HTNode,* HuffmanTree;
typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码，二维数组
//选择k个结点中无双亲且权值最小的两个结点
void Select(HuffmanTree HT,int k,int s1,int s2){
int i;
i=1;
while(i<=k && HT[lbk]i[rbk].parent!=0)
i++;
//下面选出权值最小的结点，用s1指向其序号
s1=i;
for(i=1;i<=k;i++){
if(HT[lbk]i[rbk].parent==0 && HT[lbk]i[rbk].weight < HT[lbk]s1[rbk].weight)
s1=i;
}
//下面选出权值次小的结点，用s2指向其序号
for(i=1;i<=k;i++){
if(HT[lbk]i[rbk].parent==0 && i!=s1)
break;
}
s2=i;
for(i=1;i<=k;i++){
if(HT[lbk]i[rbk].parent==0 && i!=s1 && HT[lbk]i[rbk].weight < HT[lbk]s2[rbk].weight)
s2=i;
}
}
//构造Huffman树，求出n个字符的编码
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int *w, int n) {
//w是存放n个字符的权值的一维数组， n为叶子个数；构造赫夫曼树HT;
int m,c,f,s1,s2,i,start;
//m为结点总数，s1、s2分别记录权值最小的两个结点，i为循环变量，c,f是编码的辅助变量，start为在字符数组中编码结束符的位置
char *cd;//定义存储编码的一维数组
if(n<=1) return; //从函数中返回，没有返回值
m=2*n-1; //n个叶子结点，n-1个非叶子
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //预分配m+1个单元，0号单元未用
for(i=1; i<=n; i++){ //n个叶子结点赋初值，n个叶子最初为n个根结点
HT[lbk]i[rbk].weight=w[lbk]i[rbk]; //w的0号单元也没有值，从1号单元开始
HT[lbk]i[rbk].parent=0;
HT[lbk]i[rbk].lchild=0;
HT[lbk]i[rbk].rchild=0;
}
for(i=n+1; i<=m; i++){ //从i=n+1开始，对另外n-1个叶子结点赋初值
HT[lbk]i[rbk].weight=0;
HT[lbk]i[rbk].parent=0;
HT[lbk]i[rbk].lchild=0;
HT[lbk]i[rbk].rchild=0;
}
for (i=n+1; i<=m; i++) { //第i次循环时为第i个结点选择两个儿子结点s1与s2
Select(HT, i-1,s1,s2); // 在i-1棵子树中也即HT[lbk]1..i-1[rbk]中选择无父亲(parent为0)且权值最小的两个结点(其序号分别为s1和s2)。
HT[lbk]s1[rbk].parent=i; //修改结点s1的双亲值
HT[lbk]s2[rbk].parent=i; //修改结点s2的双亲值
HT[lbk]i[rbk].lchild=s1; //修改双亲结点的左孩子结点
HT[lbk]i[rbk].rchild=s2; //修改双亲结点的右孩子结点
HT[lbk]i[rbk].weight=HT[lbk]s1[rbk].weight+HT[lbk]s2[rbk].weight; //修改双亲结点的权值，建立父子关系
} //赫夫曼树HT构造完毕
//从叶子到根逆向求每个字符的赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量
cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间(临时空间)
cd[lbk]n-1[rbk]='\0';//编码结束符
for(i=1;i<=n;i++) { //第i次循环时求第i个字符的赫夫曼编码