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

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

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

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

4、2);1算法功能：從現(xiàn)有的結(jié)點(diǎn)中選擇出兩個(gè)最小的結(jié)點(diǎn)，返回其位置2算法基本思想：先選出兩個(gè)沒(méi)有構(gòu)建的結(jié)點(diǎn)，然后向后依次比較，篩選出最小的兩個(gè)結(jié)點(diǎn)3算法空間、時(shí)間復(fù)雜度分析：空間復(fù)雜度 O(1),要遍歷所有結(jié)點(diǎn)，時(shí)間復(fù) 雜度 O(N)4代碼邏輯int i;for(i=0;i<n;i+)arent=-1) arent=-1)i2=i;記錄第二個(gè)沒(méi)選擇過(guò)的結(jié)點(diǎn)編號(hào)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é)點(diǎn)進(jìn)行比較if(hTreei.parent=-1&&hTreei.weight<hTreei1.weight) 如果結(jié)點(diǎn)小于I1 i2=i1;使 I2=I1I1=新結(jié)點(diǎn)i1=i; else if(hTreei.parent=-1&&hTreei.weight<hTreei2.weight)I1新結(jié)點(diǎn)I2,使I2為新節(jié)點(diǎn)i2=i; 算法 4： void CreateTable();1 算法功能：對(duì)出現(xiàn)的字符進(jìn)行編碼2 算法基本思想： 根據(jù)字符在哈夫曼樹(shù)中的位置， 從下到上編碼， 是左孩子編0，右孩子編 13算法空間、時(shí)間復(fù)雜度分析：空間復(fù)雜度

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

8、度分析：時(shí)間復(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é)點(diǎn)為最后一個(gè)節(jié)點(diǎn)while(HTreeparent.lchild!=-1)child;elseparent=HTreeparent.rchild; 編碼為 1，為右孩子 s+; cout<<HCodeTableparent.d

9、ata; 輸出字符cout<<endl;注意分析程序的時(shí)間復(fù)雜度、內(nèi)存申請(qǐng)和釋放，以及算法思想的體現(xiàn)。其他在此次試驗(yàn)中使用了類(lèi)和STL中的string,使用string可以方便的將單個(gè)字符的編碼加起來(lái)成為總的編碼后的數(shù)值，再利用 STL 中的轉(zhuǎn)化函數(shù)可以直接將string 轉(zhuǎn)化為char,方便進(jìn)行解碼工作?？偠灾?，使用STL使得編碼大大的簡(jiǎn)潔了。3. 程序運(yùn)行結(jié)果分析調(diào)試過(guò)程中遇到的問(wèn)題主要是執(zhí)行時(shí)有內(nèi)存錯(cuò)誤， 檢查后發(fā)現(xiàn)是數(shù)組有越界現(xiàn)象，這提醒我在編寫(xiě)時(shí)一定要仔細(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é)實(shí)驗(yàn)的難點(diǎn)和關(guān)鍵點(diǎn)首先在輸入字符串時(shí)我發(fā)現(xiàn)直接用cin無(wú)法輸入空格，在上網(wǎng)查詢(xún)后找到了getline函數(shù)解決了這個(gè)問(wèn)題。然后還有就是如何存儲(chǔ)編碼后總的那個(gè)字符串，因?yàn)槊恳粋€(gè)字符編碼的長(zhǎng)度不定，無(wú)法用 char數(shù)組來(lái)存儲(chǔ)，于是用了string的相加函數(shù)來(lái)將所有