file.cpp

我做的一个霍夫曼编码

//file.cpp
#include "head.h"
#include<iostream.h>
Hnodetype::Hnodetype()//构造函数
{
	 value=0; 
     parent=NULL; 
     left_child=NULL; 
     right_child=NULL;
}
Hnodetype::Hnodetype(Hnodetype* left,Hnodetype* right,float possibility)//构造函数
{
	value=possibility;
	parent=NULL;
	left_child=left;
	right_child=right;
}
Huffmantree::Huffmantree()
{
    int position=0,total_number=0;
	char input,first_char,copy,dustbin;
	List<char> text;
	int number[maxsize];
	float possibility[maxsize];
    no=0;
	cout<<"Please input the text(end up with '$'):"<<endl;
	cin>>input;
	while(input!='$')//输入文本串，并以$符号结束
	{
		text.insert(position++,input);
		cin>>input;
	}
	original_text=text;
	total_number=text.size();
    while(!text.empty())//获取每个不同字符出现的总次数
	{
		text.retrieve(0,first_char);
		text.remove(0,compact[no]);
		number[no]=1;
		for(int i=0;i<text.size();i++)
		{
            if(text.retrieve(i,copy)==underflow)
				break;
			if(first_char==copy)
			{
				number[no]++;
				text.remove(i,dustbin);
                i--;
			}
		}
		no++;
	}
	for(int i=0;i<no;i++)
		possibility[i]=(float)number[i]/(float)total_number;//计算每个叶子节点的概率
    
   for(i=0;i<no;i++) //存储每个叶子节点的概率
   {
	   huffnode[i]=new Hnodetype;
	  // huffnode[i]->root=huffnode[i];
	   huffnode[i]->value=possibility[i];
   }
   cout<<endl;
   for(i=0;i<no;i++)
	   cout<<"字符"<<compact[i]<<"的个数:"<<number[i]<<endl;
   cout<<"总的字符个数为："<<total_number<<endl;
   cout<<endl;
}
void Huffmantree::MakeNode()
{
   int i,j,first,second; 
   float lower,lowest,parent_value;
   for(i=0;i<no-1;i++) /*开始循环构造哈夫曼树*/ 
   { 
      lowest=lower=MAXVALUE; 
      first=second=0; 
      for(j=0;j<no+i;j++) //选出概率值最小的两个节点（排除已选过的）
	  { 
         if(huffnode[j]->parent==NULL&&huffnode[j]->value<lowest) //选取最小的 
		 { 
           lower=lowest;
		   second=first;
		   lowest=huffnode[j]->value;
		   first=j; 
		 } 
         else if(huffnode[j]->parent==NULL&&huffnode[j]->value<lower) //选取次小的
		 { 
           lower=huffnode[j]->value;
		   second=j; 
		 } 
	  } 
    parent_value=huffnode[first]->value+huffnode[second]->value;
	//根据选出的两个节点构造新的节点作为其父节点
	huffnode[no+i]=new Hnodetype(huffnode[first],huffnode[second],parent_value);
	huffnode[first]->parent=huffnode[no+i];
	huffnode[second]->parent=huffnode[no+i];   
   } 
}
void Huffmantree::GetCode()
{
	int index;
	Hcodetype temp;
	Hnodetype* up; 
	char copy;
	for(int i=0;i<no;i++) /*该循环求每个叶子节点对应字符的哈夫曼编码*/ 
	{ 
       temp.start=no-1;
	   index=i; 
       up=huffnode[index]->parent; 
       while(up!=NULL) //利用parent指针从叶子节点找根节点的方法计算编码值（逆值）
	   { 
         if(up->left_child==huffnode[index]) 
			 temp.bit[temp.start]=0; 
         else 
			 temp.bit[temp.start]=1; 
         temp.start--;
		 huffnode[index]=up; 
         up=huffnode[index]->parent; 
	   } 
      for(int j=temp.start+1;j<no;j++) /*保存求出的每个叶节点的哈夫曼编码和编码的起始位*/ 
         huffcode[i].bit[j]=temp.bit[j]; 
      huffcode[i].start=temp.start; 
	} 
    for(i=0;i<no;i++) /*输出每个叶子节点的哈夫曼编码*/ 
	{ 
	   cout<<"字符"<<compact[i]<<" 编码为:";
       for(int j=huffcode[i].start+1;j<no;j++) 
		   cout<<huffcode[i].bit[j];
	   cout<<endl;
	} 
	cout<<endl<<"最后编码为："<<endl;
	for(i=0;i<original_text.size();i++)//输出输入串的编码值
	{
		original_text.retrieve(i,copy);
		for(int j=0;j<no;j++)
		{
			if(copy==compact[j])
			{
				for(int x=huffcode[j].start+1;x<no;x++) 
		          cout<<huffcode[j].bit[x];
				cout<<" ";
			}
		}
	}
	cout<<endl;	    	
}