哈夫曼应用

哈夫曼编码应用

问题描述

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

分析一下

构建哈夫曼树

​ 使用静态链表，先将所有的结点关系全部清零，再进行结点和相应权值的赋值，遍历后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;
}
标签 , , ,