哈夫曼编码应用

问题描述

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

分析一下

构建哈夫曼树

? 使用静态链表，先将所有的结点关系全部清零，再进行结点和相应权值的赋值，遍历后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){//结点的双亲的左孩子与