haffmantree.cpp

哈弗曼编码的递归实现算法

//程序名：HaffmanTree.cpp
//程序功能：实现哈弗曼树的编码和译码功能
//作者：黄秋旋
//日期：2008.12.4
//版本：1.0
//对应类头文件：hafuman.h
//对应主程序：main.cpp

#include"hafuman.h"

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：初始化函数
//函数功能：初始化数据，并生成哈弗曼树
//函数参数：无
//参数返回值：
//      如果重新初始化哈弗曼树，则返回叶子节点的个数
//      如果从文件中读取哈弗曼树，则返回0表示读取成功

int HaffmanTree::Haffman()          
{
	int num;
	int choice;
	cout<<"\n1:重新构造哈弗曼树！";
	cout<<"\n2:从文件中读取哈弗曼树！";
	cout<<"请选择： 1 或 2 ！";             //选择重新构造哈弗曼树，还是从文件中读取哈弗曼树
	cin>>choice;
	
	if(choice==1)       //选择重新构造哈弗曼树
	{
		int n;
	    cout<<"请输入叶子的个数：";
		cin>>n;
		num=n;

	    ofstream fop;
	    fop.open("hfmTreey.txt", ios::out|ios::binary);    //打开文件，存储哈弗曼树的初始化字符
	    
		HaffNode * ht= new HaffNode[2*num-1];            //申请存储哈弗曼树的节点的空间
	    char *yezi=new char[num];              //申请存储初始化字符的空间
		
	    for(int i=0; i<num; i++)
		{
			cout<<"请出入第"<<i+1<<"个字符： ";
            cin>>yezi[i];				//从终端输入初始化字符
		    fop<<yezi[i];               //并将字符存储到文件 hfmTreey.txt 中
		    cout<<"请输入该字符的权值: ";
		    cin>>ht[i].weight;         //从终端输入初始化字符的权值
		    ht[i].parent=0;            
		    ht[i].lchild=-1;
		    ht[i].rchild=-1;
		    cout<<endl;		        
		}
	    cout<<endl; 
	    fop.close();       //关闭文件

	    for(i=num; i<2*num-1; i++)
		{
			ht[i].weight=0;
		    ht[i].parent=0;		
		    ht[i].lchild=-1;
		    ht[i].rchild=-1;		
		}

	    for(i=0; i<num-1; i++)            //构造哈弗曼树 
		{
			int m1,m2,x1,x2;
		    m1=m2=1000;                  //存储两个最小的权值
		    x1=x2=0;                 //存储两个最小权值在结构体数组中的位置
			for(int j=0; j<num+i; j++)
			{
				if(ht[j].weight<m1 && ht[j].parent==0)
				{
					m2=m1;
				    x2=x1;
				    m1=ht[j].weight;
				    x1=j;
				}
			    else if(ht[j].weight<m2 && ht[j].parent==0)
				{
					m2=ht[j].weight;
				    x2=j;
				}
			}

			ht[x1].parent=num+i;
	        ht[x2].parent=num+i;
	        ht[num+i].lchild=x1;
	        ht[num+i].rchild=x2;
	        ht[num+i].weight=ht[x1].weight+ht[x2].weight;           //给新节点付权值
		}

		ofstream fop1;                  
	    fop1.open("hfmTree.txt",ios::out|ios::binary);    //打开文件，写入初始化字符的信息
	    for(i=0;i<2*num-1;i++)                         //向文件hfmTree.txt写入哈弗曼树的信息
		{ 
			fop1<<ht[i].weight<<" ";         
			fop1<<ht[i].parent<<" ";
		    fop1<<ht[i].lchild<<" ";
		    fop1<<ht[i].rchild<<" ";
		    fop1<<endl;
		}
	    fop1.close();                         //关闭文件
	
    	cout<<"\n初始化完成，且已将哈弗曼树存储到hfmTree.dat文件中！\n";
	}
	
	else if(choice==2)         //选择从文件中已有的哈弗曼树
	{   
		int i=0;
		int in;
		ifstream fip0;
	    fip0.open("hfmTree.txt",ios::in|ios::binary);             //打开文件，读取哈弗曼树的信息
		if(fip0.fail())            //判断打开是否失败
		{
			cout<<"\n打开失败! 该文件不存在!\n";
            return 0;
		}
		while(fip0>>in)              //计算文件hfmTree中的节点个数   
			i++;                                                   
		fip0.close();
		leafnum=i/8+1;
       
		
	    cout<<"\n该二叉树有"<<leafnum<<"个叶子节点!"<<endl;      //测试段
        HaffNode *ht= new HaffNode[2*leafnum-1];           //申请存储节点的空间

	    ifstream fip;
	    fip.open("hfmTree.txt",ios::in|ios::binary);   //打开文件hfmTree,读取文件中的内容
	    i=0;
	
		while(fip>>in)           //读取哈弗曼树的节点信息
		{
			int j=i/4;
		    int k=i%4;
		    switch(k)
			{
			case 0:
				ht[j].weight=in;

			    break;
		    case 1:
				ht[j].parent=in;

			    break;
		    case 2:
				ht[j].lchild=in;//cout<<ht[j].lchild<<" ";//
			    break;
			case 3:
			    ht[j].rchild=in;//cout<<ht[j].rchild<<" ";cout<<endl;//
			    break;
			}
		    i++;
		}
	    fip.close();    //关闭文件hfmTree
 
		cout<<"\n读取完成！请进行下一步操作！";
	    return 0; 
	}
	return leafnum=num;
}


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//编码函数
//函数功能：利用哈弗曼树为文件中的内容编码
//函数参数：无
//参数返回值：无

void HaffmanTree::Encode()
{
	char ch;
	ifstream fip2;
	fip2.open("hfmTreey.txt",ios::in|ios::binary);                  //打开存储初始化字符的文件
	if(fip2.fail()) 
	{
		cout<<"\n打开失败！\n";
		return;
	}
	
	HaffNode *ht= new HaffNode[2*leafnum-1];
    char *yezi=new char[leafnum];
   
	int i=0;
	while(fip2.get(ch))                          
	{  
		yezi[i]=ch;              //将文件中的字符读取到yezi数组中
		i++;
	}
	yezi[i]='\0';                 //结束标志
	fip2.close();                 //关闭文件hfmTreey
     
	ifstream fip3;
	fip3.open("hfmTree.txt",ios::in|ios::binary);   //打开文件hfmTree,读取文件中的内容
	if(fip3.fail())
	{
		cout<<"\n打开失败! 该文件不存在!\n";
		return;
	}
	i=0;
	int in;
	while(fip3>>in)        //读取文件中内容
	{
		int j=i/4;
		int k=i%4;
		switch(k)
		{
		case 0:
			ht[j].weight=in;
			break;
		case 1:
			ht[j].parent=in;
			break;
		case 2:
			ht[j].lchild=in;
			break;
		case 3:
			ht[j].rchild=in;
			break;
		}
		i++;
	}
	fip3.close();    //关闭文件hfmTree
 
	ifstream fip;
	fip.open("ToBeTran.txt",ios::in|ios::binary);     //打开文件ToBeTran
	int count=0;

	while(fip.get(ch))
		count++;     //计算ToBeTran.txt中字符的个数
	fip.close();    //关闭文件ToBeTran.txt
  
	char *Tran=new char[count++];    //存储ToBeTran.txt中字符
    count=0;
	ifstream fipp;
	fipp.open("ToBeTran.txt",ios::in|ios::binary);
	if(fipp.fail())
	{
		cout<<"\n 打开文件失败！\n";
		return;
	}
	                  
	cout<<"\n需要编码的内容是:  ";                   
	while(fipp.get(ch))
	{   
		cout<<ch;
		Tran[count]=ch;       //读取ToBeTran.txt中字符
		count++;
	}
	cout<<endl;
	Tran[count]='\0';
	fipp.close();         //关闭文件ToBeTran.txt
    
   	ofstream fop;
	fop.open("CodeFile.txt", ios::out|ios::binary);     //打开存储代码的文件

	char *code=new char[leafnum];    //存储字符编码            
	int k=0;
	while(Tran[k]!='\0')            //为文件ToBeTran.txt中的内容编码
	{   
		int start=0;int l;
	    for(l=0;l<leafnum;l++)
			if(yezi[l]==Tran[k])    //查找与需要编码字符的对应字符
			{
				int child=l;
	            int parent=ht[child].parent;
	            while(parent!=0)         //编码
		        {   
			        start++;
		            if(ht[parent].lchild==child)
				        code[start]='0';
		            else 
			 	        code[start]='1';
                   
		            child=parent;
			        parent=ht[child].parent;
		        }//while
		        
			    while(start!=0)
	            {
		            fop<<code[start];
		            start--;
		        }//whilec
			}//if
			k++;
	}//while
	fop.close();
	cout<<"\n编码完成！且已存储到文件CodeFile.txt中！\n";

};//Encode


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//译码函数
//函数功能：将代码还原称字符
//函数参数：无
//参数返回值：无

void HaffmanTree::Decode()                       
{
	char ch;
    ifstream fip2;
    fip2.open("hfmTreey.txt",ios::in|ios::binary);        //打开存储初始化字符的文件
	if(fip2.fail()) 
	{
		cout<<"\n 打开失败！\n";
		return;
	}

	HaffNode *ht= new HaffNode[2*leafnum-1];       //申请存储二叉树的空间
	char *yezi=new char[leafnum];                //申请存储初始化字符的空间
   
	int i=0;
	while(fip2.get(ch))                          
	{  
		yezi[i]=ch;                    //将文件中的字符读取到yezi数组中
		i++;
	}
	yezi[i]='\0';          //结束标志
	fip2.close();        //关闭文件hfmTreey
       
	ifstream fip1;
	fip1.open("hfmTree.txt",ios::in|ios::binary);   //打开文件hfmTree,读取文件中的内容
	i=0;
	int in;
	while(fip1>>in)                 //读取文件中的内容
	{
		int j=i/4;
		int k=i%4;
		switch(k)
		{
		case 0:
			ht[j].weight=in;
			break;
		case 1:
			ht[j].parent=in;
			break;
		case 2:
			ht[j].lchild=in;
			break;
		case 3:
			ht[j].rchild=in;
		    break;
		}
		i++;
	}
	fip1.close();    //关闭文件hfmTree

	ifstream fip3;
	fip3.open("CodeFile.txt",ios::in|ios::binary);
		
	i=0;
	while(fip3.get(ch))
		i++;                  //计算文件CodeFile中字符的个数
	fip3.close();
		
	char *code=new char[i++];   //申请存放文件CodeFile中字符的数组
        
	ifstream fip4;
	fip4.open("CodeFile.txt",ios::in|ios::binary);
	i=0;
	while(fip4.get(ch))
	{
		code[i]=ch;               //读取文件CodeFile中的代码
		i++;
	}
	code[i]='\0';
	fip4.close();//关闭文件
   
	i=0;
    int j=2*leafnum-1-1;    //初始化变量j,使j指向ht数组的跟节点
       
	cout<<"\n译码后，得到字符为： ";
    while(code[i]!='\0')
   {
	   if(code[i]=='0')
		   j=ht[j].lchild;
	   else j=ht[j].rchild;
		   if(ht[j].rchild ==-1)
		   {    
			   cout<<yezi[j];    //找到代码对应字符，输出该字符
		        j=2*leafnum-1-1;           //j指向ht数组的跟节点，进行大二个字符的翻译
		   }
	       i++;
	}
	cout<<endl;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////
//印代码函数
//函数功能：印代码文件中的代码
//函数参数：无
//参数返回值：无

void HaffmanTree::Print()
{
	ifstream fip;                                      
	fip.open("CodeFile.txt",ios::in|ios::binary);       //以只读方式打开代码文件
	ofstream fop;
	fop.open("CodePrin.txt",ios::out|ios::binary);       //打开文件,将代码写入该文件

	char ch;
	cout<<"\n编码文件中的代码为:\n\n";
	int i=0;
	while(fip.get(ch))
	{
		
		if(i%50==0)           //每行输入50个代码        
		{
			cout<<endl;
            fop<<endl;	 //将代码存储到文件CodePrin.txt中
		}
		i++;
		cout<<ch;
        fop<<ch;	
	}//while
	fip.close();    //关闭文件
	fop.close();
	cout<<"\n代码已写入文件CodePrint.txt中!\n";
}


/////////////////////////////////////////////////////////////////////////////////////////////////////////////
//印哈弗曼树
//函数功能：通过调用递归函数输出哈弗曼树
//函数参数：无
//参数返回值：无

void HaffmanTree::PrintTree()
{
	char ch;
	ifstream fip2;
    fip2.open("hfmTreey.txt",ios::in|ios::binary);                  //打开存储初始化字符的文件
	if(fip2.fail()) 
	{
		cout<<"\n 打开失败！\n";
        return;
	}

     HaffNode *ht= new HaffNode[2*leafnum-1];       //申请存储二叉树的空间
     char *yezi=new char[leafnum];                //申请存储初始化字符的空间
   
     int i=0;
	 while(fip2.get(ch))                          
	{  
		yezi[i]=ch;                    //将文件中的字符读取到yezi数组中
		i++;
	}
	yezi[i]='\0';         //结束标志
	fip2.close();     //关闭文件hfmTreey
       
	ifstream fip1;
	fip1.open("hfmTree.txt",ios::in|ios::binary);   //打开文件hfmTree,读取文件中的内容
	i=0;
	int in;
	while(fip1>>in)
	{
		int j=i/4;
		int k=i%4;
		switch(k)
		{
		case 0:
			ht[j].weight=in;
			break;
		case 1:
			ht[j].parent=in;
			break;
		case 2:
			ht[j].lchild=in;
			break;
		case 3:
			ht[j].rchild=in;
		    break;
		}
		i++;
	}
	fip1.close();    //关闭文件hfmTree
		
		
    int j=2*leafnum-1-1;      //初始化整形变量j，使j指向哈弗曼树的跟节点
	int len=13;
    
	ofstream op;
	op.open("TreePrint.txt",ios::out|ios::binary|ios::trunc);
	op.close();

	cout<<"\n该哈夫曼树的凹入表示图为:\n";
	Printline(ht,yezi,j,len);     //调用递归函数
		
}


////////////////////////////////////////////////////////////////////////////////////////////
//印哈弗树的递归函数
//函数功能：利用递归算法已凹型表示输出哈弗曼树
//函数参数：
//    ht[]:将存储哈弗曼树节点的数组传给函数，
//    yezi[]：将存储初始化字符的数组传给函数，
//    j:表示节点在数组中的位置；
//    len：表示输出横杆的长度
//函数返回值：无

void HaffmanTree::Printline(HaffNode ht[],char yezi[],int j,int len)
{
	ofstream fop;
	fop.open("TreePrint.txt",ios::out|ios::binary|ios::app);    //打开文件，用于存入哈弗曼树
	fop<<endl;
	cout<<endl;
	for(int i=0;i<len;i++)        //输出哈弗曼树各节点对应长度的横杆，并写到文件TreePrint.txt
	{   
		fop<<"--";
		cout<<"--";
	}
    fop<<ht[j].weight<<" ";         //向文件写入节点各权值
	cout<<ht[j].weight<<" ";        //向终端输出节点权值
    if(j<leafnum)
	{
		fop<<"  "<<yezi[j];        //当节点是叶子节点时，向文件写入对应的字符
		cout<<"  "<<yezi[j];       //当节点是叶子节点时，向终端输出对应的字符
	}
    fop.close();    //关闭文件
	if(ht[j].lchild!=-1)      //当有左孩子时，调用递归，输出左子树
		Printline(ht,yezi,ht[j].lchild,len-1);
	if(ht[j].rchild!=-1)      //当有右孩子时，调用递归，输出右子树
		Printline(ht,yezi,ht[j].rchild,len-1); 
	
}