immenu.h

哈夫曼算法的应用

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

//************************************
//哈夫曼改进树编码主菜单显示函数
//************************************
void ImDisplayMenu()
{
	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  ImEnCode()
{
	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记录不同字符的个数

	//申请哈夫曼改进树空间
	ImHaffNode *ImmyHaffTree=new ImHaffNode[2*n-1];

	//申请哈夫曼改进树编码空间
	ImCode *ImmyHaffCode=new ImCode[n];

    //构造哈夫曼改进树
	ImHaffmanTree(character,weight,n,ImmyHaffTree);   

	//将建好的哈夫曼改进树存储到二进制文件中，以便解码用
	if((n-1)%2!=0)//如果节点个数不是奇数，则增加一个节点,其权值为零
		n+=1;
    int Count=3*((n-1)/2)+1;   //count记录哈夫曼改进树中节点的个数

	ofstream file;
	file.open("ImHaffTree.dat",ios::binary);

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

	file.clear();

	for(i=0;i<Count;i++)
	{
		file.write((char*)&ImmyHaffTree[i],sizeof(ImHaffNode));
	}

	file.close();

	//将建好的哈夫曼树存储到文本文件中，以便核对哈夫曼树正确与否
	ofstream File;
	File.open("ImHaffTree.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)<<"middleChild";
	File<<setw(13)<<"rightChild";
	File<<setw(13)<<"flag";

	File<<endl;
	
	for(i=0;i<Count;i++)
	{
		File<<setiosflags(ios::left);
		File<<setw(13)<<ImmyHaffTree[i].Position;
		File<<setw(13)<<ImmyHaffTree[i].Character;
		File<<setw(13)<<ImmyHaffTree[i].Weight;
		File<<setw(13)<<ImmyHaffTree[i].Parent;
		File<<setw(13)<<ImmyHaffTree[i].LeftChild;
		File<<setw(13)<<ImmyHaffTree[i].MiddleChild;
		File<<setw(13)<<ImmyHaffTree[i].RightChild;
		File<<setw(13)<<ImmyHaffTree[i].Flag;

		File<<endl;
	}

	File.close();

	//对哈夫曼改进树进行编码
    ImHaffmanCode(ImmyHaffTree,n,ImmyHaffCode);   

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

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

	outFile.clear();

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

		outFile<<"Weight="<<setw(8)<<ImmyHaffCode[i].Weight;
		
		outFile<<"Code=";
		for(j=ImmyHaffCode[i].Start+1;j<n;j++)
		{
			outFile<<ImmyHaffCode[i].Bit[j];
		}

		outFile<<endl;
	}

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

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

	outFile1.clear();

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

	outFile1.close();

	delete ImmyHaffTree;   //释放哈夫曼树空间
	delete ImmyHaffCode;   //释放哈夫曼编码空间

	system("cls");

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

	system("cls");
}

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

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

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

	file.clear();

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

	file.close();

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

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

	inFile.clear();

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

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

	outFile.clear();

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

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

		else
		{
			break;
		}
	}

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

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

		if(ch=='2')
		{
			j=ImmyHaffTree[j].RightChild;
		}

		if(ch=='1')
		{
			j=ImmyHaffTree[j].MiddleChild;
		}

	    if(ch=='0')
		{
			j=ImmyHaffTree[j].LeftChild;
		}

        if(ImmyHaffTree[j].LeftChild==-1&&ImmyHaffTree[j].RightChild==-1&&ImmyHaffTree[j].MiddleChild==-1)   //找到叶子节点了，就把叶子节点的字符写到文件中
		{
		   outFile.put(ImmyHaffTree[j].Character);
		   j=n-1; 
		}
	}

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

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

	system("pause");

	system("cls");
}