資源描述：
《課程設(shè)計哈夫曼樹及哈夫曼編碼》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、課程設(shè)計哈夫曼樹及哈夫曼編碼一.課程設(shè)計簡介哈夫曼樹及哈夫曼編碼目的：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本，試設(shè)計一個哈夫曼編碼系統(tǒng)。通過本課程設(shè)計，應(yīng)使學(xué)生掌握哈夫曼編碼的特點、存儲方法和基木原理，培養(yǎng)學(xué)牛運用C語言正確編程及調(diào)試的能力，運用數(shù)據(jù)結(jié)構(gòu)解決簡單的實際問題的能力，為后續(xù)計算機專業(yè)課程的學(xué)習(xí)打下堅實的基礎(chǔ)。題目：一、用下表中給出的字符和頻度數(shù)據(jù)編程建立哈夫曼樹，并實現(xiàn)對以下報文進行編碼。THISPROGRAMISMYFAVORITE字符空格ABCDEFGHIJKLM頻度186641
2、3223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161二、編程從鍵盤任意輸入一段報文，統(tǒng)計字符的頻度并建立哈夫曼樹，并給出報文的編碼。二.哈夫曼編碼的基木原理和方法哈夫曼編碼是根據(jù)可變長最佳編碼定理，應(yīng)用哈夫曼算法而產(chǎn)生的一種編碼，是消除編碼冗余度最常用的方法。它的平均碼字長度在具有相同輸入概率集合的前提下，比其它任何一種可譯碼都小，因此，也常被稱為緊湊碼。1.哈夫曼樹原理：一般而言，給定n個實數(shù)wl,w2,,wn(n^2),求一個具有n個結(jié)點的二叉數(shù)，使其帶權(quán)路徑
3、長度最小。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度(若根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù))。樹的帶權(quán)路徑長度記為WPL=(Wl*Ll+W2*L2+W3*L3+???+Wn*Ln),N個權(quán)值Wi(i=l,2,…n)構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為Li(i二1,2,...“?？梢宰C明哈夫曼樹的WPL是最小的。哈夫曼在上世紀五十年代初就提出這種編碼時，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應(yīng)符號岀現(xiàn)概率的
4、大小的逆序排列，則編碼的平均長度是最小的。(注：碼字即為符號經(jīng)哈夫曼編碼后得到的編碼，其長度是因符號出現(xiàn)的概率而不同，所以說哈夫曼編碼是變長的編碼。)由于哈夫曼給出了構(gòu)造這種樹的規(guī)律，將給定結(jié)點構(gòu)成一棵帶權(quán)樹的路徑長度最小的二叉數(shù)，因此稱為哈夫曼樹。方法：(1)根據(jù)與n個權(quán)值｛wl,w2???wn｝對應(yīng)的n個結(jié)點構(gòu)成具有n棵二叉樹的森林F二｛Tl,T2???Tn｝,其中第i棵二叉樹Ti(lWiWn)都只有一個權(quán)值為wi的根結(jié)點，其左、右子樹均為空（2）在森林F屮選出兩棵根結(jié)點的權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結(jié)點的
5、權(quán)值為其左、右子樹上根結(jié)點權(quán)值之和（3）從F中刪除構(gòu)成新樹的那兩棵，同時把新樹加入F中（4）重復(fù)第（2）和第（3）步，直到F中只含有一棵為止，此樹便為哈夫曼樹此部分參考：曲建民劉元紅鄭陶然編著.數(shù)據(jù)結(jié)構(gòu)（c語言）.清華大學(xué)出版社（2005）（即課本）1.哈夫曼編碼（1）根據(jù)最優(yōu)二叉樹構(gòu)造哈夫曼編碼利用哈夫曼樹很容易求出給定字符集及其概率（或頻度）分布的最優(yōu)前綴碼。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。該技術(shù)一般可將數(shù)據(jù)文件壓縮掉20%至90%,其壓縮效率取決于被壓縮文件的特征。（2）具體做法（1）用字符ci作為葉子，p
6、i或fi做為葉子ci的權(quán)，構(gòu)造一棵哈夫曼樹，并將樹屮左分支和右分支分別標(biāo)記為0和1；（2）將從根到葉子的路徑上的標(biāo)號依次相連，作為該葉子所表示字符的編碼。該編碼即為最優(yōu)前綴碼（也稱哈夫曼編碼）。（3）哈夫曼編碼為最優(yōu)前綴碼由哈夫曼樹求得編碼為最優(yōu)前綴碼的原因:①每個葉子字符ci的碼長恰為從根到該葉子的路徑長度li,平均碼長（或文件總長）乂是二叉樹的帶權(quán)路徑長度WPLo而哈夫曼樹是WPL最小的二叉樹，因此編碼的平均碼長（或文件總長）亦最小。②樹屮沒有一片葉子是另一葉子的祖先，每片葉子對應(yīng)的編碼就不可能是其它葉子編碼的前綴。即上述編碼是
7、二進制的前綴碼。（4）求哈夫曼編碼的算法思想方法給定字符集的哈夫曼樹生成后，求哈夫曼編碼的具體實現(xiàn)過程是：依次以葉子T[i]（OWiWn-1）為出發(fā)點，向上冋溯至根為止。上溯吋走左分支則生成代碼0,走右分支則生成代碼1。注意：①由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依次存放在一個臨時向量屮，并設(shè)一個指針start指示編碼在該向量屮的起始位置（start初始13寸指示向量的結(jié)束位置）。②當(dāng)某字符編碼完成時，從臨時向量的start處將編碼復(fù)制到該字符相應(yīng)的位串bits中即可。③因為字符集大小為n,故變長編碼的長度不會超過
8、n,加上一個結(jié)束符'[message]*,bits的大小應(yīng)為n+1。（5）文件的編碼和解碼：有了字符集的哈夫曼編碼表之后，對數(shù)據(jù)文件的編碼過程是：依次讀人文件中的字符c,在哈夫曼編碼表H中找到此字符，若H.ch=c，則將字符c轉(zhuǎn)換為H
