^{<blockquote id="bel14"></blockquote>}

正文內容

最優二叉樹哈夫曼樹-資料下載頁

2026-06-10 06:37本頁面

　　

【正文】符c轉換為H[i].bits中存放的編碼串。對壓縮后的數據文件進行解碼則必須借助于哈夫曼樹T，其過程是：依次讀人文件的二進制碼，從哈夫曼樹的根結點(即T[m1])出發，若當前讀人0，則走向左孩子，否則走向右孩子。一旦到達某一葉子T[i]時便譯出相應的字符H[i].ch。然后重新從根出發繼續譯碼，直至文件結束。在本章的引入部分，兩個例子都是判定問題，這兩個判定問題都可以通過構造哈夫曼樹來優化判定，以達到總的判定次數最少。再如，要編制一個將百分制轉換為五級分制的程序。顯然，此程序很簡單，只要利用條件語句便可完成。【程序段】if a60 then b:=’bad’ else if a70 then b:=’pass’ else if a80 then b:=’general’ else if a90 then b:=’good’ else b:=’excellent’。如果上述程序需反復使用，而且每次的輸入量很大，則應考慮上述程序的質量問題，即其操作所需要的時間。因為在實際中，學生的成績在五個等級上的分布是不均勻的，：分數 0－59 60－69 70－79 80－89 90－100比例數分數段的分布頻率則80％以上的數據需進行三次或三次以上的比較才能得出結果。假定以5，15，40，30和10為權構造一棵有五個葉子結點的哈夫曼樹，它可使大部分的數據經過較少的比較次數得出結果。但由于每個判定框都有兩次比較，將這兩次比較分開，得到新的判定樹，按此判定樹可寫出相應的程序。請您自己畫出此判定樹。假設有10000個輸入數據，若上程序段的判定過程進行操作，則總共需進行31500次比較；而若新判定樹的判定過程進行操作，則總共僅需進行22000次比較。習題一、解答題1．證明：在結點數大于1的哈夫曼樹中不存在度為1的結點。2．假設用于通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別為13210。試為這8個字母設計哈夫曼編碼。如果用0～7這8個數的二進制數表示這8個字母也是一種編碼方案，試比較這兩種方法的優劣。3．有7個帶權結點a,b,c,d,e,f,g分別帶權4，試以它們為葉子結點構造一棵哈夫曼樹（請按照左子樹根節點的權小于等于右子樹根節點的權的次序構造）。二、編寫程序題文件壓縮press【問題描述】假設有一張黑白的二進制位圖，M行N列（0M,N2048），將位圖用文件存儲時0表示白、1表示黑，這樣的存儲的文件很大，最大達2048*2048Byte。我們知道八位二進制可以跟有相同ASCII碼值的一個字符的建立起對應關系，如果將位圖以字符的方式存儲，理想狀態下存儲空間變以原來的1/8。但這樣仍然很大，我們剛剛學習了哈夫曼編碼，可以先統計各字符出現的頻率，然后依此進行哈夫曼編碼，這樣存儲又將節省不少空間。其實JPEG圖形格式就有類似的處理方式。現在請你對于輸入的由0、1構成的文件，以八位為基礎，先統計頻率然后構造哈夫曼樹，從而進行壓縮處理。處理的過程中如果出現頻率相同的情況，先考慮序號小的（即左子樹節點的權小于等于右子樹節點的權）。【輸入】第一行兩個數M、N，表示圖形共有M行、每行N列，N mod 8=0。接下是M行，每行有N個0或1。【輸出】就一行，表示壓縮后形成的編碼的字節數（所需存儲空間，8個二進制位為一個字節，如果總的二進制位數b除以8有余數，則輸出b div 8+1）。【樣例】8 16000000111100000000000011110000000000001111000000000000111100000000000011110000000000001111000000000000111100000000000011110000002 {說明：哈夫曼編碼為0101010101010101}10

點擊復制文檔內容

環評公示相關推薦

最優二叉樹哈夫曼樹-資料下載頁

第6章樹和二叉樹-資料下載頁

數據結構---樹和二叉樹-資料下載頁

第6章樹和二叉樹-資料下載頁

第6章樹與二叉樹-資料下載頁

二叉樹定價模型-資料下載頁

樹和森林與二叉樹的轉換-資料下載頁

數據結構二叉樹-資料下載頁

樹和二叉樹ppt課件(2)-資料下載頁

樹和二叉樹的基本知識-資料下載頁

二叉樹期權定價模型-資料下載頁

數據結構4樹與二叉樹-資料下載頁

二叉樹的建立與遍歷與二叉樹的線索化與線索化遍歷-資料下載頁

第五章樹和二叉樹-資料下載頁

可視化計算第6章信息論哈夫曼編碼與二叉樹a-資料下載頁

特殊二叉樹ppt課件-資料下載頁

最優二叉樹哈夫曼樹-全文預覽

最優二叉樹哈夫曼樹-預覽頁

最優二叉樹哈夫曼樹-免費閱讀

最優二叉樹哈夫曼樹(存儲版)

最優二叉樹哈夫曼樹-文庫吧在線文庫