hm.h

c++实现霍夫曼编码

///hm.h

#include<iostream.h>
#include<string.h>
#include"file1.h" ///相当全局变量
#include"file2.h"
#define N 96      //叶子结点数
#define M 2*N-1  //树中结点总数

class huffman
{ public:
   huffman(int m)
   {
	   n=m;
   }
   void CreateHT();//构造霍夫曼树
   void CreateHCode();//构造霍夫曼编码
   void DispHCode();//输出霍夫曼编码
   void input();
private:
	HTNode ht[M]; //节点
	HCode hcd[N];///编码
	int n;

};
/////////////////////////////
void huffman::CreateHT()//构造霍夫曼树
{
int i,k,lnode,rnode;
int min1,min2;
for(i=0;i<2*n-1;i++)
 ht[i].parent=ht[i].lchild=ht[i].rchild=-1 ;//所有结点相关域初值-1
  for(i=n;i<2*n-1;i++)        //构造树
  {
	 min1=min2=9999;
     lnode=rnode=-1;         //lnode和rnode权最小的两个结点位置
  for(k=0;k<i;k++)
   if(ht[k].parent==-1)      //只在未构造二叉树的结点中查找
   { 
	     if (ht[k].weight<min1)
		 {min2=min1;rnode=lnode;
          min1=ht[k].weight;lnode=k;
  }
    else if(ht[k].weight<min2) 
	{ min2=ht[k].weight;
      rnode=k;
	}
}
  ht[lnode].parent=i;ht[rnode].parent=i;
  ht[i].weight=ht[lnode].weight+ht[rnode].weight;
  ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
/////////////////////////////
void huffman::CreateHCode()   //构造霍夫曼编码
{
int i,f,c;
HCode hc; 
for(i=0;i<n;i++)     //根据霍夫曼树求霍夫曼编码
{
  hc.start=n; c=i;
  f=ht[i].parent;
  while(f!=-1)            //循环至根节点
  {
  if(ht[f].lchild==c)  //处理左孩子结点
	  hc.cd[hc.start--]='0';
  else                //处理右孩子结点
       hc.cd[hc.start--]='1';
      c=f;f=ht[f].parent;
  }
  hc.start++;        //start指向霍夫曼编码最开始字符
  hcd[i]=hc;
}
}
///////////////////////////////////
void huffman::input()
{	
   int i;
   char str[8];
   int fnum;
   for(i=0;i<n;i++)
   {  
	cout<<"请输入第"<<i+1<<"个字符 :";
	cin>>str;
	cout<<"第"<<i+1<<"个字符对应权值:";
	cin>>fnum;
	strcpy(ht[i].data,str);
	ht[i].weight=fnum;
}
	  cout<<endl;
}
/////////////////////////////////////
void huffman::DispHCode()//输出霍夫曼编码
{
int i,k;
int sum=0,m=0,j;
cout<<"输出霍夫曼编码如下所示 : "<<endl;
for(i=0;i<n;i++)
{
   j=0;
   cout<<ht[i].data<<":  ";     //字符部分
   for(k=hcd[i].start;k<=n;k++)
   {
   cout<<hcd[i].cd[k];    //编码部分
   j++;
   }
   cout<<endl;
   m+=ht[i].weight;        
   sum+=ht[i].weight*j;     ///编码总长度
   cout<<endl;
}
cout<<"编码的平均长度 =  "<<1.0*sum/m<<endl; ////平均长度
 cout<<"/*---------/\----------*/"<<endl;
}