哈夫曼樹編碼譯碼實驗報告

哈夫曼樹編碼譯碼實驗報告

ID:12719439

大?。?39.00 KB

頁數(shù):21頁

時間:2018-07-18

哈夫曼樹編碼譯碼實驗報告_第1頁
哈夫曼樹編碼譯碼實驗報告_第2頁
哈夫曼樹編碼譯碼實驗報告_第3頁
哈夫曼樹編碼譯碼實驗報告_第4頁
哈夫曼樹編碼譯碼實驗報告_第5頁
資源描述:

《哈夫曼樹編碼譯碼實驗報告》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目:哈夫曼樹編碼譯碼18課題名稱哈夫曼樹編碼譯碼院系年級專業(yè)學(xué)號姓名成績課題設(shè)計目的與設(shè)計意義1、課題設(shè)計目的:在當(dāng)今信息爆炸時代,如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視,哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式,以哈夫曼樹—即最優(yōu)二叉樹,帶權(quán)路徑長度最小的二叉樹,經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符(例如某文件中的一個符號)進行編碼。這張編碼表的特殊之處在于,它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的。2

2、、課題設(shè)計意義:哈夫曼編碼的應(yīng)用很廣泛,利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑,對路徑上的各分支約定:指向左子樹的分支表示“0”碼,指向右子樹的分支表示“1”碼,取每條路徑上的“0”或“1”的序列作為和各個葉子對應(yīng)的字符的編碼,這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進制代碼,輸入二進制代碼時可以編譯成字符串。指導(dǎo)教師:年月日18目 錄第一章需求分析1第二章設(shè)計要求1第三章概要設(shè)計2(1)其主要流程圖如圖1-1所示。3(2)設(shè)計包含的幾個方面4第四章詳細(xì)設(shè)計4(1)①哈夫曼樹的存儲結(jié)

3、構(gòu)描述為:4(2)哈弗曼編碼5(3)哈弗曼譯碼7(4)主函數(shù)8(5)顯示部分源程序:8第五章調(diào)試結(jié)果10第六章心得體會12第七章參考文獻12附錄:1218第一章需求分析在當(dāng)今信息爆炸時代,如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視,哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式,以哈夫曼樹—即最優(yōu)二叉樹,帶權(quán)路徑長度最小的二叉樹,經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符(例如某文件中的一個符號)進行編碼。這張編碼表的特殊之處在于,它是根據(jù)每一個源

4、字符出現(xiàn)的估算概率而建立起來的(出現(xiàn)概率高的字符使用較短的編碼,反之出現(xiàn)概率低的則使用較長的編碼,這便使編碼之后的字符串的平均期望長度降低,從而達到無損壓縮數(shù)據(jù)的目的)。哈夫曼編碼的應(yīng)用很廣泛,利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑,對路徑上的各分支約定:指向左子樹的分支表示“0”碼,指向右子樹的分支表示“1”碼,取每條路徑上的“0”或“1”的序列作為和各個葉子對應(yīng)的字符的編碼,這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進制代碼,輸入二進制代碼時可以編譯成字符串。第二章設(shè)計要求對輸入的

5、一串電文字符實現(xiàn)哈夫曼編碼,再對哈夫曼編碼生成的代碼串進行譯碼,輸出電文字符串。通常我們把數(shù)據(jù)壓縮的過程稱為編碼,解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時,總希望總長度能盡可能短,即采用最短碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi,編碼長度為Li,電文中有n種字符,則電文編碼總長度為∑WiLi。若將此對應(yīng)到二叉樹上,Wi為葉結(jié)點的權(quán),Li為根結(jié)點到葉結(jié)點的路徑長度。那么,∑WiLi恰好為二叉樹上帶權(quán)路徑長度。因此,設(shè)計電文總長最短的二進制前綴編碼,就是以n種字符出現(xiàn)的頻率作權(quán),構(gòu)造一棵哈夫曼樹,此構(gòu)造過程

6、稱為哈夫曼編碼。設(shè)計實現(xiàn)的功能:(1)哈夫曼樹的建立;(2)哈夫曼編碼的生成;(3)編碼文件的譯碼。18第三章概要設(shè)計哈夫曼編譯碼器的主要功能是先建立哈夫曼樹,然后利用建好的哈夫曼樹生成哈夫曼編碼后進行譯碼。在數(shù)據(jù)通信中,經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符0、1組成的二進制串,稱之為編碼。構(gòu)造一棵哈夫曼樹,規(guī)定哈夫曼樹中的左分之代表0,右分支代表1,則從根節(jié)點到每個葉子節(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點對應(yīng)字符的編碼,稱之為哈夫曼編碼。最簡單的二進制編碼方式是等長編碼。若采用不等長編碼,讓出現(xiàn)頻率高的字符具有較短的編碼,讓

7、出現(xiàn)頻率低的字符具有較長的編碼,這樣可能縮短傳送電文的總長度。哈夫曼樹課用于構(gòu)造使電文的編碼總長最短的編碼方案。18(1)其主要流程圖如圖1-1所示。開始結(jié)束結(jié)點數(shù)是否大于1將data和權(quán)值賦給ht輸出根結(jié)點和權(quán)值調(diào)用SELECT函數(shù)計算根結(jié)點函數(shù)雙親結(jié)點為兩子結(jié)點之和輸出兩子結(jié)點和已構(gòu)造的結(jié)點是否為根結(jié)點?左子是否為空?此時編碼為0I<2*N?I++編碼為1否否否右子是否為空是是否否是是是18(2)設(shè)計包含的幾個方面:①哈夫曼樹的建立哈夫曼樹的建立由哈夫曼算法的定義可知,初始森林中共有n棵只含有根結(jié)點的二叉樹。算法的第二步是:將當(dāng)前森林中的

8、兩棵根結(jié)點權(quán)值最小的二叉樹,合并成一棵新的二叉樹;每合并一次,森林中就減少一棵樹,產(chǎn)生一個新結(jié)點。顯然要進行n-1次合并,所以共產(chǎn)生n-1個新結(jié)點,它們都是具有兩個

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。