第4頁北京郵電大學(xué)電信工程學(xué)院第1頁數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗三——樹學(xué)生姓名：班級：2011211114班內(nèi)序號：14學(xué)號：2011210400日期：2012年11月29日1．實驗要求（1）實驗?zāi)康恼莆斩鏄浠静僮鞯膶崿F(xiàn)方法了解赫夫曼樹的思想和相關(guān)概念學(xué)習(xí)使用二叉樹解決實際問題的能力（2）實驗內(nèi)容利用二叉樹結(jié)構(gòu)實現(xiàn)赫夫曼編/解碼器。基本要求：初始化(Init)：能夠?qū)斎氲娜我忾L度的字符串s進(jìn)行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立赫夫曼樹建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹進(jìn)行編碼，并將每個字符的編碼輸出。編碼(Encoding)：根據(jù)編碼表對輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹對編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。打印(Print)：以直觀的方式打印赫夫曼樹（選作）計算輸入的字符串編碼前和編碼后的長度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。測試數(shù)據(jù)：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.2.程序分析2.1存儲結(jié)構(gòu)該程序使用哈夫曼樹結(jié)構(gòu)存儲數(shù)據(jù)，并利用哈夫曼樹進(jìn)行編碼得到每個字符的編碼從而減少數(shù)據(jù)的存儲空間，哈夫曼樹是二叉樹，以各頻度作為葉子結(jié)點(diǎn)組成哈夫曼樹，而每個結(jié)點(diǎn)存儲的有其頻度，其雙親結(jié)點(diǎn)，其左孩子和右孩子，并且哈夫曼樹有一個相應(yīng)的編碼表存儲各葉子結(jié)點(diǎn)的編碼。哈夫曼樹的存儲結(jié)構(gòu)如圖：EDEDBAC2.2關(guān)鍵算法分析1．關(guān)鍵算法哈夫曼樹解碼和譯碼問題的實質(zhì)就是把已知的一段字符串，統(tǒng)計每個字符的頻度，并按照頻度建立哈夫曼樹，每個葉子結(jié)點(diǎn)都為一個頻度，然后利用建好的哈夫曼樹建立編碼表，從而得到每個字符的編碼，這樣每輸入一段字符都可以去編碼表找對應(yīng)的字符從而編碼成一段二進(jìn)制碼，這樣的編碼存儲更節(jié)省存儲空間，從而達(dá)到壓縮效果。關(guān)鍵算法如下：1：把輸入的一段字符串轉(zhuǎn)化為每個字符的頻度，并對應(yīng)一個字符數(shù)組存儲字符：利用ASCII碼有128個并對應(yīng)著的整形，用一個整形數(shù)組存儲每個字符出現(xiàn)的次數(shù)，數(shù)組的下標(biāo)為每個字符的ASCII碼對應(yīng)整數(shù)。用賦好值的整形數(shù)組每個元素除以總的元素并對應(yīng)存入一個double類型的數(shù)組（元素為0的不存），并建立一個字符數(shù)組存儲每個字符對應(yīng)double數(shù)組的每一個元素（頻度）。2：利用建好的double數(shù)組建立哈夫曼樹：①建立一個含2*k-1個結(jié)點(diǎn)的樹，并把k個頻度對應(yīng)存入0--k-1個結(jié)點(diǎn)的weight域，并令這些結(jié)點(diǎn)的左孩子，右孩子，和雙親都為-1。②找出0——k-1個結(jié)點(diǎn)頻度最小的兩個結(jié)點(diǎn)，并令第k個結(jié)點(diǎn)的頻度等于兩節(jié)點(diǎn)頻度之和，一個結(jié)點(diǎn)為其左孩子，一個結(jié)點(diǎn)為其右孩子。③循環(huán)步驟2，使建好的樹每個結(jié)點(diǎn)的域都填充好（每次比較除去已經(jīng)提取出來的結(jié)點(diǎn)，并加入新建好的結(jié)點(diǎn)）。3：利用建好的哈夫曼樹建立編碼表:①編碼表data域存字符，code域存每個字符的編碼。②找到葉子結(jié)點(diǎn)的雙親，判斷如果該結(jié)點(diǎn)是雙親的左孩子則存編碼0，右孩子存編碼1，然后再找其雙親的雙親，判斷雙親是祖父結(jié)點(diǎn)的左孩子還是右孩子，重復(fù)上述步驟直到根結(jié)點(diǎn)。③把每個字符的編碼倒置并輸出每個字符的編碼。4：譯碼函數(shù):如果是第一個字符是0則找根結(jié)點(diǎn)的左孩子，如果是1則找右孩子。繼續(xù)令找到的結(jié)點(diǎn)作為雙親并找下一個字符重復(fù)步驟（1）（2）直到葉子結(jié)點(diǎn)。重復(fù)(1)(2)直到遍歷字符數(shù)組。5：編碼函數(shù)：把字符數(shù)組的第一個字符與葉子結(jié)點(diǎn)的字符比較，找到相同的字符，把其編碼并入一個字符數(shù)組存儲起來。字符下標(biāo)加1，重復(fù)步驟（1）直到遍歷整個字符數(shù)組。2.代碼詳細(xì)分析:（1）把輸入的一段字符串轉(zhuǎn)化為每個字符的頻度，并對應(yīng)一個字符數(shù)組存儲字符：①利用ASCII碼有128個并對應(yīng)著的整形，用一個整形數(shù)組存儲每個字符出現(xiàn)的次數(shù)，數(shù)組的下標(biāo)為每個字符的ASCII碼對應(yīng)整數(shù);while(p[i]) { a[p[i]]++; i++; }②用賦好值的整形數(shù)組每個元素除以總的元素并對應(yīng)存入一個double類型的數(shù)組（元素為0的不存），并建立一個字符數(shù)組存儲每個字符對應(yīng)double數(shù)組的每一個元素（頻度）：for(intj=0;j<128;j++) { if(a[j]) { b[k]=(double)a[j]/i; c[k]=(char)j; k++; } }(2)利用建好的double數(shù)組建立哈夫曼樹①建立一個含2*k-1個結(jié)點(diǎn)的樹，并把k個頻度對應(yīng)存入0--k-1個結(jié)點(diǎn)的weight域，并令這些結(jié)點(diǎn)的左孩子，右孩子，和雙親都為-1：for(intj=0;j<k;j++) { HTree[j].weight=b[j]; HTree[j].LChild=-1; HTree[j].RChild=-1; HTree[j].parent=-1; }②找出0——k-1個結(jié)點(diǎn)頻度最小的兩個結(jié)點(diǎn)，并令第k個結(jié)點(diǎn)的頻度等于兩節(jié)點(diǎn)頻度之和，一個結(jié)點(diǎn)為其左孩子，一個結(jié)點(diǎn)為其右孩子： for(intj=k;j<2*k-1;j++) { doublemin1=1000,min2=1000;intx=-1,y=-1;for(intp=0;p<=j-1;p++) { if(HTree[p].parent==-1) { if(HTree[p].weight<min1) { min2=min1; y=x; min1=HTree[p].weight; x=p; } elseif(HTree[p].weight<min2)y { min2=HTree[p].weight; y=p; } } }（3）譯碼函數(shù):①如果是第一個字符是0則找根結(jié)點(diǎn)的左孩子，如果是1則找右孩子：while(HTree[parent].LChild!=-1) { if(s[i]=='0') parent=HTree[parent].LChild; else parent=HTree[parent].RChild; i++; }(4)編碼函數(shù)：①輸把字符數(shù)組的第一個字符與葉子結(jié)點(diǎn)的字符比較，找到相同的字符，把其編碼并入一個字符數(shù)組存儲起來; while(s[i]) { for(intj=0;j<n;j++) if(s[i]==HCodeTable[j].data) { strcat(h,HCodeTable[j].code); } i++; }3．時間復(fù)雜度的計算[1]O(n)[1.1]O(n)[2.1]O(n)[2.2]O(n)[2.3]O(n)[3.1]O(1)[3.2]O(n)[3.3]O(n)[4.1]O(n)[4.2]O(n)[5.1]O(n)2.3其他在此需要說明的是，這里編碼函數(shù)和譯碼函數(shù)都是在輸入字符串建立的編碼表基礎(chǔ)上調(diào)用的，不能另外輸入字符串調(diào)用其函數(shù)。3.程序運(yùn)行結(jié)果1．流程流程圖如下：開始開始用cin.getline()函數(shù)接受一段可含空格的字符串。用cin.getline()函數(shù)接受一段可含空格的字符串。調(diào)用菜單函數(shù)，實參為輸入的字符串。調(diào)用菜單函數(shù)，實參為輸入的字符串。對字符串進(jìn)行處理，用double類型數(shù)組b[]存頻度，用字符數(shù)組c[]存對應(yīng)字符。對字符串進(jìn)行處理，用double類型數(shù)組b[]存頻度，用字符數(shù)組c[]存對應(yīng)字符。調(diào)用哈夫曼樹建立函數(shù)，實參為數(shù)組b[]和數(shù)組中總頻度數(shù)k。調(diào)用哈夫曼樹建立函數(shù)，實參為數(shù)組b[]和數(shù)組中總頻度數(shù)k。調(diào)用編碼表初始化函數(shù)，實參為c[]和k。調(diào)用編碼表初始化函數(shù)，實參為c[]和k。用戶輸入整形n，判斷n大小用戶輸入整形n，判斷n大小n=3n=3n=1n=1n=2n=2調(diào)用編碼函數(shù)，實參為數(shù)組c[]和k，輸出編碼。調(diào)用譯碼函數(shù)，輸出譯碼。調(diào)用計算數(shù)組大小函數(shù)，然后輸入壓縮效果調(diào)用編碼函數(shù)，實參為數(shù)組c[]和k，輸出編碼。調(diào)用譯碼函數(shù)，輸出譯碼。調(diào)用計算數(shù)組大小函數(shù)，然后輸入壓縮效果結(jié)束結(jié)束2.測試結(jié)論：4.總結(jié)（1）調(diào)試時出現(xiàn)的問題及解決方法①在調(diào)試時發(fā)現(xiàn)用字符指針不能用cin輸入字符串，后來把字符指針改為字符數(shù)組后問題得到解決。②在執(zhí)行時發(fā)現(xiàn)輸出編碼時后面總有一段亂碼，在給字符數(shù)組賦值的地方設(shè)置斷點(diǎn)調(diào)試后發(fā)現(xiàn)字符數(shù)組沒初始化時為亂碼，后來把字符數(shù)組初始化后問題得到解決。（2）心得體會在本次實驗中，熟悉了哈夫曼樹的各種基本操作，特別是初始化哈夫曼樹操作、建立編碼表操作和編碼隊頭和譯碼操作有了較深的理解。對于數(shù)組和指針的用法也