《《哈夫曼樹構(gòu)造》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《哈夫曼樹構(gòu)造》PPT課件.ppt（27頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、1/39,哈夫曼樹構(gòu)造及其編碼,主講人: 程玉勝,2013.11.29,數(shù)據(jù)結(jié)構(gòu)精品資源共享課,2/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,3/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,4/39,,二叉樹、樹、森林,N個結(jié)點(diǎn)的二叉樹中結(jié)點(diǎn)空域的個數(shù)是【 ？】,證明的方法：從結(jié)點(diǎn)數(shù)和分支數(shù)兩個角度來證明。,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,在一棵度為3的樹中，其中度為3
2、的結(jié)點(diǎn)數(shù)為2個，度為2的結(jié)點(diǎn)數(shù)為1個，度為1的結(jié)點(diǎn)數(shù)為2個，則度為0的結(jié)點(diǎn)數(shù)為 個,思考,樹、森林到二叉樹的相互轉(zhuǎn)換,5/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,6/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,7/39,,成績判定問題 1,把下面成績轉(zhuǎn)換為5分制，計(jì)算不同的if語句比較的次數(shù)，假設(shè)100個學(xué)生。,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,第一種寫法：if(c
3、j<6) cout<<“不及格” elseif(cj<70) cout<<“及格” elseif(cj<80) cout<<“中等” elseif(cj<90)cout<<“良好” else cout<<“優(yōu)秀”,8/39,,成績判定問題 2,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,對應(yīng)的流程圖：,(1)、計(jì)算2種方法在比較次數(shù)上的時間差異性：,1*5+2*15+3*40+4*30+4*10=315,3*5+3*15+2*40+2*30+2*20=220,(2)、哪個二叉樹好？怎樣保證比較次數(shù)最少呢？,最好的 最優(yōu)二叉樹,9/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入 哈夫
4、曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,10/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,11/39,,哈夫曼樹的相關(guān)定義,樹的帶權(quán)路徑長度定義為： 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和 WPL(T) = wklk (對所有葉子結(jié)點(diǎn)),復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,最優(yōu)二叉樹（哈夫曼樹） 使 WPL最小的二叉樹,WPL(T)=72+52+23+43+92 =60,12/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入
5、 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,13/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,14/39,,構(gòu)造方法 1,假設(shè)給定n個權(quán)值的結(jié)點(diǎn)構(gòu)造：,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,（1）：n個結(jié)點(diǎn)看成n顆樹F （2）：在F中選取兩個最小的結(jié)點(diǎn)，作為左 右子樹，且根結(jié)點(diǎn)的權(quán)值等于左右子 樹權(quán)值之和 （3）：在F中刪除這兩顆樹，并把剛得到的 二叉樹加入F中 （4）：重復(fù)（2）-（3），一棵樹結(jié)束,1
6、5/39,,構(gòu)造方法 2,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,例,已知權(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í) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,例,9,16,,,29,,,5個葉子結(jié)點(diǎn)，構(gòu)造后有多少個結(jié)點(diǎn)？,17/39,,構(gòu)造算法 1,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,思考,有度為1的結(jié)點(diǎn)嗎？，n個葉子結(jié)點(diǎn)構(gòu)造的哈夫曼樹有多少結(jié)點(diǎn)？,算法,數(shù)組 HT1m 存放結(jié)點(diǎn) 其中 m=2n-1 前n 個(1 n)
7、為葉結(jié)點(diǎn) 最后一個為根結(jié)點(diǎn) 數(shù)組 HC 1n 存放編碼,18/39,,構(gòu)造算法 2,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(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í) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(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í) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造
8、哈夫曼編碼,,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 7,21/39,,構(gòu)造算法 4,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,for( i=n+1;i<=m;++i) //構(gòu)造 Huffman樹 Select(HT,i-1, s1, s2); //在HTk(1ki-1)中選擇兩個其雙親域?yàn)?, // 且權(quán)值最小的結(jié)點(diǎn), // 并返回它們在HT中的序號s1和s2 HTs1.parent=i; HTs2 .parent=i
9、; //表示從F中刪除s1,s2 HTi.lch=s1; HTi.rch=s2 ; //s1,s2分別作為i的左右孩子 HTi.weight=HTs1.weight + HTs2 .weight; //i 的權(quán)值為左右孩子權(quán)值之和 ,22/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,23/39,內(nèi)容提要,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,24/39,,HFM編碼,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義
10、哈夫曼樹構(gòu)造 哈夫曼編碼,9,16,,,29,,,0,0,0,0,1,1,1,1,00,01,11,100,101,25/39,,HFM編碼,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,//從葉子到根逆向求每個字符的哈夫曼編碼 HC=new 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; els
11、e cd--start=1; HCi.bits=new charn-start; //為第i個葉子分配空間 strcpy(HCi.bits, ,26/39,,哈夫曼應(yīng)用,復(fù)習(xí) 知識點(diǎn)引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(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)文長度為100個字符，請選擇最短報(bào)文，并計(jì)算發(fā)送報(bào)文的長度。,例,27/39,謝謝 !,歡迎通過數(shù)據(jù)結(jié)構(gòu)精品課程網(wǎng)站 http://210.45.168.34:8080/08/sjjg/Learning/SelfLearningDS/index.asp,,Thanks for Your Attention,
《哈夫曼樹構(gòu)造》PPT課件.ppt
