哈夫曼应用

哈夫曼编码应用

问题描述

​ 给定字符串,将每个不同的字符的哈夫曼编码表示并输出其哈夫曼编码,并再将其哈夫曼编码还原回字符串

分析一下

构建哈夫曼树

​ 使用静态链表,先将所有的结点关系全部清零,再进行结点和相应权值的赋值,遍历后n-1个结点 (新根),从n个结点中选两个最小的权值了合成一棵树,并将新根加入到比较结点中(并将这两棵树标记以及结合,不再进行下次的比较),最后后合成一颗哈夫曼树

哈夫曼编码

​ 在这里用到了一个大数组嵌套一个小数组,大数组I的功能是存放每一个结点的哈夫曼编码,小数组中存放每一个结点的没有个哈夫曼编码的反码

​ 从叶子结点分别向根出发即可,若该结点时双亲结点的左孩子,则记0,反之记为1,记录在一个记录数组中直到该结点没有双亲(根结点),每遍历完一个结点后将记录数组复制到对应的小数组中。并及时清空记录数组进行下次使用。

​ 在输出方面使用了多重的for循环,依次遍字符串,将字符串的每一个字符与结点进行比较,若相等则输出对应的(该结点)的哈夫曼编码,最后再用一数组接收,以便后续的使用

解码

​ 依次遍历没有过哈夫曼遍历,从根结点出发,遇0向左,遇1则右,若到了叶子(无左孩子或无右孩子),则输出。并将更新结点值

看看代码吧

必没问题!!!(有问题就用个dev吧...)

#include<iostream>
#define Max_S 1000000 
#define MaxSize 100
using namespace std;
//静态链表 
typedef struct TreeNode{
	char data;
 int weight;
 int parent,lchild,rchild; 
}HTNode, *HuffmanTree; 
//编码数组 
typedef struct{
	int HC[MaxSize];
}info,*Info;//一个大数组套一个小数组 
//===========================================================
//一些串和二叉树的算法 
//求串长 
int Strstrlen(char a[]){
	int i = 1;
	for(;a[i] !='\0';){ i++; }
	return i;
} 
//字符串赋值 
void StrAssige(char(&S)[MaxSize+1],char a[]){
	S[0] = Strstrlen(a);
	for(int i = 1;i <= Strstrlen(a);i++){
	S[i] = a[i-1];
	}
}
//求深度
int qiushendu(HuffmanTree t,int root){
	if(root == 0) return 0;
	if(t[root].lchild == 0&&t[root].rchild == 0) return 1;
	return (max(qiushendu(t,t[root].lchild),qiushendu(t,t[root].rchild)) + 1);
} 
//==================================================================
//获取两个最小值
int *Select(HuffmanTree HT,int n){
	int s1,s2;////最小值与极小值 
	int mmin = Max_S;//先等于无穷大 
	int min = Max_S;
 for(int i = 1;i <= n;i++){
 if(HT[i].parent != 0) continue;//双亲不为零代表已经构成新树,应去除
 else{
 if(mmin >= HT[i].weight){//最小的
 min = mmin ;
 s2 = s1;
 mmin = HT[i].weight;
 s1 = i;
 }else if(min >= HT[i].weight){//次小的 
 min = HT[i].weight;
 s2 = i; 
 }
 }
 }
 //若最小值相等,则浅(先遍历的)树的序号在前 
 int S1 = qiushendu(HT,s1);
 int S2 = qiushendu(HT,s2);
 if(S1 >= S2){
 	int temp;
 	temp = s1; s1 = s2; s2 = temp;//交换顺序 
	}
	//用数组存放最小值和次小值 
 int a[3] = {0,s1,s2};
 return a;
}
//===========================================================================
//构建哈夫曼树 
void CreatHuffmanTree(HuffmanTree &HT,char *huf,int *wei,int n){
 int s1,s2;//最小值与极小值 
 if(n <= 1){
 cout << "抱歉,您输入的结点数不符合逻辑";
 return;
 }
 int m = 2*n-1;//总结点树
 HT = new HTNode[m+1];//放弃下标为零的数组
 //先遍历前n个数,初始化
 for(int i = 1;i <= m;i++){//全部初始化为零
 HT[i].parent = 0;
 HT[i].lchild = 0;
 HT[i].rchild = 0;
 }
 
	//赋结点、权值 
 for(int i;i <= n;i++){
 	HT[i].data = huf[i];//结点 
 	HT[i].weight = wei[(int)huf[i]];//权值 
 
	}
 //遍历后n+1个,新根
 for(int i = n+1;i <= m;i++){
 //找出最小额两个结点
 int *a;//获取s1和s2 
	a = Select(HT,i-1);//在n个数中找
	s1 = a[1]; s2 = a[2];
 //更新各个数值
 HT[s1].parent = i;
 HT[s2].parent = i; 
 HT[i].lchild = s1;
 HT[i].rchild = s2; 
 HT[i].weight = HT[s1].weight + HT[s2].weight; 
 }
}
//=================================================
//哈夫曼树编码化,并输出 
void HuffmanCode(HuffmanTree HT,info* I, int n){
	int lchild,rchilg,parent,copyparent;//左孩子值,有孩子子,双亲值,类双亲值(永远是双亲值值的孩子,但不知是左孩子右) 
	int jilv[100];//记录数组每个结点的编码(0/1),算深度即可无需大开 
	for(int i = 1;i <= n;i++){//依次遍历叶子结点 
	int n = 0;//记录数 
	//初始化各个双亲值
	copyparent = i; 
	 parent = HT[i].parent;
	 while(parent != 0&&copyparent != 0){//两个双亲都不为零 
	 	if(HT[parent].lchild == copyparent){//结点的双亲的左孩子与他的序号相等,记为零 
	 	jilv[++n] = 0;
	}else{
	jilv[++n] = 1;
	}
	copyparent = parent;//更新类双亲 
	parent = HT[parent].parent;//更新双亲 
	}
	
	I[i].HC[0] = jilv[0] = n;//第一个字符的总编码数 
	for(int m = 1;m <= jilv[0];m++)//将第一个字符的所有编码复制到第一个存在数组中去 
	 I[i].HC[m] = jilv[m];
	
	//输出 
	cout << HT[i].data << ":";
	for(int m = jilv[0];m >=1;m--){//反向输出 
	 cout << I[i].HC[m];	
	 jilv[m] = 0;//记录数组清空 
	 }
	 cout << endl;
	 jilv[0] = 0;//记录数组清零 
	}	
}
//完整输出哈夫曼编码
int *printHuf(char *h,char *huf,info* I){
	static int hufman[MaxSize+1];
	int mum = 0;
	for(int i = 1;i <= h[0];i++){//遍历原数组 
	for(int j = 1;j <= huf[0];j++){//遍历结点 
	if(h[i] == huf[j]){//如果相等 
	for(int m = I[j].HC[0];m >=1;m--){//反向输出 
	 cout << I[j].HC[m];
	hufman[++mum] = I[j].HC[m];	 
	 }
	 }
	}	
 }
 hufman[0] = mum; 
 return hufman; 
} 
//==================================================================================
//哈夫曼解码,并输出 
void HuffmanDeCode(int * HufMan,HuffmanTree HT,int n){
 HuffmanTree p = HT;
	int lchild,rchid,r,m = 2*n-1;
	for(int i = 1;i <= HufMan[0];i++){//遍历每一个哈夫曼编码
	 //与0向左,由1向右 
	if(HufMan[i] == 0){
	m = p[m].lchild;
	}else{
	m = p[m].rchild;
	}
	//若无孩子则直接输出(没有度为一的数),并更新根结点和m的值 
	if(p[m].lchild == 0||p[m].rchild == 0){
	cout << p[m].data;
	p = HT;
	m = 2*n- 1;
	}
	}
}
int main(){
	int wei[1000] = {0};//权值数组 
 char huf[MaxSize+1];//哈夫曼结点数组 
	char a[MaxSize+1];//赋值串 
	char h[MaxSize+1];//要编译的字符串 
	
 cout << "请输入要编码的字符:"; 
	gets(a);
	StrAssige(h,a);
 //赋结点、权值 
	for(int i = 1,n = 0;i <=h[0];i++){
	wei[(int)h[i]]++;//权值++ 
	if(wei[(int)h[i]] == 1){//第一次遇到的不同得字符 
	huf[++n] = h[i];//结点确定 
	}	
	huf[0] = n;//总结点数 
	}
	
	//哈夫曼树 
	HuffmanTree HT;
	//创建哈夫曼树 
	CreatHuffmanTree(HT,huf,wei,huf[0]);
	
	//======================================================================================
	
	//将字符串哈夫曼编码化,并输出每个结点的哈夫曼编码 
	info *I = new info[huf[0]];//就是一个大数组,大数组存放每一个字符的哈夫曼编码,小数组存放每一位的
	HuffmanCode(HT,I,huf[0]);
	//输出完整的哈夫曼编码 ,并捕获 
	int* HufMan;
	cout << "获得的哈夫曼编码为:";
	HufMan = printHuf(h,huf,I);
 cout << endl;
 
 //==================================================================================
	
	//解码哈夫曼编码 
	cout << "该哈夫曼编码的解码为:"; 
	HuffmanDeCode(HufMan,HT,huf[0]);
	cout <<endl;
	return 0;
}
作者:T,a,o原文地址:https://www.cnblogs.com/wht-de-bk/p/16916164.html

%s 个评论

要回复文章请先登录注册