hufflemantree.cpp

哈夫曼树的源代码

#include <iostream> 
#include <string> 
using namespace std; 
typedef struct            //定义结点结构体
{ 
     char letter;           //字母
     int weight;            //权数
	 int tag;
     int parent,left,right; //父结点，左右孩子结点
}HTNode,*HuffmanTree; 
typedef char **HuffmanCode;     //存储编码
void Create(HuffmanTree &ht,int *frq,char *s,int n);//创建哈夫曼树
void Coding(HuffmanTree ht,HuffmanCode &hc,int n);//对字符进行编码
void Select(HuffmanTree ht,int i,int&s1,int&s2); //找取最小的两个数 
void Encode(HuffmanTree ht,HuffmanCode hc,string s,int n); //将字符串编码
void Create(HuffmanTree &ht,int *frq,char *s,int n)//创建哈夫曼树
{ 
  int i,m; 
  int s1,s2; 
  HuffmanTree p; 
  m=2*n-1;                                            
  ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));          //创建2n-1个结点空间  
  for(p=ht+1,i=1;i<=n;i++,p++,frq++,s++) //0号单元未用
  {                                                    //初始化结点 
    p->letter=*s; 
    p->weight=*frq; 
    p->parent=p->left=p->right=0; //对每个结点的父，左右孩子结点都设为0
  } 
  for(i=n+1;i<=m;++i,++p) 
  { 
    p->weight=p->parent=p->right=p->left=0; 
  } 
  for(i=1;i<=m;i++)
	  ht[i].tag=0;
  for(i=n+1;i<=m;++i) 
  { 
    Select(ht,i-1,s1,s2);                    
    ht[s1].parent=ht[s2].parent=i; 
    ht[i].weight=ht[s1].weight+ht[s2].weight; 
    ht[i].left=s1; 
    ht[i].right=s2; 
  } 
} 
void Coding(HuffmanTree ht,HuffmanCode &hc,int n)//对字符进行编码
{ 
   int i,c,f,start; 
   char *cd; 
   hc=new char *[n+1]; 
   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].left==c) 
	      cd[--start]='0'; //left:'0' 
       else 
	      cd[--start]='1'; //right:'1' 
     hc[i]=new char [n-start]; 
   strcpy(hc[i],&cd[start]); 
   } 
   free(cd); 
} 
void Select(HuffmanTree ht,int i,int&s1,int&s2)
{ 
   int sm1,sm2;
   s1 = 1; 
   s2 = 1; 
   int m=0; 
   for(m=1;m<=i;m++)    //第一次得到第一个父母为0的接点的权数
   { 
      if(ht[m].parent!=0) 
         continue; 
      else 
	  { 
         sm1=ht[m].weight; 
         s1=m; 
         break; 
	  } 
   } 
  for(int j=m+1;j<=i;j++)    //得到最小权数的结点序号
  { 
     if(ht[j].parent!=0) continue; 
     else 
	 { 
       if(sm1>ht[j].weight) 
	   { 
         sm1=ht[j].weight; 
         s1=j; 
	   } 
	 } 
  } 
 for(m=1;m<=i;m++)     //第二次得到第一个父母为0且不等于s1的接点的权数
 { 
  if(ht[m].parent!=0) continue; 
  else 
  { 
    sm2=ht[m].weight; 
    s2=m; 
    if(s2==s1) continue; 
    else break; 
  } 
 } 
 for(int k=m+1;k<=i;k++) //得到最小权数的结点序号
 { 

   if(ht[k].parent!=0) continue; 
   else 
   { 
     if((ht[k].weight<sm2)&&(k!=s1)) 
	 { 
       sm2=ht[k].weight; 
       s2=k; 
	 } 
   } 
 } 
} 
void View(HuffmanTree ht,HuffmanCode hc, char *c,int n)   //打印哈夫曼编码
{ 
                                                             
   int i; 
   for(i=1;i<=n;i++)
   { 
      cout<<ht[i].letter<<"---"<<hc[i]<<endl; 
   } 
   cout<<endl; 
} 
void Encode(HuffmanTree ht,HuffmanCode hc,string s,int n)    //将字符串编码
{ 
 int m=s.length();
 for(int i=0;i<m;i++)
 { 
   for(int j=0;j<n;j++)
   { 
           if(s[i]==ht[j+1].letter) 
                cout<<hc[j+1]; 
   } 
 } 
                  cout<<endl; 
}
int main()
{ 
     HuffmanTree ht; 
     HuffmanCode hc; 	
     int *frq;  //权数 
     char *c;   //字母
     int n,k=1; 
     string s; 	                     
	 cout<<"--------创建哈夫曼树-------------"<<endl; 
     cout<<"请输入字母总数:"<<endl; 
     cin>>n; 
     frq=new int [n]; 
     c=new char [n]; 
	 cout<<"请输入所以字符以及字符的频度:"<<endl;
	 for(int i=0;i<n;i++){
		 cin>>c[i];
		 cin>>frq[i];
	 }
     Create(ht,frq,c,n);
     Coding(ht,hc,n); 
	 cout<<"字符编码为:"<<endl; 
     View(ht,hc,c,n);
	 cout<<"创建成功!\n";
	 cout<<endl;
	 cout<<"请输入要编码的字符串:"<<endl; 
     cin>>s; 
     cout<<"编码结果: "<<endl;
     Encode(ht,hc,s,n);
	  _sleep(1000);
     return 0; 
}