最優(yōu)二叉樹(shù)哈夫曼樹(shù)-閱讀頁(yè)
2025-07-04 06:37本頁(yè)面
【正文】 夫曼樹(shù)的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉結(jié)點(diǎn)所經(jīng)過(guò)的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。所以，對(duì)于第i個(gè)字符，它的哈夫曼編碼存放在HuffCode[i].bit中的從HuffCode[i].start到n的分量上。 {定義最多葉結(jié)點(diǎn)數(shù)}MaxNode=255。 {定義哈夫曼編碼的最大長(zhǎng)度}type HCodeType =record bit: array[0..MaxBit] of integer。 end。 {生成哈夫曼編碼}var HuffNode: array[0..MaxNode] of HCodeType。cd : HcodeType 。begin HuffmanTree (HuffNode )。 c:=i。 while p0 do {由葉結(jié)點(diǎn)向上直到樹(shù)根} if HuffNode[p].lchild=c then []:=0 else []:=1。 c:=p。 end。HuffCode[i].start=。for i:=0 to n1 do {輸出每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼} beginfor j:=HuffCode[i].start+1 to n1 do write(HuffCode[i].bit[j]:10)。 end。 文件的編碼和解碼 通過(guò)從上一節(jié)的學(xué)習(xí)，我們知道了如何利用哈夫曼樹(shù)來(lái)構(gòu)造字符編碼。 對(duì)壓縮后的數(shù)據(jù)文件進(jìn)行解碼則必須借助于哈夫曼樹(shù)T，其過(guò)程是：依次讀人文件的二進(jìn)制碼，從哈夫曼樹(shù)的根結(jié)點(diǎn)(即T[m1])出發(fā)，若當(dāng)前讀人0，則走向左孩子，否則走向右孩子。然后重新從根出發(fā)繼續(xù)譯碼，直至文件結(jié)束。再如，要編制一個(gè)將百分制轉(zhuǎn)換為五級(jí)分制的程序?！境绦蚨巍縤f a60 then b:=’bad’ else if a70 then b:=’pass’ else if a80 then b:=’general’ else if a90 then b:=’good’ else b:=’excellent’。因?yàn)樵趯?shí)際中，學(xué)生的成績(jī)?cè)谖鍌€(gè)等級(jí)上的分布是不均勻的，：分?jǐn)?shù) 0－59 60－69 70－79 80－89 90－100比例數(shù) 分?jǐn)?shù)段的分布頻率則80％以上的數(shù)據(jù)需進(jìn)行三次或三次以上的比較才能得出結(jié)果。但由于每個(gè)判定框都有兩次比較，將這兩次比較分開(kāi)，得到新的判定樹(shù)，按此判定樹(shù)可寫(xiě)出相應(yīng)的程序。假設(shè)有10000個(gè)輸入數(shù)據(jù)，若上程序段的判定過(guò)程進(jìn)行操作，則總共需進(jìn)行31500次比較；而若新判定樹(shù)的判定過(guò)程進(jìn)行操作，則總共僅需進(jìn)行22000次比較。2． 假設(shè)用于通訊的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為13210。如果用0～7這8個(gè)數(shù)的二進(jìn)制數(shù)表示這8個(gè)字母也是一種編碼方案，試比較這兩種方法的優(yōu)劣。二、編寫(xiě)程序題文件壓縮press【問(wèn)題描述】假設(shè)有一張黑白的二進(jìn)制位圖，M行N列（0M,N2048），將位圖用文件存儲(chǔ)時(shí)0表示白、1表示黑，這樣的存儲(chǔ)的文件很大，最大達(dá)2048*2048Byte。但這樣仍然很大，我們剛剛學(xué)習(xí)了哈夫曼編碼，可以先統(tǒng)計(jì)各字符出現(xiàn)的頻率，然后依此進(jìn)行哈夫曼編碼，這樣存儲(chǔ)又將節(jié)省不少空間?，F(xiàn)在請(qǐng)你對(duì)于輸入的由0、1構(gòu)成的文件，以八位為基礎(chǔ)，先統(tǒng)計(jì)頻率然后構(gòu)造哈夫曼樹(shù)，從而進(jìn)行壓縮處理?！据斎搿康谝恍袃蓚€(gè)數(shù)M、N，表示圖形共有M行、每行N列，N mod 8=0?！据敵觥烤鸵恍校硎緣嚎s后形成的編碼的字節(jié)數(shù)（所需存儲(chǔ)空間，8個(gè)二進(jìn)制位為一個(gè)字節(jié)，如果總的二進(jìn)制位數(shù)b除以8有余數(shù)，則輸出b div 8+
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1