huffman.cpp

本程序是数据结构的一个作业题目

//用于对字符的Huffman编码
//首先输入要编码的字符个数例：6个，和要编码的字符例：a,b,c,d,e,f
//被编码的字符串保存在文件"in"中
//HUFFMAN编码保存在文件"out_1"中, 译码保存在文件"out_2"中
#include<iostream.h>
#include<fstream.h>
typedef char ElemType;
#define MAXSIZE 100//H树中的最大叶子结点数
struct HTNode
{
	ElemType v;//表示结点
	int weight;//结点的权重
	int parent,lchild,rchild;//结点的双亲、左右儿子
};
class Huffman
{
private:
	HTNode HTN[2*MAXSIZE-1];//表示结点HUFFMAN树结点个数
	int sum;//结点个数
public:
	Huffman();//构造函数
	void FWrite();//把输入的字符串保存在文件中
	void HTNodeWeight();//求一个结点的权值
	void InitHT();//初始化一棵树
	void CreateHT();//构造HUFFMAN树
	void HTCoding();//对文件编码
	void HTUnCoding();//对文件译码
	void Selectmins(int n,int &s1,int &s2);//找树中0……n-1中的最小的两个结点返回值放s1,s2中
};
Huffman::Huffman()
{
	sum=0;
}
void Huffman::InitHT()
{
	int i;
	cout<<"请输入叶子结点个数"<<endl;
	cin>>sum;
	cout<<"请依次输入叶子结点的名称"<<endl;
	for(i=0;i<sum;i++)
	{
		cin>>HTN[i].v;
		HTN[i].weight=0;
		HTN[i].parent=0;
		HTN[i].lchild=HTN[i].rchild=0;
	}
}
void Huffman::FWrite()
{
	char ch;
	ofstream fout;
	fout.open("in",ios::trunc);//打开文件的同时删除同名文件
	if(!fout)
	{
		cout<<"When writing coding,cannot open file"<<endl;
	}
	cout<<"请依次输入被编码的字符串以'＠'结束(同时保存在文件'in'中)"<<endl;
	cin>>ch;
	while(ch!='@')
	{
		fout<<ch;
		cin>>ch;
	}
	fout.close();
}
void Huffman::HTNodeWeight()
{
	char ch;//保存返回字符
	int i;
	ifstream fin;
	fin.open("in");
	if(!fin)
	{
		cout<<"When reading,cannot open file"<<endl;
	}
	while(fin)//文件in结束时返回值为-1
	{
		fin.get(ch);//从第i个位置读一个字符用ch保存
		for(i=0;i<sum;i++)
		{
			if(HTN[i].v==ch)
				HTN[i].weight++;
		}
	}
	fin.close();
	cout<<"叶子结点的权重分别为:"<<endl;
	for(i=0;i<sum;i++)
		cout<<HTN[i].weight<<" ";
	cout<<endl;
}
void Huffman::CreateHT()
{
	int s1,s2;//保存返回值
	int i,m;//H树中结点个数
	m=2*sum-1;
	for(i=sum;i<m;i++)
	{
		HTN[i].v='@';
		HTN[i].weight=0;
		HTN[i].parent=0;
		HTN[i].lchild=HTN[i].rchild=0;
	}
	for(i=sum;i<m;i++)
	{
		Selectmins(i,s1,s2);
		HTN[s1].parent=i;
		HTN[s2].parent=i;
		HTN[i].lchild=s1;
		HTN[i].rchild=s2;
		HTN[i].weight=HTN[s1].weight+HTN[s2].weight;
	}
}
void Huffman::HTCoding()//从叶子到根逆向求每个字符的赫夫曼编码
{
	int i,j,c,f,start;
	char cd[MAXSIZE][MAXSIZE+1];
	//存编码cd[i]中HTN[i].v的编码
	//cd[i][0]中存放HTN[i].v
	for(i=0;i<sum;i++)
	{
		start=MAXSIZE;//编码结束位置
		cd[i][0]=HTN[i].v;
		for(c=i,f=HTN[i].parent;f!=0;c=f,f=HTN[c].parent)//从叶子到根逆向求编码
		{
			if(HTN[f].lchild==c)
				{cd[i][start]='0';start--;}
			else
				{cd[i][start]='1';start--;}
		}
	}//编码完毕
	for(i=0;i<sum;i++)//输出叶子结点字符对应的编码
	{
		cout<<cd[i][0]<<": ";
		for(j=1;j<=MAXSIZE;j++)
			if(cd[i][j]=='1'||cd[i][j]=='0')
				cout<<cd[i][j];
		cout<<endl;
	}
	ofstream fout;
	ifstream fin;
	char ch;
	fout.open("out_1",ios::trunc);//打开文件的同时删除同名文件
	if(!fout)
	{
		cout<<"When writing coding,cannot open file"<<endl;
	}
	fin.open("in");
	if(!fin)
	{
		cout<<"When reading,cannot open file"<<endl;
	}
	cout<<"输入的字符串编码为:(同时保存在文件'out_1'中)"<<endl;
	while(fin)//文件in结束时返回值为-1
	{
		fin.get(ch);//从第i个位置读一个字符用ch保存		
		for(i=0;i<sum;i++)
			if(HTN[i].v==ch)
				for(j=1;j<=MAXSIZE;j++)
					if(cd[i][j]=='1'||cd[i][j]=='0')
					{
						fout.put(cd[i][j]);	
						cout<<cd[i][j];
					}
	}
	fin.close();
	fout.close();
	cout<<endl;
}
void Huffman::HTUnCoding()
{
	HTNode HN;//  用于保存H树结点
	ofstream fout;
	ifstream fin;
	char ch;
	fout.open("out_2",ios::trunc);//打开文件的同时删除同名文件
	if(!fout)
	{
		cout<<"When writing coding,cannot open file"<<endl;
	}
	fin.open("out_1");
	if(!fin)
	{
		cout<<"When reading the file 'out_1',cannot open file"<<endl;
	}
	cout<<"输入的字符串的编码译后为:(同时保存在文件'out_2'中)"<<endl;
	while(fin)//文件in结束时返回值为-1
	{
lable_1:
		HN=HTN[2*sum-2];//把根结点赋给HN
lable_2:
		fin.get(ch);//从第i个位置读一个字符用ch保存
		if(ch=='0')
		{
			HN=HTN[HN.lchild];
			if(HN.v=='@')
				goto lable_2;
			else
			{
				fout<<HN.v;
				cout<<HN.v;
				goto lable_1;
			}//else
		}//if
		if(ch=='1')
		{
			HN=HTN[HN.rchild];
			if(HN.v=='@')
				goto lable_2;
			else
			{
				fout<<HN.v;
				cout<<HN.v;
				goto lable_1;
			}//else
		}//if
	}//while(fin)
	fin.close();
	fout.close();
}
void Huffman::Selectmins(int n,int &s1,int &s2)
{
	int temp,min1=0,min2=0;
	//表示树的叶子结点中具有最小权值的结点并赋初值0假设HTN[i].weight不为0
	int i;
	for(i=0;i<n;i++)
	{
		if(HTN[i].parent==0&&min1==0)
		{
			min1=HTN[i].weight;
			s1=i;
			break;
		}
	}
	i++;//不加1　则min2=min1
	for(i;i<n;i++)
	{
		if(HTN[i].parent==0&&min2==0)
		{
			min2=HTN[i].weight;
			s2=i;
			break;
		}
	}
	if(min2<min1)//min1<min2这两个为被查找的结点中最小的两个结点
	{
		temp=min1;
		min1=min2;
		min2=temp;
		temp=s1;
		s1=s2;
		s2=temp;
	}
	for(i=0;i<n;i++)
	{
		if(HTN[i].parent==0&&HTN[i].weight<min1)
		{
			min2=min1;
			min1=HTN[i].weight;
			s2=s1;
			s1=i;
		}
		else
			if(HTN[i].parent==0&&HTN[i].weight<min2&&HTN[i].weight>min1)
			{
				min2=HTN[i].weight;
				s2=i;
			}
	}
}
void main()
{
	char flag;//用于选择进行编码的类型
	Huffman HT;
	HT.InitHT();//H树的初始化
	cout<<"你是要对直接输入的字符串编码还是对文件中已经有的字符进行编码?"<<endl;
	cout<<"对已有的文件编码时请键入'1'并且把文件名改为:'in'存入相应的地方"<<endl;
	cout<<"否则请键入'2'"<<endl;
	cin>>flag;
	switch(flag)
	{
	case '1':break;
	case '2':HT.FWrite();break; 
	}
	HT.HTNodeWeight();
	HT.CreateHT();
	HT.HTCoding();
	HT.HTUnCoding();
}