huffmantree.h

实现用哈夫曼树进行简单的编码译码功能

//程序名：HuffmanTree.h
//程序功能：哈夫曼树的实现文件
//程序作者：伍世浩 20072102310
//日期：2008.12.11
//文件信息：
//  Huffman.h             哈夫曼树的定义文件
//  HuffmanTree.h         哈夫曼树的实现文件
//  HuffmanTree_Main.cpp  主函数



#include"Huffman.h"
#include<iostream>
using namespace std;
#include<fstream> 
#include<iomanip> 
const int Max=10000;//定义字符数组的最大值

//////////////////////////////////////////////////////////////////////////////
//  构造函数
//  函数功能：构造哈夫曼树
//函数参数：无
//参数返回值：无
HuffmanTree::HuffmanTree ( )
{
  void ReadDefault( );//默认哈夫曼树
}
//////////////////////////////////////////////////////////////////////////////
//  析构函数
//  函数功能：构造哈夫曼树
//函数参数：无
//参数返回值：无
HuffmanTree::~HuffmanTree()
{
	delete []Info;
	delete []Node;
	LeafNum=0;
}
//////////////////////////////////////////////////////////////////////////////
//  创建函数
//  函数功能：手工方式重新创建哈夫曼树
//函数参数：叶子数
//参数返回值：无
void HuffmanTree::Create( int WeightNum )
{
	  Node=new struct HuffmanNode [ 2*WeightNum-1 ];//WeightNum权值对应的哈夫曼数中的结点总数为2*WeightNum-1个
	  Info=new char [ 2*WeightNum-1 ];

	  int i;
	  for( i=0; i<WeightNum; i++ )
	  {
		 cout<<"请输入第"<<i+1<<"个字符值:";
		 cin.get();
		 Info[i]=cin.get();                
		 if( Info[i]==' ')
			       Info[i]='*';
		 if( Info[i]=='\n')
			       Info[i]='$';
		 cout<<endl<<"请输入该字符的权值或频度:";
		 cin>>Node[i].weight;
		 cout<<endl;
	  }
	  LeafNum=WeightNum;//叶子数
	  Build();//调用生成函数
}

//////////////////////////////////////////////////////////////////////////////
//  生成函数
//  函数功能：利用现有的Info和Node信息生成一颗哈夫曼树
//函数参数：无
//参数返回值：无
void HuffmanTree::Build( )
{
	  int i, j, pos1, pos2, max1, max2;
	  int WeightNum=LeafNum;
	  for( i=WeightNum; i<2*WeightNum-1; i++ )
	  {//表示总共要做的合并数
		  pos1=-1;
		  pos2=-1;//分别用来保存当前最小值和最大值所在单元的编号
		  max1=32767;
		  max2=32767;//分别用来保存当前找到的最小值和次小值
		  for( j=0; j<= i-1; j++ )//在根结点中选出权值最小的两个
			  if( Node[j].parent==-1 )
			  {//是否为根结点
				  if( Node[j].weight < max1 )
				  {//是否比最小值小
					  max2=max1;//原最小值变为次小值
					  max1=Node[j].weight;//存放当前最小值
					  pos2=pos1;//修改次小值所在的单元编号
					  pos1=j;//修改最小值所在的单元编号
				  }
				  else if( Node[j].weight < max2 )
				  {//比最小值大但比次小值小
					  max2=Node[j].weight;//存放次小值
					  pos2=j;//	修改次小值所在的单元编号		  
				  }
			  }
		//开始新建一个结点
		   Node[pos1].parent=i;
		   Node[pos2].parent=i;// 新建结点为最小值和次小值结点的父母
		   Node[i].lchild=pos1;
		   Node[i].rchild=pos2; 
		   Node[i].parent=-1;//定义为根结点
		   Node[i].weight=Node[pos1].weight+Node[pos2].weight;//新建父母的权值为左右孩子权值之和
	  }//for	
}

//////////////////////////////////////////////////////////////////////////////
//  编码函数
//  函数功能：利用现有的哈夫曼树为字符编码
//函数参数：当前要编码的一个字符
//参数返回值：无
char *HuffmanTree::Encoder(char ch)//利用构造好的哈夫曼树对字符ch进行编码
{	
   char *code;
   int i, j, start=0;
   code = new char [LeafNum];//为所产生的编码分配容量为LeafNum的储存空间，因为不等长编码中最长的编码一定不会超过要求编码的字符个数
   for( i=0; i<LeafNum; i++)
	   if( Info[i]==ch )// 求出该文字所在单元的编号
		   break;

   j=i;
   while( Node[j].parent!=-1 )
   {//结点j非树根
	   j=Node[j].parent;//求结点j的双亲结点
	   if( Node[j].lchild  == i )//是左子数，则生成代码0
		   code[start++] = '0';
	   else
		   code[start++] = '1';//是右子树，则生成代码1
	   i=j;//   i保存当前结点的位置
   }
   code[start]='\0';//置串结束符
   for( i=0; i<start/2; i++)//对二进制序列进行逆置
   {
	   j=code[i];
	   code[i]=code[start-i-1];
	   code[start-i-1]=j;     
   }

   ofstream s_code;//打开文件流
   s_code.open( "code.txt",0x08);//用尾增添的方式打开
   for( i=0; i<start; i++)
   {
	   s_code<<code[i]<<" ";
   }
   s_code.close();
   //cout<<code<<endl;
   return(code);//返回改二进制序列串
}//Encoder


//////////////////////////////////////////////////////////////////////////////
//  译码函数
//  函数功能：利用现有的哈夫曼树为code译码
//函数参数：要译码的密码字符串地址
//参数返回值：无
void HuffmanTree::Decoder( char *BitStr )
{
	int i=0;
	int j=LeafNum*2-1-1;//表示从根结点开始往下搜索

	while(  BitStr[i]!='\0' )
	{
		if( BitStr[i]=='0' )
			j=Node[j].lchild ;//往左走
		else
			j=Node[j].rchild;//往右走
			if(Node[j].rchild==-1)//到达叶子结点
			{
				if( Info[j]=='*')
			         Info[j]=' ';
		        if( Info[j]=='$')
			         Info[j]='\n';
				cout<<Info[j];//输出叶子结点对应的字符
				j=LeafNum*2-1-1;//表示重新从根结点开始往下搜索
			}
	   i++;
	}//while
}//Decoder




//////////////////////////////////////////////////////////////////////////////
//  文件写入函数
//  函数功能：将哈夫曼树的信息保存到文件中
//函数参数：无
//参数返回值：无
void HuffmanTree::WriteFile(void)  //
{
  //HuffmanNode *p;
  int x;//用来保存结点的权重
  char infomation;//用来保存结点字符信息
  ofstream fp("Huffman.txt");
  if( !fp)
 {
	cout<<"不能打开Huffman.txt文件！";
  }
  int i;
  for( i=0; i<LeafNum; i++)
  {  
     infomation=Info[i];
	 x=Node[i].weight;
	 fp<<infomation<<" "<<x<<" ";
	 cout<<infomation<<" "<<x<<" ";
  }
  fp.close();
  cout<<"保存信息成功"<<endl;
}

//////////////////////////////////////////////////////////////////////////////
//  文件读取函数
//  函数功能：从文件中读取信息到哈夫曼树中
//函数参数：无
//参数返回值：无
void HuffmanTree::ReadFile(void)   
{ 
  delete []Info;
  delete []Node; 
  HuffmanNode temp_Node[100];
  char temp_Info[100];
  int x;//用来保存结点的权重
  char infomation;//用来保存结点字符信息
  ifstream fp("Huffman.txt");
  if( !fp )
 {
	cout<<"不能打开Huffman.txt文件！";
  }
  int i=0;
  while( !fp.eof() )
  {
	fp>>infomation>>x;
	cout<<infomation<<" "<<x<<" ";
	temp_Info[i]=infomation;
	temp_Node[i].weight=x;   
	i++;
  }
  LeafNum=i;
  Node=new struct HuffmanNode [ 2*LeafNum-1 ];//WeightNum权值对应的哈夫曼数中的结点总数为2*WeightNum-1个
  Info=new char [ 2*LeafNum-1 ];
  Build();
  fp.close();
  cout<<"读取信息成功"<<endl;
}
//////////////////////////////////////////////////////////////////////////////
//  读取默认函数
//  函数功能：读取默认的哈夫曼树
//函数参数：无
//参数返回值：无
void HuffmanTree::ReadDefault( void )
{
  LeafNum=28;//默认树的叶子数目

  Node=new struct HuffmanNode [ 2*LeafNum-1 ];//WeightNum权值对应的哈夫曼数中的结点总数为2*WeightNum-1个
  Info=new char [ 2*LeafNum-1 ];
  ifstream fp;
  int x;//用来保存结点的权重
  char infomation;//用来保存结点字符信息
  ifstream fp2("HuffmanDefault.txt");
  if(!fp2)
 {
	cout<<"不能打开Huffman.txt文件！";
  }  
  int i;
  for( i=0; i<LeafNum; i++)
  {
	fp2>>infomation>>x;
	Info[i]=infomation;
	Node[i].weight=x;   
  }
  fp2.close();
}

//////////////////////////////////////////////////////////////////////////////
//  创建哈夫曼树函数
//  函数功能：自动创建哈夫曼树
//函数参数：无
//参数返回值：无
void HuffmanTree::Auto_Creat()
{
	char input[ Max ];//保存用来编码的字符
	char temp_Info[ Max ];//用来保存新哈夫曼树中的不同字符
	int counter[ Max ];//计算权值
    int num_input=0;//要建码的字符总数
	int num_Info=0;//新哈夫曼的叶子树
	int check;//标志当前字符是否已经出现过
	int i;
	cout<<"请输入用来建立哈夫曼树的字符串（输入#号符结束）：";
	cin>>input[0];
	while( input[ num_input ]!='#')
	{
		if( input[ num_input ]==' ')
			input[ num_input ]='*';
		if( input[ num_input ]=='\n')
			input[ num_input ]='$';
		check=0;
		for( i=0; i<num_Info; i++)
		{
			if( input[ num_input ]==temp_Info[ i ])
			{//如果当前字符已经出现过
				counter[i]++;//权值增加
				check=1;//标志
			    break;
			}
		}
		if( check==0 )
		{//如果当前字符是新字符，则插入          
			temp_Info[ num_Info ]=input[ num_input ];
			counter[ num_Info ]=1;
			num_Info++;
		}		
		num_input++;
		input[ num_input ]=cin.get();
	}

     LeafNum=num_Info;
     Node=new struct HuffmanNode [ 2*LeafNum-1 ];//WeightNum权值对应的哈夫曼数中的结点总数为2*WeightNum-1个
     Info=new char [ 2*LeafNum-1 ];

	int WeightNum=num_Info;   
	cout<<endl;
	  for( i=0; i<WeightNum; i++ )
	  {
	     Info[i]=temp_Info[i];
		 Node[i].weight=counter[i];
	  }
	  Build( );//调用生成函数
}

//////////////////////////////////////////////////////////////////////////////
//  显示函数
//  函数功能：用递归算法，凹入表示法显示哈夫曼树
//函数参数：哈夫曼树的总节点数和层数
//参数返回值：无
void HuffmanTree::Print(int T,int layer){
	if (T!=-1){  //如果是非空二叉树
		//递归输出左子树
		Print( Node[T].lchild,layer+1);
		//输出根

		cout<<endl;
		for (int i=0;i<layer*5;i++) { //按layer输出空格
			cout<<"-";
		}
		if ( Node[T].lchild==-1){ //叶结点
			cout<<Info[T]<<Node[T].weight<<endl;
		}
		else {//内部结点
			cout<<Node[T].weight<<endl;
		}
		//递归输出右子树
		Print( Node[T].rchild,layer+1);
	}
}

int HuffmanTree::Get_LeafNum( )//取出叶子数
{
	return LeafNum;
}

char code_name[30],huffman_name[30];