哈夫曼編碼解碼器的實(shí)現(xiàn)課程設(shè)計(jì)

1、課程設(shè)計(jì)報(bào)告 院（系）:_電氣與信息工程學(xué)院_ 專(zhuān)業(yè)班級(jí): 計(jì)科普 學(xué)生姓名: 學(xué) 號(hào): 設(shè)計(jì)地點(diǎn)（單位）_計(jì)算機(jī)基礎(chǔ)自主學(xué)習(xí)中心_ _設(shè)計(jì)題目:_哈夫曼編碼解碼器的實(shí)現(xiàn) _ _ 完成日期： 指導(dǎo)教師評(píng)語(yǔ): _ _ _ 成績(jī)（五級(jí)記分制）:_ _ 指導(dǎo)教師（簽字）:_ _ 課程設(shè)計(jì)任務(wù)書(shū)設(shè)計(jì)題目：哈夫曼編碼解碼器的實(shí)現(xiàn)學(xué)生姓名課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)專(zhuān)業(yè)班級(jí)計(jì)科地 點(diǎn)計(jì)算機(jī)基礎(chǔ)自主學(xué)習(xí)中心起止時(shí)間設(shè)計(jì)內(nèi)容及要求功能：利用哈夫曼編碼對(duì)數(shù)據(jù)進(jìn)行無(wú)損壓縮，實(shí)現(xiàn)Huffman壓縮的編碼器和譯碼器。1. 首先讀入待壓縮源文件。2. 然后建立并分析字母表，對(duì)每種字符的出現(xiàn)頻度進(jìn)行統(tǒng)計(jì)，以頻度作為建立Huf

2、fman樹(shù)的權(quán)值。3.頻度表建好后，就可以根據(jù)算法建立Huffman樹(shù)，對(duì)出現(xiàn)的每種字符進(jìn)行Huffman編碼。4. 此時(shí)，再次讀入源文件，逐字節(jié)編碼，將得到的編碼流寫(xiě)入到磁盤(pán)文件，并且計(jì)算壓縮率。5. 譯碼過(guò)程先讀入被壓縮的文件，將其解釋為比特流，根據(jù)Huffman樹(shù)，對(duì)比特流逐位譯碼，將譯碼結(jié)果逐次寫(xiě)入到磁盤(pán)文件。要求：完成編碼譯碼功能。設(shè)計(jì)參數(shù) 測(cè)試數(shù)據(jù)要求：自行設(shè)計(jì)。 輸出數(shù)據(jù)要求：輸出每個(gè)字符（或是詞）的使用頻率，及編碼規(guī)則。進(jìn)度要求2011.1.4 星期二（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、完成任務(wù)的講解、并接受課程設(shè)計(jì)任務(wù)，選定課程設(shè)計(jì)的題目2011.1.5 星期三（上午教師指導(dǎo)

3、，下午學(xué)生獨(dú)立完成）、了解任務(wù)的算法、并畫(huà)出算法的程序流程圖2011.1.6 星期四（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、對(duì)任務(wù)的關(guān)鍵技術(shù)進(jìn)行驗(yàn)證、并確定解決辦法2011.1.7 星期五（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、編制任務(wù)的程序2011.1.10 星期一（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、編制任務(wù)的程序2011.1.11 星期二（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、對(duì)程序的調(diào)試，并試運(yùn)行。2011.1.12 星期三（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、整理課程設(shè)計(jì)過(guò)程中的各個(gè)參數(shù)、并進(jìn)行總結(jié)，提出改進(jìn)意見(jiàn)2011.1.13 星期四（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、編寫(xiě)課程設(shè)計(jì)報(bào)告、準(zhǔn)備答辨

4、2011.1.14 星期五（上午答辨）、進(jìn)行答辨驗(yàn)收工作。參考資料其它說(shuō)明.本表應(yīng)在每次實(shí)施前一周由負(fù)責(zé)教師填寫(xiě)二份，院系審批后交院系辦備案，一份由負(fù)責(zé)教師留用。.若填寫(xiě)內(nèi)容較多可另紙附后。3.一題多名學(xué)生共用的，在設(shè)計(jì)內(nèi)容、參數(shù)、要求等方面應(yīng)有所區(qū)別。教研室主任： 指導(dǎo)教師： 摘要 哈夫曼編碼是廣泛用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。哈夫曼編碼算法使用字符在文件中出現(xiàn)的頻率，并用哈夫曼樹(shù)來(lái)建立一個(gè)用01串表示各字符的最優(yōu)表示方式。通過(guò)0，1串替換字符，并壓縮為bit流寫(xiě)入文件，從而實(shí)現(xiàn)文件的壓縮，解壓則通過(guò)讀取文件頭和文件尾的解碼規(guī)則，實(shí)現(xiàn)文件的解壓。本程序就是基于以上原理設(shè)計(jì)了壓縮、解壓

5、和打印哈夫曼編碼的功能。本程序經(jīng)過(guò)測(cè)試后，功能均能實(shí)現(xiàn)，運(yùn)行穩(wěn)定。關(guān)鍵詞：哈夫曼編碼 壓縮 01串 bit流 二叉樹(shù) 目錄 TOC o 1-3 h z u HYPERLINK l _Toc282707582 摘要 PAGEREF _Toc282707582 h I HYPERLINK l _Toc282707583 1需求分析 PAGEREF _Toc282707583 h 1 HYPERLINK l _Toc282707584 2系統(tǒng)分析與設(shè)計(jì) PAGEREF _Toc282707584 h 1 HYPERLINK l _Toc282707585 算法設(shè)計(jì) PAGEREF _Toc28270

6、7585 h 1 HYPERLINK l _Toc282707586 程序流程圖 PAGEREF _Toc282707586 h 1 HYPERLINK l _Toc282707587 程序模塊圖 PAGEREF _Toc282707587 h 1 HYPERLINK l _Toc282707588 2.2.3 Compress()函數(shù)流程圖 PAGEREF _Toc282707588 h 2 HYPERLINK l _Toc282707589 2.2.4 Uncompress()函數(shù)流程圖 PAGEREF _Toc282707589 h 3 HYPERLINK l _Toc282707590

7、 2.2.4 文本存儲(chǔ)示意圖 PAGEREF _Toc282707590 h 4 HYPERLINK l _Toc282707591 2.3 關(guān)鍵代碼分析 PAGEREF _Toc282707591 h 4 HYPERLINK l _Toc282707592 結(jié)構(gòu)體定義 PAGEREF _Toc282707592 h 5 HYPERLINK l _Toc282707593 數(shù)組的初始化 PAGEREF _Toc282707593 h 5 HYPERLINK l _Toc282707594 2.3.3 生成Huffman樹(shù) PAGEREF _Toc282707594 h 6 HYPERLINK

8、l _Toc282707595 2.3.4 生成Huffmancode PAGEREF _Toc282707595 h 7 HYPERLINK l _Toc282707596 3軟件測(cè)試 PAGEREF _Toc282707596 h 9 HYPERLINK l _Toc282707597 測(cè)試壓縮功能 PAGEREF _Toc282707597 h 9 HYPERLINK l _Toc282707598 測(cè)試解壓功能 PAGEREF _Toc282707598 h 9 HYPERLINK l _Toc282707599 測(cè)試Huffmancode打印功能 PAGEREF _Toc282707

9、599 h 10 HYPERLINK l _Toc282707600 4總結(jié) PAGEREF _Toc282707600 h 11 HYPERLINK l _Toc282707601 5軟件使用說(shuō)明書(shū) PAGEREF _Toc282707601 h 13 HYPERLINK l _Toc282707602 致謝 PAGEREF _Toc282707602 h 14 HYPERLINK l _Toc282707603 參考文獻(xiàn) PAGEREF _Toc282707603 h 15 HYPERLINK l _Toc282707604 附錄 PAGEREF _Toc282707604 h 161需求

10、分析在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來(lái)越引起人們的重視，哈夫曼在上世紀(jì)五十年代初就提出這種編碼時(shí)，根據(jù)字符出現(xiàn)的概率來(lái)構(gòu)造平均長(zhǎng)度最短的編碼，是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹(shù)即最優(yōu)二叉樹(shù)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈夫曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來(lái)的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而

11、達(dá)到無(wú)損壓縮數(shù)據(jù)的目的）。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹(shù)求得的用于通信的二進(jìn)制編碼稱(chēng)為哈夫曼編碼。樹(shù)中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹(shù)的分支表示“0”碼，指向右子樹(shù)的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)葉子對(duì)應(yīng)的字符的編碼，這就是哈夫曼編碼。哈夫曼譯碼輸入字符串可以把它編譯成二進(jìn)制代碼，輸入二進(jìn)制代碼時(shí)可以編譯成字符串。哈夫曼編碼所以能產(chǎn)生較短的碼文，是因?yàn)楣蚵鼧?shù)具有最小加權(quán)路徑長(zhǎng)度的二叉樹(shù)。如果葉結(jié)點(diǎn)的權(quán)值恰好是某個(gè)需編碼的文本中各字符出現(xiàn)的次數(shù)，則編碼后文本的長(zhǎng)度就是該哈夫曼樹(shù)的加權(quán)路徑長(zhǎng)度。譯碼過(guò)程為自做向右逐一掃描碼文，并從

12、哈夫曼樹(shù)的根開(kāi)始，將掃到的二進(jìn)制位串中的相鄰位與哈夫曼樹(shù)上標(biāo)的0，1相匹配，以確定一條從根到葉子結(jié)點(diǎn)的路徑，一旦到達(dá)葉子，則譯出了一個(gè)字符。本程序具有對(duì)文本壓縮和解壓的功能，并能打印出哈夫曼編碼。2系統(tǒng)分析與設(shè)計(jì)算法設(shè)計(jì)Huffman編碼是一種可變長(zhǎng)編碼方式，是二叉樹(shù)的一種特殊轉(zhuǎn)化形式。編碼的原理是：將使用次數(shù)多的代碼轉(zhuǎn)換成長(zhǎng)度較短的代碼，而使用次數(shù)少的可以使用較長(zhǎng)的編碼，并且保持編碼的唯一可解性。Huffman算法的最根本的原則是：累計(jì)的(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長(zhǎng)度)為最小，也就是權(quán)值(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長(zhǎng)度)的和最小。權(quán)值統(tǒng)計(jì)：因?yàn)槭翘幚砦谋疚募?，本程序定義了512個(gè)結(jié)構(gòu)體數(shù)組

13、，因?yàn)橐粋€(gè)字節(jié)存儲(chǔ)的范圍是0255，及256個(gè)字符（包括漢字的半個(gè)編碼），根據(jù)定義Huffman樹(shù)的節(jié)點(diǎn)個(gè)數(shù)m=2*n-1,所以512個(gè)數(shù)組剛好能把所有字符統(tǒng)計(jì)出來(lái)。在逐個(gè)讀取文本字符的時(shí)候，根據(jù)字符的ASCII碼做為數(shù)組下標(biāo)，同時(shí)初始化512個(gè)數(shù)組，并將文件中存在的字符的ASCII碼存入對(duì)應(yīng)的結(jié)構(gòu)體中。生成Huffman樹(shù)：每次取最小的那兩個(gè)節(jié)點(diǎn)(node)合并成一個(gè)節(jié)點(diǎn)(node)，并且將累計(jì)數(shù)值相加作為新的接點(diǎn)的累計(jì)數(shù)值，最頂層的是根節(jié)點(diǎn)(root) 注：列表中最小節(jié)點(diǎn)的是指包括合并了的節(jié)點(diǎn)在內(nèi)的所有節(jié)點(diǎn)，已經(jīng)合并的節(jié)點(diǎn)不在列表。生成Huffmancode：根據(jù)Huffman樹(shù)中個(gè)節(jié)點(diǎn)的

14、關(guān)系生成Huffmancode，規(guī)則為左節(jié)點(diǎn)編碼0，右節(jié)點(diǎn)編碼1.將編碼裝入結(jié)構(gòu)體。寫(xiě)入文件：讀取文件中字符，按照對(duì)應(yīng)的編碼和文件中的字符順序，拼接成大于8的字符串，使用位操作轉(zhuǎn)化為bit流。滿一個(gè)字節(jié)就寫(xiě)入壓縮后的文件中，重復(fù)上述過(guò)程。解壓：首先讀取解壓文件的文件頭和尾部的解壓法則，按照解壓法則，將文件恢復(fù)到解壓的文件中。解壓法則實(shí)際上就是字符對(duì)應(yīng)的Huffman編碼。程序流程圖.1程序模塊圖以下為主函數(shù)對(duì)個(gè)函數(shù)的調(diào)用關(guān)系圖，其中Compress()為文本壓縮函數(shù)，Uncompress()為文本解壓函數(shù)，printHUMcode()為哈夫曼編碼打印函數(shù)，printMenu()為菜單顯示函數(shù)。

15、Main()Compress()Uncompress()printHUMcode()printMenu()圖2.1 模塊圖.2程序流程圖程序開(kāi)始后，提示用戶(hù)選擇操作功能。1：壓縮文件；2：解壓文件；3：打印哈夫曼編碼；0：退出程序。當(dāng)功能完成后，繼續(xù)循環(huán)（0除外）。開(kāi)始C=Getch()TC=1Compress()breakFTUncompres()breakC=2FTC=3printHUMcode()breakFFC=0輸入有誤breakT結(jié)束圖2.2 程序流程圖.3 Compress()函數(shù)流程圖調(diào)用Compress()函數(shù)，輸入源文件地址，和目標(biāo)文件地址后。函數(shù)開(kāi)始讀取字符進(jìn)行頻率統(tǒng)計(jì)，

16、根據(jù)頻率從大到小對(duì)512個(gè)數(shù)組排序。接下來(lái)用排序后的數(shù)組生成Huffman樹(shù)，然后根據(jù)Huffman中的各元素的關(guān)系生成Huffmancode,然后根據(jù)編碼對(duì)文件中的字符進(jìn)行替換，并壓縮為bit流寫(xiě)入目標(biāo)文件。開(kāi)始輸入源文件和目標(biāo)文件統(tǒng)計(jì)頻率數(shù)組排序生成Huffman樹(shù)生成Huffmancode轉(zhuǎn)化bit流寫(xiě)入文件結(jié)束圖2.3 Compress()函數(shù)流程圖.4 Uncompress()函數(shù)流程圖 Uncompress()函數(shù)先讀取解壓文件頭和尾部的解壓法則，對(duì)文件中間的字符進(jìn)行解壓。開(kāi)始輸入源文件和目標(biāo)文件讀取解壓法則對(duì)文本中間的數(shù)據(jù)解壓寫(xiě)入目標(biāo)文件結(jié)束圖2.4 Uncompress()函數(shù)

17、流程圖.4 文本存儲(chǔ)示意圖字符在存儲(chǔ)的時(shí)候，前04個(gè)字節(jié)存儲(chǔ)源文件字符個(gè)數(shù)，58個(gè)字節(jié)存儲(chǔ)壓縮后字符個(gè)數(shù)。接下來(lái)存儲(chǔ)壓縮后的字符及01串，緊接著是字符種類(lèi)，然后是字符，再然后是字符對(duì)應(yīng)編碼的長(zhǎng)度，最后是字符對(duì)應(yīng)的編碼。源文件字符個(gè)數(shù)壓縮后字符個(gè)數(shù)010101字符種類(lèi)字符字符編碼長(zhǎng)度字符對(duì)應(yīng)編碼圖2.5 文本存儲(chǔ)示意圖2.3 關(guān)鍵代碼分析結(jié)構(gòu)體定義typedef struct HuffmanTree unsigned char b; /記錄字符的ASC碼long count; /字符出現(xiàn)頻率（權(quán)值） long parent,lch,rch; /定義哈夫曼樹(shù)指針變量char bits256; /定

18、義存儲(chǔ)哈夫曼編碼的數(shù)組Huffman;數(shù)組的初始化 此段代碼不但實(shí)現(xiàn)了對(duì)512個(gè)數(shù)組的初始化，還實(shí)現(xiàn)了將文件中出現(xiàn)的字符放入以字符ASCII碼確定下標(biāo)的數(shù)組中，方便查找。while(!feof(ifp) fread(&c,1,1,ifp); headerc.count+; /字符重復(fù)出現(xiàn)頻率+1 flength+; /字符出現(xiàn)原文件長(zhǎng)度+1flength-; /文件末尾讀了兩次length1=flength; /原文件長(zhǎng)度用作求壓縮率的分母headerc.count-; for(i=0;i512;i+) /初始化數(shù)組 if(headeri.count!=0) headeri.b=(unsign

19、ed char)i; /記錄該數(shù)組對(duì)應(yīng)的字符的ASC碼 else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /對(duì)結(jié)點(diǎn)進(jìn)行初始化 生成Huffman樹(shù)每次取最小的那兩個(gè)節(jié)點(diǎn)合并成一個(gè)節(jié)點(diǎn)，并且將累計(jì)數(shù)值相加作為新的接點(diǎn)的累計(jì)數(shù)值，最頂層的是根節(jié)點(diǎn)。新生成的節(jié)點(diǎn)全部放在緊接在數(shù)組中存儲(chǔ)節(jié)點(diǎn)的最后一個(gè)后面 注：列表中最小節(jié)點(diǎn)的是指包括合并了的節(jié)點(diǎn)在內(nèi)的所有節(jié)點(diǎn)，已經(jīng)合并的節(jié)點(diǎn)不在列表。for(i=0;in;i+) f=i; headeri.bits0=0; /起始符為空 while(headerf.parent!=-1) j

20、=f; f=headerf.parent; if(headerf.lch=j) /判斷是否為左孩子 j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=0; else /置右分支編碼1 j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=1; 生成Huffmancode 生成Huffman的原理是通過(guò)位操作，將01的字符串，轉(zhuǎn)換為bit流，如果當(dāng)前為0的話則向左移以為，若為1的話則

21、向左移以為并或上1。while(!feof(ifp) c=fgetc(ifp); f+; for(i=0;i=8) /對(duì)哈夫曼編碼位操作進(jìn)行壓縮存儲(chǔ) for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c0) /對(duì)哈夫曼編碼位操作進(jìn)行壓縮存儲(chǔ)strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); pt1+; 3軟件測(cè)試 為源文件，為壓縮后的文件。圖3.2 壓縮后文件對(duì)比圖3.3 解壓功能測(cè)試圖3.4 解壓后文件對(duì)比Huffmancode打印

22、功能圖3.4 哈夫曼編碼打印4總結(jié)由于本課題中的許多知識(shí)點(diǎn)都沒(méi)有學(xué)過(guò)都要靠自己到課外的資料中去查找。在用的時(shí)候難免出現(xiàn)這樣那樣的錯(cuò)誤。回顧起此次課程設(shè)計(jì)，至今我仍感慨頗多，的確，從拿到題目到完成整個(gè)編程，從理論到實(shí)踐，在將近半個(gè)月的日子里，可以學(xué)到很多很多的東西，同時(shí)不僅可以鞏固了以前所學(xué)過(guò)的知識(shí)，而且學(xué)到了很多在書(shū)本上所沒(méi)有學(xué)到過(guò)的知識(shí)。通過(guò)這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才能提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。在設(shè)計(jì)的過(guò)程中遇到問(wèn)題，可以說(shuō)得是困難重重，這畢竟第一次做的，難免會(huì)遇到過(guò)各種

23、各樣的問(wèn)題，同時(shí)在設(shè)計(jì)的過(guò)程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過(guò)的知識(shí)理解得不夠深刻，掌握得不夠牢固，比如說(shuō)文本操作通過(guò)這次課程設(shè)計(jì)之后，一定把以前所學(xué)過(guò)的知識(shí)鞏固一下。本次課程設(shè)計(jì)結(jié)束了，對(duì)于我的影響很大。我通過(guò)這次實(shí)踐學(xué)到了許多知識(shí)。學(xué)到了設(shè)計(jì)一個(gè)程序。要注意哪些方面。也使我知道自己哪些方面做得還不夠。5軟件使用說(shuō)明書(shū)1)選擇1：壓縮功能。 若源文件在根文件夾中直接輸入文件如1.txt。如果在其它地方，這注明路徑如e:1.txt。 2)選擇2：解壓功能。 解壓時(shí)直接輸入解壓文件名，如a，程序會(huì)自動(dòng)個(gè)a加上.hub的后綴名。存儲(chǔ)文件可以寫(xiě)為X.txt.圖3.3 解壓功能測(cè)試3)選擇3：打印哈

24、夫曼編碼。4)選擇0：退出程序。致謝首先感謝我的父母，沒(méi)有他們辛勤的付出也就沒(méi)有我的今天，在這一刻，將最崇高的敬意獻(xiàn)給你們！同時(shí)感謝向毅、陳劉奎、熊茜老師，他們不求回報(bào)，無(wú)私奉獻(xiàn)的精神很讓我感動(dòng)，再次向他表示由衷的感謝。在這幾學(xué)期中結(jié)識(shí)的各位生活和學(xué)習(xí)上的摯友讓我得到了人生最大的一筆財(cái)富。在此，也對(duì)他們表示衷心感謝。本文參考了大量的文獻(xiàn)資料，在此，向各學(xué)術(shù)界的前輩們致敬！簽名： 付作輝 日期 2011/1/12參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.清華大學(xué)出版社.2 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）.清華大學(xué)出版社.3 DATA STRUCTURE WITH C+. Wil

25、liam Ford,William Topp .清華大學(xué)出版社（影印版）. 4 譚浩強(qiáng).c語(yǔ)言程序設(shè)計(jì). 清華大學(xué)出版社. 5 數(shù)據(jù)結(jié)構(gòu)與算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 張銘,劉曉丹譯 電子工業(yè)出版社 2001 年1月6 附錄程序代碼/主函數(shù)#include #include #include #include #includeHuffmantype.h#includeprintMenu.h#in

26、cludecompress.h#includeuncompress.h#includeprintHUMcode.h/*主函數(shù)*/int main() int c;Huffman header512=0;Huffman header1512=0;Huffman tmp;while(1) printMenu();/菜單工具欄 do printf(nt*請(qǐng)選擇相應(yīng)功能(0-3):); c=getch(); printf(%cn,c); if(c!=0 & c!=1 & c!=2 & c!=3) printf(t請(qǐng)檢查您的輸入在03之間！n); printf(t請(qǐng)?jiān)佥斎胍槐?！n); while(c!=

27、0 & c!=1 & c!=2 & c!=3); if(c=1) compress(header,header1,tmp); /調(diào)用壓縮子函數(shù) else if(c=2) uncompress(header,tmp); /調(diào)用解壓縮子函數(shù) else if(c=3) printHUMcode(header1); /調(diào)用打印編碼子函數(shù) else printf(t歡迎您再次使用n); exit(0); /退出該工具 system(pause); /任意鍵繼續(xù) system(cls); /清屏return 0;/void compress(Huffman *header,Huffman *header1

28、,Huffman &tmp) char filename255,outputfile255,buf100; unsigned char c; long i,j,m,n,f; long min1,pt1,flength,length1,length2; double div;FILE *ifp,*ofp; printf(t請(qǐng)您輸入需要壓縮的文件：); gets(filename); ifp=fopen(filename,rb); if(ifp=NULL) printf(nt文件打開(kāi)失敗!nn); return; printf(t請(qǐng)您輸入壓縮后的文件名：); gets(outputfile); o

29、fp=fopen(strcat(outputfile,.hub),wb); if(ofp=NULL) printf(nt壓縮文件失敗!nn); return; flength=0; while(!feof(ifp) fread(&c,1,1,ifp); headerc.count+; /字符重復(fù)出現(xiàn)頻率+1 flength+; /字符出現(xiàn)原文件長(zhǎng)度+1flength-; /文件末尾讀了兩次length1=flength; /原文件長(zhǎng)度用作求壓縮率的分母headerc.count-; for(i=0;i512;i+) /初始化數(shù)組 if(headeri.count!=0) headeri.b=(

30、unsigned char)i; /記錄該數(shù)組對(duì)應(yīng)的字符的ASC碼 else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /對(duì)結(jié)點(diǎn)進(jìn)行初始化 for(i=0;i256;i+) /根據(jù)頻率（權(quán)值）大小，對(duì)結(jié)點(diǎn)進(jìn)行排序，選擇較小的結(jié)點(diǎn)進(jìn)樹(shù) for(j=i+1;j256;j+) if(headeri.countheaderj.count)/從大小 tmp=headeri; headeri=headerj; headerj=tmp; for(i=0;i256;i+) if(headeri.count=0) break; n=i;

31、 /外部葉子結(jié)點(diǎn)數(shù)為n個(gè)時(shí)，內(nèi)部結(jié)點(diǎn)數(shù)為n-1，整個(gè)哈夫曼樹(shù)的需要的結(jié)點(diǎn)數(shù)為2*n-1. m=2*n-1;for(i=n;im;i+) /構(gòu)建哈夫曼樹(shù) min1=999999999; /預(yù)設(shè)的最大權(quán)值，即結(jié)點(diǎn)出現(xiàn)的最大次數(shù) for(j=0;jheaderj.count) /找權(quán)值最小的那個(gè)數(shù)組 pt1=j; min1=headerj.count; continue; headeri.count=headerpt1.count; /在原有的基礎(chǔ)上向后面添加數(shù)組 headerpt1.parent=i; /記錄parent的下標(biāo) headeri.lch=pt1; /記錄左孩子的下標(biāo) min1=999

32、999999; for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count+=headerpt1.count; headeri.rch=pt1; /記錄右分支下標(biāo) headerpt1.parent=i; /記錄parent下標(biāo)/*生成哈夫曼編碼*/for(i=0;in;i+) f=i; headeri.bits0=0; /起始符為空 while(headerf.parent!=-1) j=f; f=headerf.parent; if(headerf.lch=j) /判斷是否為左孩子 j=strlen(h

33、eaderi.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=0; else /置右分支編碼1 j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=1; for(i=0;headeri.b!=0;i+)header1i=headeri;/ fseek(ifp,0,SEEK_SET);/文件定位 fwrite(&flength,sizeof(int),1,ofp); fseek(ofp,8,SEEK_SET);

34、buf0=0; f=0; /記錄字符 pt1=8; while(!feof(ifp) c=fgetc(ifp); f+; for(i=0;i=8) /對(duì)哈夫曼編碼位操作進(jìn)行壓縮存儲(chǔ) for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c0) /對(duì)哈夫曼編碼位操作進(jìn)行壓縮存儲(chǔ) strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); pt1+; fseek(ofp,4,SEEK_SET); fwrite(&pt1,sizeof(long),1,

35、ofp); fseek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(long),1,ofp); for(i=0;in;i+) fwrite(&(headeri.b),1,1,ofp); c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0) /若存儲(chǔ)的位數(shù)不是8的倍數(shù)，則補(bǔ)0 for(f=j%8;f8;f+) strcat(headeri.bits,0); while(headeri.bits0!=0) /判斷是否為空 c=0; for(j=0;j8;j+) /字符

36、的有效存儲(chǔ)不超過(guò)8位，則對(duì)有效位數(shù)左移實(shí)現(xiàn)兩字符編碼的連接 if(headeri.bitsj=1) c=(c1)|1; /|1不改變?cè)恢蒙系?1值 else c=c1; strcpy(headeri.bits,headeri.bits+8); /把字符的編碼按原先存儲(chǔ)順序連接 fwrite(&c,1,1,ofp); length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /計(jì)算文件的壓縮率fclose(ifp); fclose(ofp); printf(nt壓縮文件成功!n); printf(t壓縮率為 %f%nn

37、,div*100); return; /*解壓縮*/void uncompress(Huffman *header,Huffman &tmp) char filename255,outputfile255,buf255,bx255; unsigned char c; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; printf(t請(qǐng)您輸入需要解壓縮的文件：); gets(filename); ifp=fopen(strcat(filename,.hub),rb); if(ifp=NULL) printf(nt文件打開(kāi)失敗!n); return

38、; printf(t請(qǐng)您輸入解壓縮后的文件名：); gets(outputfile); ofp=fopen(outputfile,wb); if(ofp=NULL) printf(nt解壓縮文件失敗!n); return; fread(&flength,sizeof(long),1,ifp); /讀取原文件長(zhǎng)度，對(duì)文件進(jìn)行定位fread(&f,sizeof(long),1,ifp); fseek(ifp,f,SEEK_SET); fread(&n,sizeof(long),1,ifp); for(i=0;i0) m=p/8+1; else m=p/8; for(j=0;jf;l-) strcat(headeri.bits,0); /處理編碼全為零的 strcat(headeri.bits,buf); headeri.bitsp=0; for(i=0;in;i+) /根據(jù)哈夫曼編碼的長(zhǎng)短，對(duì)結(jié)點(diǎn)進(jìn)行排序