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

1、.數(shù) 據(jù) 結 構實驗報告實驗名稱：哈夫曼樹學生姓名：袁普班 級：2013211125班班內序號：14號學 號：2013210681日 期：2014年12月1. 實驗目的和內容利用二叉樹結構實現(xiàn)哈夫曼編/解碼器。基本要求：1、 初始化(Init)：能夠對輸入的任意長度的字符串 s進行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立哈夫曼樹2、 建立編碼表(CreateTable)：利用已經建好的哈夫曼樹進行編碼，并將每個字符的編碼輸出。3、 編碼(Encoding)：根據(jù)編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。4、 譯碼(Decoding)：利用已經建好的哈夫曼樹對編碼后的字符串進行譯碼，并輸出譯

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

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

4、點，初始化編碼表 2 算法基本思想：對輸入字符一個一個的統(tǒng)計，并統(tǒng)計出現(xiàn)次數(shù)，構建權值數(shù)組， 3 算法空間、時間復雜度分析：空間復雜度O（1），要遍歷一遍字符串，時間復雜度O（n） 4 代碼邏輯： leaf=0; /初始化葉子節(jié)點個數(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; 構建權值數(shù)組 j+; leaf=j; /葉子節(jié)點個數(shù)即字符個數(shù)

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

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

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

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

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

10、編碼個數(shù) while(parent!=-1) if(child=HTreeparent.lchild) HCodeTablei.codek=0; /左孩子標0 else HCodeTablei.codek=1; /右孩子標1 k+; child=parent; 孩子結點上移 parent=HTreechild.parent; 父節(jié)點也上移 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; /每一個字符編碼的長度，為求編碼總長度做準備 算法5：void Encoding(); 1 算法功能：對輸入的字符串進行編碼 2 算法基本思想：找到每個字符對應的編碼，將編碼按順序輸出 3 算法空間、時間復雜度分析：空間復雜度O(1),時間復雜度0（n） 4 代碼邏輯 coutendl輸入的字符串轉化為哈夫曼編碼為:endl; for (int i=0;stri!=0;i+) 遍歷輸入的每一個字符 for(int j=0;jleaf;j+) if(stri=HCodeTa

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

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