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

word數(shù) 據(jù) 結(jié) 構(gòu)實驗報告實驗名稱：哈夫曼樹學生：袁普班 級：2013211125班班序號：14號學 號：2013210681日 期：2014年12月1. 實驗目的和容利用二叉樹結(jié)構(gòu)實現(xiàn)哈夫曼編/解碼器。根本要求：1、 初始化(Init)：能夠?qū)斎氲娜我忾L度的字符串 s進展統(tǒng)計，統(tǒng)計每個字符的頻度，并建立哈夫曼樹2、 建立編碼表(CreateTable)：利用已經(jīng)建好的哈夫曼樹進展編碼，并將每個字符的編碼輸出。3、 編碼(Encoding)：根據(jù)編碼表對輸入的字符串進展編碼，并將編碼后的字符串輸出。4、 譯碼(Decoding)：利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進展譯碼，并輸出譯碼結(jié)果。5、 打印(Print)：以直觀的方式打印哈夫曼樹選作6、 計算輸入的字符串編碼前和編碼后的長度，并進展分析，討論赫夫曼編碼的壓縮效果。7、 可采用二進制編碼方式選作測試數(shù)據(jù)：I love data Structure, I love puter。I will try my best to study data Structure.提示：1、用戶界面可以設(shè)計為“菜單方式：能夠進展交互。2、根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計頻度，對沒有出現(xiàn)的字符一律不用編碼2. 程序分析2.1 存儲結(jié)構(gòu)用struct結(jié)構(gòu)類型來實現(xiàn)存儲樹的結(jié)點類型struct HNode int weight; /權(quán)值int parent; /父節(jié)點int lchild; /左孩子int rchild; /右孩子;struct HCode /實現(xiàn)編碼的結(jié)構(gòu)類型 char data; /被編碼的字符char code100; /字符對應的哈夫曼編碼; 2.2 程序流程 輸入字符串統(tǒng)計出現(xiàn)的字符種類和次數(shù)，構(gòu)建權(quán)值數(shù)組，初始化樹結(jié)點與編碼表根據(jù)哈夫曼構(gòu)建規(guī)如此構(gòu)建哈夫曼樹，根據(jù)編碼規(guī)如此對出現(xiàn)字符進展編碼，構(gòu)建編碼表將輸入的字符挨個編碼對編碼后的字符進展解碼分析存儲大小2.3 關(guān)鍵算法分析 算法1：void Huffman:Count() 1 算法功能：對出現(xiàn)字符的和出現(xiàn)字符的統(tǒng)計，構(gòu)建權(quán)值結(jié)點，初始化編碼表 2 算法根本思想：對輸入字符一個一個的統(tǒng)計，并統(tǒng)計出現(xiàn)次數(shù)，構(gòu)建權(quán)值數(shù)組， 3 算法空間、時間復雜度分析：空間復雜度O1，要遍歷一遍字符串，時間復雜度On 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;i<128;i+) if(si!=0) dataj=(char)i; 給編碼表的字符賦值weightj=si; 構(gòu)建權(quán)值數(shù)組j+; leaf=j; /葉子節(jié)點個數(shù)即字符個數(shù)for(i=0;i<leaf;i+) cout<<datai<<"的權(quán)值為："<<weighti<<endl;算法2：void Init(); 1 算法功能：構(gòu)建哈弗曼樹 2 算法根本思想：根據(jù)哈夫曼樹構(gòu)建要求，選取權(quán)值最小的兩個結(jié)點結(jié)合，新結(jié)點參加數(shù)組，再繼續(xù)選取最小的兩個結(jié)點繼續(xù)構(gòu)建。 3 算法空間、時間復雜度分析：取決于葉子節(jié)點個數(shù)，時間復雜度On，空間復雜度O1 4 代碼邏輯HTree=new HNode2*leaf-1; n2=n0-1，一共需要2n-1個結(jié)點空間 for(int i=0;i<leaf;i+) HTreei.weight=weighti; 給每個結(jié)點附權(quán)值 HTreei.lchild=-1; 初始化左右孩子和父節(jié)點，都為-1 HTreei.rchild=-1; HTreei.parent=-1; int x,y; /用于記錄兩個最小權(quán)值 for(int i=leaf;i<2*leaf-1;i+) Selectmin(HTree,i,x,y); 選出兩個最小權(quán)值的結(jié)點 HTreex.parent=i; 父節(jié)點設(shè)置為新建立的結(jié)點 HTreey.parent=i; HTreei.weight=HTreex.weight+HTreey.weight; 父節(jié)點權(quán)值為兩個相加 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 &i2); 1 算法功能：從現(xiàn)有的結(jié)點中選擇出兩個最小的結(jié)點，返回其位置 2 算法根本思想：先選出兩個沒有構(gòu)建的結(jié)點，然后向后依次比擬，篩選出最小的兩個結(jié)點 3 算法空間、時間復雜度分析：空間復雜度O(1)，要遍歷所有結(jié)點，時間復 雜度O(N) 4 代碼邏輯int i;for(i=0;i<n;i+) /n為現(xiàn)在有的結(jié)點個數(shù)，是個變化值,會有相加后的新權(quán)值參加 if(hTreei.parent=-1) /父節(jié)點不是-1意味著這個結(jié)點還沒有被選擇過i1=i; 記錄結(jié)點位置break; i+; /執(zhí)行一遍for循環(huán)就加1，意為下次查找從當前位置開始查找for(;i<n;i+)if(hTreei.parent=-1) i2=i; 記錄第二個沒選擇過的結(jié)點編號break; if(hTreei1.weight>hTreei2.weight) 進展比擬，使I1為最小的，I2為第二小的int j=0;j=i2;i2=i1;i1=j; i+;for(;i<n;i+) 將I1 I2 與后面的結(jié)點進展比擬if(hTreei.parent=-1&&hTreei.weight<hTreei1.weight) 如果結(jié)點小于I1i2=i1; 使I2=I1 I1=新結(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)的字符進展編碼 2 算法根本思想：根據(jù)字符在哈夫曼樹中的位置，從下到上編碼，是左孩子編0，右孩子編1 3 算法空間、時間復雜度分析：空間復雜度O(1)，要遍歷data數(shù)組，時間復雜度0(N) 4 代碼邏輯HCodeTable=new HCodeleaf; 新建編碼結(jié)點，個數(shù)為葉子節(jié)點個數(shù) for(int i=0;i<leaf;i+) HCodeTablei.data=datai; int child=i; 初始化要編碼的結(jié)點的位置 int parent=HTreei.parent; 初始化父結(jié)點 int k=0; /統(tǒng)計編碼個數(shù) while(parent!=-1) if(child=HTreeparent.lchild) HCodeTablei.codek='0' /左孩子標0 else HCodeTablei.codek='1' /右孩子標1 k+; child=parent; 孩子結(jié)點上移 parent=HTreechild.parent; 父節(jié)點也上移 HCodeTablei.codek='0' /將編碼反向 char code100; for(int u=0;u<k;u+) codeu=HCodeTablei.codek-u-1; for(int u=0;u<k;u+) HCodeTablei.codeu=codeu; cout<<datai<<"的哈夫曼編碼為：" cout<<HCodeTablei.code<<endl; length3i=k; /每一個字符編碼的長度，為求編碼總長度做準備 算法5：void Encoding(); 1 算法功能：對輸入的字符串進展編碼 2 算法根本思想：找到每個字符對應的編碼，將編碼按順序輸出 3 算法空間、時間復雜度分析：空間復雜度O(1),時間復雜度0n 4 代碼邏輯 cout<<endl<<"輸入的字符串轉(zhuǎn)化為哈夫曼編碼為:"<<endl; for (int i=0;stri!='0'i+) 遍歷輸入的每一個字符 for(int j=0;j<leaf;j+) if(stri=HCodeTablej.data) 找到字符對應的編碼 s1=s1+HCodeTablej.code; 將所有編碼按順序加起來 cout<<HCodeTablej.code; 輸出編碼 cout<<endl;算法6：void Decoding(); 1 算法功能：對編碼串進展解碼 2 算法根本思想：找到每段編碼對應的字符，輸出字符 3 算法空間、時間復雜度分析：時間復雜度0(N)，空間復雜度01 4 代碼邏輯可用偽代碼描述 cout<<"解碼后的字符串為: "<<endl; char *s = const_cast<char*>(s1.c_str(); 將編碼字符串轉(zhuǎn)化為char while(*s!='0') int parent=2*leaf-2; 父節(jié)點為最后一個節(jié)點 while(HTreeparent.lchild!=-1) /還有左子樹，不可能是葉子節(jié)點 if(*s='0') 編碼為0，為左孩子 parent=HTreeparent.lchild; else parent=HTreeparent.rchild; 編碼為1，為右孩子 s+; cout<<HCodeTableparent.data; 輸出字符 cout<<endl;注意分析程序的時間復雜度、存申請和釋放，以與算法思想的表現(xiàn)。2.4 其他在此次試驗中使用了類和STL中的string，使用string可以方便的將單個字符的編碼加起來成為總的編碼后的數(shù)值，再利用STL中的轉(zhuǎn)化函數(shù)可以直接將string轉(zhuǎn)化為char，方便進展解碼工作?？偠灾?，使用STL使得編碼大大的簡潔了。3. 程序運行結(jié)果分析調(diào)試過程中遇到的問題主要是執(zhí)行時有存錯誤，檢查后發(fā)現(xiàn)是數(shù)組有越界現(xiàn)象，這提醒我在編寫時一定要仔細，特別是在for循環(huán)條件上一定要注意圍總結(jié)首先在輸入字符串時我發(fā)現(xiàn)直接用cin無法輸入空格，在上網(wǎng)查詢后找到了getline函數(shù)解決了這個問題。然后還有就是如何存儲編碼后總的那個字符串，因為每一個字符編碼的長度不定，無法用char數(shù)組來存儲，于是用了string的相加函數(shù)來將所有編碼加起來。最后由于在解碼時要用char數(shù)組，又上網(wǎng)查詢到了string轉(zhuǎn)化成char的函數(shù)解決了這個問題，實驗難點也在于如何找到兩個最小權(quán)值來構(gòu)建哈夫曼樹，尋找兩個最小權(quán)值的思想主要是通過一個個的比擬來找到最小值，而且注意形參要用引用。通過此次實驗我體會到了stl的優(yōu)越性。還有就是編碼時要注意數(shù)組的大小。再者就是有問題時可以試著去網(wǎng)上查詢答案。12 / 12