數(shù)據(jù)結(jié)構(gòu)(5)_文件壓縮

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：文件壓縮實(shí)驗(yàn)類型：綜合性試驗(yàn)班級(jí)：20112111學(xué)號(hào)：2011211107姓名：馮若航實(shí)驗(yàn)日期：2003.6.19 下午4:001.問題描述文件壓縮基本要求哈夫曼編碼是一種常用的數(shù)據(jù)壓縮技術(shù)，對(duì)數(shù)據(jù)文件進(jìn)行哈夫曼編碼可大大縮短文件的傳輸長(zhǎng)度，提高信道利用率及傳輸效率。要求采用哈夫曼編碼原理，統(tǒng)計(jì)文本文件中字符出現(xiàn)的詞頻，以詞頻作為權(quán)值，對(duì)文件進(jìn)行哈夫曼編碼以達(dá)到壓縮文件的目的，再用哈夫曼編碼進(jìn)行譯碼解壓縮。l 統(tǒng)計(jì)待壓縮的文本文件中各字符的詞頻，以詞頻為權(quán)值建立哈夫曼樹，并將該哈夫曼樹保存到文件HufTree.dat中。l 根據(jù)哈夫曼樹（保存在HufTree.dat

2、中）對(duì)每個(gè)字符進(jìn)行哈夫曼編碼，并將字符編碼保存到HufCode.txt文件中。l 壓縮：根據(jù)哈夫曼編碼，將源文件進(jìn)行編碼得到壓縮文件CodeFile.dat。l 解壓：將CodeFile.dat文件利用哈夫曼樹譯碼解壓，恢復(fù)為源文件。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)此類問題，應(yīng)設(shè)計(jì)文件的數(shù)據(jù)結(jié)構(gòu)。*4壓縮頭標(biāo)記*1文件名長(zhǎng)度*ns文件名*4源文件長(zhǎng)度*1020huffman樹*1021EOF文件內(nèi)容赫夫曼樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)typedef struct nodelong w;/權(quán)short p,l,r;/父親，左孩子，右孩子HTNODE,*HTNP;/霍夫曼樹的結(jié)點(diǎn)赫夫曼編碼數(shù)組元素的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)typedef

3、struct huffman_codeBYTE len;/長(zhǎng)度BYTE *codestr;/字符串HFCODE;/霍夫曼編碼數(shù)組元素3.算法設(shè)計(jì)源代碼#define _CRT_SECURE_NO_DEPRECATE#include #include #include typedef unsigned int UINT;typedef unsigned char BYTE;typedef struct nodelong w;/權(quán)short p,l,r;/父親，左孩子，右孩子HTNODE,*HTNP;/霍夫曼樹的結(jié)點(diǎn)typedef struct huffman_codeBYTE len;/長(zhǎng)度BY

4、TE *codestr;/字符串HFCODE;/霍夫曼編碼數(shù)組元素#define OK 1#define ERROR -1#define UNUSE -1/未鏈接節(jié)點(diǎn)標(biāo)志#define CHAR_BITS 8/一個(gè)字符中的位數(shù)#define INT_BITS 32/一個(gè)整型中的位數(shù)#define HUFCODE_SIZE 256/霍夫曼編碼個(gè)數(shù)#define BUFFERSIZE 256/緩沖區(qū)大小大小#define UINTSIZE sizeof(UINT)#define BYTESIZE sizeof(BYTE)#define TAG_ZIGHEAD 0xFFFFFFFF/壓縮文件頭標(biāo)#d

5、efine MAX_FILENAME512 /函數(shù)聲明/壓縮模塊int Compress(char *SourceFilename,char *DestinationFilename);/壓縮調(diào)用int Initializing(char *SourceFilename,FILE *inp,char *DestinationFilename,FILE *outp);/初始化文件工作環(huán)境long AnalysisFiles(FILE *in,long frequency);/計(jì)算每個(gè)不同字節(jié)的頻率以及所有的字節(jié)數(shù)int CreateHuffmanTree(long w,int n,HTNODE

6、ht);/生成霍夫曼樹int HuffmanTreeCoding(HTNP htp,int n,HFCODE hc);/霍夫曼編碼int Search(HTNP ht,int n);/查找當(dāng)前最小權(quán)值的霍夫曼樹節(jié)點(diǎn)并置為占用BYTE Char2Bit(const BYTE charsCHAR_BITS);/將一個(gè)字符數(shù)組轉(zhuǎn)換成二進(jìn)制數(shù)字int Search(HTNP ht,int n);/查找當(dāng)前最小權(quán)值的霍夫曼樹節(jié)點(diǎn)并置為占用int WriteZipFiles(FILE *in,FILE *out,HTNP ht,HFCODE hc,char* SourceFilename,long sou

7、rce_filesize);/寫壓縮文件/解壓縮模塊int DeCompress(char *SourceFilename,char *DestinationFilename);/解壓縮調(diào)用int Initializing_Dezip(char *SourceFilename,FILE *inp,char *DestinationFilename,FILE *outp);/為處理解壓縮流程初始化文件void ReadHuffmanTree(FILE* in,short mini_ht2);/從待解壓縮文件中讀取huffman樹int WriteDeZipFiles(FILE *in,FILE*

8、 out,short mini_ht2,long bits_pos,long Dst_Filesize);/寫解壓縮文件void ErrorReport(int error_code);/報(bào)錯(cuò)/函數(shù)定義/函數(shù)實(shí)現(xiàn)/壓縮int Compress(char *SourceFilename,char *DestinationFilename)FILE *in,*out;/輸入輸出流int i;/計(jì)數(shù)變量float Compress_rate;/存放壓縮率HFCODE hcHUFCODE_SIZE;/存放256個(gè)字符的huffman編碼HTNODE htHUFCODE_SIZE*2-1;/256個(gè)字符

9、的huffman樹需要2*256-1=511個(gè)節(jié)點(diǎn)。long frequencyHUFCODE_SIZE ,source_filesize,Dst_Filesize=0;/字符頻率數(shù)組，源文件，目標(biāo)文件。/處理待壓縮與壓縮文件文件Initializing(SourceFilename,&in,DestinationFilename,&out);puts(Loading Files.);/處理各個(gè)字符的頻率，并輸出原始文件長(zhǎng)度source_filesize=AnalysisFiles(in,frequency); puts(Loading Complete!Now Analysising.);p

10、rintf(Original size:%ld Byte n,source_filesize);/創(chuàng)建Huffman樹CreateHuffmanTree(frequency,HUFCODE_SIZE,ht);/Huffman編碼puts(Huffman Tree Initialized Successfully,HuffmanCoding Processing.); HuffmanTreeCoding(ht,HUFCODE_SIZE,hc);/計(jì)算目標(biāo)文件長(zhǎng)度for(i=0;iHUFCODE_SIZE;i+)/計(jì)算位的個(gè)數(shù),計(jì)算每個(gè)字符的頻數(shù)與其編碼長(zhǎng)度乘積之和Dst_Filesize+=fr

11、equencyi*hci.len;/將文件主體部分的位個(gè)數(shù)轉(zhuǎn)換為字節(jié)個(gè)數(shù);Dst_Filesize=Dst_Filesize%8=0?Dst_Filesize/8:Dst_Filesize/8+1;for(i=0;iHUFCODE_SIZE-1;i+)/huffmantree長(zhǎng)度Dst_Filesize+=2*sizeof(short);Dst_Filesize+=strlen(SourceFilename)+1;/源文件名占用空間Dst_Filesize+=sizeof(long);/源文件名長(zhǎng)度信息占用空間Dst_Filesize+=UINTSIZE;/文件頭長(zhǎng)度Compress_rate

12、=(float)Dst_Filesize/source_filesize;/壓縮率puts(Coding Successfully.Now producing zip files.);printf(Compressed File Size:%ld Byte,radiation: %.2lf n,Dst_Filesize,Compress_rate*100);/生成壓縮文件WriteZipFiles(in,out,ht,hc,SourceFilename,source_filesize);puts(Compress Complete!);/擦屁股fclose(in);fclose(out);/關(guān)

13、閉文件 for(i=0;iHUFCODE_SIZE;i+)free(hci.codestr);return OK;int Initializing(char *SourceFilename,FILE *inp,char *DestinationFilename,FILE *outp)if(strcmp(SourceFilename,DestinationFilename)=0)/重名判斷return ERROR;printf(Source File:%s,Destination File:%sn,SourceFilename,DestinationFilename);if(*outp=fope

14、n(DestinationFilename,wb)=NULL)/文件打開錯(cuò)誤return ERROR;if(*inp=fopen(SourceFilename,rb)=NULL)/文件打開錯(cuò)誤return ERROR;return OK;long AnalysisFiles(FILE *in,long frequency)int i,read_len;BYTE bufBUFFERSIZE;/緩沖區(qū)long filesize;/文件總長(zhǎng)for(i=0;iHUFCODE_SIZE;i+)frequencyi=0;/初始化所有字符頻率為0fseek(in,0L,SEEK_SET);/將文件定位符指向

15、文件開頭read_len=BUFFERSIZE;/設(shè)置讀入長(zhǎng)度=緩沖區(qū)長(zhǎng)度while(read_len=BUFFERSIZE)/每當(dāng)讀取字符長(zhǎng)度達(dá)到緩沖區(qū)長(zhǎng)度時(shí)read_len=fread(buf,1,BUFFERSIZE,in);for(i=0;iread_len;i+)frequency*(buf+i)+;/統(tǒng)計(jì)字頻for(i=0,filesize=0;iHUFCODE_SIZE;i+)filesize+=frequencyi;/計(jì)算文件長(zhǎng)度，計(jì)算方法是把所有字符的頻數(shù)相加return filesize;int Search(HTNP ht,int n)int i,x;for(x=0;xn

16、;x+)if(htx.p=UNUSE) break;/找到第一個(gè)沒有使用的葉子節(jié)點(diǎn)，跳出for(i=x;in;i+)if(hti.p=UNUSE&hti.whtx.w)x=i;/找權(quán)值最小的葉子節(jié)點(diǎn)htx.p=-2;/將葉子節(jié)點(diǎn)占用return x;int CreateHuffmanTree(long w,int n,HTNODE ht)int m,i,s1,s2;if (n1) return ERROR;m=2*n-1;/霍夫曼樹節(jié)點(diǎn)總數(shù)=葉子數(shù)*2-1if (ht=NULL) return ERROR;for(i=0;in;i+)hti.w=wi,hti.p=hti.l=hti.r=UNU

17、SE;/初始化葉子節(jié)點(diǎn) for(;im;i+)hti.w=hti.p=hti.l=hti.r=UNUSE;/初始化分支節(jié)點(diǎn)for(i=n;im;i+)/建立huffman樹/循環(huán)至m-n個(gè)分支節(jié)點(diǎn)全部被使用完為止s1=Search(ht,i);s2=Search(ht,i);/找到權(quán)值最小的兩個(gè)節(jié)點(diǎn)，這里通過兩次調(diào)用尋找最小權(quán)值的函數(shù)search解決問題hts1.p=hts2.p=i;/設(shè)置父節(jié)點(diǎn)hti.l=s1,hti.r=s2;/設(shè)置孩子hti.w=hts1.w+hts2.w;/設(shè)置權(quán)為兩個(gè)孩子權(quán)之和return OK;int HuffmanTreeCoding(HTNP htp,int

18、n,HFCODE hc)int i,j,p,codelen;/codelen:臨時(shí)字符數(shù)組長(zhǎng)度變量BYTE *code=(BYTE*)malloc(n*BYTESIZE);/臨時(shí)字符數(shù)組，為每一個(gè)字符的編碼申請(qǐng)一個(gè)字節(jié)的空間for(i=0;in;i+)/從當(dāng)前節(jié)點(diǎn)到根節(jié)點(diǎn)逆向求huffman編碼，遍歷所有葉子節(jié)點(diǎn)。for(p=i,codelen=0;p!=2*n-2;p=htpp.p,codelen+)/循環(huán)到根節(jié)點(diǎn)為止codecodelen=(htphtpp.p.l=p?0:1);/第i位編碼：p節(jié)點(diǎn)如果是其父親的：左孩子:0;右孩子:1 if(hci.codestr=(BYTE *)mal

19、loc(codelen)*BYTESIZE)=NULL)return ERROR;/分配葉子節(jié)點(diǎn)huffman編碼的空間，長(zhǎng)度為hci.len=codelen;/該字符編碼的碼長(zhǎng)for(j=0;jcodelen;j+)hci.codestrj=codecodelen-j-1;/反轉(zhuǎn)（因?yàn)樵瓉硎悄娴模ゝree(code);/擦屁股return OK;BYTE Char2Bit(const BYTE charsCHAR_BITS)int i;BYTE bits=0;bits|=chars0;for(i=1;iCHAR_BITS;+i)/將8個(gè)字符轉(zhuǎn)換成8個(gè)二進(jìn)制位bits=1;/左移或?qū)崿F(xiàn)bits

20、|=charsi; return bits;int WriteZipFiles(FILE *in,FILE *out,HTNP ht,HFCODE hc,char* SourceFilename,long source_filesize)UINT i,Read_Counter,Write_Counter,zip_head=TAG_ZIGHEAD;/讀緩存計(jì)數(shù)器,寫緩存計(jì)數(shù)器,壓縮文件頭標(biāo)BYTE write_char_counter,code_char_counter,copy_char_counter;/寫字符計(jì)數(shù)器,huffman碼字符計(jì)數(shù)器,復(fù)制字符計(jì)數(shù)器BYTEread_bufBUFF

21、ERSIZE,write_bufBUFFERSIZE,write_charsCHAR_BITS;/讀緩存,寫緩存,轉(zhuǎn)換字符數(shù)組,BYTE filename_size=strlen(SourceFilename);/文件名長(zhǎng)度HFCODE *Cur_HuffCode;/當(dāng)前數(shù)據(jù)的huffman編碼指針/預(yù)處理fseek(in,0L,SEEK_SET);/定位讀文件到文件開始處fseek(out,0L,SEEK_SET);/定位寫文件到文件開始處fwrite(&zip_head,UINTSIZE,1,out);/寫入文件頭標(biāo)示符fwrite(&filename_size,BYTESIZE,1,ou

22、t);/寫入源文件名長(zhǎng)度fwrite(SourceFilename,sizeof(char),filename_size,out);/寫入源文件名fwrite(&source_filesize,sizeof(long),1,out);/寫入源文件長(zhǎng)度for(i=HUFCODE_SIZE;iHUFCODE_SIZE*2-1;i+)/寫huffman樹的左右孩子(前HUFCODE_SIZE個(gè)節(jié)點(diǎn)無孩子，不寫)fwrite(&(hti.l),sizeof(hti.l),1,out);/寫入左孩子fwrite(&(hti.r),sizeof(hti.r),1,out);/寫入右孩子/寫正文Write_

23、Counter=write_char_counter=0;/寫緩沖計(jì)數(shù)器以及寫字符計(jì)數(shù)器清0Read_Counter=BUFFERSIZE;/置讀緩存字符數(shù)/當(dāng)讀入的緩存字符數(shù)不等于緩存時(shí)，文件讀完，退出循環(huán)while(Read_Counter=BUFFERSIZE)Read_Counter=fread(read_buf,1,BUFFERSIZE,in);/讀入大小為BUFFSIZE的數(shù)據(jù)到讀緩存/為每個(gè)緩存的數(shù)據(jù)找huffman編碼for(i=0;ilen) /獲取本次復(fù)制字符的長(zhǎng)度為 可用寫字符長(zhǎng)度與可用huffman編碼長(zhǎng)度中的較小者copy_char_counter= (CHAR_BI

24、TS-write_char_counter Cur_HuffCode-len-code_char_counter ? Cur_HuffCode-len-code_char_counter : CHAR_BITS-write_char_counter);/復(fù)制一段字符memcpy(write_chars+write_char_counter,Cur_HuffCode-codestr+code_char_counter,copy_char_counter);write_char_counter+=copy_char_counter;/寫字符計(jì)數(shù)器增加code_char_counter+=copy_

25、char_counter;/編碼字符計(jì)數(shù)器增加/當(dāng)寫字符計(jì)算器滿=8時(shí)if(write_char_counter=CHAR_BITS)write_char_counter=0;/寫字符計(jì)數(shù)器清0/當(dāng)寫緩存滿時(shí)write_bufWrite_Counter+=Char2Bit(write_chars);/轉(zhuǎn)化寫字符為二進(jìn)制數(shù)并存入寫緩存if(Write_Counter=BUFFERSIZE)fwrite(write_buf,1,BUFFERSIZE,out);/輸出到文件Write_Counter=0;/寫緩存清0fwrite(write_buf,1,Write_Counter,out);/寫緩存

26、中剩余數(shù)據(jù)輸出到文件,擦屁股/當(dāng)寫字符數(shù)組中還有字符未轉(zhuǎn)換if(write_char_counter!=0)write_char_counter=Char2Bit(write_chars);/轉(zhuǎn)化為二級(jí)制數(shù)據(jù)fwrite(&write_char_counter,1,1,out);/輸出到文件return OK;/解壓縮int DeCompress(char *SourceFilename,char *DestinationFilename)FILE *in,*out;/定義輸入輸出流short mini_htHUFCODE_SIZE*2-12;long Dst_Filesize;Initial

27、izing_Dezip(SourceFilename,&in,DestinationFilename,&out);/初始化文件處理環(huán)境puts(File open Successfully.);fread(&Dst_Filesize,sizeof(long),1,in);/讀取解壓縮文件長(zhǎng)度printf(Expected Length: %ldn,Dst_Filesize);puts(Establishing HuffmanTree.);ReadHuffmanTree(in,mini_ht);/生成mini的huffmantreeputs(Rebuild Successfully.Now De

28、compressing.);WriteDeZipFiles(in,out,mini_ht,ftell(in),Dst_Filesize);/解碼壓縮文件并生成解壓縮文件puts(Decompress Complete!);/擦屁股fclose(in);fclose(out);return OK;int Initializing_Dezip(char *SourceFilename,FILE *inp,char *DestinationFilename,FILE *outp)UINT zip_head;BYTE filename_size;char temp_filenameMAX_FILENA

29、ME;/處理源文件printf(Source Files:%s,SourceFilename);if (*inp=fopen(SourceFilename,rb)=NULL)return ERROR;/不能讀文件/讀取源文件頭,如果讀入的文件頭與常量不符，報(bào)錯(cuò)退出。fread(&zip_head,UINTSIZE,1,*inp);if(zip_head!=TAG_ZIGHEAD)return ERROR;/非法的文件頭/處理解壓縮文件名if(DestinationFilename=NULL)/如果目標(biāo)文件名未分配DestinationFilename = temp_filename;fread

30、(&filename_size,BYTESIZE,1,*inp);/得到目標(biāo)文件名長(zhǎng)度fread(DestinationFilename,sizeof(char),filename_size,*inp);/得到目標(biāo)文件名DestinationFilenamefilename_size=0;/添加結(jié)尾字符elsefread(&filename_size,BYTESIZE,1,*inp);fseek(*inp,filename_size,SEEK_CUR);/若分配了，直接跳過文件名信息printf(Decompress Files:%sn,DestinationFilename);if(*outp=fopen(DestinationFilename,wb)=NULL)return ERROR;/不能寫文件return OK;void ReadHuffmanTree(FILE* in,short mini_ht2)int i;for(i=0;i=1)cur_pos=(read_bufRead_Counter&convert_bit)=0?mini_htcur_pos0:mini_htcur_pos1);/按位查找huffmantree節(jié)點(diǎn)，0左，1右if(cur_posHUFCODE_SIZE)/如果當(dāng)前節(jié)點(diǎn)位