數(shù)據(jù)結(jié)構(gòu)-哈夫曼樹實(shí)驗(yàn)報(bào)告(包含文件壓縮).doc
《數(shù)據(jù)結(jié)構(gòu)-哈夫曼樹實(shí)驗(yàn)報(bào)告(包含文件壓縮).doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)-哈夫曼樹實(shí)驗(yàn)報(bào)告(包含文件壓縮).doc（6頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
2008級數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)名稱： 實(shí)驗(yàn)三——實(shí)現(xiàn)哈夫曼樹 學(xué)生姓名： *** 班 級： ********** 班內(nèi)序號： ** 學(xué) 號： ******** 日 期： 2009年11月14日 1．實(shí)驗(yàn)要求 利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)赫夫曼編/解碼器。 基本要求： 1、 初始化(Init)：能夠?qū)斎氲娜我忾L度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立赫夫曼樹 2、 建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹進(jìn)行編碼，并將每個(gè)字符的編碼輸出。 3、 編碼(Encoding)：根據(jù)編碼表對輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。 4、 譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹對編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。 5、 打印(Print)：以直觀的方式打印赫夫曼樹（選作） 6、 計(jì)算輸入的字符串編碼前和編碼后的長度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。 測試數(shù)據(jù)： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用戶界面可以設(shè)計(jì)為“菜單”方式：能夠進(jìn)行交互。 2、根據(jù)輸入的字符串中每個(gè)字符出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對沒有出現(xiàn)的 字符一律不用編碼。 2. 程序分析 2.1 存儲結(jié)構(gòu) 在哈夫曼樹編碼這個(gè)程序中，所有數(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é)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)是一個(gè)負(fù)數(shù)，用來說明該節(jié)點(diǎn)是該節(jié)點(diǎn)的父節(jié)點(diǎn)的左孩子，正數(shù)說明的是該節(jié)點(diǎn)的父節(jié)點(diǎn)的右孩子。父節(jié)點(diǎn)這零的節(jié)點(diǎn)說明該節(jié)點(diǎn)是該哈夫曼樹的根節(jié)點(diǎn)。畫出樹的結(jié)構(gòu)如下畫所示：（結(jié)點(diǎn)中第一個(gè)數(shù)表示這個(gè)字符的ASCⅡ編碼，第二個(gè)數(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 紅色箭頭表示父指針，黑色箭頭表示孩子指針 由上面的圖可知，原字符串編碼后的二進(jìn)制編碼為 11101111111111011011011010101010101010100000000000000000 字符串中出現(xiàn)的所有的字符的編碼如下： a 1110 ； s 1111 ； d 110 ； f 10 ； g 0 2.2 關(guān)鍵算法分析 算法1：哈夫曼樹的構(gòu)造 這個(gè)算法分兩個(gè)部分，每一個(gè)部分是對一個(gè)字符串中每個(gè)字符出現(xiàn)次數(shù)的統(tǒng)計(jì)，并為每一個(gè)出現(xiàn)的字符建立一個(gè)葉子節(jié)點(diǎn)；第二個(gè)部分是以上面的統(tǒng)計(jì)的數(shù)據(jù)為依據(jù)建立起一棵哈夫曼樹。 問題的規(guī)模由兩部分組成，一是字符串中總的字符的個(gè)數(shù)m，二是這個(gè)字符串中出現(xiàn)的所有的不同的字符的個(gè)數(shù)n。 算法的第一部分須要對輸入的字符串進(jìn)行一次遍歷，故其時(shí)間復(fù)雜度為O(m)，為了對每一個(gè)字符出現(xiàn)的次數(shù)進(jìn)行計(jì)數(shù)，程序在開始的時(shí)候初始化了一個(gè)整形數(shù)組 Asc[256] 用256個(gè)元素的存儲空間來分別計(jì)算可能出現(xiàn)的256個(gè)字符在字符串中出現(xiàn)的頻數(shù)，因此這個(gè)算法的空間復(fù)雜度是一個(gè)常數(shù)，即O(1)。 算法的第二部分是構(gòu)造一棵哈夫曼樹，這算法首先在之前每個(gè)出現(xiàn)過的字符的頻數(shù)的統(tǒng)計(jì)的依據(jù)下，為每一個(gè)字符建立一個(gè)節(jié)點(diǎn)。并按每一個(gè)葉子節(jié)點(diǎn)的權(quán)值進(jìn)行一次從大到小的排序（這里的排序所用的算法是冒泡算法），排序后的結(jié)果進(jìn)行哈夫曼樹的構(gòu)造（實(shí)際上就是為數(shù)組 hft 填入相關(guān)的數(shù)據(jù)）?，F(xiàn)在對審一部分的每一個(gè)小的部分進(jìn)行時(shí)間和空間復(fù)雜度的分析。對于建立節(jié)點(diǎn)這一部分，程序中并沒有用到額外的存儲空間，只用到之前所申請的511個(gè)節(jié)點(diǎn)空間的數(shù)組，故其空間復(fù)雜度為O(1)，遍歷了數(shù)組Asc，差為出現(xiàn)過的n個(gè)字符各自建立起了一個(gè)葉子節(jié)點(diǎn)，故其時(shí)間復(fù)雜度為O(n)。 對于冒泡排序這個(gè)算法，無論輸入的問題規(guī)模有多大，其調(diào)用的額外的存儲空間都是一個(gè)常數(shù)，易知其空間復(fù)雜度為O(1)；對于冒泡算法，其時(shí)間復(fù)雜度為O(n2)。 最后的一部分就是樹的構(gòu)造，對于一棵有n個(gè)葉子節(jié)點(diǎn)樹，須要進(jìn)行n-1次的復(fù)合，而每一次進(jìn)行復(fù)合所要運(yùn)行的語句數(shù)都是一個(gè)常數(shù)。故其時(shí)間復(fù)雜度是O(n)，其空間復(fù)雜度仍然是O(1)。 該算法的自然描述如下： 先對輸入的字符串進(jìn)行每一個(gè)所出現(xiàn)的字符出行頻數(shù)的統(tǒng)計(jì)，再為每一個(gè)字符建立一個(gè)葉子節(jié)點(diǎn)，并按每個(gè)葉子節(jié)點(diǎn)的權(quán)值進(jìn)行從小到大的排序。再從所存在的節(jié)點(diǎn)當(dāng)中尋找兩個(gè)權(quán)值之和最小的節(jié)點(diǎn)進(jìn)行復(fù)合，作為一個(gè)新的節(jié)點(diǎn)的左右孩子，并把這個(gè)節(jié)點(diǎn)加入到節(jié)點(diǎn)數(shù)組之中，一直到數(shù)組中只剩下一個(gè)節(jié)點(diǎn)（這個(gè)結(jié)點(diǎn)最后作為哈夫曼樹的根節(jié)點(diǎn)用在捕的編碼之中） 下面的 偽代碼描述如下： 1、統(tǒng)計(jì)字符串出每個(gè)出現(xiàn)的符號出現(xiàn)的次數(shù)，把統(tǒng)計(jì)后的結(jié)果留在數(shù)組Asc之路； 2、為每一個(gè)在字符串中出現(xiàn)的結(jié)點(diǎn)建立一個(gè)葉子節(jié)點(diǎn)，并將每一個(gè)葉子節(jié)點(diǎn) 的左右孩子及父節(jié)點(diǎn)設(shè)為-1，但未寫入權(quán)值（后面的排序須要用到其權(quán)值，只要按這個(gè)葉子節(jié)點(diǎn)所存儲的字符找到其在數(shù)組Asc中的位置即能找到其權(quán)值）； 3、按每一個(gè)葉子節(jié)點(diǎn)的權(quán)值的大小進(jìn)行從小到大的排序，即要值小的葉子節(jié)點(diǎn)放在前面； 4、寫入每一個(gè)葉子節(jié)點(diǎn)的權(quán)值； 5、在節(jié)點(diǎn)數(shù)組中找到兩個(gè)節(jié)點(diǎn)（包括葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)），使他們的權(quán)值之和最小。并將這兩個(gè)節(jié)點(diǎn)作為一個(gè)新的節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）的左右孩子，并將這兩個(gè)結(jié)點(diǎn)的權(quán)值之和作這個(gè)新的節(jié)點(diǎn)的權(quán)值,再將這兩個(gè)復(fù)合的節(jié)點(diǎn)的父節(jié)點(diǎn)指向這一個(gè)新的節(jié)點(diǎn)，若這個(gè)節(jié)點(diǎn)是該節(jié)點(diǎn)的父節(jié)點(diǎn)的左葉孩子，則將這個(gè)父節(jié)點(diǎn)在數(shù)組中的下標(biāo)的相反數(shù)寫入其父指針中，若是右孩子，則直接寫到其父指針中。一直到數(shù)組中只剩下一個(gè)沒有進(jìn)行過復(fù)合的節(jié)點(diǎn)，并將這個(gè)節(jié)點(diǎn)作為哈夫曼樹的根節(jié)點(diǎn)。 算法二：寫編碼表 這個(gè)算法的目的是按之前所建立的哈夫曼樹，為每一個(gè)所出現(xiàn)的字符進(jìn)行二進(jìn)制編碼，并寫入編碼表。 這個(gè)算法從節(jié)點(diǎn)數(shù)組中找到所有在字符串中出現(xiàn)過的字符，并一一為其進(jìn)行編碼，再寫到編碼表里。該程序中的編碼表由一個(gè)string類的動態(tài)數(shù)組組成，它根據(jù)葉子節(jié)點(diǎn)的個(gè)數(shù)申請足夠大的內(nèi)存空間，再根據(jù)其在哈夫曼樹中的位置進(jìn)行編碼。 編碼的過程是自下而上的，因而二進(jìn)制的編碼是從后面開始的，為了實(shí)現(xiàn)這一編碼，程序中使用的類的一個(gè)成員函數(shù) operator+ （即加法運(yùn)算符的重載）把新的一位二進(jìn)制數(shù)字加到該string類字符串的前面。一直加到哈夫曼樹的根節(jié)點(diǎn)為止。這個(gè)算法要對出現(xiàn)的n個(gè)字符進(jìn)行編碼，由于每一個(gè)編碼的長度不一樣，故不易從這里直接得到其時(shí)間復(fù)雜度。但考慮到兩種極端的情況，即所有編碼的長度加起來最長和最短的時(shí)候，其所用的空間復(fù)雜度分別為n(nlog2n)，n(n2)，由于每增加一個(gè)字符的空間，則就得調(diào)用一次string的成員operator+，故其時(shí)間復(fù)雜度也分別為n(nlog2n)，n(n2)。 該算法的自然語言描述為：對節(jié)點(diǎn)數(shù)組中的每一個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼，查看其父節(jié)點(diǎn)，若其父節(jié)點(diǎn)是一個(gè)負(fù)數(shù)，則在這個(gè)字符的二進(jìn)制編碼前面加一個(gè)0，若是一個(gè)負(fù)數(shù)，則加一個(gè)1。然后再查看其父節(jié)點(diǎn)的父節(jié)點(diǎn)的正負(fù)，一直走到根節(jié)點(diǎn)，再對下一個(gè)字符進(jìn)行編碼。 偽代碼： 1、根據(jù)節(jié)點(diǎn)數(shù)組中葉子節(jié)點(diǎn)的個(gè)數(shù)，為編碼表申請足夠大的內(nèi)存空間； 2、對節(jié)點(diǎn)數(shù)組中的每一個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼，進(jìn)行下面的操作 2．1、用一個(gè)帶型變量p指向葉子節(jié)點(diǎn)位置； 2．2、若這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是一個(gè)負(fù)數(shù)，則在這個(gè)字符的編碼前加一個(gè)0， 若是一個(gè)負(fù)數(shù)，則加一個(gè)1； 2．3、將這個(gè)節(jié)點(diǎn)父節(jié)點(diǎn)的位置的絕對值賦給p，循環(huán)2.2和2.3的操作， 直到p指向的是根節(jié)點(diǎn)； 2.3 其他 在構(gòu)造哈夫曼樹的時(shí)選取兩個(gè)權(quán)值之和最小的結(jié)點(diǎn)的時(shí)候，這個(gè)程序使用了一點(diǎn)小技巧，即先對葉子節(jié)點(diǎn)進(jìn)行了一次排序，使權(quán)值小的節(jié)點(diǎn)放在數(shù)組的前面。這是為了在后面構(gòu)造樹的時(shí)候免得再在節(jié)點(diǎn)數(shù)組中遍歷一次尋找符合要求的兩個(gè)節(jié)點(diǎn)。 這種方法的具體實(shí)現(xiàn)如下：每一次復(fù)合有三種選擇：在葉子節(jié)點(diǎn)中取出最靠前的兩個(gè)葉子節(jié)點(diǎn)進(jìn)行復(fù)合、在非葉子節(jié)點(diǎn)中取出最靠前的兩個(gè)節(jié)點(diǎn)進(jìn)行復(fù)合、在葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)中各取出一個(gè)最靠前的節(jié)點(diǎn)進(jìn)行復(fù)合。每次復(fù)合只要找到三種方法中其復(fù)合節(jié)點(diǎn)權(quán)值最小的一種，再把復(fù)合后的節(jié)點(diǎn)放到非葉子節(jié)點(diǎn)的尾部。 為了更好說明這個(gè)辦法的可行性，在這里假設(shè)程序中將葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)放在兩個(gè)不同的數(shù)組中，每次復(fù)合節(jié)點(diǎn)時(shí)在這兩個(gè)數(shù)組中找到合適的兩個(gè)節(jié)點(diǎn)進(jìn)行復(fù)合，并放到非葉子節(jié)點(diǎn)數(shù)組的尾部（這個(gè)非葉子節(jié)點(diǎn)的數(shù)組看起來就像是一個(gè)隊(duì)列）。下面用數(shù)學(xué)歸納法簡單地證明一下這種方法在每次進(jìn)行復(fù)合的時(shí)候選擇的都是權(quán)值之和最小的兩節(jié)點(diǎn)： 為了達(dá)到上面的證明，只要證明每次復(fù)合后的節(jié)點(diǎn)的權(quán)值都不小于上一次復(fù)合即可。 已知葉子節(jié)點(diǎn)的數(shù)組中的節(jié)點(diǎn)的權(quán)值是從小到大排列的，開始的時(shí)候從葉子節(jié)點(diǎn)數(shù)組中取出兩個(gè)節(jié)點(diǎn)進(jìn)行復(fù)合，并把復(fù)合后的節(jié)點(diǎn)放到非葉子節(jié)點(diǎn)的數(shù)組中去。因?yàn)榉侨~子節(jié)點(diǎn)數(shù)組中只有一個(gè)元素，所以我們現(xiàn)在可以認(rèn)為這個(gè)數(shù)組也是從小到大排序的，以這一條作為歸納假設(shè)開始證明： 假設(shè)現(xiàn)在已經(jīng)對節(jié)點(diǎn)進(jìn)行了n次復(fù)合，且這n次復(fù)合成的非葉子節(jié)點(diǎn)的權(quán)值都是非遞減排列的，并且前n次復(fù)合的方法嚴(yán)格按照前面所說的方法進(jìn)行。由于第n次復(fù)合的方法有三種可能性，而第n+1次復(fù)合的方法也有三種，現(xiàn)在要對這九種情況進(jìn)行分析。 首先先肯定這兩次算命選取方法一樣的三種情況，因?yàn)檫@兩個(gè)數(shù)組都是從小到大進(jìn)行排列的，因?yàn)榈趎+1次選擇的兩個(gè)節(jié)點(diǎn)的權(quán)值都不小于前兩次選擇的兩個(gè)節(jié)點(diǎn)。然后就是第n次選擇第一種方法，每n+1次選二種方法的，以及第n次選擇第二種方法，每n+1次選一種方法的。因?yàn)樵谶M(jìn)行第n次復(fù)合的時(shí)候已經(jīng)對葉子節(jié)點(diǎn)數(shù)組前兩個(gè)節(jié)點(diǎn)和非葉子節(jié)點(diǎn)前兩個(gè)節(jié)點(diǎn)的權(quán)值之和進(jìn)行了一次比較，并在第n次的時(shí)候選擇了比較小的一組，所以第n+1復(fù)合之后的節(jié)點(diǎn)的權(quán)值之和必然會大于每n次的?，F(xiàn)在就只剩下四種情況了。再來就是第n次選擇第三種，第n+1次選擇第一種（或第二種，由于兩種情況是對稱的，這里就只說明其中的一種）用把證法會比較容易說明 ，設(shè) a1、a2、a3為葉子節(jié)點(diǎn)最靠前的三個(gè)節(jié)點(diǎn)，b1為非葉子節(jié)點(diǎn)最靠前的一個(gè)節(jié)點(diǎn)。則第n次取的是a1和b1，第二次選的是a2和a3若a2+a3下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎勵(lì)！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹 實(shí)驗(yàn) 報(bào)告 包含 文件 壓縮
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
相關(guān)搜索
鏈接地址：http://m.appdesigncorp.com/p-6547800.html