并統(tǒng)計其葉子結點的個數(shù)。方案二：哈夫曼樹的建立和編(編輯修改稿)
2024-11-16 03:07 本頁面
【文章內(nèi)容簡介】 F中 。 (4) 重復 (2) 和 (3) , 直到 F 只含一棵樹為止。這棵樹便是 Huffman樹。 怎樣證明它就是 WPL最小的最優(yōu)二叉樹？ 參考 《 信源編碼 》 Huffman樹的特點：沒有度為 1的結點。 15 step1： 對權值進行合并、刪除與替換 —— 在權值集合 {7,5,2,4}中，總是合并 當前值最小 的兩個權 具體操作步驟： a. 初始 方框表示外結點（葉子，字符） 圓框表示內(nèi)結點（合并后的權值） b. 合并 {2} {4} c. 合并 {5} {6} d. 合并 {7} {11} 16 step2： 按左 “ 0”右 “ 1” 對 Huffman樹的所有分支編號 d a i n 1 1 1 0 0 0 Huffman編碼結果： d=0, i=10, a=110, n=111 WPL=1bit 7＋ 2bit 5+3bit(2+4)=35（小于等長碼的 WPL=36） 特征：每一碼不會是另一碼的前綴，譯碼時可惟一復原 Huffman編碼也稱為 前綴碼 —— 將 Huffman樹 與 Huffman編碼 掛鉤 17 二、 Huffman編碼 （ 1） 由于 Huffman樹的 WPL最小， 說明編碼所需要的 比特數(shù)最少 。 （ 4） Huffman編碼時是從葉子走到根；而譯碼時又要從根走到葉子，因此每個結點需要增開 雙親 指針分量（連同結點 權值共要開 5個分量） （ 5） 用計算機實現(xiàn)時，順序和鏈式兩種存儲結構都要用到。 分析 Huffman樹和編碼的特點： 霍夫曼 編碼的基本思想是 —— 出現(xiàn)概率大的信息用短碼，概率小的用長碼 ,最小冗余 這種編碼已廣泛應用于網(wǎng)絡通信中。 （ 2） Huffman樹 肯定沒有度為 1的結點； （ 3） 一棵有 n 0個葉子結點的 Huffman樹，共有 2n01個結點； （因為 n=n0+n1+n2=2n01) 18 如何編程實現(xiàn) Huffman編碼？ 建議 1： Huffman樹中結點的結構可設計成 5分量形式： char weight parent lchild rchild 將整個 Huffman樹的 結點 存儲在一個數(shù)組 HT[1..n..m]中 。 各葉子結點的 編碼 存儲在另一 “ 復合 ” 數(shù)組 HC[1..n]中。 請參見教材 P149圖 （ a)和（ c) 建議 2： Huffman樹的 存儲結構可采用 順序存儲 結構： (1)教材 P147～ 149內(nèi)容； (2)嚴蔚敏 “ 數(shù)據(jù)結構 ” 演示程序 ； (3)習題集 P149 實習 ； (4)自測卷第 6章上機方案二的源程序。 可參考： 19 typedef struct{ unsigned int weight； //權值分量（可放大取整） unsigned int parent， lchild， rchild； //雙親和孩子分量 }HTNode， *HuffmanTree； //用動態(tài)數(shù)組存儲 Huffman樹 typedef char**HuffmanCode； //動態(tài)數(shù)組存儲 Huffman編碼表 Huffman樹和 Huffman樹編碼的存儲表示： 0 0 0 r 0 9 2 0 0 19 0 0 7 l p w 3 2 1 雙親 *HuffmanTree或 HT向量 HT[3].parent=9 指針型指針 20 如何編程實現(xiàn) Huffman編碼？ 參見教材 P147 先構造 Huffma
教學課件相關推薦
鄂ICP備17016276號-1