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

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

2、fman樹的權(quán)值。3.頻度表建好后，就可以根據(jù)算法建立Huffman樹，對出現(xiàn)的每種字符進(jìn)行Huffman編碼。4. 此時(shí)，再次讀入源文件，逐字節(jié)編碼，將得到的編碼流寫入到磁盤文件，并且計(jì)算壓縮率。5. 譯碼過程先讀入被壓縮的文件，將其解釋為比特流，根據(jù)Huffman樹，對比特流逐位譯碼，將譯碼結(jié)果逐次寫入到磁盤文件。要求：完成編碼譯碼功能。設(shè)計(jì)參數(shù) 測試數(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ù)的算法、并畫出算法的程序流程圖2011.1.6 星期四（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、對任務(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ú)立完成）、對程序的調(diào)試，并試運(yùn)行。2011.1.12 星期三（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、整理課程設(shè)計(jì)過程中的各個(gè)參數(shù)、并進(jìn)行總結(jié)，提出改進(jìn)意見2011.1.13 星期四（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、編寫課程設(shè)計(jì)報(bào)告、準(zhǔn)備答辨

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

5、和打印哈夫曼編碼的功能。本程序經(jīng)過測試后，功能均能實(shí)現(xiàn)，運(yùn)行穩(wěn)定。關(guān)鍵詞：哈夫曼編碼 壓縮 01串 bit流 二叉樹 目錄 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樹 PAGEREF _Toc282707594 h 6 HYPERLINK

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

9、599 h 10 HYPERLINK l _Toc282707600 4總結(jié) PAGEREF _Toc282707600 h 11 HYPERLINK l _Toc282707601 5軟件使用說明書 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í)間已越來越引起人們的重視，哈夫曼在上世紀(jì)五十年代初就提出這種編碼時(shí)，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼，是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈夫曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而

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

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

13、，因?yàn)橐粋€(gè)字節(jié)存儲(chǔ)的范圍是0255，及256個(gè)字符（包括漢字的半個(gè)編碼），根據(jù)定義Huffman樹的節(jié)點(diǎn)個(gè)數(shù)m=2*n-1,所以512個(gè)數(shù)組剛好能把所有字符統(tǒng)計(jì)出來。在逐個(gè)讀取文本字符的時(shí)候，根據(jù)字符的ASCII碼做為數(shù)組下標(biāo)，同時(shí)初始化512個(gè)數(shù)組，并將文件中存在的字符的ASCII碼存入對應(yīng)的結(jié)構(gòu)體中。生成Huffman樹：每次取最小的那兩個(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樹中個(gè)節(jié)點(diǎn)的

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

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

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

17、流程圖.4 文本存儲(chǔ)示意圖字符在存儲(chǔ)的時(shí)候，前04個(gè)字節(jié)存儲(chǔ)源文件字符個(gè)數(shù)，58個(gè)字節(jié)存儲(chǔ)壓縮后字符個(gè)數(shù)。接下來存儲(chǔ)壓縮后的字符及01串，緊接著是字符種類，然后是字符，再然后是字符對應(yīng)編碼的長度，最后是字符對應(yīng)的編碼。源文件字符個(gè)數(shù)壓縮后字符個(gè)數(shù)010101字符種類字符字符編碼長度字符對應(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; /定義哈夫曼樹指針變量char bits256; /定

18、義存儲(chǔ)哈夫曼編碼的數(shù)組Huffman;數(shù)組的初始化 此段代碼不但實(shí)現(xiàn)了對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)原文件長度+1flength-; /文件末尾讀了兩次length1=flength; /原文件長度用作求壓縮率的分母headerc.count-; for(i=0;i512;i+) /初始化數(shù)組 if(headeri.count!=0) headeri.b=(unsign

19、ed char)i; /記錄該數(shù)組對應(yīng)的字符的ASC碼 else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /對結(jié)點(diǎn)進(jìn)行初始化 生成Huffman樹每次取最小的那兩個(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的原理是通過位操作，將01的字符串，轉(zhuǎn)換為bit流，如果當(dāng)前為0的話則向左移以為，若為1的話則

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

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

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

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

25、liam Ford,William Topp .清華大學(xué)出版社（影印版）. 4 譚浩強(qiáng).c語言程序設(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*請選擇相應(yīng)功能(0-3):); c=getch(); printf(%cn,c); if(c!=0 & c!=1 & c!=2 & c!=3) printf(t請檢查您的輸入在03之間！n); printf(t請?jiā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請您輸入需要壓縮的文件：); gets(filename); ifp=fopen(filename,rb); if(ifp=NULL) printf(nt文件打開失敗!nn); return; printf(t請您輸入壓縮后的文件名：); 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)原文件長度+1flength-; /文件末尾讀了兩次length1=flength; /原文件長度用作求壓縮率的分母headerc.count-; for(i=0;i512;i+) /初始化數(shù)組 if(headeri.count!=0) headeri.b=(

30、unsigned char)i; /記錄該數(shù)組對應(yīng)的字符的ASC碼 else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /對結(jié)點(diǎn)進(jìn)行初始化 for(i=0;i256;i+) /根據(jù)頻率（權(quán)值）大小，對結(jié)點(diǎn)進(jìn)行排序，選擇較小的結(jié)點(diǎn)進(jìn)樹 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è)哈夫曼樹的需要的結(jié)點(diǎn)數(shù)為2*n-1. m=2*n-1;for(i=n;im;i+) /構(gòu)建哈夫曼樹 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) /對哈夫曼編碼位操作進(jìn)行壓縮存儲(chǔ) for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c0) /對哈夫曼編碼位操作進(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ǔ)不超過8位，則對有效位數(shù)左移實(shí)現(xiàn)兩字符編碼的連接 if(headeri.bitsj=1) c=(c1)|1; /|1不改變原位置上的01值 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請您輸入需要解壓縮的文件：); gets(filename); ifp=fopen(strcat(filename,.hub),rb); if(ifp=NULL) printf(nt文件打開失敗!n); return

38、; printf(t請您輸入解壓縮后的文件名：); gets(outputfile); ofp=fopen(outputfile,wb); if(ofp=NULL) printf(nt解壓縮文件失敗!n); return; fread(&flength,sizeof(long),1,ifp); /讀取原文件長度，對文件進(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ù)哈夫曼編碼的長短，對結(jié)點(diǎn)進(jìn)行排序