haff.h

利用哈夫曼编码构造的完整的编/译码系统

#include<iostream.h>
#include<deque>
#include<vector>
using namespace std;

class HuffNode
{
public:
	HuffNode():weight(0),parent(-1),lchild(-1),rchild(-1),flag(0){}
	friend class HuffManTree;
private:
	int weight;
	int parent;
	int lchild;
	int rchild;
	int flag;
};//定义哈夫曼树的节点

class HuffManTree
{
public:
	HuffManTree(int huffleaf):leaf(huffleaf)
	{
		huffnode=new HuffNode[2*leaf-1];//树的结点数
		head=-1;//未被初始化时
		huffcode.resize(huffleaf);//调整树枝的大小
	}//构造函数
	~HuffManTree(){delete []huffnode;}//析构函数
	void initialization();//初始化函数
	void Encoding();//编译译码函数
	void Decoding();//译码函数
	void Print();//打印代码文件函数
	void printTree(int,int,FILE*);//打印树函数
	int head;//定义“头”
private:
	HuffNode *huffnode;
	vector<pair<char,char*> >   huffcode;//储存字符和译码
	int leaf;
};//定义哈夫曼树类

void  HuffManTree::initialization()
{
	int maxvalue=32767;

	for(int k=0;k<leaf;k++)
	{
Loop://当输入了相同的编码元素时回到此处重新输入	
		cout<<"第"<<k+1<<"个节点值";
		cin>>huffcode[k].first;//输入结点值

		for(int i=0;i<k-1;i++)
		{	
			if(huffcode[k].first==huffcode[i].first)
			{
				cout<<endl<<"编码元素必须是不同的，请重新输入"<<endl;
				goto Loop;
			}
		}//判断刚输入的结点值是否与已经输入的重复

		cout<<"该节点的权值:";
		cin>>huffnode[k].weight;//输入权值
		cout<<endl;
	}

	for(int i=0;i<leaf-1;i++)
	{
		int value1=maxvalue,value2=maxvalue;
		int x1=0,x2=0;

		for(int h=0;h<leaf+i;h++)
		{
			if(huffnode[h].flag==0 )
			{
				if( huffnode[h].weight<value1)
				{
					value2=value1;
					x2=x1;
					value1=huffnode[h].weight;
					x1=h;
				}
				else if( huffnode[h].weight<value2)
				{  	
					value2=huffnode[h].weight;
					x2=h;
				}
			}
		}

		huffnode[x1].parent=leaf+i; 
		huffnode[x2].parent=leaf+i;
    	huffnode[x1].flag=1;
		huffnode[x2].flag=1;
		huffnode[leaf+i].weight=huffnode[x1].weight+huffnode[x2].weight;
		huffnode[leaf+i].lchild=x1;
		huffnode[leaf+i].rchild=x2;
	}//查找两个最小的结点

	head=2*leaf-2;
	deque<char> coll;

	for(int j=0;j<leaf;j++)
	{
		int k,p;k=j;
		while(huffnode[k].parent!=-1)
		{
			p=huffnode[k].parent;
			if(huffnode[p].lchild==k)
				coll.push_front('0');
				else coll.push_front('1');
				k=p;
		}
		
		int siz;
		siz=coll.size();
		huffcode[j].second=new char[siz+1];
		
		for(int i=0;i<siz;i++)
		{
			char ch=coll.front();
			coll.pop_front();
			huffcode[j].second[i]=ch;
		}
		
		huffcode[j].second[siz]=0;
		coll.clear();
	}
	FILE *fp;
	fp=fopen("huftree.txt","w");//把译码保存到文件里
	
	for(int y=0;y<leaf;y++)
	{
		fputc(huffcode[y].first,fp);
		fputs(huffcode[y].second,fp);
	}

	fclose(fp);
}//初始化函数

void HuffManTree::Encoding()//It has already been there!
{
	FILE *fp,*fpobj;

	fp=fopen("ToBeTran.txt","r");
	fpobj=fopen("CodeFile.txt","w");
	int ch=fgetc(fp);

	while(!feof(fp))
	{
		for(int i=0;i<leaf;i++)
		{
			if(ch==huffcode[i].first)
			{
				fputs(huffcode[i].second,fpobj);
				break;
			}
		}
		ch=fgetc(fp);
	}
	fclose(fp);
	fclose(fpobj);
}//编译译码

void HuffManTree::Decoding()	 
{
	FILE *fp,*fpobj;
	fp=fopen("CodeFile.txt","r");//打开文件
	fpobj=fopen("TextFile.txt","w");//打开文件

	char ch=fgetc(fp);
	int present=head;

	while(!feof(fp))
	{
		if(ch=='0')
			present=huffnode[present].lchild;
		else
			present=huffnode[present].rchild;

		if(huffnode[present].lchild==-1&&huffnode[present].rchild==-1)
		{
			fputc(huffcode[present].first,fpobj);
			present=head;
		}

		ch=fgetc(fp);
	}

	fclose(fp);
	fclose(fpobj);
}//译码

void HuffManTree::Print()
{
	FILE *fp,*fpobj;
	int k=1;
	char ch;

	fp=fopen("CodeFile.txt","r");
	fpobj=fopen("CodePrin.txt","w");
	ch=fgetc(fp);

	while(ch!=EOF)
	{
		if(k%50==0)
		{
			cout<<endl;
			fprintf(fpobj,"\n");
		}
		cout<<ch;
		fputc(ch,fpobj);
		ch=fgetc(fp);
		k++;
	}

	fclose(fp);
	fclose(fpobj);
}//打印文件代码

void HuffManTree::printTree(int bt,int levl,FILE *fp)
{
	if(bt==-1)return;//当不存在时

	printTree(huffnode[bt].rchild,levl+1,fp);

	for(int i=0;i<levl;++i)
	{
		cout<<"   ";
		fprintf(fp,"  ");
	}
	if(levl>=1)
	{	
		cout<<"--";
		fprintf(fp,"--");
	}

	cout<<"("<<huffnode[bt].weight<<")";
	fprintf(fp,"(%d)",huffnode[bt].weight);

	if(huffnode[bt].lchild==-1)
	{  	
		cout<<huffcode[bt].first;
		cout<<':'<<huffcode[bt].second<<endl;
		fprintf(fp,"%c:%s\n",huffcode[bt].first,huffcode[bt].second);
	}
	else
	{	
		cout<<endl;
		fprintf(fp,"\n");
	}
	printTree(huffnode[bt].lchild,levl+1,fp);
}//打印哈夫曼树