源代码.txt

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

	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); 
	
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//程序名：hafuman.h
//程序功能：哈弗曼树类的头文件
//作者：黄秋旋
//2008.12.4
//版本：1.0

#include<iostream>
#include<fstream>
using namespace std;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct HaffNode                            //定义哈夫曼树节点结构
{
	int weight;
	int lchild;
	int rchild;
	int parent;
};


class HaffmanTree             //定义哈弗曼树的类
{
private:
	HaffNode *ht;      //哈弗曼树的节点指针
	int leafnum;       //叶子个数
	char *yezi;        //初始化字符指针
	

public:
	HaffmanTree(){leafnum=0; ht=NULL; yezi=NULL;};      //构造函数
	~HaffmanTree(){};       //析构函数
    int Haffman();    //初始化函数
    void Encode();    //编码函数
    void Decode() ;   //译码函数
	void Print();     //印代码文件函数
    void PrintTree();    //印哈弗曼树函数
    void Printline(HaffNode ht[],char yezi[],int j,int len);    //以凹型表示，印哈弗曼树的递归函数
};