[工學(xué)]數(shù)據(jù)結(jié)構(gòu)11樹和二叉樹-在線瀏覽
2025-04-05 08:16本頁(yè)面
【正文】 15 29 11 3 5 8 19 23 42 11 3 5 8 19 23 42 29 14 8 7 15 29 58 11 3 5 8 19 23 42 29 14 8 7 15 29 58 100 最優(yōu)判定 等級(jí) 分?jǐn)?shù)段 比例 A B C D E 0~59 60~69 70~79 80~89 90~100 cini。 } 在解某些判定問題時(shí)，利用哈夫曼樹可以得到最佳判定算法。 等級(jí) 分?jǐn)?shù)段 比例 A B C D E 0~59 60~69 70~79 80~89 90~100 a60 a90 a80 a70 E Y N D Y N C Y N B Y N A 70?a80 a60 C Y N B Y N D Y N E Y N A 80?a90 60?a70 a80 a70 a60 a90 E Y N D Y N C Y N B Y N A If條件語(yǔ)句的判定樹 考慮比例，實(shí)現(xiàn)的比較 考慮比例，減少判定框的兩次比較，實(shí)現(xiàn)的轉(zhuǎn)換 轉(zhuǎn)換五級(jí)分制的判定過程 4 哈夫曼編碼 哈夫曼樹除了能求解最優(yōu)判定問題解，還用于其他一些最優(yōu)問題的求解。 在進(jìn)行數(shù)據(jù)通訊時(shí)，涉及數(shù)據(jù)編碼問題。例如：郵局發(fā)電報(bào)，發(fā)送方將原文轉(zhuǎn)換成二進(jìn)制字符串，接收方將二進(jìn)制字符串還原成原文。 且沒有考慮每種指令的使用頻率。因此利用二叉樹設(shè)計(jì)不等長(zhǎng)編碼： 應(yīng)用中每個(gè)字符的使用頻率是不一樣的。 問：下面的變長(zhǎng)編碼是否可行？ 解答：不行，因?yàn)闄C(jī)器無(wú)法解碼。 如何使機(jī)器能對(duì)變長(zhǎng)編碼產(chǎn)生的編碼串進(jìn)行正確識(shí)別？ 結(jié)論：變長(zhǎng)編碼必須滿足條件： 任意一個(gè)編碼不能稱為其它任意編碼的前綴，把滿足這個(gè)條件的編碼叫做前綴編碼。首先以每條指令的使用頻率為權(quán)值構(gòu)造哈夫曼樹。 從根結(jié)點(diǎn)開始，走到葉子結(jié)點(diǎn)，所經(jīng)過的代碼序列，就構(gòu)成了相應(yīng)指令的哈夫曼編碼。 則，程序總位數(shù)是： 定長(zhǎng)編碼： 3*10000=30000 哈夫曼編碼： 1*400+2*300+3*150+5*50+5*40+5*30+5*30=2200 哈夫曼編碼的平均碼長(zhǎng)為： *1+*2+*3+*5+*5+*5+*5= 例 某通訊系統(tǒng)只使用 8種字符 a、 b、 c、 d、 e、 f、 g、 h，其使用頻率分別為, , ,。 每個(gè)結(jié)點(diǎn)同時(shí)還包含其雙親信息和孩子結(jié)點(diǎn)信息，構(gòu)成一個(gè)靜態(tài)三叉鏈表。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1