北郵數(shù)據(jù)結構哈夫曼樹報告

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

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

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

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

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

6、0(1),要遍歷data數(shù)組，時間復雜度 0(N)新建編碼結點，個數(shù)為葉子節(jié)點個數(shù)4 代碼邏輯HCodeTable=new HCodeleaf;for(int i=0;i<leaf;i+)HCodeTablei.data=datai;int child=i;初始化要編碼的結點的位置int parent=HTreei.parent;初始化父結點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)找到字符對應將所有編碼按順序加起來輸出編碼cout<<endl;算法 6： void Decoding();1 算法功能：對編碼串進行解碼2 算法基本思想：找到每段編碼對應的字符，輸出字符3算法空間、時間復雜

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

10、字將串，檸回三遍結束;沙狗物者輸入法學;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總結實驗的難點和關鍵點首先在輸入字符串時我發(fā)現(xiàn)直接用cin無法輸入空格，在上網(wǎng)查詢后找到了getline函數(shù)解決了這個問題。然后還有就是如何存儲編碼后總的那個字符串，因為每一個字符編碼的長度不定，無法用 char數(shù)組來存儲，于是用了string的相加函數(shù)來將所有