源代码.txt

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

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

#include"hafuman.h"
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//主函数
//参数返回值：无

int main()
{
	HaffmanTree HTree;    //声明哈弗曼树对象
	
	int finish=1,choice;
	            
	while(finish)
	{
		cout<<"\n ******MENU********\n";
		cout<<"\n 1:初始化哈弗曼树\n";
		cout<<"\n 2:对文件进行编码\n";
		cout<<"\n 3:对已编码文件进行译码\n";
		cout<<"\n 4:印代码文件\n";
		cout<<"\n 5:印哈弗曼树\n";
		cout<<"\n 6:exit\n";
		cout<<"\n 请输入你的选择（1~6）： ";
		cin>>choice;
		cout<<endl;
		switch(choice)
		{
		case 1:
	       HTree.Haffman();            //调用初始化函数，生成哈弗曼树      
		   break;
		case 2:
           HTree.Encode();             //调用编码函数，对指定文件进行编码
           break;
		case 3:
	        HTree.Decode();            //调用译码函数，对代码文件进行翻译
		    break;
		case 4:
			HTree.Print();             //调用输出函数，输出代码文件中的代码
	        break;
		case 5:
			HTree.PrintTree();         //调用输出函数，输出哈弗曼树
			break;
		case 6:
			finish=0;                  //结束
			cout<<"欢迎使用! 再见!\n";
			break;
		}
	} 
	return 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//程序名：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;
			    break;
			case 3:
			    ht[j].rchild=in;
			    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);     //打开存储代码的文件