[数据结构] 使用最小堆思想实现哈夫曼编解码

哈夫曼树的定义

假设有n个权值，构造有n个叶子结点的二叉树，每个叶子结点的权值是n个权值之一，这样的二叉树可以构造很多棵，其中必有一棵是带权路径长度最小的，这棵二叉树就称为最优二叉树或哈夫曼树。

构建哈夫曼树的方式

假设有7个树（一个节点），其权重分别为1、2、3、4、5、6、7。

找到两个权重最小的树1和2。

1 和2 分别作为新树的左右子树，新树的根结点权重为1 2 =3。剩下的树：3、3、4、5、6、7。

再找到两个最小的树，分别是3和3构成新树，新树权重为6。剩下的树为：6、4、5、6、7。

重复步骤2和3，直到只剩一棵树的时候，即为Huffman树。

下面描述下我实现哈夫曼编码的主要核心的几个部分：

构建哈夫曼树

构建哈夫曼树的第一步是建立最小堆：先读取用户输入的字符与其对应的权值，并将其无序插入到堆中，再根据权值，不断调整堆，使其变成为最小堆。

有了最小堆以后，就可以开始构建哈夫曼树了。整体思路是：先创建一个空的树的节点，再从刚刚创建好的最小堆中，取出两个最小节点，作为这个节点的左右分支。显然，这个节点为非叶节点。然后将这个节点再插入最小堆，重复此步骤直至原堆中的元素都被处理了即可结束。

取出树根节点(也就是堆顶节点)，即可作为哈夫曼树的开始树根。

生成哈夫曼编码字典

有了哈夫曼树，需要其对应的字典才能实现编码解码，每次重新完全的遍历一遍树是完全低效率的做法。主要解决手段是在构建好了树之后，仅仅遍历一遍哈夫曼树，以0为左，1为右记录找到其所走的路径，找到所有的叶节点，并将其对应的路径记录为编码，保存到一个Key-Value键值对中以供索引即可。

编码与解码

对于编码，对字符串中的每个字符逐个通过查询字典的方式获取其对应的哈夫曼编码值。而对于解码，对于一个特定字符的编码，反过来查询哈夫曼树，从根节点开始，由于我们规定‘0’为当前节点的左子节点，‘1’为当前节点的右子节点，只需要根据编码来进行指针的移动，直到找到最终存储对应字符的叶节点即可。

编码文件的读写

按照数据结构实验的要求，要将哈夫曼树保存在HuffmanTree文件里，然后在程序初始化的时候读入内存，同时要将字典输出到对应的CodeFile中。对于哈夫曼树保存到文件，有两种方法：一种是直接将哈夫曼树结构以二进制流的方式输出到hfmTree中，一种是保存用户输入后再次加载输入内容并重新建树。目前使用的是第二种方式。

程序运行结果

相关代码

下面附上我所实现的相关代码，基本上实现了哈夫曼编解码的整体过程，可能会有一些不足之处，如有发现，还望能及时在本文章下方评论或直接联系我指出。

#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdlib>
#include<limits> // 用于获取INT_MIN
#define MAX_DATA 100  // 最大容量 
using namespace std;
/*
	Author: Titan
	Date: 2020-04-27
*/
// 定义哈夫曼树结构
typedef struct TreeNode *hfmTree;
struct TreeNode{
	int weight; // 节点的权重 
	char ch;	//  节点的数据 
	hfmTree left; // 节点右分支 
	hfmTree right; // 节点左分支 
};
// 定义最小堆的结构 
typedef struct HeapNode *Heap;
struct HeapNode{
	hfmTree* data;
	int size; // 定义堆当前的大小
	int capacity; // 定义堆的最大容量 
};
// 一些全局变量的定义
int code[30]; // 哈夫曼编码临时空间
bool dictLoaded = false; // 是否已经加载了字典
// 编码字典Key-Val对(实际上可以用STL库的map来实现,这里简单用两个数组) 
char dictKey[30];
char dictVal[30][100];
// 	字典计数
int total=0;
ofstream outFile; 
hfmTree globalTree = NULL; 

// 声明函数
void buildHeap(Heap H);
hfmTree buildHfmTree(Heap H);
void createDict(hfmTree tree,int depth);
Heap createHeap();
hfmTree createNode(char ch,int weight);
bool insertHeap(Heap H,hfmTree tree);
bool isEmpty(Heap H);
bool isFull(Heap H);
hfmTree popHeap(Heap H);
void printTree(hfmTree tree);
void setHeap(Heap H,int p);
void loadDict(ifstream &inFile);
int getCode(char ch);
void encode(char chs[],char* encodeResult);
void decode(hfmTree tree,char* code,char* result);
void loadTreeFile();
void doInit();
void printMenu();
void printDict();
void loadTreeByInput();
// END

int main(){
	// 进行初始化 
	doInit();
	int choice;
	char inCode[200];
	char result[200];
	char outCode[200];
	char inputStr[50];
	bool flag = true;
	while(flag){
		printMenu();
		cin >> choice;
		switch(choice){
			case 1: 
				printTree(globalTree);
				break;
			case 2:
				printDict();
				break;
			case 3:
				loadTreeByInput();
				break;
			case 4:
				getchar();
				gets(inputStr);
				encode(inputStr,outCode);
				cout <<"编码后的文本为: "<<endl<<outCode<<endl;
				break;
			case 5:
				getchar();
				gets(inCode);
				decode(globalTree,inCode,result);
				cout<<"解码后的文本为: "<<endl<<result<<endl;
				break;
			case 6:
				flag = false;
				break;
		}
	}
	cout << "Powered by Titan. 2020-04-27" << endl;
	
	
}
// 打印菜单
void printMenu(){
	cout << endl;
	cout << "--------- Menu ----------" << endl;
	cout << "-- 1. 查看哈夫曼树结构 --" << endl;
	cout << "-- 2. 查看编码字典 ------" << endl;
	cout << "-- 3. 重新建立哈夫曼树 --" << endl;
	cout << "-- 4. 进行编码 ----------" << endl;
	cout << "-- 5. 进行解码 ----------" << endl;
	cout << "-- 6. 退出程序 ----------" << endl;
	cout << "请输入您的选择: ";
}
// 输出编码字典
void printDict(){
	for(int i=0;i<total;i++){
		cout << "字符: " << dictKey[i] << ", 编码值: " << dictVal[i] << endl; 
	}
} 
// 构造节点
hfmTree createNode(char ch,int weight){
	hfmTree treeNode = new TreeNode;
	treeNode->ch = ch;
	treeNode->weight = weight;
	treeNode->left=treeNode->right=NULL;
} 

// 生成堆的实现
Heap createHeap(){
	Heap heap = new HeapNode(); 
	heap->data = new hfmTree[MAX_DATA+1]; // 为data分配数组内存，给哨兵多分配1个 
	heap->size=0;
	heap->capacity=MAX_DATA;
	heap->data[0] = createNode('\0',INT_MIN);
	return heap;
}
// 构建最小堆 ---- Start 
// 调整局部为最小堆 传入Heap和局部的根节点 [p]
void setHeap(Heap H,int p){
	int parent,child;
	// rootTree指向局部的根节点 
	hfmTree rootTree = H->data[p];
	for(parent=p;parent*2<=H->size;parent=child){
		// 将Child指向Parent的左右子节点中最小者 
		child = parent*2;
		if((child!=H->size) && H->data[child]->weight > H->data[child+1]->weight){
			child++;
		}
		// 如果child的权重不再小于parent,调整完毕,否则继续进行调整
		if(rootTree->weight <= H->data[child]->weight){
			break;
		}else{
			H->data[parent] = H->data[child];
		}
	}
	// 最后一定指向最终位置
	H->data[parent] = rootTree;
}
// 构造最小堆的直接实现 
void buildHeap(Heap H){
	// 不断调整局部, 这里默认已经将乱序的数据放入了data中.
	// 从最后一个节点的父节点开始,一直到根节点1 (0是哨兵节点) 
	for(int i=H->size/2;i>0;i--){
		setHeap(H,i);
	}
}
// 构建最小堆 ---- End
// 判断堆是否已满, 堆是否为空 
bool isFull(Heap H){
	return (H->size==H->capacity);
}
bool isEmpty(Heap H){
	return (H->size==0);
}
// 插入堆的操作
bool insertHeap(Heap H,hfmTree tree){
	if(isFull(H)){
		cout << "堆已满，无法插入数据: " << tree->ch << endl;
		return false; 
	}
	int i=++H->size;
	// i为最后一个位置，然后一层一层向上过滤 
	for(;H->data[i/2]->weight>tree->weight;i/=2){
		H->data[i]=H->data[i/2];
	}
	H->data[i]=tree;
	return true;
}
// 从堆中取出最小元素的实现
hfmTree popHeap(Heap H){
	if(isEmpty(H)){
		cout << "堆已空，无元素" << endl;
		return NULL;
	}
	int parent,child;
	// 取出根节点
	hfmTree rootTree = H->data[1];
	// xTree为最后一个元素，同时size-1（因为取出了根节点） 
	hfmTree xTree = H->data[H->size--];
	// 从根节点下面找出最小的替换上来
	for(parent=1;parent*2<=H->size;parent=child){
		child = parent*2;
		if((child!=H->size) && (H->data[child]->weight>H->data[child+1]->weight)){
			child++;
		}
		if(xTree->weight <= H->data[child]->weight){
			break;
		}else{
			H->data[parent]=H->data[child];
		}
	}
	H->data[parent]=xTree;
	return rootTree;
}
// -------------- 哈夫曼树部分 ------------
// 哈夫曼树的构造
hfmTree buildHfmTree(Heap H){
	// 假设已经无序的将节点保存在堆的data中,
	// 首先要将堆调整为最小堆
	hfmTree tree;
	buildHeap(H);
	int size = H->size;
	for(int i=1;i<size;i++){
		tree = new TreeNode();
		// 取出两个最小节点，作为这个节点的左右分支
		tree->ch='\0';
		tree->left = popHeap(H);
		tree->right = popHeap(H);
		// 计算新的权值
		tree->weight=tree->left->weight + tree->right->weight;
		// 将这个节点再插入最小堆
		insertHeap(H,tree); 
	}
	// 取出哈夫曼树根节点(也就是堆顶节点)
	tree = popHeap(H);
	return tree; 
}
// 先序遍历哈夫曼树
void printTree(hfmTree tree){
	if(tree){
		if((tree->left == NULL) && (tree->right == NULL)){
			printf("(权重:%d, 数据:%c )\n",tree->weight,tree->ch);
		}else{
			printf("(权重:%d, 数据:非叶节点 )\n",tree->weight);
		}
		printTree(tree->left);
		printTree(tree->right); 
	}
}
// 哈夫曼编码字典生成 
void createDict(hfmTree tree,int depth){
	if(tree){
		if((tree->left == NULL) && (tree->right == NULL)){
			if(outFile==NULL){
				cout << "写出编码字典文件失败!" << endl; 
				exit(-1);
			}
//			cout<<"字符: " << tree->ch << " 权值: " << tree->weight << " 编码:";																	   			cout<<"字符: " << tree->ch << " 权值: " << tree-
			outFile << tree->ch <<",";
			for(int i=0;i<depth;i++){
//				cout<< code[i];
				outFile<<code[i];
			}
//			printf("\n");
			outFile<<endl;
		}else{
			code[depth]=0;
			createDict(tree->left,depth+1);
			code[depth]=1;
			createDict(tree->right,depth+1);
		}
	}
}
// 哈夫曼编码字典加载
void loadDict(ifstream &inFile){
	if(inFile==NULL){
		cout << "打开编码文件失败!!" << endl;
		return; 
	}
	char temp[30];
	while(!inFile.eof()){
		inFile.getline(temp,30);
		if(strstr(temp,",")!=NULL){
			sscanf(temp,"%c,%s\n",&dictKey[total],&dictVal[total]);
		//  cout<<dictKey[total] <<":"<<dictVal[total] << endl; 调试语句 
			total++;
		}
	}
}
// 哈夫曼树文件加载 -- 从文件 
void loadTreeFile(){
	ifstream treeFile("hfmTree.txt");
	if(treeFile==NULL){
		cout << "加载树文件hfmTree失败!"<<endl;
		return; 
	}
	char temp[20];
	int weight,count;
	char ch;
	Heap heap = createHeap();
	while(!treeFile.eof()){
		treeFile.getline(temp,20);
		if(strstr(temp,",")!=NULL){
			sscanf(temp,"%c,%d\n",&ch,&weight);
			heap->data[++heap->size]=createNode(ch,weight);
		}
	}
	treeFile.close();
	globalTree = buildHfmTree(heap);
	cout << "成功从hfmTree数据文件中加载树的数据" << endl;
}
// 哈夫曼树文件加载 -- 从用户输入
void loadTreeByInput(){
	cout << "从输入中构建哈夫曼树..." <<endl; 
	ofstream outTreeFile("hfmTree.txt",ios::out); 
	int weight,count;
	char ch;
	Heap heap = createHeap();
	cout << "请输入一共要读入的数据数: ";
	scanf("%d",&count); 
	getchar();
	cout << "请输入数据,格式: ( data,weight ) 以空格分隔,以换行符结尾 (可能需要Ctrl+Z结束输入): " <<endl; 
	for(int i=1;i<=count;i++){
		scanf("%c,%d ",&ch,&weight);
		heap->data[i]=createNode(ch,weight);
		heap->size++;
		outTreeFile << ch <<","<<weight<<endl;
	}
	globalTree = buildHfmTree(heap);
	cout << "成功从用户输入中加载并保存树的数据."<<endl;
	outTreeFile.close();
}
// 哈夫曼编码读取
int getCode(char ch){
	int i;
	for(i=0;i<total;i++){
		if(dictKey[i]==ch){
			return i;
		}
	}
	return -1;
}

// 编码过程
void encode(char chs[],char* encodeResult){
	int count=0;
	for(int i=0;(chs[i]!='\n' && chs[i]!='\0');i++){
		int index = getCode(chs[i]);
		for(int j=0;dictVal[index][j]!='\0';j++){
			encodeResult[count]=dictVal[index][j];
			count++;
		}
		encodeResult[count]=' ';
		count++;
	}
	encodeResult[count]='\0';
}

// 解码过程 
void decode(hfmTree tree,char* code,char* result){
	int flag,count=0;
	hfmTree treeIndex = tree;
	for(int i=0;code[i]!='\0';i++){
		if(code[i]==' ' || code[i]=='\n'){
			result[count]=treeIndex->ch;
			count++;
			treeIndex=tree;
		}else{
			if(code[i]=='1'){
				treeIndex=treeIndex->right;
			}else{
				treeIndex=treeIndex->left;
			}
		}
	}
	result[count]=treeIndex->ch;
	count++;
	treeIndex=tree;
	result[count]='\0';
}
// 程序初始化 
void doInit(){
	ifstream testHfmTree("hfmTree.txt");
	if(testHfmTree!=NULL){
		testHfmTree.close();
		loadTreeFile();
	}else{
		testHfmTree.close();
		loadTreeByInput();
	}
	outFile.open("CodeFile.txt",ios::out);
	createDict(globalTree,0);
	outFile.close();
	ifstream inFile("CodeFile.txt",ios::in);
	loadDict(inFile);
}