最優(yōu)二叉樹(shù)哈夫曼樹(shù)-wenkub.com
2025-06-16 06:37 本頁(yè)面
【正文】 【輸出】就一行，表示壓縮后形成的編碼的字節(jié)數(shù)（所需存儲(chǔ)空間，8個(gè)二進(jìn)制位為一個(gè)字節(jié)，如果總的二進(jìn)制位數(shù)b除以8有余數(shù)，則輸出b div 8+1）?，F(xiàn)在請(qǐng)你對(duì)于輸入的由0、1構(gòu)成的文件，以八位為基礎(chǔ)，先統(tǒng)計(jì)頻率然后構(gòu)造哈夫曼樹(shù)，從而進(jìn)行壓縮處理。二、編寫(xiě)程序題文件壓縮press【問(wèn)題描述】假設(shè)有一張黑白的二進(jìn)制位圖，M行N列（0M,N2048），將位圖用文件存儲(chǔ)時(shí)0表示白、1表示黑，這樣的存儲(chǔ)的文件很大，最大達(dá)2048*2048Byte。2． 假設(shè)用于通訊的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為13210。但由于每個(gè)判定框都有兩次比較，將這兩次比較分開(kāi)，得到新的判定樹(shù)，按此判定樹(shù)可寫(xiě)出相應(yīng)的程序?！境绦蚨巍縤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’。然后重新從根出發(fā)繼續(xù)譯碼，直至文件結(jié)束。 文件的編碼和解碼 通過(guò)從上一節(jié)的學(xué)習(xí)，我們知道了如何利用哈夫曼樹(shù)來(lái)構(gòu)造字符編碼。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。 while p0 do {由葉結(jié)點(diǎn)向上直到樹(shù)根} if HuffNode[p].lchild=c then []:=0 else []:=1。begin HuffmanTree (HuffNode )。 {生成哈夫曼編碼}var HuffNode: array[0..MaxNode] of HCodeType。 {定義哈夫曼編碼的最大長(zhǎng)度}type HCodeType =record bit: array[0..MaxBit] of integer。所以，對(duì)于第i個(gè)字符，它的哈夫曼編碼存放在HuffCode[i].bit中的從HuffCode[i].start到n的分量上。 下面討論實(shí)現(xiàn)哈夫曼編碼的算法。 在建立不等長(zhǎng)編碼時(shí)，必須使任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴，這樣才能保證譯碼的唯一性。如當(dāng)字符A，B，C， (c)所示的編碼時(shí)，上述電文的代碼為0110010101110，長(zhǎng)度僅為13。在傳送電文時(shí)，我們總是希望傳送時(shí)間盡可能短，這就要求電文代碼盡可能短，顯然，這種編碼方案產(chǎn)生的電文代碼不夠短。 end。 HuffNode[x2].parent:=n+i。endelse if (HuffNode[j].weightm2) and (HuffNode[j].parent=1) then begin m2:=HuffNode[j].weight。 for j:=0 to n+i1 do if (HuffNode[j].weightm1) and (HuffNode[j].parent=1) then begin m2:=m1。 {輸入n個(gè)葉子結(jié)點(diǎn)的權(quán)值} for i:=0 to n1 do {構(gòu)造哈夫曼樹(shù)} begin m1:=MAXVALUE。 HuffNode[i].lchild=1。 {哈夫曼樹(shù)的構(gòu)造算法}var i,j,m1,m2,x1,x2,n: integer。 rchild: integer。 {定義哈夫曼樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)} maxnode=maxleaf*21。構(gòu)造哈夫曼樹(shù)時(shí)，首先將由n個(gè)字符形成的n個(gè)葉結(jié)點(diǎn)存放到數(shù)組HuffNode的前n個(gè)分
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1