哈夫曼树的编码与解码

Question

综合训练2 利用哈夫曼树进行编码与解码 一、主要目的: 理解哈夫曼树的概念、掌握哈夫曼树的建立以及利用利用哈夫曼树进行哈夫曼编码的方法。 二、主要内容: 在基于哈夫易树进行哈夫易编码的基础理论之上，完成对英文文竟的编码和解码，要求如下: 1、使用文件流方式。 自行查阅关于文件流的相关资料。 2、要求提供编码和解码两种方式 3、能够打开原文文件(dataxt)，统计其中英文字母(假设均为小写)出现的频率，并以此进行哈夫曼编码(空格以及其他字符不加处理)，将每个字母的哈夫曼编码输出到屏幕，并将编码后的结果输出到码文文件(code.xt)中。 4、能够根据3中得到的字符编码，将码文文件中的码文进行解码，得到解码后的原文(result.txt) 5、本综合训练以个人方式完成。 上交方法:各班班长统一收齐发送给我。(只要 CPP 文件，不用 data.txt 文件。)命名格式:数学X班 xxx.cpp 提示: (1)建立的哈夫曼树结点应添加保存字母的域 (2)教材中求哈夫曼编码的算法为递归算法，每次在递归中输出所求编码，而我们需要在对原文编码时使用每个字母的哈夫曼编码，所以应该将递归中求得的字母编码保存下来，以备后用。保存方式自行考虑。 (3)对原文进行编码时，根据读取到的每个字符进行处理:如果是字母，则往code.txt中输出相应编码(根据2中所得编码);如果是其它字符，则不加处理，直接输出到code.txt。(4)解码应在所建立的哈夫曼树基础上进行。依次读取code.txt 文件中字符，若为0或1.则0进左子树1进右子树，直到叶子结点然后取出叶子节点中的字母输出到result.txt:如果是其它字符，则不加处理，直接输出到result.txt。

Answer 1

tips:
1，二进制文件读写（无法使用string)
2，ASCII码和字符转换
3，哈夫曼算法
4，哈希思想的妙用（计算字频；编码使用） 

数据结构
typedef struct
{
	int ascii,weight,parent,lchild,rchild;//哈夫曼树，它们依次表示：字符的ASCII码，双亲，左孩子，右孩子 
}HTNode,*HuffmanTree;

算法
假设有n个字符，申请2n个空间，0号不用 ,HTree数组首地址 
1，初始化1，所有成员赋0；初始化2，读入字符及相应的权值
2，令下个根节点j = n+1,在parent=0的点中挑选出最小值，次小值分别记录其下标index1，index2；
3，最小值和次小值的parent=j;  
*/
#include<iostream>
using namespace std;
#include<stdlib.h> 
#include<fstream>
#include<string>
#include<stack>

#define MIN1 0x1fffffff
#define MIN2 0x2fffffff


//Attention：只可以识别英文输入法下的所有字符，中文打出来的‘？’都不行 
char code[20];//二进制读写准备 

typedef struct
{
	int ascii,weight,parent,lchild,rchild;//哈夫曼树，它们一次表示：字符的ASCII码，双亲，左孩子，右孩子 
}HTNode,*HuffmanTree;

//统计每个字符出现次数：只有英文符号，否则报错 
void Count_Character_Occur_Frequency()
{
	int cof[256];//存储相应字符出现的次数，字符ASCII为下标。charater_occur_frequency 
	for(int i = 0; i < 256; i++)//初始化字符出现次数统计表 
	{
		cof[i] = 0;
	}
	//从源文件按行读取，并统计字符个数，由于字符个数有限，所以用字符的ASCII码作为数组下标，数组值作为次数，类似哈希映射 
	fstream inFile("source.txt",ios::in); 
	if(!inFile)cout<<"source.txt 打开失败！"<<endl;
	
	int sum = 0;//总行数，记录换行个数 
	string s;//存放一行 
	while(true)
	{
		getline(inFile,s);
		if(!inFile)break;//避免重复读取最后一个字符 
		sum++;
		for(int i = 0; i < s.size(); i++)
		{
			int a = s[i];//cout<<"a:"<<a<<endl;中文会溢出 
			cof[a]++; //计数 
		}
	}
	inFile.close();//好习惯 
	int a = '\n';//换行符 
	cof[a] = sum; //换行符个数 
	//=======将所有出现的字符及其次数写入文件（类似全局数组）========= 
	int n = 0;//计算出现字符总个数 
	for(int i = 0; i < 256; i++)
	{
		if(cof[i] != 0)n++; 
	}
	fstream outFile("data.txt",ios::out);
	if(!outFile)cout<<"data.txt 打开失败！"<<endl;
	outFile<<n<<endl;//写入字符总个数 
	//打印调试 
	for(int i = 0; i < 256; i++)
	{
		if(cof[i] != 0)
		{
			char ch = i - '\0';
	//		cout<<"i: "<<i<<"  字符："<<ch<<" cof[i]: "<<cof[i]<<endl;
			outFile<<i<<" "<<cof[i]<<endl;//写入文件 
		}
	}
	outFile.close();
}
//创建哈夫曼树 
void CreateHT()
{
	HuffmanTree HTree;
	fstream inFile("data.txt",ios::in);
	if(!inFile)cout<<"data.txt 打开失败！"<<endl;
	
	int n;//节点个数
	inFile>>n;
	HTree = (HTNode*)malloc(2*n*sizeof(HTNode));//哈夫曼构造，共需2n-1个，0号单元不用
	for(int i = 1; i < 2*n; i++)//初始化 1
	{
		HTree[i].ascii = HTree[i].lchild = HTree[i].parent = HTree[i].rchild = HTree[i].weight = 0;//0号单元无用 
	} 
	for(int i = 1; i <= n; i++)//初始化 2，从文件读取ASCII码及相应权值 
	{
		inFile>>HTree[i].ascii>>HTree[i].weight;
	} 
	inFile.close();
/*	for(int i = 1; i < 2*n; i++)//打印输出调试 
	{
		cout<<HTree[i].ascii <<" "<<HTree[i].weight<<endl;
	} 
*/	
	for(int i = n+1; i < 2*n; i++)//从n+1开始，进行n-1次计算 
	{
		//寻找最小，次小值，记录其下标 
		int min1 = MIN1,min2 = MIN2;
		int index1 = 0,index2 = 0;
		
		for(int j = 1; j < i; j++)//i是即将要被填入的根节点 
		{
			if(HTree[j].parent == 0)//双亲为0表示尚待操作 
			{
				if(min1 > HTree[j].weight)
				{
					min2 = min1;//先赋给次小值 
					index2 = index1;
					min1 = HTree[j].weight;
					index1 = j;
				}
				else if(min2 > HTree[j].weight)
				{
					min2 = HTree[j].weight;
					index2 = j;
				}
			}
		}//cout<<index1<<" "<<index2<<endl; 
		
		HTree[i].weight = HTree[index1].weight + HTree[index2].weight;//双亲权值更新 
		HTree[index1].parent = HTree[index2].parent = i;//孩子的双亲节点更新
		if(HTree[index1].weight < HTree[index2].weight)//1，两个节点权值不同，左小右大 ；相同，下标小者在左 
		{
			HTree[i].lchild = index1;//下标赋值 
			HTree[i].rchild = index2;
		}
		else if(HTree[index1].weight > HTree[index2].weight)
		{
			HTree[i].lchild = index2;
			HTree[i].rchild = index1;
		}
		else 
		{
			if(index1 < index2)
			{
				HTree[i].lchild = index1;
				HTree[i].rchild = index2;
			}
			else
			{
				HTree[i].lchild = index2;
				HTree[i].rchild = index1;
			}
		}
	} 
	fstream outFile("result.txt",ios::out);
	if(!outFile)cout<<"result.txt 无法打开！"<<endl;
	outFile<<n<<endl;//节点个数 
	for(int i = 1; i < 2*n; i++)//打印输出调试 
	{
//		cout<<"i:"<<i<<" ascii:"<<HTree[i].ascii <<" weight:"<<HTree[i].weight<<" parent:"<<HTree[i].parent<<" lchild:"<<HTree[i].lchild<<" rchild:"<<HTree[i].rchild<<endl;
		outFile<<" "<<HTree[i].ascii <<" "<<HTree[i].weight<<" "<<HTree[i].parent<<" "<<HTree[i].lchild<<" "<<HTree[i].rchild<<endl;	
	} 
	outFile.close();
	
	//==========建立编码表，写入字符，权值，编码==================
	outFile.open("result.txt",ios::out);
	if(!outFile)cout<<"result.txt 打开失败！"<<endl;
	//利用栈从叶子出发读取每个字符的编码，在写入文件 
	stack<char> code;//存储编码 
	for(int i = 1; i <= n; i++)//对n个字符分别求编码 
	{
		int j = i;
		do{
			int p = HTree[j].parent;
			if(p != 0)
			{
				int l,r;
				l = HTree[p].lchild;
				r = HTree[p].rchild;
				if(j == l)code.push('0');
				if(j == r)code.push('1');
				j = p;
			}
		}while(HTree[j].parent != 0);
		
		outFile<<HTree[i].ascii<<" "<<HTree[i].weight<<" ";//写入字符，权值 
		while(!code.empty())
		{
			outFile<<code.top();//写入编码 
			code.pop();
		}outFile<<endl;
	} 
	outFile.close();
} 
void Encode()
{
	fstream inFile("result.txt",ios::in);
	if(!inFile)cout<< "result.txt"<<endl;
	string s,codeList[256];//将编码表从文件读入该数组中，ASCII码为下标，类似哈希映射 
	int ch,w;
	while(true)
	{
		inFile>>ch>>w>>s;
		if(!inFile)break;
		codeList[ch] = s; 
	}
	inFile.close();
	
	inFile.open("source.txt",ios::in);
	if(!inFile)cout<<"source.txt 打开失败！"<<endl;
	fstream outFile("code.dat",ios::out|ios::binary);
	if(!outFile)cout<<"code.dat打开失败！"<<endl;
	string s2;
	while(true)
	{
		getline(inFile,s);
		if(!inFile)break;
		int a;
		for(int i = 0; i < s.size(); i++)
		{
			a = s[i];//转化为ASCII码 
			int j; 
			for(j = 0; j < codeList[a].size();j++)
			{	
				s2 = codeList[a];
				code[j] = s2[j];
			}code[j]='\0';//!!!关键的一句 
			outFile.write((char*)code,20*sizeof(char));
		}
		a = '\n';
		for(int j = 0; j < codeList[a].size();j++)
		{
			code[j]  = (codeList[a])[j];
		}
		outFile.write((char*)code,20*sizeof(char));
	}
	inFile.close();
	outFile.close(); 
}
//解码 
void Decode()
{
	fstream inFile("data.txt",ios::in);
	if(!inFile)cout<<"data.txt 打开失败！"<<endl; 
	int n;
	inFile>>n;
	HuffmanTree HTree;
	HTree = (HTNode*)malloc(2*n*sizeof(HTNode));
	for(int i = 1; i < 2*n; i++)
	{
		inFile>>HTree[i].ascii >>HTree[i].weight>>HTree[i].parent>>HTree[i].lchild>>HTree[i].rchild;	
	}
	inFile.close();
	for(int i = 1; i < 2*n; i++)//打印输出调试 
	{
	//	cout<<"i:"<<i<<" ascii:"<<HTree[i].ascii <<" weight:"<<HTree[i].weight<<" parent:"<<HTree[i].parent<<" lchild:"<<HTree[i].lchild<<" rchild:"<<HTree[i].rchild<<endl;
	} 
/*	inFile.open("code.txt",ios::in);
	if(!inFile)cout<<"code.txt 打开失败！"<<endl;
*/
	inFile.open("code.dat",ios::in|ios::binary);
	if(!inFile)cout<<"code.dat 打开失败！"<<endl;
	
	fstream outFile("recode.txt",ios::out);
	if(!outFile)cout<<"recode.txt 打开失败！"<<endl;
	char ch;
	int root = 2*n - 1;//char code[100];
//	string s;
	while(true)
	{
		inFile.read((char*)code,20*sizeof(char));
		if(!inFile)break;
	//	cout<<"ch: "<<ch<<" root: "<<root<<endl;	
		for(int i = 0; code[i] != '\0'; i++)
		{//cout<<ch;
			ch = code[i];
			if(ch == '0')root = HTree[root].lchild;
		else if(ch == '1')root = HTree[root].rchild;
		
		if(HTree[root].lchild == 0)
		{//cout<<endl;
			char cht = HTree[root].ascii;
			outFile<<cht;
			root = 2*n - 1;
		} 
		
		}//cout<<endl;
	}
	outFile.close();
}
int main()
{
	Count_Character_Occur_Frequency();
	CreateHT();
	Encode();
	Decode();
	return 0;
}