huffman.cpp

huffman编码是一种无损压缩编码

#include   <time.h> 
#include   <stdio.h> 
#include   <stdlib.h> 
#include   <iostream.h> 
#define   letter 
#define   N   2400 
#define   MAX   100 
typedef   struct{ 
unsigned   int   weight; 
unsigned   int   parent,lchild,rchild; 
}HTNode; 
void   Select(HTNode   *HT,int   i,int   &s1,int   &s2) 
{ 
//在HT[1,...,i-1]选择parent为0且weight最小的2个结点，序号分别为s1,s2 
int   j; 
s2=0; 
for(j=1;j <=i;j++) 
if(HT[j].parent==0) 
{s1=j;break;} 
for(j=s1+1;j <=i;j++) 
if(HT[j].parent==0) 
{ 
if(HT[j].weight <HT[s1].weight) 
{s2=s1;s1=j;} 
else   if(s2==0||HT[j].weight <HT[s2].weight)   s2=j; 
} 
} 

void   HuffumanCoding(HTNode   *HT,char   **HC,int   w[],int   n) 
{ 
//w存放的是n个字符的权值（> 0)，构造最优树HT 
//HC用于存放n个字符的编码。 
int   i,m,f,c,j,s1,s2,start; 
char   *cd=0; 
HTNode   *p=0; 
if(n <=1)   return; 
m=2*n-1; 
for(p=HT+1,i=1;i <=n;i++,p++) 
{   p-> weight=w[i-1];p-> parent=0;p-> lchild=0; 
p-> rchild=0;} 
for(;i <=m;i++,p++) 
{   p-> weight=0;p-> parent=0;p-> lchild=0; 
p-> rchild=0;} 
for(i=n+1;i <=m;i++) 
{ 

Select(HT,i-1,s1,s2);   //注意：值传递的形参并不能用来改变实参的值 
//在HT[1,...,i-1]选择parent为0且weight最小的2个结点，序号分别为s1,s2 
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; 
} 
#ifdef   letter   //预   编译 
//无栈非递归遍历最优数，求最优编码 

int   p1=m; 
int   cdlen=0; 
cd=new   char[n]; 
for(i=1;i <=m;i++)   HT[i].weight=0; 
while(p1) 
{ 
if(HT[p1].weight==0) 
{ 
//向左遍历 
HT[p1].weight=1; 
if(HT[p1].lchild!=0) 
{p1=HT[p1].lchild;cd[cdlen++]= '0 ';} 
else   if(HT[p1].rchild==0){ 
//对于最优树，这个条件可以去掉 
HC[p1]=new   char[cdlen+1]; 
cd[cdlen]= '\0 '; 
strcpy(HC[p1],cd); 
} 
} 
else   if(HT[p1].weight==1) 
{ 
//向右遍历 
HT[p1].weight=2; 
if(HT[p1].rchild!=0) 
{p1=HT[p1].rchild;cd[cdlen++]= '1 ';} 
} 
else 
{ 
//从结点向上退 
HT[p1].weight=0; 
p1=HT[p1].parent; 
cdlen--; 
} 
} 
delete   []cd; 
cout < < "无栈非递归求霍夫曼编码 " < <endl; 
} 


#else 
//从叶子到根逆向求每个字符的最优编码 
cd=new   char[n]; 
cd[n-1]= '\0 '; 
for(i=1;i <=n;i++) 
{ 
start=n-1; 
for(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 ';//为了区分权值比较小的2个字符 
HC[i]=new   char[n-start]; 
for(j=start;j <n;j++) 
HC[i][j-start]=cd[j]; 
//把cd[start,...,n-1]复制给HC[i] 
} 
delete   []cd; 
cout < < "从叶子到根求霍夫曼编码 " < <endl; 
} 
#endif 


int   main() 
{ 

int   i; 
HTNode   HT[2*N]; 
char   *HC[N+1]; 
int   w[N];   //每个符号对应的出现几率，根据它写出每个符号的编码 
srand(time(NULL)); 
for(i=0,w[0]=1,w[1]=2;i <N;i++) 
//   w[i]=w[i-1]+w[i-2]+1; 
//当w数组满足   w[i]> =w[i-1]+w[i-2]+1时，编码的情况最坏，即此时树最深 
w[i]=rand()%MAX+1; 
HuffumanCoding(HT,HC,w,N); 
for(i=1;i <N+1;i++) 
printf( "%d   's   huffumancode   is   %s\n ",w[i-1],HC[i]); 
printf( "\n "); 
/* 
for(i=1;i <2*N;i++) 
printf( "%d--%d--%d--%d\n ",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);*/ 
printf( "\n "); 
return   1; 
} 


/* 


void   translate(char   code[],int   n,char   *parentcode) 
{ 
//   译码 
p=m; 
k=0; 
for(i=0;i <n;i++) 
{ 
if(str[i]== '0 ') 
{ 
p=HT[p].lchild; 
if(p==0) 
{ 
str[k,...,i]->   译成原来的字符//即在HC中查找与之相匹配的字符串 
k=i+1; 
p=m; 
} 

} 
else   //即str[i]== '1 ' 
{ 
p=HT[p].lchild; 
if(p==0) 
{ 
str[k,...,i]->   译成原来的字符//即在HC中查找与之相匹配的字符串 
k=i+1; 
p=m; 
} 
} 
} 
}