最優(yōu)二叉樹哈夫曼樹(文件)
【正文】 ger。 end。begin readln(n)。 HuffNode[i].rchild=1。 m2:=MAXVALUE。 x2:=x1。 x2:=j。 HuffNode[n+i].weight:= HuffNode[x1].weight+HuffNode[x2].weight。 end。 (b)所示為另一種編碼方案，用此編碼對(duì)上述電文進(jìn)行編碼所建立的代碼為00010010101100，長(zhǎng)度為14。 表a 表b 表c 表d 字符 編碼 字符 編碼 字符 編碼 字符 編碼 A 000 A 00 A 0 A 01 B 010 B 01 B 110 B 010 C 100 C 10 C 10 C 001 D 111 D 11 D 111 D 10 字符的四種不同的編碼方案 哈夫曼樹可用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。 (d)的編碼方案，字符A的編碼01是字符B的編碼010的前綴部分，這樣對(duì)于代碼串0101001，既是AAC的代碼，也是ABD和BDA的代碼，因此，這樣的編碼不能保證譯碼的唯一性，我們稱之為具有二義性的譯碼。實(shí)現(xiàn)哈夫曼編碼的算法可分為兩大部分： （1）構(gòu)造哈夫曼樹； （2）在哈夫曼樹上求葉結(jié)點(diǎn)的編碼?！厩蠊蚵幋a程序段】const Maxleaf=128。 start: integer。 HuffCode: array[0..MaxLeaf] of HcodeType。 {建立哈夫曼樹}for i:=0 to n1 do {求每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼} begin:=n1。 dec ()。 for j:=+1 to n1 do {保存求出的每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位}begin HuffCode[i].bit[j]:=[j]。 writeln。有了字符集的哈夫曼編碼表之后，對(duì)數(shù)據(jù)文件的編碼過程是：依次讀人文件中的字符c，在哈夫曼編碼表H中找到此字符，若H[i].ch=c，則將字符c轉(zhuǎn)換為H[i].bits中存放的編碼串。 在本章的引入部分，兩個(gè)例子都是判定問題，這兩個(gè)判定問題都可以通過構(gòu)造哈夫曼樹來優(yōu)化判定，以達(dá)到總的判定次數(shù)最少。如果上述程序需反復(fù)使用，而且每次的輸入量很大，則應(yīng)考慮上述程序的質(zhì)量問題，即其操作所需要的時(shí)間。請(qǐng)您自己畫出此判定樹。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。我們知道八位二進(jìn)制可以跟有相同ASCII碼值的一個(gè)字符的建立起對(duì)應(yīng)關(guān)系，如果將位圖以字符的方式存儲(chǔ)，理想狀態(tài)下存儲(chǔ)空間變以原來的1/8。處理的過程中如果出現(xiàn)頻率相同的情況，先考慮序號(hào)小的（即左子樹節(jié)點(diǎn)的權(quán)小于等于右子樹節(jié)點(diǎn)的權(quán)）?！緲永? 16000000111100000000000011110000000000001111000000000000111100000000000011110000000000001111000000000000111100000000000011110000002 {說明：哈夫曼編碼為0101010101010101}10。接下是M行，每行有N個(gè)0或1。其實(shí)JPEG圖形格式就有類似的處理方式。3． 有7個(gè)帶權(quán)結(jié)點(diǎn)a,b,c,d,e,f,g分別帶權(quán)4，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹（請(qǐng)按照左子樹根節(jié)點(diǎn)的權(quán)小于等于右子樹根節(jié)點(diǎn)的權(quán)的次序構(gòu)造）。習(xí)題一、 解答題1． 證明：在結(jié)點(diǎn)數(shù)大于1的哈夫曼樹中不存在度為1的結(jié)點(diǎn)。假定以5，15，40，30和10為權(quán)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1