數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---基于哈夫曼樹(shù)的文件壓縮解壓程序

1、<p><b>　　計(jì)算機(jī)科學(xué)學(xué)院</b></p><p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p>　　題 目：基于哈夫曼樹(shù)的文件壓縮/解壓程序</p><p><b>　　學(xué)生姓名： </b></p><p><b>　　學(xué) 號(hào)：

2、</b></p><p>　　專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)</p><p><b>　　班 級(jí)： </b></p><p>　　指導(dǎo)教師姓名及職稱(chēng)： 講師</p><p>　　起止時(shí)間： 2014 年 3 月—— 2014 年 4 月</p><p><b>　　1

3、需求分析</b></p><p>　　1.1課題背景及意義</p><p>　　近年來(lái)，隨著計(jì)算機(jī)技術(shù)的發(fā)展，多媒體計(jì)算機(jī)技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)以及現(xiàn)代多媒體通信技術(shù)正在向著信息化、高速化、智能化迅速發(fā)展。各個(gè)領(lǐng)域的應(yīng)用與發(fā)展，各個(gè)系統(tǒng)的數(shù)據(jù)量越來(lái)越大，給數(shù)據(jù)的存儲(chǔ)、傳輸以及有效、快速獲取信息帶來(lái)了嚴(yán)重的障礙。數(shù)據(jù)壓縮技術(shù)能夠比較有效地解決這個(gè)問(wèn)題。</p><

4、;p>　　還有在最近幾年中興起的物聯(lián)網(wǎng)和云計(jì)算都是對(duì)海量的數(shù)據(jù)進(jìn)行處理和傳輸?shù)?，如果不?duì)數(shù)據(jù)進(jìn)行壓縮，那么數(shù)據(jù)傳輸所需的帶寬要求就很高，物理成本上也隨之上升。所以說(shuō)數(shù)據(jù)壓縮在計(jì)算機(jī)通信中占有很重要的位置，且涉及領(lǐng)域多，應(yīng)用廣泛，與我們的生活息息相關(guān)。</p><p><b>　　1.2課題要求</b></p><p>　　1.2.1．實(shí)現(xiàn)一個(gè)基于哈夫曼樹(shù)的文件壓

5、縮程序和文件解壓程序。</p><p>　　1.2.2.壓縮程序能輸入源文件進(jìn)行壓縮，輸出壓縮文件；</p><p>　　1.2.3．解壓程序讀入壓縮文件，根據(jù)相應(yīng)的哈夫曼編碼解壓還原 ，得到對(duì)應(yīng)的源文件。</p><p>　　1.2.4．可選做：求出壓縮率；打印哈夫曼樹(shù)；對(duì)文件夾壓縮；圖形圖形化窗口操作界面。</p><p><b&g

6、t;　　1.3任務(wù)和要求</b></p><p>　　1.3.1選擇1時(shí)：</p><p>　　輸入一個(gè)待壓縮的文本文件名稱(chēng)(可帶路徑)。如:D:\1\XXX.txt壓縮文件名稱(chēng)= D:\1\XXX.zip</p><p>　　1.3.2選擇2時(shí)：</p><p>　　輸入一個(gè)待解壓的壓縮文件名稱(chēng)(可帶路徑)。如:D:\1\

7、YYY.txt</p><p>　　解壓文件名稱(chēng)=D:\1\YYY.zip</p><p><b>　　2概要設(shè)計(jì)</b></p><p>　　2.1問(wèn)題解決的思路概述</p><p><b>　　圖1 主程序流程圖</b></p><p><b>　　2.2 算法

8、思想：</b></p><p>　　2.2.1輸入要壓縮的文件</p><p>　　首先運(yùn)行的時(shí)候，用戶主界面上有菜單提示該如何使用軟件，根據(jù)菜單提示選擇所要執(zhí)行的項(xiàng)，依次進(jìn)行，因?yàn)楦鱾€(gè)環(huán)節(jié)之間有先后順序。第一步為輸入壓縮軟件的名稱(chēng)，由鍵盤(pán)輸入文件路徑和文件名稱(chēng)，讀入字符數(shù)組中，打開(kāi)該文件，按照提示進(jìn)行壓縮。若打不開(kāi)，則繼續(xù)輸入。</p><p>　　2

9、.2.2讀文件并計(jì)算字符頻率</p><p>　　文件將信息存放在字符數(shù)組中；計(jì)算每個(gè)字符出現(xiàn)的次數(shù)，申請(qǐng)一個(gè)結(jié)構(gòu)體數(shù)組空間， 用讀取的字符減去字符結(jié)束符作為下標(biāo)記錄字符的頻率。</p><p>　　2.2.3根據(jù)字符的頻率，利用Huffman編碼思想創(chuàng)建Huffman樹(shù)</p><p>　　將所記錄的字符的頻率作為權(quán)值來(lái)創(chuàng)建Huffman樹(shù)，依次選擇權(quán)值最小的兩個(gè)

10、字符作為左右孩子，其和作為父結(jié)點(diǎn)的權(quán)值，依次進(jìn)行下去，直到所有的字符結(jié)點(diǎn)都成為葉子結(jié)點(diǎn)。</p><p>　　2.2.4由創(chuàng)建的Huffman樹(shù)來(lái)決定字符對(duì)應(yīng)的編碼，進(jìn)行文件的壓縮</p><p>　　根據(jù)創(chuàng)建的Huffman樹(shù)來(lái)確定個(gè)字符的01編碼，左孩子為0，右孩子為1。讀取文件，依次將每個(gè)字符用他們的編碼表示，即完成一次編碼。</p><p>　　2.2.5解

11、碼壓縮即根據(jù)Huffman樹(shù)進(jìn)行譯碼</p><p>　　讀取編碼文件，依據(jù)創(chuàng)建的Huffman樹(shù)，定義一個(gè)指針指向根結(jié)點(diǎn)。從根結(jié)點(diǎn)開(kāi)始，每讀一個(gè)字符，指針變化一次（當(dāng)讀取的字符是‘1’時(shí)，指針指向當(dāng)前所指結(jié)點(diǎn)的右孩子，當(dāng)讀取的字符是‘0’時(shí)，指針指向當(dāng)前所指結(jié)點(diǎn)的左孩子），直至該指針?biāo)附Y(jié)點(diǎn)為葉子結(jié)點(diǎn)時(shí)結(jié)束（即當(dāng)結(jié)點(diǎn)的左右孩子均為空時(shí)）。將當(dāng)前葉子結(jié)點(diǎn)所代表的字符值輸出到譯碼文件中，依次讀取編碼文件中的字符，按

12、照上述方法依次進(jìn)行下去直至文件</p><p><b>　　2.3數(shù)據(jù)結(jié)構(gòu)定義</b></p><p>　　typedef struct node //哈夫曼樹(shù)結(jié)構(gòu)體</p><p><b>　　{ </b></p><p>　　long w;//權(quán)重</p><p&

13、gt;　　short p,l,r; //定義雙親，左孩子，右孩子</p><p>　　}htnode,*htnp;</p><p>　　typedef struct huffman_code </p><p><b>　　{ </b></p><p>　　unsigned char len;//記錄該結(jié)點(diǎn)哈夫曼編碼的

14、長(zhǎng)度</p><p>　　unsigned char *codestr; //記錄該結(jié)點(diǎn)的哈夫曼編碼</p><p><b>　　}hufcode;</b></p><p>　　2.5主程序的流程及模塊間關(guān)系</p><p>　　主函數(shù)實(shí)例化huffmanTree類(lèi)，并實(shí)現(xiàn)菜單工具欄，通過(guò)用戶的選擇輸入，用switch

15、語(yǔ)句進(jìn)行分支執(zhí)行huffmanTree類(lèi)中功能函數(shù)：</p><p>　　1:壓縮函數(shù) int compress(char *source_file,char *obj_file)；</p><p>　　2:解壓函數(shù) int decompress(char *source_file,char*obj_file)；</p><p>　　并可在完成相應(yīng)功能后安全退出，壓

16、縮或解壓的文件在同文件夾下生成。</p><p><b>　　3. 詳細(xì)設(shè)計(jì)</b></p><p>　　核心算法----huffman算法：</p><p>　　3.1根據(jù)給定的n個(gè)權(quán)值｛w1,w2,……,wn｝構(gòu)成n棵二叉樹(shù)的集合F=｛T1,T2,……,Tn｝,其中每棵二叉樹(shù)T1中只有一個(gè)帶權(quán)的 w1的根據(jù)點(diǎn)，其左右子樹(shù)均空。</p&

17、gt;<p>　　3.2在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。</p><p>　　3.3在F中刪除這兩棵樹(shù)，同時(shí)將所得到的二叉樹(shù)加入F中。</p><p>　　3.4重復(fù)3.2,3.3,直到F中只含一棵樹(shù)為止。這棵樹(shù)便是Huffman樹(shù)。Huffman樹(shù)可用于構(gòu)造代碼總長(zhǎng)度最短的編碼方案。

18、</p><p>　　為了詳細(xì)說(shuō)明這個(gè)問(wèn)題，特以下面例子來(lái)說(shuō)明:</p><p><b>　　圖2 問(wèn)題詳解</b></p><p>　　編碼完成之后，開(kāi)始對(duì)源文件進(jìn)行壓縮。</p><p>　　從源文件讀一個(gè)字符，從葉子結(jié)點(diǎn)中找出和此字符相同的字符結(jié)點(diǎn)，將其編碼寫(xiě)入一個(gè)臨時(shí)字符組codes；</p>&l

19、t;p>　　當(dāng)codes的長(zhǎng)度大于等于8時(shí)，將其前8位轉(zhuǎn)換成字符寫(xiě)入目標(biāo)文件中；</p><p>　　重復(fù)1和2此過(guò)程，直至讀完源文件中的所有字符；</p><p>　　若codes最后還有剩余的不足8位的01代碼，則將其低位補(bǔ)0至8位，再寫(xiě)入目標(biāo)文件。 </p><p><b>　　主程序模塊:</b></p><p

20、><b>　　圖 3 主程序模塊</b></p><p><b>　　調(diào)試分析報(bào)告</b></p><p>　　由于壓縮與解壓過(guò)程中沒(méi)有輸入新生成文件的路徑，因此解壓后的文件會(huì)將原文件覆蓋。如圖：</p><p><b>　　圖4 壓縮前原文件</b></p><p>　

21、　圖 5 壓縮后生成文件</p><p><b>　　圖 6 解壓后文件</b></p><p><b>　　5.用戶使用說(shuō)明</b></p><p>　　在運(yùn)行程序之前，首先在D盤(pán)先建立一個(gè)待壓縮的文件1.doc，</p><p>　　運(yùn)行程序如下圖所示。</p><p>

22、　　圖7 版本測(cè)試結(jié)果圖</p><p>　　壓縮：在命令行下輸入1對(duì)文件進(jìn)行壓縮，根據(jù)提示輸入剛剛建的文本文件（1.doc），和要生成的壓縮文件名稱(chēng)，按回車(chē)確認(rèn)進(jìn)行壓縮。</p><p>　　圖 8 執(zhí)行壓縮操作圖</p><p>　　成功執(zhí)行完畢后如下圖所示。</p><p>　　圖 9 執(zhí)行壓縮操作圖</p><p&

23、gt;　　選擇打印哈夫曼樹(shù)及編碼。</p><p>　　圖10 執(zhí)行打印操作圖</p><p><b>　　解壓：</b></p><p>　　在命令行下輸入2對(duì)本程序壓縮的文件進(jìn)行恢復(fù)，根據(jù)提示輸入待恢復(fù)的</p><p>　　文件名稱(chēng)和恢復(fù)后的文件名稱(chēng)，按回車(chē)確定，成功執(zhí)行后如下圖所示。</p><

24、;p>　　圖11 執(zhí)行解壓操作圖</p><p><b>　　6.測(cè)試結(jié)果</b></p><p>　　詳細(xì)測(cè)試結(jié)果請(qǐng)參見(jiàn) 5 使用功能。</p><p><b>　　6.1測(cè)試報(bào)告</b></p><p><b>　　參考文獻(xiàn)</b></p><p&

25、gt;　　[1]鄭莉 等編著《C++語(yǔ)言程序設(shè)計(jì)（第三版）》北京：清華大學(xué)出版社.</p><p>　　[2]譚浩強(qiáng) .C++面向?qū)ο蟪绦蛟O(shè)計(jì)(第二版) [M].北京：中國(guó)鐵道出版社，2009.</p><p>　　[3]洪國(guó)勝 等編著 《C++ Builder程序設(shè)計(jì)輕松上手》北京：清華大學(xué)出版社.</p><p>　　[4

26、]胡學(xué)鋼等《數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo)》北京：清華大學(xué)出版社，1999年 第1版.</p><p>　　[5]王昆侖 等編著 《數(shù)據(jù)結(jié)構(gòu)域算法（高等學(xué)校計(jì)算機(jī)精品課程系列教材）》 中國(guó)鐵道工業(yè)出版社.</p><p><b>　　附錄：源程序</b></p><p>　　#include <stdio.h

27、> </p><p>　　#include <string.h> </p><p>　　#include <stdlib.h> </p><p>　　#include <windows.h></p><p>　　typedef struct node //哈夫曼樹(shù)結(jié)構(gòu)體</p>&

28、lt;p><b>　　{ </b></p><p>　　long w;//權(quán)重</p><p>　　short p,l,r; //定義雙親，左孩子，右孩子</p><p>　　}htnode,*htnp;</p><p>　　typedef struct huffman_code </p>

29、<p><b>　　{ </b></p><p>　　unsigned char len;//記錄該結(jié)點(diǎn)哈夫曼編碼的長(zhǎng)度</p><p>　　unsigned char *codestr; //記錄該結(jié)點(diǎn)的哈夫曼編碼</p><p><b>　　}hufcode;</b></p><p>

30、;　　typedef char **huffmancode;</p><p>　　int initial_files(char *source_file,FILE **inp,char *obj_file,FILE **outp);//文件初始信息</p><p>　　char *create_file(char *source_file,char* obj_file);//創(chuàng)建待壓縮文件

31、名</p><p>　　int compress(char *source_file,char *obj_file);//壓縮函數(shù)</p><p>　　long frequency_data(FILE *in,long fre[]);//計(jì)算字符頻率</p><p>　　int search_set(htnp ht,int n,int *s1, int *s2);/

32、/查找文件</p><p>　　int create_hftree(long w[],int n,htnode ht[]);//創(chuàng)建哈夫曼樹(shù)</p><p>　　int encode_hftree(htnp htp,int n,hufcode hc[]);//記錄哈夫曼編碼</p><p>　　unsigned char chars_to_bits(const un

33、signed char chars[8]);//計(jì)算文件大小</p><p>　　int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc[],char* source_file,long source_filesize);//輸入待壓縮文件路徑</p><p>　　int decompress(char *source_f

34、ile,char *obj_file);//解壓函數(shù)</p><p>　　void get_mini_huffmantree(FILE* in,short mini_ht[][2]);//建立哈弗曼樹(shù)中用于選擇最小權(quán)值結(jié)點(diǎn)的函數(shù)</p><p>　　int write_decompress_file(FILE *in,FILE* out,short mini_ht[][2],long bi

35、ts_pos,long obj_filesize);//輸入待解壓文件路徑</p><p>　　int d_initial_files(char *source_file,FILE **inp,char *obj_file,FILE **outp);</p><p><b>　　main()</b></p><p><b>　　{&l

36、t;/b></p><p><b>　　int s;</b></p><p>　　char file[10];</p><p>　　system("color 3F");</p><p>　　printf(" *******************

37、********************\n");</p><p>　　printf(" * 菜單： *\n");</p><p>　　printf(" * 1.------壓縮------

38、 *\n");</p><p>　　printf(" * 2.------解壓------ *\n");</p><p>　　printf(" * 0.------退出------ *\n")

39、;</p><p>　　printf(" ***************************************\n");</p><p>　　scanf("%d",&s);</p><p>　　while(s!=0)</p><p><b&g

40、t;　　{</b></p><p>　　getchar();</p><p><b>　　switch(s)</b></p><p><b>　　{</b></p><p><b>　　case 1:</b></p><p>　　puts(&

41、quot;請(qǐng)輸入待壓縮文件路徑：");</p><p>　　gets(file);</p><p>　　compress(file,NULL);</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p><p>　

42、　puts("請(qǐng)輸入待解壓文件路徑：");</p><p>　　gets(file);</p><p>　　decompress(file,NULL);</p><p><b>　　break;</b></p><p>　　default : </p><p>　　printf

43、("指令錯(cuò)誤！請(qǐng)重新輸入指令：\n");</p><p><b>　　}</b></p><p>　　puts(" ");</p><p>　　printf(" ***************************************\n")

44、;</p><p>　　printf(" * 菜單： *\n");</p><p>　　printf(" * 1.------壓縮------ *\n");</p>&l

45、t;p>　　printf(" * 2.------解壓------ *\n");</p><p>　　printf(" * 0.------退出------ *\n");</p><p>　　print

46、f(" ***************************************\n");</p><p>　　scanf("%d",&s);</p><p><b>　　}</b></p><p><b>　　}</b></

47、p><p><b>　　//文件初始信息</b></p><p>　　int initial_files(char *source_file,FILE **inp,char *obj_file,FILE **outp) </p><p><b>　　{ </b></p><p>　　if(fopen(s

48、ource_file,"rb")==NULL) </p><p><b>　　{ </b></p><p>　　return -1;</p><p><b>　　} </b></p><p>　　if(obj_file==NULL) </p><p>&l

49、t;b>　　{ </b></p><p>　　if((obj_file=(char*)malloc(256*sizeof(char)))==NULL) </p><p><b>　　{ </b></p><p>　　return -1;</p><p>　　} &

50、lt;/p><p>　　create_file(source_file,obj_file);</p><p><b>　　} </b></p><p>　　if(strcmp(source_file,obj_file)==0) </p><p><b>　　{ </b></p><p

51、>　　return -1;</p><p><b>　　} </b></p><p>　　printf("待壓縮文件:%s,壓縮文件:%s\n",source_file,obj_file); </p><p>　　if((*outp=fopen(obj_file,"wb"))==NULL) <

52、/p><p><b>　　{ </b></p><p>　　return -1;</p><p><b>　　} </b></p><p>　　if((*inp=fopen(source_file,"rb"))==NULL) </p><p><b>

53、;　　{ </b></p><p>　　return -1;</p><p><b>　　}</b></p><p>　　free(obj_file); </p><p>　　return 0; </p><p><b>　　} </b></p>&

54、lt;p>　　//創(chuàng)建待壓縮文件名</p><p>　　char *create_file(char *source_file,char* obj_file) </p><p><b>　　{ </b></p><p>　　char *temp; </p><p>　　if((temp=strrchr(source

55、_file,'.'))==NULL) </p><p><b>　　{ </b></p><p>　　strcpy(obj_file,source_file);</p><p>　　strcat(obj_file,".zip");</p><p><b>　　} </b

56、></p><p><b>　　else </b></p><p><b>　　{ </b></p><p>　　strncpy(obj_file,source_file,temp-source_file); </p><p>　　obj_file[temp-source_file]='

57、;\0';</p><p>　　strcat(obj_file,".zip");</p><p><b>　　} </b></p><p>　　return obj_file;</p><p><b>　　}</b></p><p><b&g

58、t;　　//壓縮函數(shù)</b></p><p>　　int compress(char *source_file,char *obj_file) </p><p><b>　　{ </b></p><p>　　FILE *in,*out;</p><p><b>　　char ch;</b>

59、;</p><p>　　int error_code,i,j; </p><p>　　float compress_rate; </p><p>　　hufcode hc[256]; //編碼的位數(shù)最多為256位</p><p>　　htnode ht[256*2-1]; </p><p>　　long freque

60、ncy[256],source_filesize,obj_filesize=0; </p><p>　　error_code=initial_files(source_file,&in,obj_file,&out); </p><p>　　if(error_code!=0) </p><p><b>　　{ </b></p

61、><p>　　puts("文件打開(kāi)失??！請(qǐng)重新輸入文件路徑：");</p><p>　　return error_code; </p><p><b>　　} </b></p><p>　　source_filesize=frequency_data(in,frequency); </p>

62、<p>　　printf("文件大小 %ld 字節(jié)\n",source_filesize); </p><p>　　error_code=create_hftree(frequency,256,ht); </p><p>　　if(error_code!=0) </p><p><b>　　{ </b><

63、/p><p>　　puts("建立哈夫曼樹(shù)失?。?quot;);</p><p>　　return error_code; </p><p><b>　　} </b></p><p>　　error_code=encode_hftree(ht,256,hc); </p><p>　　if(e

64、rror_code!=0) </p><p><b>　　{ </b></p><p>　　puts("建立哈夫曼編碼失敗！");</p><p>　　return error_code; </p><p><b>　　} </b></p><p>　　f

65、or(i=0;i<256;i++) </p><p>　　obj_filesize+=frequency[i]*hc[i].len;</p><p>　　obj_filesize=obj_filesize%8==0?obj_filesize/8:obj_filesize/8+1;</p><p>　　for(i=0;i<256-1;i++) </p

66、><p>　　obj_filesize+=2*sizeof(short);</p><p>　　obj_filesize+=strlen(source_file)+1;</p><p>　　obj_filesize+=sizeof(long);</p><p>　　obj_filesize+=sizeof(unsigned int);</p

67、><p>　　compress_rate=(float)obj_filesize/source_filesize; </p><p>　　printf("壓縮文件大小:%ld字節(jié),壓縮比例:%.2lf%%\n",obj_filesize,compress_rate*100); </p><p>　　error_code=write_compress_

68、file(in,out,ht,hc,source_file,source_filesize); </p><p>　　if(error_code!=0) </p><p><b>　　{ </b></p><p>　　puts("寫(xiě)入文件失??！");</p><p>　　return error_co

69、de; </p><p><b>　　} </b></p><p>　　puts("壓縮完成!"); </p><p>　　puts(" ");</p><p>　　puts("是否打印該文件中字符對(duì)應(yīng)的huffman樹(shù)及編碼？");</p>&l

70、t;p>　　puts(" Please input Y OR N");</p><p><b>　　do{</b></p><p>　　scanf("%s",&ch);</p><p>　　switch(ch)</p><p><b>　　

71、{</b></p><p>　　case 'Y': </p><p>　　puts("以下是哈夫曼樹(shù)：");</p><p>　　for(i=256;i<256*2-2;i++)</p><p><b>　　{</b></p><p>　　if

72、(ht[i].w>0)</p><p>　　printf("%-10d%-10d%-10d%-10d%-10d\n",i,ht[i].w,ht[i].p,ht[i].l,ht[i].r);</p><p><b>　　}</b></p><p>　　puts("以下是哈夫曼編碼：");</p

73、><p>　　for(i=0;i<256;i++)</p><p><b>　　{</b></p><p>　　if(frequency[i]==0)</p><p><b>　　i++;</b></p><p><b>　　else</b></

74、p><p><b>　　{</b></p><p>　　printf("%d\t",frequency[i]);</p><p>　　for(j=0;j<hc[i].len;j++)</p><p>　　printf(" %d",hc[i].codestr[j]);</p&

75、gt;<p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case 'N':break

76、;</p><p>　　default : </p><p>　　printf("指令錯(cuò)誤！請(qǐng)重新輸入指令：\n");</p><p><b>　　}</b></p><p>　　}while(ch!='Y'&&ch!='N');</p>

77、<p>　　fclose(in); </p><p>　　fclose(out);</p><p>　　for(i=0;i<256;i++) </p><p><b>　　{ </b></p><p>　　free(hc[i].codestr); </p><p><b>

78、;　　} </b></p><p>　　return 0; </p><p><b>　　} </b></p><p><b>　　//計(jì)算字符頻率</b></p><p>　　long frequency_data(FILE *in,long frequency[]) </p&g

79、t;<p><b>　　{ </b></p><p>　　int i,read_len; </p><p>　　unsigned char buf[256];</p><p>　　long filesize;</p><p>　　for(i=0;i<256;i++) //去掉權(quán)值為0

80、的結(jié)點(diǎn)</p><p><b>　　{ </b></p><p>　　frequency[i]=0; </p><p><b>　　} </b></p><p>　　fseek(in,0L,SEEK_SET); </p><p>　　read_len=256; <

81、;/p><p>　　while(read_len==256) </p><p><b>　　{ </b></p><p>　　read_len=fread(buf,1,256,in); </p><p>　　for(i=0;i<read_len;i++) //初始化根結(jié)點(diǎn)</p><p><

82、;b>　　{ </b></p><p>　　frequency[*(buf+i)]++;</p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　for(i=0,filesize=0;i<256;i++) </p>

83、<p><b>　　{ </b></p><p>　　filesize+=frequency[i];</p><p><b>　　} </b></p><p>　　return filesize; </p><p><b>　　} </b></p>&

84、lt;p>　　int search_set(htnp ht,int n,int *s1, int *s2) </p><p><b>　　{ </b></p><p><b>　　int i,x; </b></p><p>　　long minValue = 999999,min = 0;</p>&l

85、t;p>　　for(x=0;x<n;x++) </p><p><b>　　{ </b></p><p>　　if(ht[x].p==-1) break; </p><p><b>　　} </b></p><p>　　for(i=0;i<n;i++) </p>&

86、lt;p><b>　　{ </b></p><p>　　if(ht[i].p==-1 && ht[i].w < minValue) </p><p><b>　　{ </b></p><p>　　minValue = ht[i].w;</p><p><b>　

87、　min=i;</b></p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　*s1 = min;</p><p>　　minValue = 999999,min = 0;</p><p>　　for(i=0;i&

88、lt;n;i++) </p><p><b>　　{ </b></p><p>　　if(ht[i].p==-1 && ht[i].w < minValue && i != *s1) </p><p><b>　　{ </b></p><p>　　minValu

89、e = ht[i].w;</p><p><b>　　min=i;</b></p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　*s2 = min;</p><p>　　return 1; </p

90、><p><b>　　} </b></p><p><b>　　//創(chuàng)建哈夫曼樹(shù)</b></p><p>　　int create_hftree(long w[],int n,htnode ht[]) </p><p><b>　　{ </b></p><p&g

91、t;　　int m,i,s1,s2; </p><p>　　if (n<1) return -1; </p><p><b>　　m=2*n-1;</b></p><p>　　if (ht==NULL) return -1; </p><p>　　for(i=0;i<n;i++) </p>

92、;<p><b>　　{ </b></p><p>　　ht[i].w=w[i];</p><p>　　ht[i].p=ht[i].l=ht[i].r=-1; </p><p><b>　　} </b></p><p>　　for(;i<m;i++) </p>&

93、lt;p><b>　　{ </b></p><p>　　ht[i].w=ht[i].p=ht[i].l=ht[i].r=-1;</p><p><b>　　} </b></p><p>　　for(i=n;i<m;i++)</p><p><b>　　{ </b>&

94、lt;/p><p>　　search_set(ht,i,&s1,&s2); </p><p>　　ht[s1].p = ht[s2].p = i;</p><p>　　ht[i].l = s1;</p><p>　　ht[i].r = s2; </p><p>　　ht[i].w = ht[s1].w

95、+ ht[s2].w; </p><p><b>　　} </b></p><p>　　return 0; </p><p><b>　　} </b></p><p>　　int encode_hftree(htnp htp,int n,hufcode hc[]) </p><p

96、><b>　　{ </b></p><p>　　int i,j,p,codelen;</p><p>　　unsigned char *code=(unsigned char*)malloc(n*sizeof(unsigned char)); </p><p>　　if (code==NULL) return -1; </p>

97、<p>　　for(i=0;i<n;i++)</p><p><b>　　{ </b></p><p>　　for(p=i,codelen=0;p!=2*n-2;p=htp[p].p,codelen++) </p><p><b>　　{ </b></p><p>　　code[

98、codelen]=(htp[htp[p].p].l==p?0:1);</p><p><b>　　} </b></p><p>　　if((hc[i].codestr=(unsigned char *)malloc((codelen)*sizeof(unsigned char)))==NULL) </p><p><b>

99、;　　{ </b></p><p>　　return -1;</p><p><b>　　} </b></p><p>　　hc[i].len=codelen; </p><p>　　for(j=0;j<codelen;j++) </p><p><b>　　{ <

100、;/b></p><p>　　hc[i].codestr[j]=code[codelen-j-1];</p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　free(code);</p><p>　　return 0; &

101、lt;/p><p><b>　　} </b></p><p>　　unsigned char chars_to_bits(const unsigned char chars[8]) </p><p><b>　　{ </b></p><p><b>　　int i; </b><

102、;/p><p>　　unsigned char bits=0; </p><p>　　bits|=chars[0]; </p><p>　　for(i=1;i<8;++i)</p><p><b>　　{ </b></p><p>　　bits<<=1; </p>&l

103、t;p>　　bits|=chars[i]; </p><p><b>　　} </b></p><p>　　return bits; </p><p><b>　　} </b></p><p>　　int write_compress_file(FILE *in,FILE *out,

104、htnp ht,hufcode hc[],char* source_file,long source_filesize) </p><p><b>　　{ </b></p><p>　　unsigned int i,read_counter,write_counter,zip_head=0xFFFFFFFF;</p><p>　　unsi

105、gned char write_char_counter,code_char_counter,copy_char_counter,</p><p>　　read_buf[256],write_buf[256],write_chars[8],file_size=strlen(source_file);</p><p>　　hufcode *cur_hufcode; </p>

106、<p>　　fseek(in,0L,SEEK_SET); </p><p>　　fseek(out,0L,SEEK_SET); </p><p>　　fwrite(&zip_head,sizeof(unsigned int),1,out);</p><p>　　fwrite(&file_size,sizeof(unsigned char)

107、,1,out); </p><p>　　fwrite(source_file,sizeof(char),file_size,out); </p><p>　　fwrite(&source_filesize,sizeof(long),1,out); </p><p>　　for(i=256;i<256*2-1;i++) </p><p

108、><b>　　{ </b></p><p>　　fwrite(&(ht[i].l),sizeof(ht[i].l),1,out);</p><p>　　fwrite(&(ht[i].r),sizeof(ht[i].r),1,out);</p><p><b>　　} </b></p>&

109、lt;p>　　write_counter=write_char_counter=0;</p><p>　　read_counter=256;</p><p>　　while(read_counter==256) </p><p><b>　　{ </b></p><p>　　read_counter=fread(r

110、ead_buf,1,256,in);</p><p>　　for(i=0;i<read_counter;i++) </p><p><b>　　{ </b></p><p>　　cur_hufcode=&hc[read_buf[i]];</p><p>　　code_char_counter=0;</

111、p><p>　　while(code_char_counter!=cur_hufcode->len) </p><p><b>　　{</b></p><p>　　copy_char_counter= (8-write_char_counter > cur_hufcode->len-code_char_counter ? &l

112、t;/p><p>　　cur_hufcode->len-code_char_counter : 8-write_char_counter); </p><p>　　memcpy(write_chars+write_char_counter,cur_hufcode->codestr+code_char_counter,copy_char_counter); </p>&

113、lt;p>　　write_char_counter+=copy_char_counter;</p><p>　　code_char_counter+=copy_char_counter;</p><p>　　if(write_char_counter==8) </p><p><b>　　{ </b></p><p&g

114、t;　　write_char_counter=0;</p><p>　　write_buf[write_counter++]=chars_to_bits(write_chars); </p><p>　　if(write_counter==256) </p><p><b>　　{ </b></p><p>　　fwri

115、te(write_buf,1,256,out);</p><p>　　write_counter=0;</p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　} </b></p><p><

116、b>　　} </b></p><p><b>　　} </b></p><p>　　fwrite(write_buf,1,write_counter,out);</p><p>　　if(write_char_counter!=0) </p><p><b>　　{ </b><

117、;/p><p>　　write_char_counter=chars_to_bits(write_chars);</p><p>　　fwrite(&write_char_counter,1,1,out);</p><p><b>　　} </b></p><p>　　return 0; </p>&l

118、t;p><b>　　} </b></p><p>　　//建立哈弗曼樹(shù)中用于選擇最小權(quán)值結(jié)點(diǎn)的函數(shù)</p><p>　　void get_mini_huffmantree(FILE* in,short mini_ht[][2]) </p><p><b>　　{ </b></p><p>&l

119、t;b>　　int i; </b></p><p>　　for(i=0;i<256;i++) </p><p><b>　　{ </b></p><p>　　mini_ht[i][0]=mini_ht[i][1]=-1;</p><p><b>　　} </b></p&

120、gt;<p>　　fread(mini_ht[i],sizeof(short),2*(256-1),in);</p><p><b>　　} </b></p><p>　　int write_decompress_file(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,long obj_files

121、ize) </p><p><b>　　{ </b></p><p>　　long cur_size; </p><p>　　unsigned char read_buf[256],write_buf[256],convert_bit; </p><p>　　unsigned int read_count

122、er,write_counter,cur_pos; </p><p>　　fseek(in,bits_pos,SEEK_SET);</p><p>　　fseek(out,0L,SEEK_SET);</p><p>　　read_counter=256-1;</p><p>　　cur_size=write_counter=0;</p&

123、gt;<p>　　cur_pos=256*2-2;</p><p>　　while(cur_size!=obj_filesize) </p><p><b>　　{ </b></p><p>　　if(++read_counter==256) </p><p><b>　　{ </b&g

124、t;</p><p>　　fread(read_buf,1,256,in);</p><p>　　read_counter=0;</p><p><b>　　} </b></p><p>　　for(convert_bit=128;convert_bit!=0;convert_bit>>=1) </p&

125、gt;<p><b>　　{ </b></p><p>　　cur_pos=((read_buf[read_counter]&convert_bit)==0?mini_ht[cur_pos][0]:mini_ht[cur_pos][1]);</p><p>　　if(cur_pos<256)</p><p><

126、b>　　{ </b></p><p>　　write_buf[write_counter]=(unsigned char)cur_pos; </p><p>　　if(++write_counter==256)</p><p><b>　　{ </b></p><p>　　fwrite(write_bu

127、f,1,256,out);</p><p>　　write_counter=0;</p><p><b>　　} </b></p><p>　　cur_pos=256*2-2;</p><p>　　if(++cur_size==obj_filesize) </p><p><b>　　{

128、 </b></p><p><b>　　break;</b></p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>

129、;　　} </b></p><p>　　fwrite(write_buf,1,write_counter,out);</p><p>　　return 0; </p><p><b>　　} </b></p><p><b>　　//解壓函數(shù)</b></p><p&g

130、t;　　int decompress(char *source_file,char *obj_file) </p><p><b>　　{ </b></p><p>　　int error_code; </p><p>　　FILE *in,*out; </p><p>　　short mini_ht[

131、256*2-1][2]; </p><p>　　long obj_filesize; </p><p>　　error_code=d_initial_files(source_file,&in,obj_file,&out); </p><p>　　if(error_code!=0) </p><p><b>　

132、　{ </b></p><p>　　puts("打開(kāi)文件失??！請(qǐng)重新輸入文件路徑：");</p><p>　　return error_code; </p><p><b>　　} </b></p><p>　　fread(&obj_filesize,sizeof(long),1,

133、in); </p><p>　　printf("解壓文件大小:%ld字節(jié)\n",obj_filesize); </p><p>　　get_mini_huffmantree(in,mini_ht); </p><p>　　error_code=write_decompress_file(in,out,mini_ht,ftell(in),obj_f

134、ilesize); </p><p>　　if(error_code!=0) </p><p><b>　　{ </b></p><p>　　puts("解壓失敗！");</p><p>　　return error_code; </p><p><b>　　} &l

135、t;/b></p><p>　　puts("解壓完成!"); </p><p>　　fclose(in); </p><p>　　fclose(out); </p><p>　　return 0; </p><p><b>　　} </b></p><

136、p>　　int d_initial_files(char *source_file,FILE **inp,char *obj_file,FILE **outp) </p><p><b>　　{ </b></p><p>　　unsigned int zip_head; </p><p>　　unsigned char file

137、_size; </p><p>　　if ((*inp=fopen(source_file,"rb"))==NULL) </p><p><b>　　{ </b></p><p>　　return -1;</p><p><b>　　} </b></p>&