huffman.cpp

哈夫曼编码器

#include <fstream>
#include "huffman.h"

huffman::~huffman()
{
	delete[] hft;
}

huffman::huffman()
{
	hft=NULL;
	n=0;
}

bool filenamestd(string &filename)
{
	if(filename.find(".txt")==string::npos)
		filename=filename+".txt";
	return true;
}

bool fileprint(string filename)
{
	int i;
	char ch;
	ifstream infile;
	filenamestd(filename);
	infile.open(filename.c_str());
	system("cls");
	cout<<filename<<endl;
	while(1)
	{
		for(i=0;i<60;i++)
		{
			infile.get(ch);
			if(!infile) break;
			cout<<ch;
		}
		cout<<endl;
		if(!infile) break;
	};
	infile.close();
	ch=getch();
	return true;
}

bool huffman::writehfm(string filename)
{
	int i;
	if(!filenamestd(filename)) return false;
	ofstream outfile;
	outfile.open(filename.c_str());
	outfile<<"这是一个赫夫曼树文件：第一个为字符元素个数，后面为树结构。"<<endl;
	outfile<<n<<endl;
	for(i=1;i<2*n;i++)
		outfile<<hft[i].elem<<' '<<hft[i].weight<<' '<<hft[i].parent<<' '<<hft[i].lchild<<' '<<hft[i].rchild<<endl;
	outfile.close();
	return true;
}

bool huffman::readhfm(string filename)
{
	int i;
	if(!filenamestd(filename)) return false;
	ifstream infile;
	infile.open(filename.c_str());
	infile.ignore(1000,'\n');
	infile>>n;
	infile.ignore(100,'\n');
	hft=new hfnode[2*n];
	for(i=1;i<2*n;i++)
	{
		infile.get(hft[i].elem);
		infile>>hft[i].weight>>hft[i].parent>>hft[i].lchild>>hft[i].rchild;
		infile.ignore(100,'\n');
	}
	infile.close();
	return true;
}

bool huffman::readdate()
{
	int i;
	cout<<"请输入字符种类的个数：";
	cin>>n;
	cin.ignore(100,'\n');
	cout<<"请输入各字符及其权重："<<endl;
	hft=new hfnode[2*n];
	for(i=1;i<=n;i++)
	{
		hft[i].lchild=0;
		hft[i].rchild=0;
		hft[i].parent=0;
		cin.get(hft[i].elem);
		cin>>hft[i].weight;
		cin.ignore(100,'\n');
	}
	for(;i<=2*n-1;i++)
	{
		hft[i].lchild=0;
		hft[i].rchild=0;
		hft[i].parent=0;
		hft[i].elem=-1;
		hft[i].weight=0;
	}
	return true;
}


bool huffman::selectmin(int m,int &lc,int &rc)
{
	int i,wmin;
	for(i=1,wmin=-1;i<=m;i++)
	{
		if(hft[i].parent==0)
		{
			if(wmin==-1)
			{
				wmin=hft[i].weight;
				lc=i;
			}
			else
			{
				if(wmin>hft[i].weight)
				{
					wmin=hft[i].weight;
					lc=i;
				}
			}
		}
	}

	for(i=1,wmin=-1;i<=m;i++)
	{
		if(hft[i].parent==0&&i!=lc)
		{
			if(wmin==-1)
			{
				wmin=hft[i].weight;
				rc=i;
			}
			else
			{
				if(wmin>hft[i].weight)
				{
					wmin=hft[i].weight;
					rc=i;
				}
			}
		}
	}
	return false;
}

bool huffman::creathuffmantree()
{
	string filename;
	int i,lc,rc;
	char bd;
	readdate();
	for(i=n+1;i<=(2*n-1);i++)
	{
		selectmin(i-1,lc,rc);
		hft[lc].parent=i;
		hft[rc].parent=i;
		hft[i].weight=hft[lc].weight+hft[rc].weight;
		hft[i].lchild=lc;
		hft[i].rchild=rc;
	}
	do
	{
		cout<<endl;
		cout<<"是否保存此赫夫曼树？(y/n):";
		bd=getch();
	}while(bd!='y'&&bd!='n');
	cout<<endl;
	if(bd=='y')
	{
		cout<<"请输入文件名：";
		cin>>filename;
		writehfm(filename);
		cout<<"树文件保存成功！"<<endl;
		bd=getch();
	}
	return true;
}

bool huffman::creathuffmantree(string filename)
{
	char bd;
	if(readhfm(filename))
		cout<<"读取树文件成功！"<<endl;
	bd=getch();
	return true;
}

bool huffman::encoding(string filename)
{
	int i,c,f,start;
	char ch,*cd,bd;
	string outfilename;
	filenamestd(filename);
	ifstream infile;
	ofstream outfile;
	infile.open(filename.c_str());
	cout<<"请输入编码输出文件名：";
	cin>>outfilename;
	filenamestd(outfilename);
	outfile.open(outfilename.c_str());
	cd=new char[n];
	cd[n-1]='\0';
	while(1)
	{
		infile.get(ch);
		if(!infile) break;
		for(i=1;ch!=hft[i].elem;i++);
		start=n-1;
		for(c=i,f=hft[i].parent;f!=0;c=f,f=hft[f].parent)
		{
			if(hft[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
		}
		for(;cd[start]!='\0';start++)
			outfile<<cd[start];
	}
	infile.close();
	outfile.close();
	do
	{
		cout<<"是否想打印编码？(y/n):";
		bd=getch();
	}while(bd!='y'&&bd!='n');
	cout<<endl;
	if(bd=='y')
		fileprint(outfilename);
	return true;
}

bool huffman::decoding(string filename)
{
	int p;
	char ch,bd;
	string outfilename;
	filenamestd(filename);
	ifstream infile;
	ofstream outfile;
	infile.open(filename.c_str());
	cout<<"请输入译码输出文件名：";
	cin>>outfilename;
	filenamestd(outfilename);
	outfile.open(outfilename.c_str());
	p=2*n-1;
	while(1)
	{
		if(hft[p].elem==-1)
		{
			infile.get(ch);
			if(!infile) break;
			if(ch=='0')
				p=hft[p].lchild;
			else
				p=hft[p].rchild;
		}
		else
		{
			outfile<<hft[p].elem;
			p=2*n-1;
		}
	}
	infile.close();
	outfile.close();
	do
	{
		cout<<"是否想打印译码？(y/n):";
		bd=getch();
	}while(bd!='y'&&bd!='n');
	cout<<endl;
	if(bd=='y')
		fileprint(outfilename);
	return true;
}