书上赫夫曼编码编码的实现
//
huffmancode.h
// --------------------------赫夫曼树和赫夫曼编码的存储表示 ------------------------------------
typedef struct {
unsigned int weight; //权
unsigned int parent,lchild,rchild; //父，左子，右子节点
} HTNode, * HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char ** HuffmanCode; // 动态分配数组存储赫夫曼编码
// ---------------------------赫夫曼编码的算法实现---------------------------------------------
void SetHuffmanTree(HuffmanTree & HT, int weight, int parent, int lchild, int rchild) {
HT->weight=weight; HT->parent = parent; HT->lchild = lchild; HT->rchild = rchild;
}
void Select(HuffmanTree HT, int n, int & s1, int & s2) {
//在HT[1...n]选择parent为0且weight最小的两个节点,分别赋给s1,s2
//s1最小，s2次小
int min=0,mun=0;
HT[0].weight = 30000;
for(int i=1;i<=n;i++){
if(HT[i].parent==0){
if(HT[i].weight<HT[min].weight) { mun = min; min=i;}
else if(HT[i].weight<HT[mun].weight) mun=i;
}
}
s1=min; s2= mun;
}
void HuffmanCoding(HuffmanTree & HT, HuffmanCode & HC, int * w, int n) {
//w存放n个字符的劝值（均>0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码
if(n<=1) return;
int m= 2*n-1; //m：总共节点数
HT = (HuffmanTree)malloc( (m+1)*sizeof(HTNode) ); //0号单元未用
if(!HT) return ;
int i;HuffmanTree p;
for( p=HT+1,i=1; i<=n; i++,p++,w++) SetHuffmanTree(p,*w,0,0,0); //HT叶子的初值
for(;i<=m;i++,p++) SetHuffmanTree(p,0,0,0,0); //HT非叶子节点的初值
for(i=n+1;i<=m; i++){ //建赫夫曼树
int s1,s2;
Select(HT,i-1,s1,s2); //找出weight值最小的两个节点
HT[s1].parent = i; HT[s2].parent=i;
HT[i].lchild = s1; HT[i].rchild=s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
//-----------从叶子到根逆向求每个字符的赫夫曼编码 ------
HC = (HuffmanCode) malloc( (n+1)*sizeof(char *) ); //分配n个字符编码的头指针向量
char *cd = (char *)malloc(n*sizeof(char));
cd[n-1]='';
for(i=1;i<=n;i++){
int start=n-1;
for(int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){ //从叶子到根逆向的逆向过程
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
}
HC[i] = (char * )malloc((n-start)*sizeof(char));
for(int j=start;j<=n;j++) HC[i][j-start]=cd[j];
puts(HC[i]); //输出编码
}
free(cd);
}
// --------------------------赫夫曼树和赫夫曼编码的存储表示 ------------------------------------
typedef struct {
unsigned int weight; //权
unsigned int parent,lchild,rchild; //父，左子，右子节点
} HTNode, * HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char ** HuffmanCode; // 动态分配数组存储赫夫曼编码
// ---------------------------赫夫曼编码的算法实现---------------------------------------------
void SetHuffmanTree(HuffmanTree & HT, int weight, int parent, int lchild, int rchild) {
HT->weight=weight; HT->parent = parent; HT->lchild = lchild; HT->rchild = rchild;
}
void Select(HuffmanTree HT, int n, int & s1, int & s2) {
//在HT[1...n]选择parent为0且weight最小的两个节点,分别赋给s1,s2
//s1最小，s2次小
int min=0,mun=0;
HT[0].weight = 30000;
for(int i=1;i<=n;i++){
if(HT[i].parent==0){
if(HT[i].weight<HT[min].weight) { mun = min; min=i;}
else if(HT[i].weight<HT[mun].weight) mun=i;
}
}
s1=min; s2= mun;
}
void HuffmanCoding(HuffmanTree & HT, HuffmanCode & HC, int * w, int n) {
//w存放n个字符的劝值（均>0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码
if(n<=1) return;
int m= 2*n-1; //m：总共节点数
HT = (HuffmanTree)malloc( (m+1)*sizeof(HTNode) ); //0号单元未用
if(!HT) return ;
int i;HuffmanTree p;
for( p=HT+1,i=1; i<=n; i++,p++,w++) SetHuffmanTree(p,*w,0,0,0); //HT叶子的初值
for(;i<=m;i++,p++) SetHuffmanTree(p,0,0,0,0); //HT非叶子节点的初值
for(i=n+1;i<=m; i++){ //建赫夫曼树
int s1,s2;
Select(HT,i-1,s1,s2); //找出weight值最小的两个节点
HT[s1].parent = i; HT[s2].parent=i;
HT[i].lchild = s1; HT[i].rchild=s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
//-----------从叶子到根逆向求每个字符的赫夫曼编码 ------
HC = (HuffmanCode) malloc( (n+1)*sizeof(char *) ); //分配n个字符编码的头指针向量
char *cd = (char *)malloc(n*sizeof(char));
cd[n-1]='';
for(i=1;i<=n;i++){
int start=n-1;
for(int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){ //从叶子到根逆向的逆向过程
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
}
HC[i] = (char * )malloc((n-start)*sizeof(char));
for(int j=start;j<=n;j++) HC[i][j-start]=cd[j];
puts(HC[i]); //输出编码
}
free(cd);
}