哈夫曼樹及其應(yīng)用ppt課件(存儲版)
【正文】 void HuffmanCoding(HuffmanTree amp。 //指示后繼元素的存放位置 } StaticListNode, StaticLinkList [MAXSIZE] 。 則對于電文“ ABACCDA”的二進制電碼為： 000011010 總長為 9位 如 000011010中的前 4個 0的譯碼會有如下幾種不同譯碼： 0000→AAAA ； 0000→ABA ； 0000→BB 思考：如何解決這一問題？ 問題的關(guān)鍵在于編碼是否為 無前綴編碼 。 a 40 b 30 c 5 d 10 e 15 15 30 求解過程 二、哈夫曼樹及其應(yīng)用 ③ 實例：已知有 5個葉子結(jié)點的權(quán)值分別為： 5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。 i=1 n 求解過程 二、哈夫曼樹及其應(yīng)用 ① 問題： 已知 n個葉子的權(quán)值為 {w1,w2,...wn}，構(gòu)造一棵最優(yōu)二叉樹。 分數(shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績數(shù)據(jù)分布情況表 方法 1： a60 打印 bad“ yes a70 no 打印 pass yes a80 no 打印 general yes a90 no 打印 good yes 打印 excellent no 5%的學(xué)生 15%的學(xué)生 40%的學(xué)生 30%的學(xué)生 10%的學(xué)生 共做 31500次比較 讀取一個學(xué)生成績 → a 循環(huán)一萬次 i=1 i=10000 N 結(jié)束 i = i+1 分數(shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績數(shù)據(jù)分布情況表 方法 2： a80 打印 bad yes a90 no yes no a70 yes no a60 yes no 打印“ good 打印 excellent 打印 pass 打印 general 5%的學(xué)生 15%的學(xué)生 40%的學(xué)生 30%的學(xué)生 10%的學(xué)生 讀取一個學(xué)生成績 → a 循環(huán)一萬次 i=1 i=10000 N 結(jié)束 分數(shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績數(shù)據(jù)分布情況表 方法 2： a80 打印 bad yes a90 no yes no a70 yes no a60 yes no 打印“ good 打印 excellent 打印 pass 打印 general 5%的學(xué)生 15%的學(xué)生 40%的學(xué)生 30%的學(xué)生 10%的學(xué)生 共做 22022次比較 讀取一個學(xué)生成績 → a 循環(huán)一萬次 i=1 i=10000 N 結(jié)束 思考： 如何找到一棵 最優(yōu)的 判斷樹使得編寫出來的程序的運行時間是最高效的？ 有關(guān)概念 ① 結(jié)點的路徑長度： 從根結(jié)點沿某條路徑到某結(jié)點途中所經(jīng)歷的弧的條數(shù)稱為該結(jié)點的路徑長度。 步驟 3:判斷 F中是否只有唯一的一棵二叉樹。 7位二進制數(shù)可以為 27個不同的英文字符編碼。 三、實例 已知某通信用電文僅由 A、 B、 C、 D這 4個字符構(gòu)成，其出現(xiàn)的頻率分別為： 2，請給出它們的哈夫曼編碼，要求寫出相應(yīng)的哈夫曼樹。 }HTNode , * HuffmanTree 。 if (n=1) return。 HT[i].rchild=0。 i=m。 HT[i].rchild = s2。 i=n。cd[start])。（提示：哈夫曼樹中無度數(shù)為 1的結(jié)點 ,則利用教材第 124頁二叉樹的性質(zhì) 3即可得證） C語言實現(xiàn)根據(jù) n個字符（結(jié)點）的權(quán)值求哈夫曼樹及 n個字符的哈夫曼編碼的子程序，并編制主程序main{}調(diào)用該子程序?qū)ζ湔_性進行驗證。 樹求解的算法思想： 3個步驟。 c=f, f=HT[f].parent) { // 從葉子到根逆向求編碼 if (HT[f].lchild==c) cd[ start] = “0”。 //申請 n個字符編碼的頭指針數(shù) 組的存儲空間 cd = (char *)malloc(n*sizeof(char))。 // 在 i1棵子樹中也即 HT[1..i1]中選擇無父親 (parent為 0) //且權(quán)值最小的兩個結(jié)點 (其序號分別為 s1和 s2)。 HT[i].parent=0。 i=n。 HC[i] = (char *)malloc((編碼長度 +1)*sizeof(char))。 //存放表中元素的值 int next 。 例如： 對于剛才的 4個字符的編碼問題，可以按如下不等長編碼方案進行編碼： A: 0 B: 00 C: 1 D: 01 問題： 譯碼時可能出現(xiàn)多意性，即譯碼不唯一： 則對于電文“ ABACCDA”的二進制電碼為： 000011010 總長為 9位 二、哈夫曼樹及其應(yīng)用 ② 壓縮編碼： 例如： 對于剛才的 4個字符的編碼問題，可以按如下不等長編碼方案進行編碼： A: 0 B: 00 C: 1 D: 01 問題： 譯碼時可能出現(xiàn)多意性，即譯碼不唯一： 則對于電文“ ABACCDA”的二進制電碼為： 000011010 總長為 9位 二、哈夫曼樹及其應(yīng)用 ② 壓縮編碼： 例如： 對于剛才的 4個字符的編碼問題，可以按如下不等長編碼方案進行編碼： A: 0 B: 00 C: 1 D: 01 問題： 譯碼時可能出現(xiàn)多意性，即譯碼不唯一。 a 40 b 30 c 5 d 10 e 15 15 求解過程 二、哈夫曼樹及其應(yīng)用 ③ 實例：已知有 5個葉子結(jié)點的權(quán)值分別為： 5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。 有關(guān)概念 二、哈夫曼樹及其應(yīng)用 實例： 已知某二叉樹的四個葉子結(jié)點 a,b,c,d分別帶權(quán) 7， 5， 2， 4，則可構(gòu)造出有如下幾種不同形式的二叉樹： a a a 7 7 7 b 5 b 5 c 2 d 4 c 2 d 4 b 5 c 2 d 4 樹的帶權(quán)路徑長度為： WPL=2*7+2*5+2*2+2*4=36 樹的帶權(quán)路徑長度為： WPL=2*4+3*7+3*5+1*2=46 樹的帶權(quán)路徑長度為： WPL=1*7+2*5+3*2+3*4=35 有關(guān)概念 二、哈夫曼樹及其應(yīng)用 ⑤ 哈夫曼樹的定義： 設(shè)有 n個葉子結(jié)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1