2008級數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱： 實驗三實現(xiàn)哈夫曼樹學(xué)生姓名： *班 級： *班內(nèi)序號： *學(xué) 號： *日 期： 2009年11月14日1實驗要求利用二叉樹結(jié)構(gòu)實現(xiàn)赫夫曼編/解碼器?；疽螅?、 初始化(Init)：能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立赫夫曼樹2、 建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹進行編碼，并將每個字符的編碼輸出。3、 編碼(Encoding)：根據(jù)編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。4、 譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結(jié)果。5、 打印(Print)：以直觀的方式打印赫夫曼樹（選作）6、 計算輸入的字符串編碼前和編碼后的長度，并進行分析，討論赫夫曼編碼的壓縮效果。測試數(shù)據(jù)： I love data Structure, I love Computer。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)在哈夫曼樹編碼這個程序中，所有數(shù)據(jù)用的存儲結(jié)構(gòu)都是順序存儲結(jié)構(gòu)，其中包括順序表和樹（三叉樹）。樹的存儲結(jié)構(gòu)如下：（輸入的字符串為 assddddffffffffgggggggggggggggg）012345678ASC97115100102103weight124816371531lchild-1-1-1-110234rchild111111567parent-55-6-7-86780上結(jié)構(gòu)圖中，填充為黃色的部分為寫入內(nèi)存中的部分。每一行的部分為數(shù)組的下標(biāo)，左邊部分為所定義的結(jié)構(gòu)的成員。其中有的結(jié)點的父節(jié)點的下標(biāo)是一個負(fù)數(shù)，用來說明該節(jié)點是該節(jié)點的父節(jié)點的左孩子，正數(shù)說明的是該節(jié)點的父節(jié)點的右孩子。父節(jié)點這零的節(jié)點說明該節(jié)點是該哈夫曼樹的根節(jié)點。畫出樹的結(jié)構(gòu)如下畫所示：（結(jié)點中第一個數(shù)表示這個字符的ASC編碼，第二個數(shù)字表示權(quán)值）37153116102897110041152876543210000010111紅色箭頭表示父指針，黑色箭頭表示孩子指針由上面的圖可知，原字符串編碼后的二進制編碼為11101111111111011011011010101010101010100000000000000000字符串中出現(xiàn)的所有的字符的編碼如下：a1110；s1111；d110；f10；g02.2 關(guān)鍵算法分析算法1：哈夫曼樹的構(gòu)造這個算法分兩個部分，每一個部分是對一個字符串中每個字符出現(xiàn)次數(shù)的統(tǒng)計，并為每一個出現(xiàn)的字符建立一個葉子節(jié)點；第二個部分是以上面的統(tǒng)計的數(shù)據(jù)為依據(jù)建立起一棵哈夫曼樹。問題的規(guī)模由兩部分組成，一是字符串中總的字符的個數(shù)m，二是這個字符串中出現(xiàn)的所有的不同的字符的個數(shù)n。算法的第一部分須要對輸入的字符串進行一次遍歷，故其時間復(fù)雜度為O(m)，為了對每一個字符出現(xiàn)的次數(shù)進行計數(shù)，程序在開始的時候初始化了一個整形數(shù)組 Asc256 用256個元素的存儲空間來分別計算可能出現(xiàn)的256個字符在字符串中出現(xiàn)的頻數(shù)，因此這個算法的空間復(fù)雜度是一個常數(shù)，即O(1)。算法的第二部分是構(gòu)造一棵哈夫曼樹，這算法首先在之前每個出現(xiàn)過的字符的頻數(shù)的統(tǒng)計的依據(jù)下，為每一個字符建立一個節(jié)點。并按每一個葉子節(jié)點的權(quán)值進行一次從大到小的排序（這里的排序所用的算法是冒泡算法），排序后的結(jié)果進行哈夫曼樹的構(gòu)造（實際上就是為數(shù)組 hft 填入相關(guān)的數(shù)據(jù)）?，F(xiàn)在對審一部分的每一個小的部分進行時間和空間復(fù)雜度的分析。對于建立節(jié)點這一部分，程序中并沒有用到額外的存儲空間，只用到之前所申請的511個節(jié)點空間的數(shù)組，故其空間復(fù)雜度為O(1)，遍歷了數(shù)組Asc，差為出現(xiàn)過的n個字符各自建立起了一個葉子節(jié)點，故其時間復(fù)雜度為O(n)。對于冒泡排序這個算法，無論輸入的問題規(guī)模有多大，其調(diào)用的額外的存儲空間都是一個常數(shù)，易知其空間復(fù)雜度為O(1)；對于冒泡算法，其時間復(fù)雜度為O(n2)。最后的一部分就是樹的構(gòu)造，對于一棵有n個葉子節(jié)點樹，須要進行n-1次的復(fù)合，而每一次進行復(fù)合所要運行的語句數(shù)都是一個常數(shù)。故其時間復(fù)雜度是O(n)，其空間復(fù)雜度仍然是O(1)。該算法的自然描述如下：先對輸入的字符串進行每一個所出現(xiàn)的字符出行頻數(shù)的統(tǒng)計，再為每一個字符建立一個葉子節(jié)點，并按每個葉子節(jié)點的權(quán)值進行從小到大的排序。再從所存在的節(jié)點當(dāng)中尋找兩個權(quán)值之和最小的節(jié)點進行復(fù)合，作為一個新的節(jié)點的左右孩子，并把這個節(jié)點加入到節(jié)點數(shù)組之中，一直到數(shù)組中只剩下一個節(jié)點（這個結(jié)點最后作為哈夫曼樹的根節(jié)點用在捕的編碼之中）下面的偽代碼描述如下：1、統(tǒng)計字符串出每個出現(xiàn)的符號出現(xiàn)的次數(shù)，把統(tǒng)計后的結(jié)果留在數(shù)組Asc之路；2、為每一個在字符串中出現(xiàn)的結(jié)點建立一個葉子節(jié)點，并將每一個葉子節(jié)點 的左右孩子及父節(jié)點設(shè)為-1，但未寫入權(quán)值（后面的排序須要用到其權(quán)值，只要按這個葉子節(jié)點所存儲的字符找到其在數(shù)組Asc中的位置即能找到其權(quán)值）；3、按每一個葉子節(jié)點的權(quán)值的大小進行從小到大的排序，即要值小的葉子節(jié)點放在前面；4、寫入每一個葉子節(jié)點的權(quán)值；5、在節(jié)點數(shù)組中找到兩個節(jié)點（包括葉子節(jié)點和非葉子節(jié)點），使他們的權(quán)值之和最小。并將這兩個節(jié)點作為一個新的節(jié)點（非葉子節(jié)點）的左右孩子，并將這兩個結(jié)點的權(quán)值之和作這個新的節(jié)點的權(quán)值,再將這兩個復(fù)合的節(jié)點的父節(jié)點指向這一個新的節(jié)點，若這個節(jié)點是該節(jié)點的父節(jié)點的左葉孩子，則將這個父節(jié)點在數(shù)組中的下標(biāo)的相反數(shù)寫入其父指針中，若是右孩子，則直接寫到其父指針中。一直到數(shù)組中只剩下一個沒有進行過復(fù)合的節(jié)點，并將這個節(jié)點作為哈夫曼樹的根節(jié)點。算法二：寫編碼表這個算法的目的是按之前所建立的哈夫曼樹，為每一個所出現(xiàn)的字符進行二進制編碼，并寫入編碼表。這個算法從節(jié)點數(shù)組中找到所有在字符串中出現(xiàn)過的字符，并一一為其進行編碼，再寫到編碼表里。該程序中的編碼表由一個string類的動態(tài)數(shù)組組成，它根據(jù)葉子節(jié)點的個數(shù)申請足夠大的內(nèi)存空間，再根據(jù)其在哈夫曼樹中的位置進行編碼。編碼的過程是自下而上的，因而二進制的編碼是從后面開始的，為了實現(xiàn)這一編碼，程序中使用的類的一個成員函數(shù) operator+ （即加法運算符的重載）把新的一位二進制數(shù)字加到該string類字符串的前面。一直加到哈夫曼樹的根節(jié)點為止。這個算法要對出現(xiàn)的n個字符進行編碼，由于每一個編碼的長度不一樣，故不易從這里直接得到其時間復(fù)雜度。但考慮到兩種極端的情況，即所有編碼的長度加起來最長和最短的時候，其所用的空間復(fù)雜度分別為n(nlog2n)，n(n2)，由于每增加一個字符的空間，則就得調(diào)用一次string的成員operator+，故其時間復(fù)雜度也分別為n(nlog2n)，n(n2)。該算法的自然語言描述為：對節(jié)點數(shù)組中的每一個葉子節(jié)點進行編碼，查看其父節(jié)點，若其父節(jié)點是一個負(fù)數(shù)，則在這個字符的二進制編碼前面加一個0，若是一個負(fù)數(shù)，則加一個1。然后再查看其父節(jié)點的父節(jié)點的正負(fù)，一直走到根節(jié)點，再對下一個字符進行編碼。偽代碼：1、根據(jù)節(jié)點數(shù)組中葉子節(jié)點的個數(shù)，為編碼表申請足夠大的內(nèi)存空間；2、對節(jié)點數(shù)組中的每一個葉子節(jié)點進行編碼，進行下面的操作21、用一個帶型變量p指向葉子節(jié)點位置；22、若這個節(jié)點的父節(jié)點是一個負(fù)數(shù)，則在這個字符的編碼前加一個0，若是一個負(fù)數(shù)，則加一個1；23、將這個節(jié)點父節(jié)點的位置的絕對值賦給p，循環(huán)2.2和2.3的操作，直到p指向的是根節(jié)點；2.3 其他在構(gòu)造哈夫曼樹的時選取兩個權(quán)值之和最小的結(jié)點的時候，這個程序使用了一點小技巧，即先對葉子節(jié)點進行了一次排序，使權(quán)值小的節(jié)點放在數(shù)組的前面。這是為了在后面構(gòu)造樹的時候免得再在節(jié)點數(shù)組中遍歷一次尋找符合要求的兩個節(jié)點。這種方法的具體實現(xiàn)如下：每一次復(fù)合有三種選擇：在葉子節(jié)點中取出最靠前的兩個葉子節(jié)點進行復(fù)合、在非葉子節(jié)點中取出最靠前的兩個節(jié)點進行復(fù)合、在葉子節(jié)點和非葉子節(jié)點中各取出一個最靠前的節(jié)點進行復(fù)合。每次復(fù)合只要找到三種方法中其復(fù)合節(jié)點權(quán)值最小的一種，再把復(fù)合后的節(jié)點放到非葉子節(jié)點的尾部。為了更好說明這個辦法的可行性，在這里假設(shè)程序中將葉子節(jié)點和非葉子節(jié)點放在兩個不同的數(shù)組中，每次復(fù)合節(jié)點時在這兩個數(shù)組中找到合適的兩個節(jié)點進行復(fù)合，并放到非葉子節(jié)點數(shù)組的尾部（這個非葉子節(jié)點的數(shù)組看起來就像是一個隊列）。下面用數(shù)學(xué)歸納法簡單地證明一下這種方法在每次進行復(fù)合的時候選擇的都是權(quán)值之和最小的兩節(jié)點：為了達到上面的證明，只要證明每次復(fù)合后的節(jié)點的權(quán)值都不小于上一次復(fù)合即可。已知葉子節(jié)點的數(shù)組中的節(jié)點的權(quán)值是從小到大排列的，開始的時候從葉子節(jié)點數(shù)組中取出兩個節(jié)點進行復(fù)合，并把復(fù)合后的節(jié)點放到非葉子節(jié)點的數(shù)組中去。因為非葉子節(jié)點數(shù)組中只有一個元素，所以我們現(xiàn)在可以認(rèn)為這個數(shù)組也是從小到大排序的，以這一條作為歸納假設(shè)開始證明：假設(shè)現(xiàn)在已經(jīng)對節(jié)點進行了n次復(fù)合，且這n次復(fù)合成的非葉子節(jié)點的權(quán)值都是非遞減排列的，并且前n次復(fù)合的方法嚴(yán)格按照前面所說的方法進行。由于第n次復(fù)合的方法有三種可能性，而第n+1次復(fù)合的方法也有三種，現(xiàn)在要對這九種情況進行分析。首先先肯定這兩次算命選取方法一樣的三種情況，因為這兩個數(shù)組都是從小到大進行排列的，因為第n+1次選擇的兩個節(jié)點的權(quán)值都不小于前兩次選擇的兩個節(jié)點。然后就是第n次選擇第一種方法，每n+1次選二種方法的，以及第n次選擇第二種方法，每n+1次選一種方法的。因為在進行第n次復(fù)合的時候已經(jīng)對葉子節(jié)點數(shù)組前兩個節(jié)點和非葉子節(jié)點前兩個節(jié)點的權(quán)值之和進行了一次比較，并在第n次的時候選擇了比較小的一組，所以第n+1復(fù)合之后的節(jié)點的權(quán)值之和必然會大于每n次的?，F(xiàn)在就只剩下四種情況了。再來就是第n次選擇第三種，第n+1次選擇第一種（或第二種，由于兩種情況是對稱的，這里就只說明其中的一種）用把證法會比較容易說明 ，設(shè) a1、a2、a3為葉子節(jié)點最靠前的三個節(jié)點，b1為非葉子節(jié)點最靠前的一個節(jié)點。則第n次取的是a1和b1，第二次選的是a2和a3若a2+a3<a1+b1,又a1<=a2<=a3，由上兩式可得a1+a2<=a2+a3<a1+b1,即第n次選擇的并不不是兩個權(quán)值之和最小的兩個節(jié)點，故第二次不符合上面的選擇的方法；用同樣的方法可以證明剩下的兩種情況也是不符合情況的。證畢。3. 程序運行結(jié)果程序運行的界面如下，通過用戶輸入指令運行?？捎玫闹噶钣腥缦聨讞l：encoding（對一個字符串進行編碼）,decoding（通過之前已經(jīng)建立過的哈夫曼樹，讓助用戶輸入一個由0和1組成的字符串，解釋用戶輸入的字符串），cls（清除之前輸入的所有數(shù)據(jù)），tree（打印出哈夫曼樹），code（打印出最近一次輸入的字符串的哈夫曼編碼），fileencoding（用哈夫曼編碼對一個文件進行壓縮），filedecoding（對一個用哈夫曼編碼壓縮后的文件解壓），quit（停止運行程序）對于輸入的字符串，可以任意輸入長度（當(dāng)然，在內(nèi)存允許的范圍之內(nèi)！不然的話會出現(xiàn)一些無法預(yù)料的后果，由于作者還沒試過這樣浩大的工程，不能給出做這樣操作的后果）。對于對一個文件進行壓縮，效果不一定很好（甚至還會越壓越大），畢竟在壓縮的文件里還必須得寫入一些額外的數(shù)據(jù)（解壓鑰匙），所以對一些每一個字符出現(xiàn)概率都一樣的文件，根本沒有壓縮效果。但對于程序中測試的那個文件來說，壓縮效果還是挺不錯的（雖然別的壓縮算法壓的效果會更好）程序運行的結(jié)果如下截圖：4. 總結(jié)對于寫這一個程序，最難的地方就是對一個文件的壓縮。因為這里涉及到很多輸入輸出流，而且是我第一次寫關(guān)于文件操作的程序，在很多地方也是現(xiàn)學(xué)現(xiàn)做。在這里首先要感謝一下一本對我很重要的書 C+ programming primer plus，從這本書學(xué)到了很多關(guān)于文件操作的，比如如何進行二進制的寫入和讀入，如何進行退格等。在這里，遇到過的最難的一個問題就是EOF，在寫入的文件中，由于不知道如何識別文件尾，在寫代碼的時候遇到了很多問題，甚至有一次一直鉆研到晚上三點最后才發(fā)現(xiàn)原來系統(tǒng)庫里已經(jīng)有了很好的實現(xiàn)方法利用cin.fail()來識別，之前用過cin.eof()但還是失敗，甚至有一段時間還懷疑自己能否完成對一個文件的操作。還好，在primer的幫助下，我堅持下來了，并很出色地完成了這一任務(wù)。