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