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

#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);
}