北郵數(shù)據(jù)結(jié)構(gòu)哈夫曼樹報告

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：哈夫曼樹學(xué)生姓名：袁普班級：25 班班內(nèi)序號： 14 號學(xué)號：81日期：2014 年12 月1. 實驗?zāi)康暮蛢?nèi)容利用二叉樹結(jié)構(gòu)實現(xiàn)哈夫曼編 / 解碼器?；疽螅?、初始化(Init):能夠?qū)斎氲娜我忾L度的字符用s進(jìn)行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立哈夫曼樹2、建立編碼表(CreateTable)利用已經(jīng)建好的哈夫曼樹進(jìn)行編碼，并將每個 字符的編碼輸出。3、編碼(Encoding):根據(jù)編碼表對輸入的字符串進(jìn)行編碼，并將編碼后的字 符串輸出。4、譯碼(Decoding):利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進(jìn)行譯碼， 并輸出譯碼結(jié)果。5、打印(Print):以直觀

2、的方式打印哈夫曼樹(選作)6 、 計算輸入的字符串編碼前和編碼后的長度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。7 、 可采用二進(jìn)制編碼方式(選作)測試數(shù)據(jù)：I love data Structure, I love Computer。 I will try my best to study data Structure.提示：1 、用戶界面可以設(shè)計為“菜單”方式：能夠進(jìn)行交互。2 、 根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計頻度， 對沒有出現(xiàn)的字符一律不用編碼2. 程序分析存儲結(jié)構(gòu)用 struct 結(jié)構(gòu)類型來實現(xiàn)存儲樹的結(jié)點類型struct HNodeint weight;eigh=W

3、4;ghti;HT閘給每個結(jié)點附權(quán)值初始化左右孩子和父節(jié)點，都為 -1HTre®陽獨樹結(jié)點與編碼表int x,y;arent=i;父節(jié)點設(shè)置為新建立HTreei.parent=-1;的結(jié)點HTreey.parent=i;父節(jié)點權(quán)值為兩個相HTreei.weight=HTreex.weight+HTreey.weight;HTreei.lchild=x;使父節(jié)點指向這兩個孩子結(jié)點HTreei.rchild=y;HTreei.parent=-1;父節(jié)點的父節(jié)點設(shè)為 -1算法 3: void Selectmin(HNode*hTree,int n,int&i1,int &i

4、2);1算法功能：從現(xiàn)有的結(jié)點中選擇出兩個最小的結(jié)點，返回其位置2算法基本思想：先選出兩個沒有構(gòu)建的結(jié)點，然后向后依次比較，篩選出最小的兩個結(jié)點3算法空間、時間復(fù)雜度分析：空間復(fù)雜度 O(1),要遍歷所有結(jié)點，時間復(fù) 雜度 O(N)4代碼邏輯int i;for(i=0;i<n;i+)arent=-1) arent=-1)i2=i;記錄第二個沒選擇過的結(jié)點編號break;if(hTreei1.weight>hTreei2.weight) 進(jìn)行比較，使I1 為最小的， I2 為第二小的int j=0;j=i2;i2=i1;i1=j; i+;for(;i<n;i+)將 I1 I2

5、與后面的結(jié)點進(jìn)行比較if(hTreei.parent=-1&&hTreei.weight<hTreei1.weight) 如果結(jié)點小于I1 i2=i1;使 I2=I1I1=新結(jié)點i1=i; else if(hTreei.parent=-1&&hTreei.weight<hTreei2.weight)I1新結(jié)點I2,使I2為新節(jié)點i2=i; 算法 4： void CreateTable();1 算法功能：對出現(xiàn)的字符進(jìn)行編碼2 算法基本思想： 根據(jù)字符在哈夫曼樹中的位置， 從下到上編碼， 是左孩子編0，右孩子編 13算法空間、時間復(fù)雜度分析：空間復(fù)雜度

6、0(1),要遍歷data數(shù)組，時間復(fù)雜度 0(N)新建編碼結(jié)點，個數(shù)為葉子節(jié)點個數(shù)4 代碼邏輯HCodeTable=new HCodeleaf;for(int i=0;i<leaf;i+)HCodeTablei.data=datai;int child=i;初始化要編碼的結(jié)點的位置int parent=HTreei.parent;初始化父結(jié)點int k=0;child)HCodeTablei.codek='0' odek='1'節(jié)點也上移arent;父HCodeTablei.codek='0'for(int u=0;u<k;u+)HC

7、odeTablei.codeu=codeu;cout<<datai<<" 的哈夫曼編碼為： "cout<<HCodeTablei.code<<endl;length3i=k;的編碼 s1=s1+HCodeTablej.code;cout<<HCodeTablej.code;odek-u-1;ata)找到字符對應(yīng)將所有編碼按順序加起來輸出編碼cout<<endl;算法 6： void Decoding();1 算法功能：對編碼串進(jìn)行解碼2 算法基本思想：找到每段編碼對應(yīng)的字符，輸出字符3算法空間、時間復(fù)雜

8、度分析：時間復(fù)雜度0(N),空間復(fù)雜度0 (1)4 代碼邏輯(可用偽代碼描述)cout<<" 解碼后的字符串為 : "<<endl;char *s = const_cast<char*>();將編碼字符串轉(zhuǎn)化為charwhile(*s!='0')int parent=2*leaf-2;父節(jié)點為最后一個節(jié)點while(HTreeparent.lchild!=-1)child;elseparent=HTreeparent.rchild; 編碼為 1，為右孩子 s+; cout<<HCodeTableparent.d

9、ata; 輸出字符cout<<endl;注意分析程序的時間復(fù)雜度、內(nèi)存申請和釋放，以及算法思想的體現(xiàn)。其他在此次試驗中使用了類和STL中的string,使用string可以方便的將單個字符的編碼加起來成為總的編碼后的數(shù)值，再利用 STL 中的轉(zhuǎn)化函數(shù)可以直接將string 轉(zhuǎn)化為char,方便進(jìn)行解碼工作?？偠灾褂肧TL使得編碼大大的簡潔了。3. 程序運行結(jié)果分析調(diào)試過程中遇到的問題主要是執(zhí)行時有內(nèi)存錯誤， 檢查后發(fā)現(xiàn)是數(shù)組有越界現(xiàn)象，這提醒我在編寫時一定要仔細(xì)，特別是在 for 循環(huán)條件上一定要注意范圍C :Wi n d owssyste m 32cmd .exe清湎人一段

10、字將串，檸回三遍結(jié)束;沙狗物者輸入法學(xué);C:Windowssystem32cmd.exe011UB10001VUlVTLVi 011110H1011011011011 Q1Q001010111Gil SOSsiiioe 001B mom 0Q11S31工& 213 ?巾一4F ri 馬 馬 nprrprrTTiTTiTTrprrmTTiprrprrp-zrT年.也一le三口 一口 T 一0 一q 一口一巾一電編編編編編編拐編編編編編編編編編編T 為為為為曇昊u K曼e曇曼曼OWUL戛曼0WHL懸曼 isw夫夫夫大夫夫夫夫夫夫夫夫夫夫夫夫 哈哈哈皓哈哈哈哈，雷目后富哈哈哈陌 n” Jl

11、1¥/1" l"!h“l(fā)3-卜3e 研/-|" 5 - - - ptL- .L .E tL -E t .E- tL-.E .匚,E -211-tk, -£tl-J二r1 J二七二出二 a -qrwCWindoi/vAsysterTi 32crnd.exe人為字符串轉(zhuǎn)化為哈夫曼編碼為:用碼后的字符串為，lave data £t jmjlc t uiro, I Lou a Computefl uill t i»w my Jbest to stud u data £ti?uc tm'e需49緋?it t bB 133 38 : .，為 1Z 曼曼曼曼曼曇具 天夫夫夫夫夫夫 哈哈哈哈哈哈哈IM TR 口 6 1 6 石工 11011總結(jié)實驗的難點和關(guān)鍵點首先在輸入字符串時我發(fā)現(xiàn)直接用cin無法輸入空格，在上網(wǎng)查詢后找到了getline函數(shù)解決了這個問題。然后還有就是如何存儲編碼后總的那個字符串，因為每一個字符編碼的長度不定，無法用 char數(shù)組來存儲，于是用了string的相加函數(shù)來將所有