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

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

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

3、赫夫曼編碼數(shù)組元素的數(shù)據(jù)結(jié)構(gòu)設(shè)計typedefstructhuffman_codeBYTElen;/ 長度BYTE *codestr;/ 字符串 HFCODE;/ 霍夫曼編碼數(shù)組元素3. 算法設(shè)計源代碼#define_CRT_SECURE_NO_DEPRECATE#include<stdio.h>#include<string.h>#include<stdlib.h>typedefunsignedintUINT;typedefunsignedcharBYTE;typedefstructnodelongw;/權(quán)short p,l,r;/父親，左孩子，右孩子 H

4、TNODE,* HTNP;/霍夫曼樹的結(jié)點typedefstructhuffman_codeBYTElen;/ 長度BYTE *codestr;/ 字符串 HFCODE;/ 霍夫曼編碼數(shù)組元素#defineOK1#defineERROR-1#defineUNUSE-1/ 未鏈接節(jié)點標(biāo)志#defineCHAR_BITS 8/ 一個字符中的位數(shù)#defineINT_BITS32/ 一個整型中的位數(shù)#defineHUFCODE_SIZE256/ 霍夫曼編碼個數(shù)#defineBUFFERSIZE256/ 緩沖區(qū)大小大小#defineUINTSIZEsizeof ( UINT)#defineBYTESI

5、ZE sizeof ( BYTE)#defineTAG_ZIGHEAD0xFFFFFFFF/ 壓縮文件頭標(biāo)#defineMAX_FILENAME512/ 函數(shù)聲明/ 壓縮模塊intCompress(char *SourceFilename,char *DestinationFilename);/ 壓縮調(diào)用intInitializing(char *SourceFilename,FILE *inp,char *DestinationFilename,FILE*outp);/ 初始化文件工作環(huán)境longAnalysisFiles(FILE *in,long frequency);精選范本 ,供參考

6、！/ 計算每個不同字節(jié)的頻率以及所有的字節(jié)數(shù)intCreateHuffmanTree(long w,intn, HTNODEht);/ 生成霍夫曼樹intHuffmanTreeCoding(HTNPhtp, intn, HFCODEhc);/ 霍夫曼編碼intSearch(HTNPht,intn);/ 查找當(dāng)前最小權(quán)值的霍夫曼樹節(jié)點并置為占用BYTE Char2Bit(constBYTEcharsCHAR_BITS);/ 將一個字符數(shù)組轉(zhuǎn)換成二進制數(shù)字intSearch(HTNPht,intn);/ 查找當(dāng)前最小權(quán)值的霍夫曼樹節(jié)點并置為占用intWriteZipFiles(FILE *in,

7、FILE *out,HTNPht,HFCODEhc, char * SourceFilename, longsource_filesize);/ 寫壓縮文件/ 解壓縮模塊intDeCompress(char*SourceFilename,char *DestinationFilename);/ 解壓縮調(diào)用intInitializing_Dezip(char *SourceFilename,FILE *inp, char*DestinationFilename,FILE *outp);/為處理解壓縮流程初始化文件voidReadHuffmanTree(FILE* in,shortmini_ht2

8、);/ 從待解壓縮文件中讀取 huffman 樹intWriteDeZipFiles(FILE *in,FILE* out,shortmini_ht2,long bits_pos,longDst_Filesize);/ 寫解壓縮文件voidErrorReport(interror_code);/ 報錯/ 函數(shù)定義/ 函數(shù)實現(xiàn)/ 壓縮intCompress( char * SourceFilename , char * DestinationFilename)FILE *in,*out;/ 輸入輸出流inti;/ 計數(shù)變量floatCompress_rate;/ 存放壓縮率HFCODEhc HU

9、FCODE_SIZE;/ 存放 256個字符的 huffman 編碼HTNODEhtHUFCODE_SIZE*2-1;/256 個字符的 huffman 樹需要 2*256-1=511 個節(jié)點。long frequencyHUFCODE_SIZE,source_filesize,Dst_Filesize=0;/ 字符頻率數(shù)組，源文件，目標(biāo)文件。/ 處理待壓縮與壓縮文件文件Initializing(SourceFilename ,&in, DestinationFilename,&out);puts( "Loading Files.");/ 處理各個字符的頻率

10、，并輸出原始文件長度精選范本 ,供參考！SourceFilename ,source_filesize);source_filesize=AnalysisFiles(in,frequency);puts( "Loading Complete!Now Analysising.");printf("Original size:%ld Byte n",source_filesize);/ 創(chuàng)建 Huffman樹CreateHuffmanTree(frequency,HUFCODE_SIZE,ht);/Huffman 編碼puts( "Huffman

11、Tree Initialized Successfully,HuffmanCoding Processing." ); HuffmanTreeCoding(ht, HUFCODE_SIZE,hc);/ 計算目標(biāo)文件長度for (i=0;i<HUFCODE_SIZE;i+) / 計算位的個數(shù) , 計算每個字符的頻數(shù)與其編碼長度乘積之和Dst_Filesize+=frequencyi*hci.len; / 將文件主體部分的位個數(shù)轉(zhuǎn)換為字節(jié)個數(shù) ;Dst_Filesize=Dst_Filesize%8=0?Dst_Filesize/8:Dst_Filesize/8+1;for (i=

12、0;i<HUFCODE_SIZE-1;i+) /huffmantree長度Dst_Filesize+=2*sizeof ( short );Dst_Filesize+=strlen(SourceFilename )+1;/ 源文件名占用空間Dst_Filesize+=sizeof ( long );/ 源文件名長度信息占用空間Dst_Filesize+=UINTSIZE;/ 文件頭長度Compress_rate=( float)Dst_Filesize/source_filesize;/ 壓縮率puts( "Coding Successfully.Now producing z

13、ip files.");printf("Compressed File Size:%ld Byte,radiation:%.2lfn" ,Dst_Filesize,Compress_rate*100);/ 生成壓縮文件WriteZipFiles(in,out,ht,hc,puts( "Compress Complete!");/ 擦屁股fclose(in);fclose(out);/ 關(guān)閉文件for (i=0;i<HUFCODE_SIZE;i+)free(hci.codestr);returnOK;精選范本 ,供參考！intInitial

14、izing(char * SourceFilename , FILE * inp , char * DestinationFilename, FILE * outp )if (strcmp( SourceFilename , DestinationFilename)=0) / 重名判斷returnERROR;printf("Source File:%s,Destination File:%sn", SourceFilename , DestinationFilename);if (* outp =fopen( DestinationFilename, "wb&qu

15、ot; )= NULL) / 文件打開錯誤returnERROR;if (* inp =fopen( SourceFilename , "rb" )= NULL) / 文件打開錯誤returnERROR;returnOK;long AnalysisFiles(FILE * in , longfrequency )inti,read_len;BYTE bufBUFFERSIZE;/ 緩沖區(qū)longfilesize;/ 文件總長for (i=0;i<HUFCODE_SIZE;i+)frequency i=0;/ 初始化所有字符頻率為0fseek( in ,0L, SEEK

16、_SET);/ 將文件定位符指向文件開頭read_len= BUFFERSIZE;/ 設(shè)置讀入長度 =緩沖區(qū)長度while (read_len= BUFFERSIZE)/ 每當(dāng)讀取字符長度達到緩沖區(qū)長度時read_len=fread(buf,1,BUFFERSIZE, in );for (i=0;i<read_len;i+)frequency *(buf+i)+;/ 統(tǒng)計字頻for (i=0,filesize=0;i<HUFCODE_SIZE;i+)filesize+=frequency i;/ 計算文件長度，計算方法是把所有字符的頻數(shù)相加精選范本 ,供參考！returnfiles

17、ize;intSearch( HTNPht , intn)inti,x;for (x=0;x< n;x+)if ( ht x.p=UNUSE)break ; / 找到第一個沒有使用的葉子節(jié)點，跳出for (i=x;i<n;i+)if ( ht i.p=UNUSE&&ht i.w<ht x.w)x=i;/ 找權(quán)值最小的葉子節(jié)點ht x.p=-2;/ 將葉子節(jié)點占用returnx;intCreateHuffmanTree(longw,intn, HTNODEht )intm,i,s1,s2;if( n<1)return ERROR;m=2*n-1;/ 霍夫曼

18、樹節(jié)點總數(shù) =葉子數(shù) *2-1if( ht =NULL)return ERROR;for (i=0;i< n;i+)ht i.w=wi,ht i.p= ht i.l= ht i.r= UNUSE;/ 初始化葉子節(jié)點for (;i<m;i+)ht i.w=ht i.p= ht i.l= ht i.r= UNUSE;/ 初始化分支節(jié)點for (i= n;i<m;i+)/ 建立 huffman 樹/ 循環(huán)至 m-n個分支節(jié)點全部被使用完為止s1=Search( ht ,i);s2=Search( ht ,i);/ 找到權(quán)值最小的兩個節(jié)點，這里通過兩次調(diào)用尋找最小權(quán)值的函數(shù) sear

19、ch 解決問題ht s1.p=ht s2.p=i;/ 設(shè)置父節(jié)點ht i.l=s1,ht i.r=s2;/ 設(shè)置孩子ht i.w=ht s1.w+ ht s2.w;/ 設(shè)置權(quán)為兩個孩子權(quán)之和精選范本 ,供參考！returnOK;intHuffmanTreeCoding( HTNPhtp , intn, HFCODEhc)inti,j,p,codelen;/codelen:臨時字符數(shù)組長度變量BYTE*code=( BYTE*)malloc(n* BYTESIZE);/ 臨時字符數(shù)組，為每一個字符的編碼申請一個字節(jié)的空間for (i=0;i<n;i+) / 從當(dāng)前節(jié)點到根節(jié)點逆向求 huf

20、fman 編碼，遍歷所有葉子節(jié)點。for (p=i,codelen=0;p!=2*n-2;p= htp p.p,codelen+) / 循環(huán)到根節(jié)點為止codecodelen=( htp htp p.p.l=p?0:1); / 第 i 位編碼： p節(jié)點如果是其父親的： 左孩子 :0; 右孩子 :1if ( hci.codestr=(BYTE*)malloc(codelen)*BYTESIZE)= NULL)returnERROR;/ 分配葉子節(jié)點 huffman 編碼的空間，長度為hci.len=codelen;/ 該字符編碼的碼長for (j=0;j<codelen;j+)hci.co

21、destrj=codecodelen-j-1;/ 反轉(zhuǎn)（因為原來是逆的）free(code);/ 擦屁股returnOK;BYTEChar2Bit(constBYTEchars CHAR_BITS)inti;BYTEbits=0;bits|=chars 0;for (i=1;i<CHAR_BITS;+i) / 將 8個字符轉(zhuǎn)換成 8個二進制位bits<<=1;/ 左移或?qū)崿F(xiàn)bits|=chars i;returnbits;intWriteZipFiles(FILE * in , FILE * out , HTNPht , HFCODEhc,char * SourceFilen

22、ame , long精選范本 ,供參考！source_filesize)UINTi,Read_Counter,Write_Counter,zip_head=TAG_ZIGHEAD;/ 讀緩存計數(shù)器 , 寫緩存計數(shù)器 , 壓縮文件頭標(biāo)BYTE write_char_counter,code_char_counter,copy_char_counter;/ 寫字符計數(shù)器 ,huffman 碼字符計數(shù)器 , 復(fù)制字符計數(shù)器BYTEread_buf BUFFERSIZE,write_bufBUFFERSIZE,write_charsCHAR_BITS;/讀緩存 , 寫緩存 , 轉(zhuǎn)換字符數(shù)組 ,BYTE

23、 filename_size=strlen(SourceFilename );/ 文件名長度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, out );/ 寫入源文件名長度fwrite(SourceFilename , sizeo

24、f ( char ),filename_size,out );/ 寫入源文件名fwrite(&source_filesize, sizeof ( long ),1, out );/ 寫入源文件長度for (i=HUFCODE_SIZE;i<HUFCODE_SIZE*2-1;i+)/ 寫 huffman 樹的左右孩子 ( 前HUFCODE_SIZE個節(jié)點無孩子，不寫)fwrite(&(ht i.l),sizeof ( ht i.l),1,out ); / 寫入左孩子fwrite(&(ht i.r),sizeof ( ht i.r),1,out ); / 寫入右孩子/

25、 寫正文Write_Counter=write_char_counter=0;/ 寫緩沖計數(shù)器以及寫字符計數(shù)器清 0 Read_Counter=BUFFERSIZE;/ 置讀緩存字符數(shù)/ 當(dāng)讀入的緩存字符數(shù)不等于緩存時，文件讀完，退出循環(huán)while (Read_Counter= BUFFERSIZE)Read_Counter=fread(read_buf,1,BUFFERSIZE, in );/ 讀入大小為 BUFFSIZE的數(shù)據(jù)到讀緩存精選范本 ,供參考！/ 為每個緩存的數(shù)據(jù)找 huffman 編碼for (i=0;i<Read_Counter;i+)Cur_HuffCode=&

26、;hcread_bufi;/ 當(dāng)前數(shù)據(jù)的 huffman 編碼位置 code_char_counter=0;/ 當(dāng)前數(shù)據(jù) huffman 編碼字符的計數(shù)器清 0/ 當(dāng) huffman 編碼字符的計數(shù)器等于碼長時，轉(zhuǎn)換完畢退出while (code_char_counter!=Cur_HuffCode->len)/ 獲取本次復(fù)制字符的長度為可用寫字符長度與可用huffman 編碼長度中的較小者copy_char_counter= ( CHAR_BITS-write_char_counter > Cur_HuffCode->len-code_char_counter ?Cur_H

27、uffCode->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;/ 寫字符計數(shù)器增加code_char_counter+=copy_char_counter;/ 編碼字符計數(shù)器增加/ 當(dāng)寫字符計算器滿 =8時if (write_char_c

28、ounter=CHAR_BITS)write_char_counter=0;/ 寫字符計數(shù)器清 0/ 當(dāng)寫緩存滿時write_bufWrite_Counter+=Char2Bit(write_chars);/ 轉(zhuǎn)化寫字符為二進制數(shù)并存入寫緩存if (Write_Counter=BUFFERSIZE)fwrite(write_buf,1,BUFFERSIZE, out ); / 輸出到文件Write_Counter=0;/ 寫緩存清 0fwrite(write_buf,1,Write_Counter,out ); / 寫緩存中剩余數(shù)據(jù)輸出到文件, 擦屁股/ 當(dāng)寫字符數(shù)組中還有字符未轉(zhuǎn)換if (w

29、rite_char_counter!=0)精選范本 ,供參考！write_char_counter=Char2Bit(write_chars);/ 轉(zhuǎn)化為二級制數(shù)據(jù)fwrite(&write_char_counter,1,1,out ); / 輸出到文件returnOK;/ 解壓縮intDeCompress(char * SourceFilename , char * DestinationFilename)FILE*in,*out;/定義輸入輸出流shortmini_htHUFCODE_SIZE*2-12;longDst_Filesize;Initializing_Dezip(Sou

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

31、huffmantreeputs( "Rebuild Successfully.Now Decompressing.");WriteDeZipFiles(in,out,mini_ht,ftell(in),Dst_Filesize);/解碼壓縮文件并生成解壓縮文件puts( "Decompress Complete!");/ 擦屁股fclose(in);fclose(out);returnOK;intInitializing_Dezip(char * SourceFilename , FILE * inp , char * DestinationFilena

32、me, FILE* outp )UINT zip_head;BYTE filename_size;chartemp_filenameMAX_FILENAME;/ 處理源文件printf("Source Files:%s,", SourceFilename );if(*inp =fopen( SourceFilename , "rb" )= NULL)精選范本 ,供參考！returnERROR; / 不能讀文件/ 讀取源文件頭 , 如果讀入的文件頭與常量不符，報錯退出。fread(&zip_head,UINTSIZE,1,* inp );if (z

33、ip_head!= TAG_ZIGHEAD)returnERROR; / 非法的文件頭/ 處理解壓縮文件名if ( DestinationFilename=NULL) / 如果目標(biāo)文件名未分配DestinationFilename= temp_filename;fread(&filename_size,BYTESIZE,1,* inp );/ 得到目標(biāo)文件名長度fread( DestinationFilename, sizeof ( char ),filename_size,*inp );/ 得到目標(biāo)文件名DestinationFilenamefilename_size='0&

34、#39;/ 添加結(jié)尾字符elsefread(&filename_size,BYTESIZE,1,* inp );fseek(* inp ,filename_size,SEEK_CUR); / 若分配了，直接跳過文件名信息printf("Decompress Files:%sn", DestinationFilename);if (* outp =fopen( DestinationFilename, "wb" )= NULL)returnERROR; / 不能寫文件returnOK;void ReadHuffmanTree( FILE* in ,

35、 shortmini_ht 2)inti;for (i=0;i<HUFCODE_SIZE;i+)mini_ht i0=mini_ht i1=UNUSE; / 葉子節(jié)點無孩子fread( mini_ht i,sizeof ( short ),2*(HUFCODE_SIZE-1),in ); / 得到非葉子節(jié)點的孩子信息int WriteDeZipFiles( FILE *in , FILE* out , short mini_ht 2, long bits_pos , long Dst_Filesize ) longcur_size;BYTE read_bufBUFFERSIZE,writ

36、e_bufBUFFERSIZE,convert_bit;UINTRead_Counter,Write_Counter,cur_pos;精選范本 ,供參考！fseek( in , bits_pos , SEEK_SET); / 定位到寫文件壓縮碼開始處fseek( out ,0L, SEEK_SET); / 定位到寫文件頭部/ 解碼開始Read_Counter=BUFFERSIZE-1; / 置寫緩存計數(shù)器cur_size=Write_Counter=0; / 當(dāng)前寫入文件長度與寫緩存計數(shù)器為 0 cur_pos= HUFCODE_SIZE*2-2; / 當(dāng)前 huffman 節(jié)點為根節(jié)點/ 如

37、果寫入文件長度達到目標(biāo)文件長度，文件寫入完畢，退出while (cur_size!=Dst_Filesize)/ 若讀緩存計數(shù)器滿if (+Read_Counter=BUFFERSIZE)fread(read_buf,1,BUFFERSIZE, in ); / 讀入到讀緩存Read_Counter=0; / 讀緩存計數(shù)器清 0/ 一次循環(huán)處理 8位，即 1字節(jié)for (convert_bit=128;convert_bit!=0;convert_bit>>=1)cur_pos=(read_bufRead_Counter&convert_bit)=0?mini_ht cur_pos0:mini_ht cur_pos1);/ 按位查找 huffmantree 節(jié)點， 0左， 1右if (cur_pos< HUFCODE_SIZE) / 如果當(dāng)前節(jié)點位置小與編碼數(shù)，則是葉子節(jié)點write_bufWrite_Counter=(BYTE)cu