哈夫曼樹_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、《 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 》課程設(shè)計 》課程設(shè)計——赫夫曼編碼 赫夫曼編碼/譯碼器 譯碼器設(shè)計 設(shè)計指導(dǎo)教師：孫樹 孫樹森、周 森、周維達(dá)班級：09 數(shù)媒（ 數(shù)媒（2）班 ）班學(xué)號： 學(xué)號：E09700203姓名：林真超 姓名：林真超1一、 一、實驗 實驗?zāi)康?目的1 進(jìn)一步掌握最優(yōu)二叉樹的含義。2 掌握最優(yōu)二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點及使用范圍。3 熟練掌握哈夫曼樹的建立和哈夫曼編碼方法。4 掌握用指針類型描述、訪問和處理運

2、算。二、 二、實驗 實驗原理 原理哈夫曼（Huffman）編碼屬于碼詞長度可變的編碼類，是哈夫曼在 1952 年提出的一種編碼方法，即從下到上的編碼方法。同其他碼詞長度可變的編碼一樣，可區(qū)別的不同碼詞的生成是基于不同符號出現(xiàn)的不同概率。生成哈夫曼編碼算法基于一種稱為“編碼樹”（coding tree）的技術(shù)。算法步驟如下：（1）初始化，根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M(jìn)行排序。（2）把概率最小的兩個符號組成一個新符號（節(jié)點），即新

3、符號的概率等于這兩個符號概率之和。（3）重復(fù)第 2 步，直到形成一個符號為止（樹），其概率最后等于 1。（4）從編碼樹的根開始回溯到原始的符號，并將每一下分枝賦值為 1，上分枝賦值為 0。譯碼的過程是分解電文中字符串，從根出發(fā)，按字符“0”或“1”確定找做孩子或右孩子，直至葉子節(jié)點，便求得該子串相應(yīng)的字符。三、 三、實驗 實驗內(nèi)容 內(nèi)容（一）需求分析 （一）需求分析一個完整的系統(tǒng)應(yīng)具有以下功能：(1) I：初始化。從終端讀入字符集大小