书上赫夫曼编码编码的实现
//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);
}
//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);}