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

1、.數(shù) 據(jù) 結(jié) 構(gòu)實(shí)驗報告實(shí)驗名稱：哈夫曼樹學(xué)生姓名：袁普班 級：2013211125班班內(nèi)序號：14號學(xué) 號：2013210681日 期：2014年12月1. 實(shí)驗?zāi)康暮蛢?nèi)容利用二叉樹結(jié)構(gòu)實(shí)現(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)行譯碼，并輸出譯

2、碼結(jié)果。5、 打印(Print)：以直觀的方式打印哈夫曼樹（選作）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. 程序分析2.1 存儲結(jié)構(gòu)用struct結(jié)構(gòu)類型來實(shí)現(xiàn)存儲樹的結(jié)點(diǎn)類型struct HNode int w

3、eight; /權(quán)值int parent; /父節(jié)點(diǎn)int lchild; /左孩子int rchild; /右孩子;struct HCode /實(shí)現(xiàn)編碼的結(jié)構(gòu)類型 char data; /被編碼的字符char code100; /字符對應(yīng)的哈夫曼編碼; 2.2 程序流程 輸入字符串 統(tǒng)計出現(xiàn)的字符種類和次數(shù)，構(gòu)建權(quán)值數(shù)組，初始化樹結(jié)點(diǎn)與編碼表根據(jù)哈夫曼構(gòu)建規(guī)則構(gòu)建哈夫曼樹，根據(jù)編碼規(guī)則對出現(xiàn)字符進(jìn)行編碼，構(gòu)建編碼表將輸入的字符挨個編碼對編碼后的字符進(jìn)行解碼分析存儲大小2.3 關(guān)鍵算法分析 算法1：void Huffman:Count() 1 算法功能：對出現(xiàn)字符的和出現(xiàn)字符的統(tǒng)計，構(gòu)建權(quán)值結(jié)

4、點(diǎn)，初始化編碼表 2 算法基本思想：對輸入字符一個一個的統(tǒng)計，并統(tǒng)計出現(xiàn)次數(shù)，構(gòu)建權(quán)值數(shù)組， 3 算法空間、時間復(fù)雜度分析：空間復(fù)雜度O（1），要遍歷一遍字符串，時間復(fù)雜度O（n） 4 代碼邏輯： leaf=0; /初始化葉子節(jié)點(diǎn)個數(shù) int i,j=0; int s128=0; 用于存儲出現(xiàn)的字符 for(i=0;stri!=0;i+) 遍歷輸入的字符串 s(int)stri+; 統(tǒng)計每個字符出現(xiàn)次數(shù) for(i=0;i128;i+) if(si!=0) dataj=(char)i; 給編碼表的字符賦值 weightj=si; 構(gòu)建權(quán)值數(shù)組 j+; leaf=j; /葉子節(jié)點(diǎn)個數(shù)即字符個數(shù)

5、for(i=0;ileaf;i+) coutdatai的權(quán)值為：weightiendl; 算法2：void Init(); 1 算法功能：構(gòu)建哈弗曼樹 2 算法基本思想：根據(jù)哈夫曼樹構(gòu)建要求，選取權(quán)值最小的兩個結(jié)點(diǎn)結(jié)合，新結(jié)點(diǎn)加入數(shù)組，再繼續(xù)選取最小的兩個結(jié)點(diǎn)繼續(xù)構(gòu)建。 3 算法空間、時間復(fù)雜度分析：取決于葉子節(jié)點(diǎn)個數(shù)，時間復(fù)雜度O（n），空間復(fù)雜度O（1） 4 代碼邏輯HTree=new HNode2*leaf-1; n2=n0-1，一共需要2n-1個結(jié)點(diǎn)空間 for(int i=0;ileaf;i+) HTreei.weight=weighti; 給每個結(jié)點(diǎn)附權(quán)值 HTreei.lchil

6、d=-1; 初始化左右孩子和父節(jié)點(diǎn)，都為-1 HTreei.rchild=-1; HTreei.parent=-1; int x,y; /用于記錄兩個最小權(quán)值 for(int i=leaf;i2*leaf-1;i+) Selectmin(HTree,i,x,y); 選出兩個最小權(quán)值的結(jié)點(diǎn) HTreex.parent=i; 父節(jié)點(diǎn)設(shè)置為新建立的結(jié)點(diǎn) HTreey.parent=i; HTreei.weight=HTreex.weight+HTreey.weight; 父節(jié)點(diǎn)權(quán)值為兩個相加 HTreei.lchild=x; 使父節(jié)點(diǎn)指向這兩個孩子結(jié)點(diǎn) HTreei.rchild=y; HTreei

7、.parent=-1; 父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為-1 算法3：void Selectmin(HNode*hTree,int n,int&i1,int &i2); 1 算法功能：從現(xiàn)有的結(jié)點(diǎn)中選擇出兩個最小的結(jié)點(diǎn)，返回其位置 2 算法基本思想：先選出兩個沒有構(gòu)建的結(jié)點(diǎn)，然后向后依次比較，篩選出最小的兩個結(jié)點(diǎn) 3 算法空間、時間復(fù)雜度分析：空間復(fù)雜度O(1)，要遍歷所有結(jié)點(diǎn)，時間復(fù) 雜度O(N) 4 代碼邏輯int i;for(i=0;in;i+) /n為現(xiàn)在有的結(jié)點(diǎn)個數(shù)，是個變化值,會有相加后的新權(quán)值加入 if(hTreei.parent=-1) /父節(jié)點(diǎn)不是-1意味著這個結(jié)點(diǎn)還沒有被選擇過i1=i;

8、 記錄結(jié)點(diǎn)位置break; i+; /執(zhí)行一遍for循環(huán)就加1，意為下次查找從當(dāng)前位置開始查找for(;ihTreei2.weight) 進(jìn)行比較，使I1為最小的，I2為第二小的int j=0;j=i2;i2=i1;i1=j; i+;for(;in;i+) 將I1 I2 與后面的結(jié)點(diǎn)進(jìn)行比較if(hTreei.parent=-1&hTreei.weighthTreei1.weight) 如果結(jié)點(diǎn)小于I1i2=i1; 使I2=I1 I1=新結(jié)點(diǎn)i1=i; else if(hTreei.parent=-1&hTreei.weighthTreei2.weight) I1新結(jié)點(diǎn)I2，使I2為新節(jié)點(diǎn)i2

9、=i; 算法4：void CreateTable(); 1 算法功能：對出現(xiàn)的字符進(jìn)行編碼 2 算法基本思想：根據(jù)字符在哈夫曼樹中的位置，從下到上編碼，是左孩子編0，右孩子編1 3 算法空間、時間復(fù)雜度分析：空間復(fù)雜度O(1)，要遍歷data數(shù)組，時間復(fù)雜度0(N) 4 代碼邏輯HCodeTable=new HCodeleaf; 新建編碼結(jié)點(diǎn)，個數(shù)為葉子節(jié)點(diǎn)個數(shù) for(int i=0;ileaf;i+) HCodeTablei.data=datai; int child=i; 初始化要編碼的結(jié)點(diǎn)的位置 int parent=HTreei.parent; 初始化父結(jié)點(diǎn) int k=0; /統(tǒng)計

10、編碼個數(shù) while(parent!=-1) if(child=HTreeparent.lchild) HCodeTablei.codek=0; /左孩子標(biāo)0 else HCodeTablei.codek=1; /右孩子標(biāo)1 k+; child=parent; 孩子結(jié)點(diǎn)上移 parent=HTreechild.parent; 父節(jié)點(diǎn)也上移 HCodeTablei.codek=0; /將編碼反向 char code100; for(int u=0;uk;u+) codeu=HCodeTablei.codek-u-1; for(int u=0;uk;u+) HCodeTablei.codeu=co

11、deu; coutdatai的哈夫曼編碼為：; coutHCodeTablei.codeendl; length3i=k; /每一個字符編碼的長度，為求編碼總長度做準(zhǔn)備 算法5：void Encoding(); 1 算法功能：對輸入的字符串進(jìn)行編碼 2 算法基本思想：找到每個字符對應(yīng)的編碼，將編碼按順序輸出 3 算法空間、時間復(fù)雜度分析：空間復(fù)雜度O(1),時間復(fù)雜度0（n） 4 代碼邏輯 coutendl輸入的字符串轉(zhuǎn)化為哈夫曼編碼為:endl; for (int i=0;stri!=0;i+) 遍歷輸入的每一個字符 for(int j=0;jleaf;j+) if(stri=HCodeTa

12、blej.data) 找到字符對應(yīng)的編碼 s1=s1+HCodeTablej.code; 將所有編碼按順序加起來 coutHCodeTablej.code; 輸出編碼 coutendl;算法6：void Decoding(); 1 算法功能：對編碼串進(jìn)行解碼 2 算法基本思想：找到每段編碼對應(yīng)的字符，輸出字符 3 算法空間、時間復(fù)雜度分析：時間復(fù)雜度0(N)，空間復(fù)雜度0（1） 4 代碼邏輯（可用偽代碼描述） cout解碼后的字符串為: endl; char *s = const_cast(s1.c_str(); 將編碼字符串轉(zhuǎn)化為char while(*s!=0) int parent=2*

13、leaf-2; 父節(jié)點(diǎn)為最后一個節(jié)點(diǎn) while(HTreeparent.lchild!=-1) /還有左子樹，不可能是葉子節(jié)點(diǎn) if(*s=0) 編碼為0，為左孩子 parent=HTreeparent.lchild; else parent=HTreeparent.rchild; 編碼為1，為右孩子 s+; coutHCodeTableparent.data; 輸出字符 coutendl; 注意分析程序的時間復(fù)雜度、內(nèi)存申請和釋放，以及算法思想的體現(xiàn)。2.4 其他在此次試驗中使用了類和STL中的string，使用string可以方便的將單個字符的編碼加起來成為總的編碼后的數(shù)值，再利用STL中的轉(zhuǎn)化函數(shù)可以直接將string轉(zhuǎn)化為char，方便進(jìn)行解碼工作?？偠灾?，使用STL使得編碼大大的簡潔了。3. 程序運(yùn)行結(jié)果分析調(diào)試過程中遇到的問題主要是執(zhí)行時有內(nèi)存錯誤，檢查后發(fā)現(xiàn)是數(shù)組有越界現(xiàn)象，這提醒我在編寫時一定要仔細(xì)，特別是在for循環(huán)條件上一定要注意范圍 總結(jié)4.1實(shí)驗的難點(diǎn)和關(guān)鍵點(diǎn) 首先在輸入字符串時我發(fā)現(xiàn)直接用cin無法輸入空格，在上網(wǎng)查詢后找到了getline函數(shù)解決了這個問題。然后還有就是如何存儲編碼后總的那個字符串，因為每一個字符編碼的長度不