數(shù)據(jù)結(jié)構(gòu)-哈夫曼樹實驗報告(包含文件壓縮).doc
《數(shù)據(jù)結(jié)構(gòu)-哈夫曼樹實驗報告(包含文件壓縮).doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)-哈夫曼樹實驗報告(包含文件壓縮).doc（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。
2008級數(shù)據(jù)結(jié)構(gòu)實驗報告 實驗名稱： 實驗三——實現(xiàn)哈夫曼樹 學(xué)生姓名： *** 班 級： ********** 班內(nèi)序號： ** 學(xué) 號： ******** 日 期： 2009年11月14日 1．實驗要求 利用二叉樹結(jié)構(gòu)實現(xiàn)赫夫曼編/解碼器。 基本要求： 1、 初始化(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） 0 1 2 3 4 5 6 7 8 ASCⅡ 97 115 100 102 103 weight 1 2 4 8 16 3 7 15 31 lchild -1 -1 -1 -1 －1 0 2 3 4 rchild －1 －1 －1 －1 －1 1 5 6 7 parent -5 5 -6 -7 -8 6 7 8 0 上結(jié)構(gòu)圖中，填充為黃色的部分為寫入內(nèi)存中的部分。每一行的部分為數(shù)組的下標(biāo)，左邊部分為所定義的結(jié)構(gòu)的成員。其中有的結(jié)點的父節(jié)點的下標(biāo)是一個負數(shù)，用來說明該節(jié)點是該節(jié)點的父節(jié)點的左孩子，正數(shù)說明的是該節(jié)點的父節(jié)點的右孩子。父節(jié)點這零的節(jié)點說明該節(jié)點是該哈夫曼樹的根節(jié)點。畫出樹的結(jié)構(gòu)如下畫所示：（結(jié)點中第一個數(shù)表示這個字符的ASCⅡ編碼，第二個數(shù)字表示權(quán)值） ^ 3 ^ 7 ^ 15 ^ 31 ^ 16 102 8 97 1 100 4 115 2 8 7 6 5 4 3 2 1 0 0 0 0 0 10 1 1 1 紅色箭頭表示父指針，黑色箭頭表示孩子指針 由上面的圖可知，原字符串編碼后的二進制編碼為 11101111111111011011011010101010101010100000000000000000 字符串中出現(xiàn)的所有的字符的編碼如下： a 1110 ； s 1111 ； d 110 ； f 10 ； g 0 2.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ù)組 Asc[256] 用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é)點是一個負數(shù)，則在這個字符的二進制編碼前面加一個0，若是一個負數(shù)，則加一個1。然后再查看其父節(jié)點的父節(jié)點的正負，一直走到根節(jié)點，再對下一個字符進行編碼。 偽代碼： 1、根據(jù)節(jié)點數(shù)組中葉子節(jié)點的個數(shù)，為編碼表申請足夠大的內(nèi)存空間； 2、對節(jié)點數(shù)組中的每一個葉子節(jié)點進行編碼，進行下面的操作 2．1、用一個帶型變量p指向葉子節(jié)點位置； 2．2、若這個節(jié)點的父節(jié)點是一個負數(shù)，則在這個字符的編碼前加一個0， 若是一個負數(shù)，則加一個1； 2．3、將這個節(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)在可以認為這個數(shù)組也是從小到大排序的，以這一條作為歸納假設(shè)開始證明： 假設(shè)現(xiàn)在已經(jīng)對節(jié)點進行了n次復(fù)合，且這n次復(fù)合成的非葉子節(jié)點的權(quán)值都是非遞減排列的，并且前n次復(fù)合的方法嚴格按照前面所說的方法進行。由于第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下載提示(請認真閱讀)
- 1.請仔細閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認領(lǐng)！既往收益都歸您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹 實驗 報告 包含 文件 壓縮
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://m.appdesigncorp.com/p-6547800.html