哈夫曼樹資料

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