huffman.cpp

这些程序是本人学习数据结构时编的

// Huffman.cpp: implementation of the Huffman class.
//
//////////////////////////////////////////////////////////////////////

#include "Huffman.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Huffman::Huffman()
{
	for (int i= 0 ;i<256;i++)
	{
		code[i].key =0;
		code[i].data = i;
	}
}

Huffman::~Huffman()
{
}

void Huffman::Add_Frequency(int n)
{
	code[n].key++;
	return;
};

//构造huffman树 
void Huffman::Creat_Huffman_Tree()
{
	int i=0,j;
	Code_plans=0;

	//频率不为空的编码
	for (;i<256;i++)
		if (code[i].key)
			Code_plans++;


//存放生成的的编码方案
	code_plan = new CodePlan[Code_plans];
//去掉频率为空的编码
	Compress_Code = new Code[Code_plans];
	for (i=0,j=0;i<256;i++)
		if (code[i].key)
		{
			Compress_Code[j].data = code[i].data ;
			Compress_Code[j].key = code[i].key;
			j++;
		};
//生成huffman树
	if (Code_plans == 1)
	{
		cerr<<"文件只包含一种字符，无法创建huffman树!"<<endl;
		exit(1);
	};
	tree.HuffmanTree(hp,Compress_Code,Code_plans,tree);

	return;
}

//接受字符串
void Huffman::Input_TargetString()
{	
	int i = 0;
	char ch;
	target.erase();
	cin>>ch;
	while (ch != 10)
	{
		target += ch;
		Add_Frequency((int)ch);
		cin.get(ch);
	};
	return;
};

//生成huffman编码方案
void Huffman::Make_Code()
{	
	string str;
	if (!tree.root)
		return;
	current_plan = 0;
	if (tree.root->leftChild)
	{
		str+= '0';
		make_code(tree.root->leftChild,str);
	}
	if (tree.root->rightChild)
	{
		str.erase ();
		str+= '1';
		make_code(tree.root->rightChild,str);
	}
	return;
};

void Huffman::make_code(Element<Code> *current,string str)
{
	string temp;
	temp = str;
	if (!current->leftChild)
	{
		code_plan[current_plan].data = current->data.data;
		code_plan[current_plan].code_plan = str;
		current_plan++;
		return;
	}
	str += '0';
	make_code(current->leftChild,str);

	temp += '1';
	make_code(current->rightChild,temp);

	return;
}

//输入01代码翻译成字符串
void Huffman::Decode()
{
	char ch;
	ch = cin.get();
	Element<Code> * current = tree.root;
	while (ch!=	10)
	{
		if ( ch == '0')
		{
			current = current ->leftChild;
			if (!current->leftChild)
			{
				cout<<current->data.data;
				current= tree.root;
			}
		}else if (ch == '1')
		{
			current = current ->rightChild;
			if (!current->rightChild)
			{
				cout<<current->data.data ;
				current= tree.root;
			}
		}else{
			cerr<<"非法字符 "<<ch<<endl;
			exit(1);
		};
		ch = cin.get ();
	}
	cout<<endl;
	return;
}

//输出编码方案
void Huffman::Output_Code_Plan()
{
	current_plan = 0;
	while (current_plan < Code_plans)
	{
		cout<<code_plan[current_plan].data<<':'<<code_plan[current_plan].code_plan<<endl;
		current_plan++;
	};
	return;
}


//压缩文件
void Huffman::CompressFile()
{
	ifstream filein;
	long i =0,length1,length2,codeslength = 0,templength;
	int j,lastcodelength,tl,ratio,preratio = 0;
	char ch;
	CodePlan temp;
	ofstream fileout;
	string str,infile,outfile;

//输入文件名
	cout<<"请输入要压缩文件名及路径（默认路径为当前路径）: ";
	cin>>infile;
	filein.open (infile.c_str(),ios::binary ) ;
	if (!filein)
	{
		cout<<"找不到文件"<<infile<<endl;
		exit(1);
	};

	cout<<"请输入压缩后文件名: ";
	cin>>outfile;
	while (outfile == infile)
	{
		cout<<"输出文件名与输入文件名相同，请再输入:";
		cin>>outfile;
	};
	fileout.open(outfile.c_str(),ios::binary | ios::trunc);
	if (!fileout)
	{
		cout<<"找不到文件"<<filein<<endl;
		exit(1);
	};

//统计文件长度和各字符出现频率
	length1 = 0;
	filein.get (ch);
	while (!filein.eof() )
	{
		Add_Frequency(((int)ch + 512) %256);
		filein.get(ch);
		length1++;
	};
	
//构造huffman树
	Creat_Huffman_Tree();
//生成huffman编码方案
	Make_Code();

	
//debug
/*	for (i=0;i<Code_plans;i++)
		fileout<<Compress_Code[i].key<<"   ";
	fileout<<endl;
*/
//计算最后一位字符长度
	lastcodelength = 0;
	for(i= 0;i<Code_plans; i++)
	{
		lastcodelength += ((code_plan[i].code_plan.length() % 8 )* (code[((int)(code_plan[i].data) + 512)%256].key %8 ));
		lastcodelength = lastcodelength % 8;
	};
	lastcodelength = lastcodelength % 8;

//写入编码最后字节的位数
	fileout<< lastcodelength; 
//输入字符‘#’阻隔两数 
	fileout.put('#');

//屏幕信息：
	cout<<"原文件大小: "<<length1 / 1048576.0<<" Mb"<<endl;
	cout<<"压缩比率为:(%)\n"<<'0';	

//把压缩信息放进压缩文件中
	current_plan = 0; length2 = 0;
	fileout<<Code_plans;
	while (current_plan < Code_plans)
	{
		if (Compress_Code[current_plan].data > 47 && Compress_Code[current_plan].data < 58)
		{
			fileout.put('#');
			fileout.put(Compress_Code[current_plan].data);
			fileout.put('#');
			fileout<<Compress_Code[current_plan].key;
			length2 += 4;
		}else{
			fileout.put(Compress_Code[current_plan].data);
			fileout<<Compress_Code[current_plan].key;
			length2 += 2;
		};
		//输出压缩比率
		ratio = length2 * 100 /length1;
		if (ratio != preratio)
			cout<<'\b'<<'\b'<<ratio;
		preratio = ratio;
		current_plan++;
	};
	fileout.put('#');

//重新打开文件，让文件指针指回文件开头
	filein.close ();
	filein.open(infile.c_str(),ios::binary ) ;
	filein.clear();


//生成huffman编码串
	str.erase();
	filein.get(ch);
	while (!filein.eof() )
	{
		temp = Find_Code_Plan(ch);
		str += temp.code_plan;
		if (str.length() >=8 )
		{
			//huffman 编码每八位处理
			i =0; 
			templength  = str.length(); 
			tl = templength %8;
			templength -= tl;
			while (i<templength)
			{	
				i += 8;
				j=0;
				ch = 0;
				if (str[i - j -1] == '1')
					ch = ch | 0x01;
				j++;
				if (str[i - j -1] == '1')
					ch = ch | 0x02;
				j++;
				if (str[i - j -1] == '1')
					ch = ch | 0x04;
				j++;
				if (str[i - j -1] == '1')
					ch = ch | 0x08;
				j++;
				if (str[i - j -1] == '1')
					ch = ch | 0x10;
				j++;
				if (str[i - j -1] == '1')
					ch = ch | 0x20;
					j++;
				if (str[i - j -1] == '1')
					ch = ch | 0x40;
				j++;	
				if (str[i - j -1] == '1')
					ch = ch | 0x80;
				fileout.put(ch);
				length2++;
			}
			//取剩下的字符
			str = str.substr(templength,tl);
		}
		//输出压缩比率
		ratio = length2 * 100 /length1;
		if (ratio != preratio)
			cout<<'\b'<<'\b'<<ratio;
		preratio = ratio;
		filein.get(ch);
	}	

	if(lastcodelength)
	{
		for (ch = 0, j = 0;j<lastcodelength;j++)
		{
			if (str[lastcodelength - j -1] == '1')
				ch = ch | (int)pow(2,j);
		}
		fileout.put(ch);
		length2 ++;
		ratio = length2 * 100 /length1;
		if (ratio != preratio)
		{
			cout<<'\b'<<'\b'<<ratio;
		}
		preratio = ratio;
	}
	
	cout<<"\n压缩后文件大小："<<length2 / 1048576.0 <<" Mb"<<endl;
	filein.close();
	fileout.close();
	return;
}

//输出编码及其长度 
void Huffman::Output_Codes()
{
	int i =0,length;
	length = target.length();
	int codeslength = 0;
	cout<<"报文：";
	CodePlan temp;
	while (i<length)
	{
		temp = Find_Code_Plan(target[i]);
		codeslength += temp.code_plan.length();
		cout<<temp.code_plan;
		i++;
	};
	cout<<"\n长度："<<codeslength<<endl;
}

//查找字符ch 向应的编码方案
CodePlan& Huffman::Find_Code_Plan(char ch)
{
	current_plan = 0;
	while (current_plan < Code_plans)
	{
		if (code_plan[current_plan].data == ch)
			return code_plan[current_plan];
		current_plan++;
	};
}

//解压文件
void Huffman::DecompressFile()
{

	ifstream filein;
	char data,temp;
	int i,lastcodelength;
	long p;
	string str,infile,outfile;
	ofstream fileout;
	Element<Code> *current;

//输入文件名
	cout<<"请输入要解压缩文件名: ";
	cin>>infile;
	filein.open (infile.c_str(),ios::binary ) ;
	if (!filein)
	{
		cout<<"找不到文件"<<infile<<endl;
		exit(1);
	};

	cout<<"请输入解压缩后文件名: ";
	cin>>outfile;
	while (outfile == infile)
	{
		cout<<"输出文件名与输入文件名相同，请再输入:";
		cin>>outfile;
	};
	fileout.open(outfile.c_str(),ios::binary | ios::trunc);
	if (!fileout)
	{
		cout<<"找不到文件"<<filein<<endl;
		exit(1);
	};


//读入最后字节位数
	filein>>lastcodelength;
	filein.get (data);
//读入未知编码数
	filein>>Code_plans;
	Compress_Code = new Code[Code_plans];
	code_plan = new CodePlan[Code_plans];

//读入编码信息: 未知码和相应的key值
	for(i = 0;i < Code_plans;i++)
	{
		filein.get (data);
		if (data == '#')
		{
			filein.get (data);
			filein.get (temp);
			if (temp == '#')
			{
				Compress_Code[i].data = data;
				filein>>Compress_Code[i].key;
			}else{
				filein.putback (temp);
				filein.putback (data);
				Compress_Code[i].data = '#';
				filein>>Compress_Code[i].key;
			}
		}else{
			Compress_Code[i].data = data;
			filein>>Compress_Code[i].key;	
		}
	}
	filein.get (temp);

//构造huffman树
	tree.HuffmanTree(hp,Compress_Code,Code_plans,tree);
	Make_Code();


//debug
/*	for (i=0;i<Code_plans;i++)
		fileout<<code_plan[i].code_plan<<' '<<((int)code_plan[i].data+512)%256<<"   ";
	fileout<<endl;
*/
//读入压缩文件，解码	
	current = tree.root;
	filein.get (data);	
	str = format(data);
	filein.get (data);	
	while(! filein.eof ())	
	{
		p = 0;
		while (p< 8)
		{
			if ( str[p] == '0')
				current = current->leftChild;
			else if (str[p] == '1')
				current = current->rightChild;
			if (!current->leftChild)
			{
				fileout.put (current->data.data);
				current = tree.root;
			}	
			p++;
		}
		str = format(data);
		filein.get(data);
	}

//最后一字节处理
	lastcodelength = lastcodelength == 0 ? 8 :  lastcodelength;
	p= 8 - lastcodelength;
	while (p< 8)
	{
		if ( str[p] == '0')
			current = current->leftChild;
		else if (str[p] == '1')
			current = current->rightChild;
		if (!current->leftChild)
		{
			fileout.put (current->data.data);
			current = tree.root;
		}	
		p++;
	}
	
	filein.close();
	fileout.close ();
	return;
}

//把一字节转变为八位01字符串
string Huffman::format(char ch)
{
	unsigned char temp;
	string str="00000000";
	temp = ch | 0xfe;
	str[7] = (temp == 0xff ? '1' : '0');
	temp = ch | 0xfd;
	str[6] = (temp == 0xff ? '1' : '0');
	temp = ch | 0xfb;
	str[5] = (temp == 0xff ? '1' : '0');
	temp = ch | 0xf7;
	str[4] = (temp == 0xff ? '1' : '0');
	temp = ch | 0xef;
	str[3] = (temp == 0xff ? '1' : '0');
	temp = ch | 0xdf;
	str[2] = (temp == 0xff ? '1' : '0');
	temp = ch | 0xbf;
	str[1] = (temp == 0xff ? '1' : '0');
	temp = ch | 0x7f;
	str[0] = (temp == 0xff ? '1' : '0');
	
	return str;
}

//演示程序
void Huffman::Demo()
{
	cout<<"这是一个演示huffman编码码的程序:"<<endl;
	cout<<"请输入报文: ";
	Input_TargetString();
	Creat_Huffman_Tree();
	Make_Code();
	cout<<"huffman编码方案:"<<endl;
	Output_Code_Plan();
	cout<<"huffman编码: "<<endl;
	Output_Codes();
	cout<<"请输入要翻译的01代码:";
	Decode();
	cout<<"演示结束。"<<endl;
	return;
}