哈夫曼編碼應用

問題描述

​ 給定字元串，將每個不同的字元的哈夫曼編碼表示並輸出其哈夫曼編碼，並再將其哈夫曼編碼還原回字元串

分析一下

構建哈夫曼樹

​ 使用靜態鏈表，先將所有的結點關係全部清零，再進行結點和相應權值的賦值，遍歷後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;
}