menu.h

哈夫曼算法的应用

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<fstream.h>
#include"Haffman.h"

//************************************
//哈夫曼树编码主菜单显示函数
//************************************
void DisplayMenu()
{
	system("cls");

	cout<<endl<<endl<<endl<<endl<<endl<<endl;

	cout<<"         **********************************************************"<<endl;
	cout<<"                            哈夫曼树编码主菜单"<<endl;
	cout<<"         **********************************************************"<<endl<<endl<<endl;
	cout<<"                                1.编码"<<endl;
	cout<<"                                2.解码"<<endl;
	cout<<"                                3.说明"<<endl;
	cout<<"                                4.返回主菜单"<<endl<<endl<<endl;
	
	cout<<"                            请输入选择（1---4）：";
}

//************************************
//编码函数，对给定的文章进行编码
//************************************
void  EnCode()
{
	system("cls");//清屏

  	cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl; 
	cout<<"                         请输入需要编码的文件名："<<endl<<endl;
	cout<<"                        提示：默认文件名为Text.txt。"<<endl<<endl;
	cout<<"                                ";

	//打开要进行编码的文章
	ifstream inFile;
	char filename[81],ch;
	cin>>filename;
	cin.ignore();

	inFile.open(filename,ios::nocreate);
	if(inFile.fail())
	{
		cout<<"打开文件失败！";
		exit(0);
	}

	inFile.clear();   //清除错误的状态位
    
	//将文件中的字符存储到数组letter[]中
	char letter[10000];   //存储文章中的字符
	int num=0;   //num存储字符的个数

	//读取文件中的字符
	inFile.get(ch);
	while(!inFile.eof())
	{
		letter[num]=ch;
		num++;
		inFile.get(ch);
	}

	inFile.close();
	
	//统计各字符出现的次数
	int count[128];  
	for(int k=0;k<128;k++)
	{
		count[k]=0;
	}

	char L[128];   //存储所有可能出现的128个字符
	for(k=0;k<128;k++)
	{
		L[k]=char(k);
	}

	for(k=0;k<num;k++)
	{
		for(int j=0;j<128;j++)
		{
			if(letter[k]==L[j])
			{
				count[j]++;
				break;
			}
		}
	}
    
	//将出现的字符以及次数分别记下，以便编码
	char character[128];   
	int weight[128];

	k=0;
	for(int j=0;j<128;j++)
	{
		if(count[j]!=0)
		{
			character[k]=L[j];
			weight[k]=count[j];
			k++;
		}
	}

	//编码
	int i;
	int n=k;   //n记录不同字符的个数

	//申请哈夫曼树空间
	HaffNode *myHaffTree=new HaffNode[2*n-1];

	//申请哈夫曼编码空间
	Code *myHaffCode=new Code[n];

    //构造哈夫曼树
	HaffmanTree(character,weight,n,myHaffTree);   

	//将建好的哈夫曼树存储到二进制文件中，以便解码用
	ofstream file;
	file.open("HaffTree.dat",ios::binary);

	if(file.fail())
	{
		cout<<"打开文件失败！";
		exit(0);
	}

	file.clear();

	for(i=0;i<2*n-1;i++)
	{
		file.write((char*)&myHaffTree[i],sizeof(HaffNode));
	}

	file.close();

	//将建好的哈夫曼树存储到文本文件中，以便核对哈夫曼树正确与否
	ofstream File;
	File.open("HaffTree.txt");

	if(File.fail())
	{
		cout<<"打开文件失败！";
		exit(0);
	}

	File.clear();

	File<<setiosflags(ios::left);
	File<<setw(13)<<"position";
	File<<setw(13)<<"character";
	File<<setw(13)<<"weight";
	File<<setw(13)<<"parent";
	File<<setw(13)<<"leftChild";
	File<<setw(13)<<"rightChild";
	File<<setw(13)<<"flag";

	File<<endl;
	
	for(i=0;i<2*n-1;i++)
	{
		File<<setiosflags(ios::left);
		File<<setw(13)<<myHaffTree[i].position;
		File<<setw(13)<<myHaffTree[i].character;
		File<<setw(13)<<myHaffTree[i].weight;
		File<<setw(13)<<myHaffTree[i].parent;
		File<<setw(13)<<myHaffTree[i].leftChild;
		File<<setw(13)<<myHaffTree[i].rightChild;
		File<<setw(13)<<myHaffTree[i].flag;

		File<<endl;
	}

	File.close();

	//对哈夫曼树进行编码
    HaffmanCode(myHaffTree,n,myHaffCode);   

	//存储每个字符的哈夫曼编码，然后存储到文件Code.txt中
	ofstream outFile;
	outFile.open("Code.txt");

	if(outFile.fail())
	{
		cout<<"打开文件失败！";
		exit(0);
	}

	outFile.clear();

	for(i=0;i<n;i++)
	{
		outFile<<setiosflags(ios::left);
		outFile<<myHaffCode[i].character<<"     ";

		outFile<<"Weight="<<setw(8)<<myHaffCode[i].weight;
		
		outFile<<"Code=";
		for(j=myHaffCode[i].start+1;j<n;j++)
		{
			outFile<<myHaffCode[i].bit[j];
		}

		outFile<<endl;
	}

	outFile.close();
	
	//对文章进行编码，编码后的文章存储在文件Text1.txt中
	ofstream outFile1;
	outFile1.open("Text1.txt");

	if(outFile1.fail())
	{
		cout<<"打开文件失败！";
		exit(0);
	}

	outFile1.clear();

	for(i=0;i<num;i++)
	{
		for(j=0;j<n;j++)
		{
			if(letter[i]==myHaffCode[j].character)   //将相应的字符转换为哈夫曼编码
			{
				for(k=myHaffCode[j].start+1;k<n;k++)
				{
					outFile1<<myHaffCode[j].bit[k];
				}
			}
		}
	}

	outFile1.close();

	delete myHaffTree;   //释放哈夫曼树空间
	delete myHaffCode;   //释放哈夫曼编码空间

	system("cls");

	cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;
	cout<<"                                 编码成功！"<<endl<<endl;
	cout<<"    各字符的哈夫曼编码已存入文件Code.txt中,编码后的文章已存入文件Text1.txt中"<<endl<<endl;
	
	system("pause");

	system("cls");
}

//************************************
//解码函数，对给定的文章进行解码
//************************************
void DeCode()
{
	system("cls");//清屏
	
    //读取哈夫曼树结构,以便根据树的结构进行解码
	HaffNode myHaffTree[255];

	ifstream file;
	file.open("HaffTree.dat",ios::binary);

	if(file.fail())
	{
		cout<<"打开文件失败！";
		exit(0);
	}

	file.clear();

	int i=0;
	while(!file.eof())
	{
		file.read((char*)&myHaffTree[i],sizeof(HaffNode));
		i++;
	}

	file.close();

	//打开编过码的文件
	ifstream inFile;
	inFile.open("Text1.txt",ios::nocreate);

	if(inFile.fail())
	{
		cout<<"打开文件失败！";
		cout<<endl;
		cout<<"您可能还未进行编码！";
		cout<<endl;
		exit(0);
	}

	inFile.clear();

	//创建文件Text2.txt，用以保存解码后的文章
	ofstream outFile;
	outFile.open("Text2.txt");

	if(outFile.fail())
	{
		cout<<"打开文件失败！";
		exit(0);
	}

	outFile.clear();

	//统计哈夫曼树中节点的个数，以便定位根节点
	int n=0;

	for(i=0;i<255;i++)
	{
		if(n==myHaffTree[n].position)
		{
			n++;
		}

		else
		{
			break;
		}
	}

	//从根节点出发直到叶子节点进行解码
	int j=n-1;
	char ch;

	while(!inFile.eof())
	{
		inFile.get(ch);

		if(ch=='1')
		{
			j=myHaffTree[j].rightChild;
		}

	    if(ch=='0')
		{
			j=myHaffTree[j].leftChild;
		}

        if(myHaffTree[j].leftChild==-1&&myHaffTree[j].rightChild==-1)   //找到叶子节点了，就把叶子节点的字符写到文件中
		{
		   outFile.put(myHaffTree[j].character);
		   j=n-1; 
		}
	}

	cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;
	cout<<"               解码成功！解码后的文章已存入文件Text2.txt中。"<<endl<<endl;

	inFile.close();
	outFile.close();

	system("pause");

	system("cls");
}