《《哈夫曼樹(shù)構(gòu)造》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《哈夫曼樹(shù)構(gòu)造》PPT課件.ppt（27頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1/39,哈夫曼樹(shù)構(gòu)造及其編碼,主講人: 程玉勝,2013.11.29,數(shù)據(jù)結(jié)構(gòu)精品資源共享課,2/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,3/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,4/39,二叉樹(shù)、樹(shù)、森林,N個(gè)結(jié)點(diǎn)的二叉樹(shù)中結(jié)點(diǎn)空域的個(gè)數(shù)是【 ？】,證明的方法：從結(jié)點(diǎn)數(shù)和分支數(shù)兩個(gè)角度來(lái)證明。,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,在一棵度為3的樹(shù)中，其中度為3的結(jié)點(diǎn)

2、數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為 個(gè),思考,樹(shù)、森林到二叉樹(shù)的相互轉(zhuǎn)換,5/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,6/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,7/39,成績(jī)判定問(wèn)題 1,把下面成績(jī)轉(zhuǎn)換為5分制，計(jì)算不同的if語(yǔ)句比較的次數(shù)，假設(shè)100個(gè)學(xué)生。,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,第一種寫(xiě)法：if(cj6) cout

3、“不及格” elseif(cj70) cout“及格” elseif(cj80) cout“中等” elseif(cj90)cout“良好” else cout“優(yōu)秀”,8/39,成績(jī)判定問(wèn)題 2,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,對(duì)應(yīng)的流程圖：,(1)、計(jì)算2種方法在比較次數(shù)上的時(shí)間差異性：,1*5+2*15+3*40+4*30+4*10=315,3*5+3*15+2*40+2*30+2*20=220,(2)、哪個(gè)二叉樹(shù)好？怎樣保證比較次數(shù)最少呢？,最好的 最優(yōu)二叉樹(shù),9/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引

4、入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,10/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,11/39,哈夫曼樹(shù)的相關(guān)定義,樹(shù)的帶權(quán)路徑長(zhǎng)度定義為： 樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 WPL(T) = wklk (對(duì)所有葉子結(jié)點(diǎn)),復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,最優(yōu)二叉樹(shù)（哈夫曼樹(shù)） 使 WPL最小的二叉樹(shù),WPL(T)=72+52+23+43+92 =60,12/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入

5、哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,13/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,14/39,構(gòu)造方法 1,假設(shè)給定n個(gè)權(quán)值的結(jié)點(diǎn)構(gòu)造：,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,（1）：n個(gè)結(jié)點(diǎn)看成n顆樹(shù)F （2）：在F中選取兩個(gè)最小的結(jié)點(diǎn)，作為左 右子樹(shù)，且根結(jié)點(diǎn)的權(quán)值等于左右子 樹(shù)權(quán)值之和 （3）：在F中刪除這兩顆樹(shù)，并把剛得到的 二叉樹(shù)加入F中 （4）：重復(fù)（2）-（3），一棵樹(shù)結(jié)束,15/39,構(gòu)造方法 2,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造

6、哈夫曼編碼,例,已知權(quán)值 W= 5, 6, 2, 9, 7 ,9,5,6,2,7,5,2,7,6,9,7,6,7,13,9,16/39,構(gòu)造方法 3,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,例,9,16,29,5個(gè)葉子結(jié)點(diǎn)，構(gòu)造后有多少個(gè)結(jié)點(diǎn)？,17/39,構(gòu)造算法 1,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,思考,有度為1的結(jié)點(diǎn)嗎？，n個(gè)葉子結(jié)點(diǎn)構(gòu)造的哈夫曼樹(shù)有多少結(jié)點(diǎn)？,算法,數(shù)組 HT1m 存放結(jié)點(diǎn) 其中 m=2n-1 前n 個(gè)(1 n)為葉結(jié)點(diǎn) 最后一個(gè)為根結(jié)點(diǎn) 數(shù)組 HC 1n 存放編碼,18/39,構(gòu)造算法 2,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)

7、相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,算法,void HuffmanCoding (HuffmanTree ,例:設(shè)n=5, w=5,6,2,9,7，試設(shè)計(jì) huffman (m=2*5-1=9),19/39,構(gòu)造算法 2,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,5,2,7,6,9,7,6,7,13,9,1,3,6,1,3,6,7,3,1,2,5,7,20/39,構(gòu)造算法 3,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,1,9,16,29,3,6,2,5,7,4,8,9,7 8 1 3,13 9 2 5,16 9 4 6,29 0 7 8,6 7 6 8

8、7,21/39,構(gòu)造算法 4,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,for( i=n+1;i=m;+i) /構(gòu)造 Huffman樹(shù) Select(HT,i-1, s1, s2); /在HTk(1ki-1)中選擇兩個(gè)其雙親域?yàn)?, / 且權(quán)值最小的結(jié)點(diǎn), / 并返回它們?cè)贖T中的序號(hào)s1和s2 HTs1.parent=i; HTs2 .parent=i; /表示從F中刪除s1,s2 HTi.lch=s1; HTi.rch=s2 ; /s1,s2分別作為i的左右孩子 HTi.weight=HTs1.weight + HTs2 .weight; /i 的權(quán)值為左右孩子權(quán)值之和

9、 ,22/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,23/39,內(nèi)容提要,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,24/39,HFM編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,9,16,29,0,0,0,0,1,1,1,1,00,01,11,100,101,25/39,HFM編碼,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,/從葉子到根逆向求每個(gè)字符的哈夫曼編碼 HC=ne

10、w CodeNoden+1;cd=new charn; cdn-1=0;/編碼結(jié)束符 for(i=1;i=n;+i) /依次求各葉子的編碼 start=n-1;/編碼起始位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lch=c)cd-start=0; else cd-start=1; HCi.bits=new charn-start; /為第i個(gè)葉子分配空間 strcpy(HCi.bits, ,26/39,哈夫曼應(yīng)用,復(fù)習(xí) 知識(shí)點(diǎn)引入 哈夫曼樹(shù)相關(guān)定義 哈夫曼樹(shù)構(gòu)造 哈夫曼編碼,已知某相同在通信聯(lián)絡(luò)中只可能出現(xiàn)8種可能字符，其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11.假設(shè)待發(fā)報(bào)文長(zhǎng)度為100個(gè)字符，請(qǐng)選擇最短報(bào)文，并計(jì)算發(fā)送報(bào)文的長(zhǎng)度。,例,27/39,謝謝 !,歡迎通過(guò)數(shù)據(jù)結(jié)構(gòu)精品課程網(wǎng)站 http:/210.45.168.34:8080/08/sjjg/Learning/SelfLearningDS/index.asp,Thanks for Your Attention,