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

1、成績評定教師簽名嘉應(yīng)學(xué)院 計算機(jī)學(xué)院實(shí)驗(yàn)報告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計2017-2018學(xué)年第2學(xué)期哈夫曼樹課程名稱： 開課學(xué)期: 班 級: 指導(dǎo)老師: 實(shí)驗(yàn)題目： 學(xué) 號: 姓 名: 上機(jī)時間：一、實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)的目的是通過對簡單的哈夫曼編 / 譯碼系統(tǒng)的設(shè)計與實(shí)現(xiàn)來熟練掌握 樹形結(jié)構(gòu)在實(shí)際問題中的應(yīng)用二、實(shí)驗(yàn)問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高通信利用率，縮短信息傳輸時間， 降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼， 在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼， 此試驗(yàn)即設(shè)計這樣的一個簡單的編 / 譯碼系統(tǒng) 系統(tǒng)應(yīng)該具備如下的幾個功能。1、求出各個葉子節(jié)點(diǎn)的權(quán)重值輸入一個字符串，

2、統(tǒng)計其中各個字母的個數(shù)和總的字母個數(shù)。2、構(gòu)造哈夫曼樹 統(tǒng)計出的字母種類為葉子結(jié)點(diǎn)個數(shù)，每個字母個數(shù)為相應(yīng)的權(quán)值，建立哈 夫曼樹。3、打印哈弗曼樹的功能模塊按照一定形式打印出哈夫曼樹4、編碼 利用已經(jīng)建立好的哈夫曼樹進(jìn)行編碼5、譯碼根據(jù)編碼規(guī)則對輸入的代碼進(jìn)行翻譯并將譯碼三、實(shí)驗(yàn)步驟1、實(shí)驗(yàn)問題分析1) 設(shè)計一個結(jié)構(gòu)體數(shù)組保存字母的類型和個數(shù);字母的種類;字母的個數(shù)點(diǎn)八、;2) 在構(gòu)造哈夫曼樹時，設(shè)計一個結(jié)構(gòu)體數(shù)組保存哈夫曼樹中各結(jié)的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個結(jié)點(diǎn)的哈夫曼樹共有21個結(jié)點(diǎn), 所以數(shù)組大小設(shè)置為 21,描述結(jié)點(diǎn)的數(shù)據(jù)類型為：;權(quán)值;雙親;左孩子;右孩子;定義此類型的數(shù)組

3、3）求哈夫曼編碼，實(shí)質(zhì)上是在已經(jīng)建立的哈夫曼樹中，從葉子結(jié)點(diǎn)開始， 沿著結(jié)點(diǎn)的雙親鏈表域退回到根節(jié)點(diǎn)，每退回一步，就走過了哈夫曼樹的一 個分支，從而得到一位哈夫曼值，由于一個字符的哈夫曼編碼是從根結(jié)點(diǎn)所 經(jīng)過的路徑上各分支所組成的 0、1 序列，因此先得到的分支代碼為所求編 碼的低位碼，后得到的分支代碼為所求編碼的高位碼，所以設(shè)計如下的數(shù)據(jù) 類型：10;每個結(jié)點(diǎn)的哈夫曼編碼; 開始位置;4）設(shè)置全局變量。s; 為輸入的字符串0;記錄輸入的字符串中字母的種類，即葉子結(jié)點(diǎn)個數(shù)0; 記錄字符串中字母的總個數(shù) 葉子結(jié)點(diǎn)類型2、功能（函數(shù)）設(shè)計1 ） 統(tǒng)計字母種類和個數(shù)模塊 此模塊的功能為從鍵盤接受一個

4、字符串， 統(tǒng)計字符串中字母種類即結(jié) 點(diǎn)個數(shù)，每種字母出現(xiàn)次數(shù)即各葉子結(jié)點(diǎn)的權(quán)值。 全局變量 s 保存輸 入的字符串，將種類和個數(shù)保存到 中。函數(shù)原型： （） 如輸入的字符串是“”則顯示如下。(2) 哈夫曼樹的建立模塊此模塊的功能為從(1)中計算出的結(jié)點(diǎn)個數(shù)和各個葉子結(jié)點(diǎn)的權(quán)值 構(gòu)造一棵哈弗曼樹。函數(shù)原型：* ()函數(shù)返回結(jié)點(diǎn)類型的數(shù)組(3) 打印哈弗曼樹的功能模塊此模塊的功能是將由(2)建立的哈弗曼樹按照一定規(guī)則 <>打印在屏幕 上。函數(shù)原型：(*)如輸入的字符串是”，則構(gòu)造的哈夫曼樹為哈弗曼樹ue igfhtlchlldrcliildparent1-1-142-11434-1 -

5、1-15G301562461035-1(4) 建立哈夫曼編碼的功能模塊此模塊功能為將(2)中建立的哈夫曼樹進(jìn)行哈弗曼編碼，然后將字符與對應(yīng)的0、1代碼串打印到屏幕上。函數(shù)原型：(*)如輸入的字符串是“”，則每個字母的代碼和輸入的字符串的哈夫曼編 碼是空弗曼編碼的代帀雇"d的代碼是皿:的代碼是他前入的字符串的哈夫曼編碼為;111ill11101S10B00B（5）譯碼的功能模塊此模塊的功能為接收需要譯碼的 0和1代碼串，按照（4）中建立的編 碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，并將翻譯的結(jié) 果在屏幕上打印出來。函數(shù)原型：（*）如輸入的代碼串是“ 110111100'

6、,則對應(yīng)的字符串是“”請輸入代碼串:110111100譯碼結(jié)果一一 sdf g請按任意犍繼練四、實(shí)驗(yàn)結(jié)果（程序）及分析1、實(shí)驗(yàn)主要模塊代碼（一）函數(shù)功能：統(tǒng)計字母種類和個數(shù)模塊（）為輸入的字符串<<"請輸入字符串"<<； >>s;（Sv）;(0<)(j1 j<m1) m21; x21; m1j;x1;1記錄最小重權(quán)值在數(shù)組中的下標(biāo)(j1 j<m2)m2j;x2;2記錄次小重權(quán)值在數(shù)組中的下標(biāo)x1;x2;12;0001；(1<)統(tǒng)計s中字母種類和個數(shù)(0<)(mk)m;(m> n)k n1; (0<

7、)輸出種類和個數(shù)<<"字符"vvmvv"有"vvmvv"個"<<(二) 函數(shù)功能：哈弗曼樹的建立模塊* ()* ;J1212;1記錄最小的重權(quán)值，m2為次小(0<2*1)結(jié)點(diǎn)初始化i1;i0;i1;i1;(0<)將每個字母的個數(shù)當(dāng)做葉子結(jié)點(diǎn)的權(quán)值ii;(0<1)m12;x12=0;；返回數(shù)組首地址(三) 函數(shù)功能：打印哈弗曼樹的功能模塊(*)<<<<<<界面優(yōu)化VV"哈弗曼樹"<<；<<""&l

8、t;<""<<""<<""<<""<<""<<""<<""<<界面優(yōu)化 (0<2*1)<<""<<i<<"IIvvivvII"<<i<<""<<i<<(四) 函數(shù)功能：建立哈弗曼編碼的功能模塊(*);(0<)求每個

9、結(jié)點(diǎn)的哈弗曼編碼1;Jc;(1)由葉子結(jié)點(diǎn)向上直到樹根(p)=0;=1;c;(1<)將結(jié)果保存ijj保存每位號碼i;保存開始位置<<<<<<<<"哈弗曼編碼"<<(0<)打印各個字母對應(yīng)的編碼<<""<<vvivv" 的代碼是"；(i1v)<<ij；<<；<<""<<；<<<<"輸入的字符串的哈夫曼編碼為："<<(0&

10、lt;)打印輸入的字符串的編碼結(jié)果(0<)匚(siy)( yi<)<<yj;<<(五) 函數(shù)功能：譯碼的功能模塊(*)；記錄輸入的0,1代碼t；<<<<<<<<"請輸入代碼串:">>0;();確定0，1代碼長度*2*2;<<<<<<<<"譯碼結(jié)果"<<(0<)(i'0')從根向下>>(>1 >1)如果到達(dá)葉子結(jié)點(diǎn)>保存葉子結(jié)點(diǎn)的權(quán)值(0<)(j

11、)<<j;輸出權(quán)值的對應(yīng)的字母J2*2;重新從根節(jié)點(diǎn)開始<<2、測試數(shù)據(jù)實(shí)驗(yàn)結(jié)果截圖乞個ssXAAAS寸 5 12 3 賀1-1有有有有 s f d »哈弗曼樹一一.uts ight512lchlld-1-1-1-1G11vchild-1-1-1-1245parent-1的代碼是0渝入的字符串的哈夫曼編碼為;BQQflR請輸入代碼串= 0110111103、調(diào)試過程中出現(xiàn)的問題以及解決策略譯碼模塊中，如果輸入的代碼串無對應(yīng)的字母，則會出錯 解決辦法：提示用戶輸入時注意;()*J1212;1記錄最小的重權(quán)值，m2為次小(0<2*1)結(jié)點(diǎn)初始化(0<)

12、將每個字母的個數(shù)當(dāng)做葉子結(jié)點(diǎn)的權(quán)值ii；(0<1)m12;x12=0;(0<)(j1j<m1)m21;x21;m1j;x1;1記錄最小重權(quán)值在數(shù)組中的下標(biāo)(j1j<m2)m2j;x2;2記錄次小重權(quán)值在數(shù)組中的下標(biāo) x1; x2;(*);J(0<)求每個結(jié)點(diǎn)的哈弗曼編碼1;Jc;(1)由葉子結(jié)點(diǎn)向上直到樹根(p)(1<) 將結(jié)果保存ijj保存每位號碼i; 保存開始位置|VVVVVV；<<"哈弗曼編碼"<<(0<)打印各個字母對應(yīng)的編碼<<""<<；5<<

13、i<<"的代碼是"<<<<'輸入的字符串的哈夫曼編碼為："<<(0<)打印輸入的字符串的編碼結(jié)果(0<)一(siy)( yi<)<<yj;<<(*)<<<<<<；<<"哈弗曼樹"<<<<" "<<""<<""<<""<<界面優(yōu)化(0<2*1)<<" vvivv"<<""<<i<<""<<i"<<i<<II(*