file1.cpp

用Huffman编码进行的加密

#include   <iostream>
#include   <fstream>   
#include   <string>   
 
using   namespace   std;   

const int   n = 97;         //   实际字符数
const int   m = (n*4+1)/3;  //Huffman树的结点树
const int   MaxWeight   =   2007;     //  MaxWeight表示一计算机能表示的最大数，此处2007只是一个较大的数

string s= "zxcvbnm,./asdfghjkl;'qwertyuiop[]\\`1234567890-=ZXCVBNM<>?ASDFGHJKL:\"QWERTYUIOP{}|~!@#$%^&*()_+ \t\n";
													//要编码的常见字符，可以增减

typedef  struct  CodeNode 
{   // 字符结点结构    
	char   ch;                       //   字符  
	int   weight;                   //   权值  
	string   code;                 //   编码     
}  Node;     
    
typedef  struct  HuffmanTreeNode  
{   //   Huffman树结点结构   
	char  ch;                //   字符     
    int  weight;            //   权值     
    char  co;              //   0 ,1 , 2, 3 ,用来生成叶子结点的编码     
    int  parent;          //   双亲结点    
	int  Child_0;        //   第一子女
	int  Child_1;		//   第二子女
	int  Child_2;	   //   第三子女
	int  Child_3;	  //   第四子女
}  TreeNode;     
    

Node  CharNode[n];       //   字符集结点数组     
TreeNode  HfmTree[m];   //   Huffman树数组  
  
int  MinWeight(int  i)   //   返回前i个结点中拥有最小权的结点     
{   
	int   nPos = -1,   nIter;   
    int   nMin = MaxWeight;   
    for   (nIter = 0;  nIter < i;  nIter++)
		if (HfmTree[nIter].parent == -1  &&  HfmTree[nIter].weight < nMin) //若双亲结点为空，且权值更小，则交换
		{ 
			nPos =  nIter;   
            nMin =  HfmTree[nIter].weight;  
        }           
	return   nPos;  //npos若等于 -1，表示huffman树已经构造完毕 
}   
    
void   CreateHT()   //   从源文件统计n个字符和及对应权值，建立哈夫曼树，   
 {                  //   并将它存入文件HfmTree中 
	for (int i = 0;  i < n;  i++)  //   从源文件中统计n个结点信息（字符和权） 
	{   
		ifstream   fIn("D:\\basis3.txt");      //basis*.txt为编码根据
		if ( !fIn )
		{
			cerr<<"File open failed when counting!"<<endl;
			exit(0);
		}
		char  cCurrentChar = s[i];  
		char  next;
		int  nCurrentWeight=0;  
		while(fIn.get(next))        //从文件basis*.txt中统计字符cCurrentChar出现的次数，即权值
		{
			if(next == cCurrentChar)
				nCurrentWeight++;
		}
		//统计完毕，建立单结点树
		CharNode[i].ch = HfmTree[i].ch = cCurrentChar; 
		CharNode[i].weight = HfmTree[i].weight = nCurrentWeight;   
		HfmTree[i].parent = -1;
	}        
	//   建立哈夫曼树
	int  first, second, third, fourth;
	for (i = n;  i < (n*4+1)/3;  i++)  
	{ //   归并拥有最小权的四棵子树为一棵新子树 
		int  count = 0;   //count统计新建树根结点子女的个数
        first = MinWeight(i);   
	    if(first != -1)     //若huffman树还未构造完毕，则将该子树作为子女链入新建树中，以下子女同理
		{
			count++;    //子女个数加1
			HfmTree[first].parent = i;  //修改双亲结点的值
			HfmTree[first].co = '0';    //将子女到根结点的路径编码
			HfmTree[i].Child_0 = first;  //修改双亲结点子女的值
		}

		second = MinWeight(i);				  
		if(second != -1)
		{ 
			count++;
			HfmTree[second].parent = i;
			HfmTree[second].co = '1';   
            HfmTree[i].Child_1 = second;
		}

		third = MinWeight(i);
		if(third != -1)
		{  
			count++;
			HfmTree[third].parent = i;   
            HfmTree[third].co = '2';   
            HfmTree[i].Child_2 = third;                  
		}	  
				 
		fourth = MinWeight(i);  
		if(fourth != -1)
		{
			count++;
			HfmTree[fourth].parent = i;  
			HfmTree[fourth].co = '3';   
			HfmTree[i].Child_3 = fourth;
		}

		switch(count)      // 计算根结点的权值
		{
			case 1:    HfmTree[i].weight += HfmTree[first].weight;
			case 2:	   HfmTree[i].weight += HfmTree[second].weight;  
			case 3:	   HfmTree[i].weight += HfmTree[third].weight;
			case 4:    HfmTree[i].weight += HfmTree[fourth].weight;  break;
			default:   cout<<"Error in CreateHT!"<<endl;   exit(0);    //事实上，count的取值只可能是2，3，4
		}  
		HfmTree[i].parent = -1;    //置根结点的双亲为空
	} 

	//   计算各叶子结点（各字符）编码   
	for (i = 0;  i < n;  i++)
	{   //利用string类中重载的操作符 += ，合并根结点到叶子的路径
		CharNode[i].code  +=  HfmTree[i].co;    
		int  j = HfmTree[i].parent;
		while  (j != (int)(n*4+1)/3-1)  //自底向上，合并路径，(int)(n*4+1)/3-1为根结点下标
		{   //   至根结点  
			CharNode[i].code += HfmTree[j].co; 
			j = HfmTree[j].parent;
		} 

		//将编码逆置 
		char e;
	    int  m = CharNode[i].code.length();
	    for(int  k = 0;  k < m/2;  k++)
		{
		   e = CharNode[i].code[k];
		   CharNode[i].code[k] = CharNode[i].code[m-1-k];
		   CharNode[i].code[m-1-k] = e;
		}

	}    
	
	//   保存至文件HfmTree 
	ofstream  fOut("D:\\HfmTree.txt");  	//   保存n个字符、权值及编码     
	if (fOut)
	{ 
		fOut<< n << endl;   //   字符数
		for(int i = 0;  i < n;  i++)
		{   
			fOut << CharNode[i].ch << "\t"; 
			fOut << CharNode[i].weight << "\t"; 
			fOut << CharNode[i].code << "\t";
			fOut << endl;  
		}
		cout << "HuffmanTree Creating Completed!" << endl;
	} 
	else   
		cerr << "File HfmTree open failed when saving HfmTree!" << endl;          
}   
    
void   Encode()   //   对文件ToBeCode中的正文进行编码然后将结果存入文件CodeFile中   
{
	ifstream  fIn("D:\\ToBeCode.txt");   
    ofstream  fOut("D:\\CodedFile.txt");
	/*if(!fIn || !fOut)
	{
		cerr << "File open failed when encoding!" << endl;
		exit(0);
	}*/
	char   next;   
	if(fIn.eof())     //若ToBeCode.txt为空
	{
		cout << "File \"ToBeCode.txt\" Is Empty!" <<endl;
		return;
	}
    while(fIn.get(next))  //逐个取文件中的字符并进行编码
	{
		int j;  
		for(j = 0;  j < n  &&  CharNode[j].ch != next;  j++);   
		if(j < n)   //   若在字符集中，则变换为编码    
            fOut << CharNode[j].code;   
		else         //若不在，原样输出
		{
			cout << "File Coding Failed! " << endl;
			exit(0);
		}
	}
	cout << "File Coding Completed!" << endl;
}
void Decode()   //   将文件ToBeDecode中的代码进行译码，结果存入文件DecodedFile中  
{
	ifstream  fIn("D:\\ToBeDecode.txt");  
	ofstream  fOut("D:\\DecodedFile.txt");  
	if (!fIn || !fOut)
	{
		cerr <<  "File open failed when decoding!" << endl;  
		exit(0);
	}
	string  line;

	/*if(fIn.eof())//若ToBeDecode.txt为空
	{
		cout << "File \"ToBeDeode.txt\" Is Empty!" <<endl;
		return;
	}*/
	while(getline(fIn, line))//逐行取字符串进行译码
	{
		string  subs;    //subs表示所取字符串line的子串
		while (line.size() > 0)       //若line长度大于0
		{
			int current = line.size();  //
			bool  flag = true;
			for (int i = 1;  flag && i < n;  i++)  
			{
				subs = line.substr(0, i);  //取line第 0 ~ i 的字符串，赋值给subs
				for (int j = 0;  flag && j < n;  j++)
					if (CharNode[j].code == subs)   //若huffman树中存在与subs匹配的编码叶子
					{
						fOut << CharNode[j].ch;   //输出编码
						int len = line.size();
						line = line.substr(i, len - i );   //将line中译码的第 0 ~ i 的字符删除
						flag = false;  // 跳出循环
					}
			}
			if( current == line.size())        //line.size()没有变化，说明该行的编码有错，跳出循环
			{
				cout << "File Decoding Failed!" << endl;
				exit(0);
			}
		}
		fOut << endl;
	}
	cout << "File Decoding Completed!" << endl;
}      
    
void main()   
{   
	CreateHT(); 
    Encode();   
    Decode();   
}