haffman.h

哈夫曼的编译码问题

typedef struct
{
    
	int weight;
	int flag;
	int parent;
	int leftchild;
	int rightchild;
}HaffNode;
typedef struct
{
	char str;
	int bit[Max];
	int start;
	int weight;
}Code;
class Haffman
{
private:
    HaffNode haffTree[2*Max];//哈夫曼树
	int leaf;//有多少个叶子结点
	Code haffCode[Max];//
	int grand;
public:
    Haffman();//构造哈夫曼树
	void HaffManC();//写编码
	void HaffCodeD();
    int Get(){return grand;}
    void HaffCodeT(int,int);
	void HaffCodeP();
};

 Haffman::Haffman ()
{
	char ch;
    int i,k,h,m1,m2,x1,x2,j;
	for(j=0;j<2*Max;j++)
		haffTree[j].weight=0;
	i=0;
    ifstream infile("file.txt");
   if(!infile)
   {
	  cout<<"can't open file"<<endl;
	  abort();//-----------退出程序
   }
   //------------从文件file.txt中把字符依次读入，并统计每 个字体符出现的次数即是它们的权值，
   //-------每出现一个新的字符就把它存到数组haffcode中，如果以前已经出现了就在该字符的权值下加一 
	while(infile>>ch)
    {
		for(k=0;k<i;k++)
			if(haffCode[k].str==ch)break;
	    if(k==i){
		haffCode[i].str=ch;
		haffTree[i].weight++;
		i++;
			}
		else haffTree[k].weight++;
	}
	//---------最后HAFFCODE的数组的长度即统计的字符的个数即是叶子结点的个数 
	leaf=i;
	cout<<"leaf="<<leaf<<endl; 
	//-----------起初把左右孩子结点及双亲都赋为空 
    for(i=0;i<2*leaf-1;i++)
	{
	haffTree[i].parent=-1;
	haffTree[i].leftchild=-1;
	haffTree[i].rightchild=-1;
	haffTree[i].flag=0;//----------标记有处于挑出两个孩子结点
	}
	//-----------构造哈夫曼树，找出叶子结点的双亲结点并一直到主根 
	//-----------确定每个根的左右孩子结点 
    for(i=0;i<leaf-1;i++)
	{
		m1=m2=MaxValue;//------把权值都设为最大的
		x1=x2=0;//------把下标都设为零
		for(j=0;j<leaf+i;j++)//-------找出下标为N+I的两个孩子结点，即在0和N+I中挑两个最小的
        {
			if(haffTree[j].weight<m1&&haffTree[j].flag==0)
			{
				m2=m1;
				x2=x1;
				m1=haffTree[j].weight;
				x1=j;
			}//--------x1的权值始终小于等于X2
			else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
			{
				m2=haffTree[j].weight;
				x2=j;
			}
		}
	
	haffTree[x1].parent=leaf+i;
	haffTree[x2].parent=leaf+i;
    haffTree[x1].flag=1;
	haffTree[x2].flag=1;
	haffTree[leaf+i].weight=haffTree[x1].weight+haffTree[x2].weight;
	haffTree[leaf+i].leftchild=x1;
	haffTree[leaf+i].rightchild=x2;
	}
}

//----------编码 
void Haffman::HaffManC()
{//------------对文件中出现的每个字符用哈夫曼编码的规则进行编码 
  Code *cd=new Code;
  int i,j,child,parent;
  char c;
  for(i=0;i<leaf;i++)
  {
	  cd->start=leaf-1;
	  cd->weight=haffTree[i].weight;
	  child=i;
	  parent=haffTree[child].parent;
	  while(parent!=-1)
	  {
		  if(haffTree[parent].leftchild==child)
			  cd->bit[cd->start]=0;
		  else cd->bit[cd->start]=1;
		   cd->start--;
		   child=parent;
		   parent=haffTree[child].parent;
	  }
	  for(j=cd->start+1;j<=leaf-1;j++)
      haffCode[i].bit[j]=cd->bit[j];
	  haffCode[i].weight=cd->weight;
	  haffCode[i].start=cd->start+1;
  }
  //----------将FILE里的字符哈夫曼编码的形式写入文本codefile文件中 
   ifstream  infile("file.txt");
    if(!infile)
	{
	  cout<<"can't open file"<<endl;
	  abort();//-----------退出程序
	} 
	ofstream out("codefile.txt");
   if(!out)
   {
	  cout<<"can't open file"<<endl;
	  abort();//-----------退出程序
   }
    while(infile>>c)
	{
		for(i=0;i<leaf;i++)
			if(c==haffCode[i].str)break;
			//cout<<i<<endl;
			for(j=haffCode[i].start;j<leaf;j++)
				out<<haffCode[i].bit[j];
	}
 out.close();
}
//---------------------译码（把文本CODEFILE中的哈夫曼编码依据哈夫曼树进行译码）
	void   Haffman::HaffCodeD()
	{
 		int i,j,a,cd,cc;
		char c;
		for(i=0;i<2*leaf-1;i++)
            if(haffTree[i].parent==-1)
			break;
		grand=i;
		ifstream in("codefile.txt");
		ofstream out("textfile.txt");
         if(!in)
		 {
	      cout<<"can't open file"<<endl;
	      abort();//-----------退出程序
		 }
		 cd=grand;//---CD的初值是主先 
		 //------每个编码从根结点开始渐渐向下逼近到叶结束，找到相应的字符再进行下一个字符的译码 
		 while(in>>c)
		 {//--------因为从文本读入的是字符，所以要转化为整型数字就要用ASCII码做变换 
			 cc=c-48;
			 if(cc==0)cd=haffTree[cd].leftchild;
			 else cd=haffTree[cd].rightchild;
			  if(haffTree[cd].leftchild==-1&&haffTree[cd].rightchild==-1)
			 {
				 out<<haffCode[cd].str;
				 cd=grand;
			 }
		 }
       out.close();
    }
    //----------以凹树的形式打印哈夫曼树 ，非叶子结点打印权值 
	void     Haffman::HaffCodeT(int a,int n)
	{
		int i;
		if(a==-1)return;
		HaffCodeT(haffTree[a].rightchild,n+1);
		for(i=0;i<n;i++)
			cout<<"      ";
        cout<<"-----";
		if(a>=0&&a<leaf)cout<<haffCode[a].str;
		cout<<"("<<haffTree[a].weight<<")";
		cout<<endl;
        HaffCodeT(haffTree[a].leftchild,n+1);
	}
//----------显示哈夫曼树每个叶结点的权值，及相应的编码
	void Haffman::HaffCodeP()
	{
		int i,j;
		for(i=0;i<leaf;i++)
		{
		cout<<haffCode[i].str<<"  "<<haffCode[i].weight<<"  ";
		for(j=haffCode[i].start;j<leaf;j++)
		cout<<haffCode[i].bit[j];
        cout<<endl;
		}
	}