北郵數(shù)據(jù)結(jié)構(gòu)實驗三

北京郵電大學(xué)信息與通信工程學(xué)院第1頁北京郵電大學(xué)電信工程學(xué)院第1頁2009級數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗三哈夫曼樹學(xué)生姓名：班級：班內(nèi)序號：學(xué)號： 日期：2010年12月2日1．實驗要求實驗?zāi)康模和ㄟ^選擇下面兩個題目之一進(jìn)行實現(xiàn)，掌握如下內(nèi)容：·掌握二叉樹基本操作的實現(xiàn)方法·了解赫夫曼樹的思想和相關(guān)概念·學(xué)習(xí)使用二叉樹解決實際問題的能力實驗內(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.提示：1、用戶界面可以設(shè)計為“菜單”方式：能夠進(jìn)行交互。2、根據(jù)輸入的字符串中每個字符出現(xiàn)的次數(shù)統(tǒng)計頻度，對沒有出現(xiàn)的字符一律不用編碼。2.程序分析2.1存儲結(jié)構(gòu) 主存儲結(jié)構(gòu)：單鏈表，三叉鏈表。另外在某些函數(shù)中也用到了其他的存儲結(jié)構(gòu)，如創(chuàng)建編碼表時棧的應(yīng)用和打印樹時隊列的應(yīng)用等等。 下面對主存儲結(jié)構(gòu)進(jìn)行簡析： 在對樹進(jìn)行初始化的過程中，首先統(tǒng)計字符出現(xiàn)頻率，然后依次生成葉子結(jié)點(diǎn)，按權(quán)值從小到大排列。存儲使用的單鏈表帶雙頭結(jié)點(diǎn)（其作用后文將提到），插入葉子結(jié)點(diǎn)后，第一個頭結(jié)點(diǎn)處于鏈?zhǔn)?，第二個頭結(jié)點(diǎn)處于鏈尾，如下圖所示（忽略某些數(shù)據(jù)）：↓firstpr↓/\/\////////////ch1w1////////////chnwn…下一步由單鏈表轉(zhuǎn)化為三叉鏈表。忽略只有一個葉子結(jié)點(diǎn)的特殊情況（這種情況的處理在后文會有提到），在第二頭結(jié)點(diǎn)后面連接新的結(jié)點(diǎn)，將合適的結(jié)點(diǎn)從單鏈上“摘下”連接到新結(jié)點(diǎn)的左右孩子上。之后依此類推，在鏈尾插入新結(jié)點(diǎn)，與前面的區(qū)別是需要在葉子結(jié)點(diǎn)和已連接的根結(jié)點(diǎn)（pr之后的結(jié)點(diǎn)）中尋找合適的結(jié)點(diǎn)。該過程中的一種情況如下圖所示：↓firstpr↓w2w2ch2w1ch1////////////ch6w6////////////chnwn…w’2/\w’3w4ch4w’1w5ch5w3ch3示意圖中忽略了葉子結(jié)點(diǎn)中空的左右孩子指針。事實上此時非根結(jié)點(diǎn)的next指針依然有效，只是在存儲結(jié)構(gòu)中已不起作用。當(dāng)結(jié)點(diǎn)的組合進(jìn)行結(jié)束時，單鏈表只含第一頭結(jié)點(diǎn)、第二頭結(jié)點(diǎn)和最終得到的根結(jié)點(diǎn)。該根結(jié)點(diǎn)即為所求哈夫曼樹的根結(jié)點(diǎn)。此時釋放掉兩個頭結(jié)點(diǎn)，頭指針前移兩位，即為哈夫曼樹的根結(jié)點(diǎn)。至此，哈夫曼樹構(gòu)造完成。示意圖如下：↓firstwwi1wi2wi3wi4wi5……2.2關(guān)鍵算法分析建樹又可分為3個子過程：頻率統(tǒng)計、創(chuàng)建葉子結(jié)點(diǎn)單鏈表、葉子結(jié)點(diǎn)連接成樹。其中頻率統(tǒng)計比較簡單，使用一個256個元素的數(shù)組，對應(yīng)unsignedchar0~255個值，并全部置初值為0。輸入的字符串由首至尾讀取，對讀取的每個字符對應(yīng)數(shù)組元素自增1即可。該算法問題規(guī)模只與字符串長度有關(guān)，時間復(fù)雜度為O(n)，空間復(fù)雜度O(1)（循環(huán)條件）。單鏈表的創(chuàng)建過程也不很復(fù)雜。對存在的每個字符建立葉子結(jié)點(diǎn)，并按權(quán)值遞增有序插入單鏈表，再將字符的葉子指針（其作用將在后文提到）指向該結(jié)點(diǎn)。插入位置選擇的代碼如下： p=first;while(p->next->next) { if(p->next->weight>=CodeList[i].freq) break; else p=p->next; }需要強(qiáng)調(diào)的是，有序插入時應(yīng)尋找權(quán)值大于當(dāng)前葉子結(jié)點(diǎn)權(quán)值的前一位置（或表尾）插入，此時工作指針p應(yīng)指向插入位置的前一結(jié)點(diǎn)，即需對p->next指針指向的結(jié)點(diǎn)的權(quán)值進(jìn)行判斷。另外，此時第二頭結(jié)點(diǎn)尚未利用，置于表尾，所以判斷工作指針指向真正的表尾的條件是p->next->next==NULL。這里的問題規(guī)模為頻率非0的字符個數(shù)，處理所有字符的時間復(fù)雜度為O(n2)（相當(dāng)于插入排序法），空間復(fù)雜度為O(1)（工作指針，臨時指針）。單鏈表建立完成，下面詳細(xì)說明單鏈表轉(zhuǎn)換成樹的過程。偽代碼如下：1.循環(huán)直至“頭指針->第一頭結(jié)點(diǎn)->第二頭結(jié)點(diǎn)->根結(jié)點(diǎn)->NULL” 1.1定義p1等于第一頭結(jié)點(diǎn)的next指針,p2等于第二頭結(jié)點(diǎn)的next指針； 1.2如果p2為空，或權(quán)值最小的兩個葉子結(jié)點(diǎn)的權(quán)值均小于已生成根結(jié)點(diǎn)的最小權(quán)值 1.2.1建立新結(jié)點(diǎn)作為根結(jié)點(diǎn) 1.2.2根結(jié)點(diǎn)權(quán)值等于權(quán)值最小的兩個葉子結(jié)點(diǎn)權(quán)值之和 1.2.3與權(quán)值最小的兩個葉子結(jié)點(diǎn)建立父子關(guān)系 1.2.4左子樹編碼為0，右子樹編碼為 1.2.5 1.2.6新結(jié)點(diǎn)插入表尾 1.2.7第一頭結(jié)點(diǎn)next指針后移兩步 后兩種情況類似。這里我們還需要考慮一種特殊情況。如果讀入的字符串中只存在一種字符，即單鏈表中只含有單一葉子結(jié)點(diǎn)時，無法找到“兩個”權(quán)值最小的葉子結(jié)點(diǎn)，故需作特殊處理。在執(zhí)行上述一般情況的代碼前加入判斷以處理特殊情況。相關(guān)的偽代碼如下：1.若第一頭結(jié)點(diǎn)的next指針指向的結(jié)點(diǎn)的next指針等于第二頭結(jié)點(diǎn)的頭指針（即兩頭結(jié)點(diǎn)間只含一個結(jié)點(diǎn)） 1.1建立新結(jié)點(diǎn)作為根結(jié)點(diǎn)； 1.2葉子結(jié)點(diǎn)權(quán)值賦值給根結(jié)點(diǎn)權(quán)值； 1.3左、右孩子指針指向同一葉子結(jié)點(diǎn)； 1.4葉子結(jié)點(diǎn)父指針指向新結(jié)點(diǎn)； 1.5葉子結(jié)點(diǎn)編碼為0； 1.6新結(jié)點(diǎn)next域置空； 1.7新結(jié)點(diǎn)插入表尾； 1.8第一頭結(jié)點(diǎn)next指針后移一步；通過上述處理，可以將特殊情況與一般情況統(tǒng)一對待，以方便執(zhí)行后續(xù)的操作。而且經(jīng)處理后的單鏈表滿足循環(huán)結(jié)束條件，不會進(jìn)入之后的循環(huán)。2.3其他關(guān)于樹的打印：考慮到控制臺的限制，不可能打印得非常形象，并且由于窗口寬度只是固定的80個字符，當(dāng)樹比較龐大時，可能會無法將整棵樹全部打印出來。粗略計算了一下，如果單行最多打印8個節(jié)點(diǎn)，那么每個結(jié)點(diǎn)可以打印10個字符，只要不打印葉子結(jié)點(diǎn)對應(yīng)的編碼，長度是足夠用的。如果打印16個結(jié)點(diǎn)的話，空間就有些狹窄了。這樣一來，我們可以將樹分層打印，先打印前4層。若第4層上存在非葉子結(jié)點(diǎn)，再依次打印以這些非葉子結(jié)點(diǎn)為根的子樹，直到所有結(jié)點(diǎn)打印完成。顯然，這是一個遞歸的過程。這樣打印出來雖然并不是非常直觀，但是至少能比較清楚的反映出樹中雙親和孩子的關(guān)系。實現(xiàn)樹的打印的核心思想是二叉樹的層序遍歷。使用隊列的存儲結(jié)構(gòu)，存儲待打印結(jié)點(diǎn)的地址。每層打印完畢，結(jié)點(diǎn)指針依次出隊，同時其左右孩子指針依次入隊，準(zhǔn)備打印下一層。3.程序運(yùn)行結(jié)果開始鍵盤讀入任意鍵開始鍵盤讀入任意鍵創(chuàng)建哈夫曼樹類的對象鍵盤讀入字符串輸入為空？yes初始化哈夫曼樹其他鍵盤讀入按鍵按鍵為？結(jié)束執(zhí)行對應(yīng)操作no‘j’‘a(chǎn)’~’i’測試結(jié)果：<初始化界面模擬>哈夫曼樹編碼字符串程序請按任意鍵開始請輸入要編碼的字符串：IlovedataStructure,IloveComputer.IwilltrymybesttostudydataStructure.初始化完成！<選項界面模擬>請選擇您要執(zhí)行的操作：A.生成編碼表B.對已輸入的字符串進(jìn)行編碼C.對編碼后的字符串進(jìn)行解碼D.打印哈夫曼樹E.打印編碼表F.打印字符串原碼G.打印字符串編碼H.打印字符串譯碼I.分析原碼與編碼的長度J.退出程序<測試結(jié)果模擬>哈夫曼樹打印如下：<注：此處西文字體若設(shè)為TimesNewRoman會導(dǎo)致錯位從而影響顯示效果>A84/\BC3351/\/\DEFG16172328/\/\/\/\HIJKLMNO888911121612/\/\/\/\t/\/\HA8/\HBHC44o/\HFHG22v/\HNHO11wpIA8/\IBIC44l/\IFIG22s/\INIO11ibJA8/\JBJC44a/\JFJG22m/\JNJO11C,KA9/\KBKC45/\/\KDKEKFKG2223cS.yMA12/\MBMC66u/\MFMG33dIOA12/\OBOC66re每個結(jié)點(diǎn)自上至下依次為：編號、權(quán)值、對應(yīng)的字符。由于窗口大小有限，無法完整地顯示整棵樹，故拆分顯示。子樹的根結(jié)點(diǎn)對應(yīng)為上一層同編號的結(jié)點(diǎn)，如結(jié)點(diǎn)“MA”對應(yīng)結(jié)點(diǎn)“M”，結(jié)點(diǎn)“KOA”對應(yīng)結(jié)點(diǎn)“KO”等等。編碼表：（每行依次為：字符，字符的值，字符的編碼，字符的出現(xiàn)頻率）3211016,440101111.46011102C670101101I73101113S83011012a9701004b980011111c99011002d100101103e10111116i1050011101l10800104m109010102o11100004p1120001111r11411106s115001102t11610011u11710106v118000102w1190001101y121011113原碼為：IlovedataStructure,IloveComputer.IwilltrymybesttostudydataStructure.編碼為：10111110001000000001011111101011001001000100110011011001110101001100100