huffman.cpp

实现huffman算法的编码与解码

#include<iostream>
#include<fstream>
#include<string.h>
#include<stdlib.h>
using namespace std;

struct HuffmanNode        //定义Huffman树各节点
{
	int weight;        
	int parent;        
	int lchild,rchild;   
};

class HuffmanTree     //建立哈夫曼树类
{
	private:
		HuffmanNode *Node;      //哈夫曼树中结点的存储结构
		char *Info;           //用来保存各字符信息
		int LeafNum;          //树中的叶子结点总数
	public:
		HuffmanTree();     
		~HuffmanTree();    
		void Initialization(int WeightNum);   //初始化函数
		void Encoder();           //编码函数
		void Decoder();          //译码函数
		    
};



//构造和析构函数

HuffmanTree::HuffmanTree()
{
	Node=NULL;           
	Info=NULL;          
	LeafNum=0;          
}
HuffmanTree::~HuffmanTree()
{
	delete[] Node;         
	delete[] Info;         
}
 
void HuffmanTree::Initialization(int WeightNum)        //初始化函数的实现
{
	int i,j,pos1,pos2,max1,max2;
    Node=new HuffmanNode[2*WeightNum-1];  
    Info=new char[WeightNum];
	for(i=0;i<WeightNum;i++)
	{
		cout<<"请输入第"<<i+1<<"个字符:";
		getchar();           
		Info[i]=getchar();   
		getchar();
		cout<<"请输入该字符的权值:";
		cin>>Node[i].weight;       
		Node[i].parent=-1;      
		Node[i].lchild=-1;      
		Node[i].rchild=-1;      
	}
  	for(i=WeightNum;i<2*WeightNum-1;i++) 
	{
		pos1=-1;
		pos2=-1;           
		max1=32767;       
		max2=32767;        
 		for(j=0;j<i;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;
	} 
	LeafNum=WeightNum;
  	ofstream fop;
	fop.open("huffman.dat",ios::out|ios::binary|ios::trunc);
	if(fop.fail())
	cout<<"文件打开失败！\n";
	fop.write((char*)&WeightNum,sizeof(WeightNum));
	for(i=0;i<WeightNum;i++)       
	{
		fop.write((char*)&Info[i],sizeof(Info[i]));
		flush(cout);
	}
	for(i=0;i<2*WeightNum-1;i++)
	{
		fop.write((char*)&Node[i],sizeof(Node[i]));
		flush(cout);
	}
	fop.close();
	cout<<"构造完成!\n\n";
}

void HuffmanTree::Encoder()
{
	if(Node==NULL)       
	{
		ifstream fip;        
		fip.open("huffman.dat",ios::binary|ios::in);
		if(fip.fail())       
		{
			cout<<"打开文件失败！\n";
			return;          
		}
		fip.read((char*)&LeafNum,sizeof(LeafNum));  
		Info=new char[LeafNum]; 
		Node=new HuffmanNode[2*LeafNum-1];
		for(int i=0;i<LeafNum;i++)              
		fip.read((char*)&Info[i],sizeof(Info[i]));
		for(i=0;i<2*LeafNum-1;i++)              
		fip.read((char*)&Node[i],sizeof(Node[i]));
	}
 
	char *Tree;          
	int i=0;
 
	ifstream fip1("hufstr.txt");
	if(fip1.fail())      
	{
		cout<<"打开文件失败!\n";
		return;         
	}
	char ch;
	int k=0;
	while(fip1.get(ch))            
	{
		k++;                    
	} 
	fip1.close();  
 
	Tree=new char[k+1];
	ifstream fip2("hufstr.txt");

	k=0; 
	while(fip2.get(ch))
	{
		Tree[k]=ch;           
		k++;
	}
	fip2.close();
	Tree[k]='\0';          
	cout<<"文件中的内容为:";
	cout<<Tree<<endl;
 
 
	ofstream fop("hufoutstr.txt",ios::trunc);      
	i=0;
	k=0;
	char *code;
	code=new char[LeafNum];        
                               
	while(Tree[k]!='\0')              
	{
		int j,start=0;
		for(i=0;i<LeafNum;i++)
			if(Info[i]==Tree[k])            
		break; 
		j=i;
		while(Node[j].parent!=-1)        
		{
			j=Node[j].parent;             
			if(Node[j].lchild==i)           
			code[start++]='0';
			else                       
			code[start++]='1';\
			i=j;
		}
		code[start]='\0';             

  
		for(i=0;i<start/2;i++)           
		{
			j=code[i];
			code[i]=code[start-i-1];
			code[start-i-1]=j;
		}
        i=0;
		while(code[i]!='\0')        
		{
			fop<<code[i];
			i++;
		}
		k++;
		}
		fop.close();
		cout<<"编码完成！且存到文件hufoutstr.txt中！\n\n";
}


void HuffmanTree::Decoder()
{
	int i=0,k=0;
	int j=LeafNum*2-1-1;      
	char* BitStr;
 
	ifstream fip1("hufoutstr.txt");          
	if(fip1.fail())         
	{
		cout<<"请先编码！\n";
		return;
	}
	cout<<"经解码后，文件中的内容为:";
	char ch;
	while(fip1.get(ch))            
	{
		k++;                     
	}
	fip1.close();  
 	BitStr=new char[k+1];
	ifstream fip2("hufoutstr.txt");
	k=0;
	while(fip2.get(ch))
	{
		BitStr[k]=ch;          
		k++;
	}
	fip2.close();                
	BitStr[k]='\0';         
	if(Node==NULL)         
	{
		cout<<"请先编码!\n";
		return;
	}
	ofstream fop("huffout.dat");         
	while(BitStr[i]!='\0')
	{
		if(BitStr[i]=='0')
			j=Node[j].lchild;          
		else
			j=Node[j].rchild;         
		if(Node[j].rchild==-1)   
		{
			cout<<Info[j];      
			j=LeafNum*2-1-1;          
			fop<<Info[j];               
		}
		i++;
	}
	fop.close();
 	cout<<"\n译码成功且已存到文件huffout.dat中！\n\n";
}




//main函数
int main()
{
	cout<<"a: 初始化Huffman树;\n";
	cout<<"b: 对文件中的字符串进行编码;\n";
	cout<<"c: 对文件中的字符串进行译码;\n";
	cout<<"d: 退出\n\n";
	HuffmanTree huftree;         //定义哈夫曼树对象
	int weight;
	char Choose;
	while(1)
	{
		cout<<"选择要执行的操作:";
		cin>>Choose;
		switch(Choose)
		{
			case 'a':
			cout<<"请输入编码长度：";
			cin>>weight;
			huftree.Initialization(weight);      //初始化哈夫曼树
			break;
	
			case 'b':
			huftree.Encoder();
			break;
			
			case 'c':
			huftree.Decoder();
			break;
									
			case 'd':
			return 0;
		}
		cout<<"a: 初始化Huffman树;\n";
		cout<<"b: 对文件中的字符串进行编码;\n";
		cout<<"c: 对文件中的字符串进行译码;\n";
		cout<<"d:退出\n\n";
	}
}