資源描述：
《哈夫曼樹編碼譯碼實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目：哈夫曼樹編碼譯碼18課題名稱哈夫曼樹編碼譯碼院系年級(jí)專業(yè)學(xué)號(hào)姓名成績(jī)課題設(shè)計(jì)目的與設(shè)計(jì)意義1、課題設(shè)計(jì)目的：在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引起人們的重視，哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)
2、每一個(gè)源字符出現(xiàn)的估算概率而建立起來的。2、課題設(shè)計(jì)意義：哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)葉子對(duì)應(yīng)的字符的編碼，這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進(jìn)制代碼，輸入二進(jìn)制代碼時(shí)可以編譯成字符串。指導(dǎo)教師：年月日18目 錄第一章需求分析1第二章設(shè)計(jì)要求1第三章概要設(shè)計(jì)2（1）其主要流程圖
3、如圖1-1所示。3（2）設(shè)計(jì)包含的幾個(gè)方面4第四章詳細(xì)設(shè)計(jì)4（1）①哈夫曼樹的存儲(chǔ)結(jié)構(gòu)描述為：4（2）哈弗曼編碼5（3）哈弗曼譯碼7（4）主函數(shù)8（5）顯示部分源程序：8第五章調(diào)試結(jié)果10第六章心得體會(huì)12第七章參考文獻(xiàn)12附錄：1218第一章需求分析在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引起人們的重視，哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹，經(jīng)常應(yīng)用于
4、數(shù)據(jù)壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0
5、”或“1”的序列作為和各個(gè)葉子對(duì)應(yīng)的字符的編碼，這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進(jìn)制代碼，輸入二進(jìn)制代碼時(shí)可以編譯成字符串。第二章設(shè)計(jì)要求對(duì)輸入的一串電文字符實(shí)現(xiàn)哈夫曼編碼，再對(duì)哈夫曼編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長(zhǎng)度能盡可能短，即采用最短碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長(zhǎng)度為L(zhǎng)i，電文中有n種字符，則電文編碼總長(zhǎng)度為∑WiLi。若將
6、此對(duì)應(yīng)到二叉樹上，Wi為葉結(jié)點(diǎn)的權(quán)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度。那么，∑WiLi恰好為二叉樹上帶權(quán)路徑長(zhǎng)度。因此，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼。設(shè)計(jì)實(shí)現(xiàn)的功能：(1)哈夫曼樹的建立；(2)哈夫曼編碼的生成；(3)編碼文件的譯碼。18第三章概要設(shè)計(jì)哈夫曼編譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進(jìn)行譯碼。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，稱之為編碼。
7、構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對(duì)應(yīng)字符的編碼，稱之為哈夫曼編碼。最簡(jiǎn)單的二進(jìn)制編碼方式是等長(zhǎng)編碼。若采用不等長(zhǎng)編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，這樣可能縮短傳送電文的總長(zhǎng)度。哈夫曼樹課用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。18（1）其主要流程圖如圖1-1所示。開始結(jié)束結(jié)點(diǎn)數(shù)是否大于1將data和權(quán)值賦給ht輸出根結(jié)點(diǎn)和權(quán)值調(diào)用SELECT函數(shù)計(jì)算根結(jié)點(diǎn)函數(shù)雙親結(jié)
8、點(diǎn)為兩子結(jié)點(diǎn)之和輸出兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn)是否為根結(jié)點(diǎn)？左子是否為空？此時(shí)編碼為0I<2*N?I++編碼為1否否否右子是否為空是是否否是是是18（2）設(shè)計(jì)包含的幾個(gè)方面：①哈夫曼樹的建立哈夫曼樹的建立由哈夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點(diǎn)的二叉樹。算法的第二步是：將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個(gè)新結(jié)點(diǎn)。顯然要進(jìn)行n－1次合并，所以共產(chǎn)生n－1個(gè)新結(jié)點(diǎn)，它們都是具有兩個(gè)
