課程設(shè)計(jì) 哈夫曼樹(shù)及哈夫曼編碼

1、課程設(shè)計(jì) 設(shè)計(jì) 哈夫曼 哈夫曼樹(shù)及哈夫曼 及哈夫曼編碼 編碼一．課程設(shè)計(jì)簡(jiǎn)介哈夫曼樹(shù)及哈夫曼編碼目的：利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本，試設(shè)計(jì)一個(gè)哈夫曼編碼系統(tǒng)。通過(guò)本課程設(shè)計(jì)，應(yīng)使學(xué)生掌握哈夫曼編碼的特點(diǎn)、存儲(chǔ)方法和基本原理，培養(yǎng)學(xué)生運(yùn)用C語(yǔ)言正確編程及調(diào)試的能力，運(yùn)用數(shù)據(jù)結(jié)構(gòu)解決簡(jiǎn)單的實(shí)際問(wèn)題的能力，為后續(xù)計(jì)算機(jī)專(zhuān)業(yè)課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。題目：一、用下表中給出的字符和頻度數(shù)據(jù)編程建立哈

2、夫曼樹(shù)，并實(shí)現(xiàn)對(duì)以下報(bào)文進(jìn)行編碼。THIS PROGRAM IS MY FAVORITE字符 空格 A B C D E F G H I J K L M頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 二、編程從鍵盤(pán)任意輸入一段報(bào)文，統(tǒng)計(jì)字符的頻度并建立哈夫曼樹(shù)，并給出

3、報(bào)文的編碼。(2) 在森林F中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為一棵新樹(shù)的左、右子樹(shù)，且置新樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)權(quán)值之和(3) 從F中刪除構(gòu)成新樹(shù)的那兩棵，同時(shí)把新樹(shù)加入F中(4) 重復(fù)第(2)和第(3)步，直到F中只含有一棵為止，此樹(shù)便為哈夫曼樹(shù)此部分參考：曲建民 劉元紅 鄭陶然 編著． 數(shù)據(jù)結(jié)構(gòu)（ｃ語(yǔ)言）．清華大學(xué)出版社(2005)(即課本)２．哈夫曼編碼（１）根據(jù)最優(yōu)二叉樹(shù)構(gòu)造哈夫曼編碼利用哈夫曼樹(shù)很容易求出給定字

4、符集及其概率(或頻度)分布的最優(yōu)前綴碼。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。該技術(shù)一般可將數(shù)據(jù)文件壓縮掉20％至90％，其壓縮效率取決于被壓縮文件的特征。（２）具體做法（1）用字符ci作為葉子，pi或fi做為葉子ci的權(quán)，構(gòu)造一棵哈夫曼樹(shù)，并將樹(shù)中左分支和右分支分別標(biāo)記為0和1；（2）將從根到葉子的路徑上的標(biāo)號(hào)依次相連，作為該葉子所表示字符的編碼。該編碼即為最優(yōu)前綴碼（也稱(chēng)哈夫曼編碼）。（３）哈夫曼編碼為最優(yōu)前綴碼由哈夫