哈夫曼樹資料

北京郵電大學(xué)信息與通信工程學(xué)院第5頁/共9頁北京郵電大學(xué)電信工程學(xué)院第1頁數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)三——哈夫曼樹學(xué)生姓名：吳淳班級(jí)：2011211106班班內(nèi)序號(hào)：27學(xué)號(hào)：2011210180日期：2012年11月29日實(shí)驗(yàn)要求一、實(shí)驗(yàn)?zāi)康模赫莆斩鏄浠静僮鞯膶?shí)現(xiàn)方法；了解哈夫曼樹的思想和相關(guān)概念；培養(yǎng)使用二叉樹解決實(shí)際問題的能力。二、實(shí)驗(yàn)內(nèi)容：利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)哈夫曼編/解碼器1.初始化（Init）：能夠?qū)斎氲娜我忾L(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立哈夫曼樹。2.建立編碼表(CreatTable)：利用已經(jīng)建好的哈夫曼樹進(jìn)行編碼，并將每個(gè)字符的編碼輸出。3.編碼(Encoding)：根據(jù)編碼表對(duì)輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。4.譯碼(Decoding)：利用已經(jīng)建好的哈夫曼樹對(duì)編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。5.打印(Print)：以直觀的方式打印哈夫曼樹(選作)。6.計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討論哈夫曼編碼的壓縮效果。測(cè)試數(shù)據(jù)如下：Ilovedatastructure.Ilovecomputer.Iwilltrymybesttostudydatastructure.7.用戶界面可以設(shè)計(jì)成“菜單”方式，能進(jìn)行交互，根據(jù)輸入的字符串中每個(gè)字符出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對(duì)沒有出現(xiàn)的字符一律不用編碼。2. 程序分析2.1存儲(chǔ)結(jié)構(gòu)哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹。且哈夫曼樹是一棵只有度為0和2的結(jié)點(diǎn)的正則二叉樹。一棵有n個(gè)葉子的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)，可以用一個(gè)大小為2n-1的一位數(shù)組存放哈夫曼樹的各個(gè)結(jié)點(diǎn)。由于每個(gè)結(jié)點(diǎn)同時(shí)還包含其雙親信息和孩子結(jié)點(diǎn)的信息，所以可以使用一個(gè)靜態(tài)三叉鏈表來存儲(chǔ)哈夫曼樹。classHuffman{private: HNode*HTree;//哈夫曼樹 HCode*HcodeTable;//編碼表public: voidInit(inta[],intn);//初始化, voidCreatTable(charcharacter[],intn);//創(chuàng)立編碼表 voidEncoding(char*s,intn);//編碼 intDecoding(char*s,intn);//解碼 voidSelectmin(HNode*hTree,intn,int&i1,int&i2);//挑出最小的};二叉樹是由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左右子樹構(gòu)成：…………【圖一】正則二叉樹的結(jié)構(gòu)圖靜態(tài)三叉鏈表C++描述如下：structHNode{intweight;//結(jié)點(diǎn)權(quán)值intparent;//雙親指針intlchild;//左孩子指針intrchild;//右孩子指針};示意圖1：intrchildintlchildintparentintweightTparentTrchildTlchilddataintrchildintlchildintparentintweightTparentTrchildTlchilddata【圖二】示意圖1編碼表的結(jié)點(diǎn)結(jié)構(gòu)：structHCode{ chardata;//編碼表中的字符 charcode[100];//該字符對(duì)應(yīng)的編碼};圖【4】主函數(shù)流程圖圖【4】主函數(shù)流程圖程序運(yùn)行結(jié)果如下：【圖5】程序運(yùn)行結(jié)果1【圖5】程序運(yùn)行結(jié)果1【圖6】程序運(yùn)行結(jié)果22.測(cè)試條件：根據(jù)系統(tǒng)提示輸入字符串，然后解碼系統(tǒng)自行進(jìn)行解碼及相關(guān)運(yùn)算。3.測(cè)試結(jié)論：程序基本運(yùn)行良好，且若輸入編碼值不存在，會(huì)自動(dòng)提醒，不會(huì)出現(xiàn)運(yùn)行問題。4．總結(jié)1.調(diào)試時(shí)出現(xiàn)的問題及解決的方法調(diào)試時(shí)，出現(xiàn)的一個(gè)較為重要的問題是在Selectmin函數(shù)的編寫過程中，久久沒有思路。后來雖然寫出來了初步版的，卻發(fā)現(xiàn)無法運(yùn)行。后來幾經(jīng)完善，卻仍有漏洞。最后，我想起老師講的PPT上有相關(guān)代碼，此次改動(dòng)后才成功運(yùn)行。當(dāng)時(shí)看見老師給的代碼以后，才發(fā)覺自己的想法存在很多漏洞。雖然也考慮到一開始i1、i2經(jīng)遍歷選出來后，要比較其大小并可能要交換。但卻沒有在i2選出時(shí)的結(jié)點(diǎn)范圍中將i1除去，這樣會(huì)造成i1和i2相等，從而導(dǎo)致結(jié)果的錯(cuò)誤甚至于無法運(yùn)行。其次，一開始也沒有考慮解碼時(shí)輸入的字符串中可能有編碼表里不存在的碼值，致使輸入不合適時(shí)，程序就無法正常運(yùn)行。后來我將Decoding函數(shù)返回值改為int類型，若在某一步解碼時(shí)，發(fā)現(xiàn)*s為空，則報(bào)告錯(cuò)誤，同時(shí)返回0并結(jié)束該函數(shù)。2.心得體會(huì)經(jīng)過這次實(shí)驗(yàn)，我了解了哈夫曼樹的創(chuàng)建過程，了解了自行編寫一種不等長(zhǎng)編碼的方法，對(duì)于曾多次在多科課本中出現(xiàn)的通過編解碼來壓縮解壓縮的問題有了實(shí)質(zhì)性的深刻認(rèn)識(shí)，相信對(duì)于以后此類問題的學(xué)習(xí)會(huì)有很大的促進(jìn)作用。對(duì)于本次試驗(yàn)中多次出現(xiàn)的字符串的多種使用方法，我通過翻閱去年學(xué)習(xí)的c++書也有了更為詳盡的認(rèn)識(shí)，第一次如此頻繁的自行將字符數(shù)組的指針作為函數(shù)形參寫到程序中去，有了此次的經(jīng)驗(yàn)，以后我會(huì)更加靈活的使用指針和引用。3.下一步的改進(jìn)這次由于時(shí)間倉(cāng)促，很多問題并未完全考慮，一些部分代碼過于冗雜，本應(yīng)將其放在相應(yīng)函數(shù)里，這樣可讀性，實(shí)用性比較強(qiáng)。然而卻由于多次調(diào)試的失敗使我不得不把它們分解開，放在易于實(shí)現(xiàn)的部分