數(shù)據(jù)結(jié)構(gòu)哈夫曼樹(shù)實(shí)驗(yàn)報(bào)告(包含文件壓縮)

1、第第 頁(yè)日期：2009年11月14日1實(shí)驗(yàn)要求利用二叉樹(shù)結(jié)構(gòu)實(shí)現(xiàn)赫夫曼編/解碼器?；疽螅?初始化：能夠?qū)斎氲娜我忾L(zhǎng)度的字符串進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立赫夫曼樹(shù)、建立編碼表（的編碼輸出、編碼輸出。、譯碼出譯碼結(jié)果、打印:、建立編碼表（的編碼輸出、編碼輸出。、譯碼出譯碼結(jié)果、打印:利用已經(jīng)建好的赫夫曼樹(shù)進(jìn)行編碼，并將每個(gè)字符:根據(jù)編碼表對(duì)輸入的字符串進(jìn)行編碼，并將編碼后的字符串:利用已經(jīng)建好的赫夫曼樹(shù)對(duì)編碼后的字符串進(jìn)行譯碼，并輸:以直觀的方式打印赫夫曼樹(shù)（選作）、計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。測(cè)試數(shù)據(jù):提示:、用1戶(hù)界面可以設(shè)計(jì)為“菜

2、單”方式:能夠進(jìn)行交互。、根2據(jù)輸入的字符串中每個(gè)字符出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對(duì)沒(méi)有出現(xiàn)的字符一律不用編碼。2.程序分析2.1存儲(chǔ)結(jié)構(gòu)在哈夫曼樹(shù)編碼這個(gè)程序中，所有數(shù)據(jù)用的存儲(chǔ)結(jié)構(gòu)都是順序存儲(chǔ)結(jié)構(gòu)，其中包括順序表和樹(shù)（三叉樹(shù)）。樹(shù)的存儲(chǔ)結(jié)構(gòu)如下:（輸入的字符串為assddddffffffffgggggggggggggggg）IC/一上結(jié)構(gòu)圖中，填充為黃色的部分為寫(xiě)入內(nèi)存中的部分。每一行的部分為數(shù)組的下標(biāo)，左邊部分為所定義的結(jié)構(gòu)的成員。其中有的結(jié)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)是一個(gè)負(fù)數(shù)，用來(lái)說(shuō)明該節(jié)點(diǎn)是該節(jié)點(diǎn)的父節(jié)點(diǎn)的左孩子，正數(shù)說(shuō)明的是該節(jié)點(diǎn)的父節(jié)點(diǎn)的右孩子。父節(jié)點(diǎn)這零的節(jié)點(diǎn)說(shuō)明該節(jié)點(diǎn)是該哈夫曼樹(shù)的根節(jié)點(diǎn)。畫(huà)出

3、樹(shù)的結(jié)構(gòu)如下畫(huà)所示：（結(jié)點(diǎn)中第一個(gè)數(shù)表示這個(gè)字符的ASCII編碼，第二個(gè)數(shù)字表示權(quán)值）紅色箭頭表示父指針，黑色箭頭表示孩子指針由上面的圖可知，原字符串編碼后的二進(jìn)制編碼為字符串中出現(xiàn)的所有的字符的編碼如下：a1110；s1111；d110；f10；g02.2關(guān)鍵算法分析算法1：哈夫曼樹(shù)的構(gòu)造這個(gè)算法分兩個(gè)部分，每一個(gè)部分是對(duì)一個(gè)字符串中每個(gè)字符出現(xiàn)次數(shù)的統(tǒng)計(jì)，并為每一個(gè)出現(xiàn)的字符建立一個(gè)葉子節(jié)點(diǎn)；第二個(gè)部分是以上面的統(tǒng)計(jì)的數(shù)據(jù)為依據(jù)建立起一棵哈夫曼樹(shù)。問(wèn)題的規(guī)模由兩部分組成，一是字符串中總的字符的個(gè)數(shù)，二是這個(gè)字符串中出現(xiàn)的所有的不同的字符的個(gè)數(shù)。算法的第一部分須要對(duì)輸入的字符串進(jìn)行一次遍歷，

4、故其時(shí)間復(fù)雜度為,為了對(duì)每一個(gè)字符出現(xiàn)的次數(shù)進(jìn)行計(jì)數(shù)，程序在開(kāi)始的時(shí)候初始化了一個(gè)整形數(shù)組用個(gè)元素的存儲(chǔ)空間來(lái)分別計(jì)算可能出現(xiàn)的個(gè)字符在字符串中出現(xiàn)的頻數(shù)，因此這個(gè)算法的空間復(fù)雜度是一個(gè)常數(shù)，即。算法的第二部分是構(gòu)造一棵哈夫曼樹(shù)，這算法首先在之前每個(gè)出現(xiàn)過(guò)的字符的頻數(shù)的統(tǒng)計(jì)的依據(jù)下，為每一個(gè)字符建立一個(gè)節(jié)點(diǎn)。并按每一個(gè)葉子節(jié)點(diǎn)的權(quán)值進(jìn)行一次從大到小的排序（這里的排序所用的算法是冒泡算法），排序后的結(jié)果進(jìn)行哈夫曼樹(shù)的構(gòu)造（實(shí)際上就是為數(shù)組填入相關(guān)的數(shù)據(jù)）?，F(xiàn)在對(duì)審一部分的每一個(gè)小的部分進(jìn)行時(shí)間和空間復(fù)雜度的分析。對(duì)于建立節(jié)點(diǎn)這一部分，程序中并沒(méi)有用到額外的存儲(chǔ)空間，只用到之前所申請(qǐng)的51個(gè)1節(jié)點(diǎn)

5、空間的數(shù)組，故其空間復(fù)雜度為，遍歷了數(shù)組，差為出現(xiàn)過(guò)的個(gè)字符各自建立起了一個(gè)葉子節(jié)點(diǎn)，故其時(shí)間復(fù)雜度為。對(duì)于冒泡排序這個(gè)算法，無(wú)論輸入的問(wèn)題規(guī)模有多大，其調(diào)用的額外的存儲(chǔ)空間都是一個(gè)常數(shù)，易知其空間復(fù)雜度為；對(duì)于冒泡算法，其時(shí)間復(fù)雜度為n最后的一部分就是樹(shù)的構(gòu)造，對(duì)于一棵有個(gè)葉子節(jié)點(diǎn)樹(shù)，須要進(jìn)行次的復(fù)合，而每一次進(jìn)行復(fù)合所要運(yùn)行的語(yǔ)句數(shù)都是一個(gè)常數(shù)。故其時(shí)間復(fù)雜度是，其空間復(fù)雜度仍然是。該算法的自然描述如下：先對(duì)輸入的字符串進(jìn)行每一個(gè)所出現(xiàn)的字符出行頻數(shù)的統(tǒng)計(jì)，再為每一個(gè)字符建立一個(gè)葉子節(jié)點(diǎn)，并按每個(gè)葉子節(jié)點(diǎn)的權(quán)值進(jìn)行從小到大的排序。再?gòu)乃嬖诘墓?jié)點(diǎn)當(dāng)中尋找兩個(gè)權(quán)值之和最小的節(jié)點(diǎn)進(jìn)行復(fù)合，作為

6、一個(gè)新的節(jié)點(diǎn)的左右孩子，并把這個(gè)節(jié)點(diǎn)加入到節(jié)點(diǎn)數(shù)組之中，一直到數(shù)組中只剩下一個(gè)節(jié)點(diǎn)（這個(gè)結(jié)點(diǎn)最后作為哈夫曼樹(shù)的根節(jié)點(diǎn)用在捕的編碼之中）下面的偽代碼描述如下：1統(tǒng)計(jì)字符串出每個(gè)出現(xiàn)的符號(hào)出現(xiàn)的次數(shù)，把統(tǒng)計(jì)后的結(jié)果留在數(shù)組之路；2、為每一個(gè)在字符串中出現(xiàn)的結(jié)點(diǎn)建立一個(gè)葉子節(jié)點(diǎn)，并將每一個(gè)葉子節(jié)點(diǎn)的左右孩子及父節(jié)點(diǎn)設(shè)為-，1但未寫(xiě)入權(quán)值（后面的排序須要用到其權(quán)值，只要按這個(gè)葉子節(jié)點(diǎn)所存儲(chǔ)的字符找到其在數(shù)組中的位置即能找到其權(quán)值）；3、按每一個(gè)葉子節(jié)點(diǎn)的權(quán)值的大小進(jìn)行從小到大的排序，即要值小的葉子節(jié)點(diǎn)放在前面；4、寫(xiě)入每一個(gè)葉子節(jié)點(diǎn)的權(quán)值；5、在節(jié)點(diǎn)數(shù)組中找到兩個(gè)節(jié)點(diǎn)（包括葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)），使他

7、們的權(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ù)寫(xiě)入其父指針中，若是右孩子，則直接寫(xiě)到其父指針中。一直到數(shù)組中只剩下一個(gè)沒(méi)有進(jìn)行過(guò)復(fù)合的節(jié)點(diǎn)，并將這個(gè)節(jié)點(diǎn)作為哈夫曼樹(shù)的根節(jié)算法二：寫(xiě)編碼表這個(gè)算法的目的是按之前所建立的哈夫曼樹(shù)，為每一個(gè)所出現(xiàn)的字符進(jìn)行二進(jìn)制編碼，并寫(xiě)入編碼表。這個(gè)算法從節(jié)點(diǎn)數(shù)組中找到所有在字符串中出現(xiàn)過(guò)的字符，并一一為其進(jìn)行編碼，再寫(xiě)到編碼表里。該程序中的編碼表由一個(gè)類(lèi)的動(dòng)態(tài)數(shù)組組成，

8、它根據(jù)葉子節(jié)點(diǎn)的個(gè)數(shù)申請(qǐng)足夠大的內(nèi)存空間，再根據(jù)其在哈夫曼樹(shù)中的位置進(jìn)行編碼。編碼的過(guò)程是自下而上的，因而二進(jìn)制的編碼是從后面開(kāi)始的，為了實(shí)現(xiàn)這一編碼，程序中使用的類(lèi)的一個(gè)成員函數(shù)（即加法運(yùn)算符的重載）把新的一位二進(jìn)制數(shù)字加到該類(lèi)字符串的前面。一直加到哈夫曼樹(shù)的根節(jié)點(diǎn)為止。這個(gè)算法要對(duì)出現(xiàn)的個(gè)字符進(jìn)行編碼，由于每一個(gè)編碼的長(zhǎng)度不一樣，故不易從這里直接得到其時(shí)間復(fù)雜度。但考慮到兩種極端的情況，即所有編碼的長(zhǎng)度加起來(lái)最長(zhǎng)和最短的時(shí)候，其所用的空間復(fù)雜度分別為，由于每增加一個(gè)字符的空間，則就得調(diào)用一次的成員，故其時(shí)間復(fù)雜度也分別為，。該算法的自然語(yǔ)言描述為：對(duì)節(jié)點(diǎn)數(shù)組中的每一個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼，查看

9、其父節(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)，再對(duì)下一個(gè)字符進(jìn)行編碼。偽代碼：1、根據(jù)節(jié)點(diǎn)數(shù)組中葉子節(jié)點(diǎn)的個(gè)數(shù)，為編碼表申請(qǐng)足夠大的內(nèi)存空間；2、對(duì)節(jié)點(diǎn)數(shù)組中的每一個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼，進(jìn)行下面的操作21用一個(gè)帶型變量指向葉子節(jié)點(diǎn)位置；22、若這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是一個(gè)負(fù)數(shù)，則在這個(gè)字符的編碼前加一個(gè)0，若是一個(gè)負(fù)數(shù)，則加一個(gè)1；2、將這個(gè)節(jié)點(diǎn)父節(jié)點(diǎn)的位置的絕對(duì)值賦給，循環(huán)和的操作,直到指向的是根節(jié)點(diǎn)；2.3其他在構(gòu)造哈夫曼樹(shù)的時(shí)選取兩個(gè)權(quán)值之和最小的結(jié)點(diǎn)的時(shí)候，這個(gè)程序使用了一點(diǎn)小技巧，即先對(duì)葉子節(jié)

10、點(diǎn)進(jìn)行了一次排序，使權(quán)值小的節(jié)點(diǎn)放在數(shù)組的前面。這是為了在后面構(gòu)造樹(shù)的時(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)的尾部。為了更好說(shuō)明這個(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ù)組

11、看起來(lái)就像是一個(gè)隊(duì)列）。下面用數(shù)學(xué)歸納法簡(jiǎn)單地證明一下這種方法在每次進(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)值是從小到大排列的，開(kāi)始的時(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è)開(kāi)始證明：假設(shè)現(xiàn)在已經(jīng)對(duì)節(jié)點(diǎn)進(jìn)行了次復(fù)合，且這次復(fù)合成的非葉子節(jié)點(diǎn)的權(quán)值都是非遞減排列的，并且前次復(fù)合的方法嚴(yán)格按照前面所說(shuō)的方法進(jìn)行。由于第次復(fù)合的方法有三種可能性，而

12、第次復(fù)合的方法也有三種，現(xiàn)在要對(duì)這九種情況進(jìn)行分析。首先先肯定這兩次算命選取方法一樣的三種情況，因?yàn)檫@兩個(gè)數(shù)組都是從小到大進(jìn)行排列的，因?yàn)榈诖芜x擇的兩個(gè)節(jié)點(diǎn)的權(quán)值都不小于前兩次選擇的兩個(gè)節(jié)點(diǎn)。然后就是第次選擇第一種方法，每次選二種方法的，以及第次選擇第二種方法，每次選一種方法的。因?yàn)樵谶M(jìn)行第次復(fù)合的時(shí)候已經(jīng)對(duì)葉子節(jié)點(diǎn)數(shù)組前兩個(gè)節(jié)點(diǎn)和非葉子節(jié)點(diǎn)前兩個(gè)節(jié)點(diǎn)的權(quán)值之和進(jìn)行了一次比較，并在第次的時(shí)候選擇了比較小的一組，所以第復(fù)合之后的節(jié)點(diǎn)的權(quán)值之和必然會(huì)大于每次的?，F(xiàn)在就只剩下四種情況了。再來(lái)就是第次選擇第三種，第次選擇第一種（或第二種，由于兩種情況是對(duì)稱(chēng)的，這里就只說(shuō)明其中的一種）用把證法會(huì)比較容易

13、說(shuō)明，設(shè)、為葉子節(jié)點(diǎn)最靠前的三個(gè)節(jié)點(diǎn)，為非葉子節(jié)點(diǎn)最靠前的一個(gè)節(jié)點(diǎn)。則第次取的是和，第二次選的是和若又，由上兩式可得即第次選擇的并不不是兩個(gè)權(quán)值之和最小的兩個(gè)節(jié)點(diǎn)，故第二次不符合上面的選擇的方法；用同樣的方法可以證明剩下的兩種情況也是不符合情況的。證畢。3.程序運(yùn)行結(jié)果程序運(yùn)行的界面如下，通過(guò)用戶(hù)輸入指令運(yùn)行。可用的指令有如下幾條：（對(duì)一個(gè)字符串進(jìn)行編碼）（通過(guò)之前已經(jīng)建立過(guò)的哈夫曼樹(shù)，讓助用戶(hù)輸入一個(gè)由和組成的字符串，解釋用戶(hù)輸入的字符串），（清除之前輸入的所有數(shù)據(jù)），（打印出哈夫曼樹(shù)），（打印出最近一次輸入的字符串的哈夫曼編碼），（用哈夫曼編碼對(duì)一個(gè)文件進(jìn)行壓縮）,c對(duì)一個(gè)用哈夫曼編碼壓縮

14、后的文件解壓）,（停止運(yùn)行程序）對(duì)于輸入的字符串，可以任意輸入長(zhǎng)度（當(dāng)然，在內(nèi)存允許的范圍之內(nèi)！不然的話(huà)會(huì)出現(xiàn)一些無(wú)法預(yù)料的后果，由于作者還沒(méi)試過(guò)這樣浩大的工程，不能給出做這樣操作的后果）。對(duì)于對(duì)一個(gè)文件進(jìn)行壓縮，效果不一定很好（甚至還會(huì)越壓越大），畢竟在壓縮的文件里還必須得寫(xiě)入一些額外的數(shù)據(jù)（解壓鑰匙），所以對(duì)一些每一個(gè)字符出現(xiàn)概率都一樣的文件，根本沒(méi)有壓縮效果。但對(duì)于程序中測(cè)試的那個(gè)文件來(lái)說(shuō)，壓縮效果還是挺不錯(cuò)的（雖然別的壓縮算法壓的效果會(huì)更好）程序運(yùn)行的結(jié)果如下截圖：對(duì)于寫(xiě)這一個(gè)程序，最難的地方就是對(duì)一個(gè)文件的壓縮。因?yàn)檫@里涉及到很多輸入輸出流，而且是我第一次寫(xiě)關(guān)于文件操作的程序，在很多地方也是現(xiàn)學(xué)現(xiàn)做。在這