哈夫曼應用

来源:https://www.cnblogs.com/wht-de-bk/archive/2022/11/22/16916164.html
-Advertisement-
Play Games

哈夫曼編碼應用 問題描述 ​ 給定字元串,將每個不同的字元的哈夫曼編碼表示並輸出其哈夫曼編碼,並再將其哈夫曼編碼還原回字元串 分析一下 構建哈夫曼樹 ​ 使用靜態鏈表,先將所有的結點關係全部清零,再進行結點和相應權值的賦值,遍歷後n-1個結點 (新根),從n個結點中選兩個最小的權值了合成一棵樹,並將 ...


哈夫曼編碼應用

問題描述

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

分析一下

構建哈夫曼樹

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

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 傳統大企業更喜歡私有化部署、個性化交付的傳統模式,因為他們需要更強的管控和更高的安全性。 然而,中小企業付費能力有限,需求往往也更加標準化,所以更喜歡價格更低的、訂購更簡單的SaaS產品。 為了滿足不同客戶的需求,多租戶的底層架構設計是至關重要的。 ...
  • 3. Drools入門案例 全套代碼及資料全部完整提供,點此處下載 本小節通過一個Drools入門案例來讓大家初步瞭解Drools的使用方式、對Drools有一個整體概念。 3.1 業務場景說明 業務場景:消費者在圖書商城購買圖書,下單後需要在支付頁面顯示訂單優惠後的價格。具體優惠規則如下: | 規 ...
  • 我們之前有<C++模板編程模塊>中的第<四>節 理解空間配置器allocator優化STL中的Vector 我將在此基礎上加入迭代器功能代碼 Iterator 為什麼可以遍歷所有的容器的方式都一樣? auto it =continer.beign(); for( ;it!=continer.end( ...
  • 最小生成樹(貪心演算法) 概念 一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖,且包含原圖中的所有 n 個結點,並且有保持圖連通的最少的邊。 連通圖有多種連接方式,而其中最小的連通圖,就是最小生成樹 連通圖分為:無向、有向 無向連通圖:所以頂點相連,但各個邊都沒有方向 有向連通圖:邊有方向 1 ...
  • 學習:SQL 語句到結構體的轉換 | Go 語言編程之旅 (eddycjy.com) 目標:SQL表轉換為Go語言結構體 可以線上體驗這個過程:SQL生成GO語言結構體 - 支持批量處理 (tl.beer) MySQL資料庫中的表結構,本質上是SQL語句。 CREATE TABLE `USER`( ...
  • 規則引擎 Drools 全套代碼及資料全部完整提供,點此處下載 1. 問題引出 現有一個線上申請信用卡的業務場景,用戶需要錄入個人信息,如下圖所示: 通過上圖可以看到,用戶錄入的個人信息包括姓名、性別、年齡、學歷、電話、所在公司、職位、月收入、是否有房、是否有車、是否有信用卡等。錄入完成後點擊申請按 ...
  • 1、static修飾局部變數 在函數體內,只初始化一次,被static聲明過的局部變數在調用過程中值不變。原因:在任意函數內定義局部變數,存儲線上程中的棧區,出函數時自動摧毀,所以在每次調用這個函數時,局部變數的初始值都為定義的值在進行運算。static在修飾局部變數時,存儲在靜態區,函數返回時值保 ...
  • 前面幾篇文章對 Yarn 基本架構、程式基礎庫、應用設計方法等進行了介紹。之後幾篇將開始對 Yarn 核心組件進行剖析。 ResourceManager(RM)是 Yarn 的核心管理服務,負責集群管理、任務調度、狀態機管理等,本篇將對 RM 總體架構進行介紹。 ...
一周排行
    -Advertisement-
    Play Games
  • 經常看到有群友調侃“為什麼搞Java的總在學習JVM調優?那是因為Java爛!我們.NET就不需要搞這些!”真的是這樣嗎?今天我就用一個案例來分析一下。 昨天,一位學生問了我一個問題:他建了一個預設的ASP.NET Core Web API的項目,也就是那個WeatherForecast的預設項目模 ...
  • 很多軟體工程師都認為MD5是一種加密演算法,然而這種觀點是不對的。作為一個 1992 年第一次被公開的演算法,到今天為止已經被髮現了一些致命的漏洞。本文討論MD5在密碼保存方面的一些問題。 ...
  • Maven可以使我們在構建項目時需要用到很多第三方類jar包,如下一些常用jar包 而maven的出現可以讓我們避免手動導入jar包出現的某些問題,它可以自動下載那須所需要的jar包 我們只需要在創建的maven項目自動生成的pom.xml中輸入如下代碼 <dependencies> <!--ser ...
  • 來源:https://developer.aliyun.com/article/694020 非同步調用幾乎是處理高併發Web應用性能問題的萬金油,那麼什麼是“非同步調用”? “非同步調用”對應的是“同步調用”,同步調用指程式按照定義順序依次執行,每一行程式都必須等待上一行程式執行完成之後才能執行;非同步調 ...
  • 1.面向對象 面向對象編程是在面向過程編程的基礎上發展來的,它比面向過程編程具有更強的靈活性和擴展性,所以可以先瞭解下什麼是面向過程編程: 面向過程編程的核心是過程,就是分析出實現需求所需要的步驟,通過函數一步一步實現這些步驟,接著依次調用即可,再簡單理解就是程式 從上到下一步步執行,從頭到尾的解決 ...
  • 10瓶毒藥其中只有一瓶有毒至少需要幾隻老鼠可以找到有毒的那瓶 身似浮雲,心如飛絮,氣若游絲。 用二分查找和二進位位運算的思想都可以把死亡的老鼠降到最低。 其中,二進位位運算就是每一隻老鼠代表一個二進位0或1,0就代表老鼠存活,1代表老鼠死亡;根據數學運算 23 = 8、24 = 16,那麼至少需要四 ...
  • 一、Kafka存在哪些方面的優勢 1. 多生產者 可以無縫地支持多個生產者,不管客戶端在使用單個主題還是多個主題。 2. 多消費者 支持多個消費者從一個單獨的消息流上讀取數據,而且消費者之間互不影響。 3. 基於磁碟的數據存儲 支持消費者非實時地讀取消息,由於消息被提交到磁碟,根據設置的規則進行保存 ...
  • 大家好,我是陶朱公Boy。 前言 上一篇文章《關於狀態機的技術選型,最後一個真心好》我跟大家聊了一下關於”狀態機“的話題。從眾多技術選型中我也推薦了一款阿裡開源的狀態機—“cola-statemachine”。 於是就有小伙伴私信我,自己項目也考慮引入這款狀態機,但網上資料實在太少,能不能系統的介紹 ...
  • 使用腳本自動跑實驗(Ubuntu),將實驗結果記錄在文件中,併在實驗結束之後將結果通過郵件發送到郵箱,最後在windows端自動解析成excel表格。 ...
  • 話說在前面,我不是小黑子~ 我是超級大黑子😏 表弟大周末的跑來我家,沒事幹天天騷擾我,搞得我都不能跟小姐姐好好聊天了,於是為了打發表弟,我決定用Python做一個小游戲來消耗一下他的精力,我思來想去,決定把他變成小黑子,於是做了一個坤坤打籃球的游戲,沒想到他還挺愛玩的~ 終於解放了,於是我把游戲寫 ...