数据结构(5)_文件压缩

1、数据结构实验报告实验名称：文件压缩实验类型：综合性试验班级：20112111学号：2011211107姓名：冯若航实验日期：2003.6.19 下午4:001.问题描述文件压缩基本要求哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。l 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat中。l 根据哈夫曼树（保存在HufTree.dat

2、中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt文件中。l 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。l 解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。2.数据结构设计此类问题，应设计文件的数据结构。*4压缩头标记*1文件名长度*ns文件名*4源文件长度*1020huffman树*1021EOF文件内容赫夫曼树节点的数据结构typedef struct nodelong w;/权short p,l,r;/父亲，左孩子，右孩子HTNODE,*HTNP;/霍夫曼树的结点赫夫曼编码数组元素的数据结构设计typedef

3、struct huffman_codeBYTE len;/长度BYTE *codestr;/字符串HFCODE;/霍夫曼编码数组元素3.算法设计源代码#define _CRT_SECURE_NO_DEPRECATE#include #include #include typedef unsigned int UINT;typedef unsigned char BYTE;typedef struct nodelong w;/权short p,l,r;/父亲，左孩子，右孩子HTNODE,*HTNP;/霍夫曼树的结点typedef struct huffman_codeBYTE len;/长度BY

4、TE *codestr;/字符串HFCODE;/霍夫曼编码数组元素#define OK 1#define ERROR -1#define UNUSE -1/未链接节点标志#define CHAR_BITS 8/一个字符中的位数#define INT_BITS 32/一个整型中的位数#define HUFCODE_SIZE 256/霍夫曼编码个数#define BUFFERSIZE 256/缓冲区大小大小#define UINTSIZE sizeof(UINT)#define BYTESIZE sizeof(BYTE)#define TAG_ZIGHEAD 0xFFFFFFFF/压缩文件头标#d

5、efine MAX_FILENAME512 /函数声明/压缩模块int Compress(char *SourceFilename,char *DestinationFilename);/压缩调用int Initializing(char *SourceFilename,FILE *inp,char *DestinationFilename,FILE *outp);/初始化文件工作环境long AnalysisFiles(FILE *in,long frequency);/计算每个不同字节的频率以及所有的字节数int CreateHuffmanTree(long w,int n,HTNODE

6、ht);/生成霍夫曼树int HuffmanTreeCoding(HTNP htp,int n,HFCODE hc);/霍夫曼编码int Search(HTNP ht,int n);/查找当前最小权值的霍夫曼树节点并置为占用BYTE Char2Bit(const BYTE charsCHAR_BITS);/将一个字符数组转换成二进制数字int Search(HTNP ht,int n);/查找当前最小权值的霍夫曼树节点并置为占用int WriteZipFiles(FILE *in,FILE *out,HTNP ht,HFCODE hc,char* SourceFilename,long sou

7、rce_filesize);/写压缩文件/解压缩模块int DeCompress(char *SourceFilename,char *DestinationFilename);/解压缩调用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);/报错/函数定义/函数实现/压缩int Compress(char *SourceFilename,char *DestinationFilename)FILE *in,*out;/输入输出流int i;/计数变量float Compress_rate;/存放压缩率HFCODE hcHUFCODE_SIZE;/存放256个字符的huffman编码HTNODE htHUFCODE_SIZE*2-1;/256个字符

9、的huffman树需要2*256-1=511个节点。long frequencyHUFCODE_SIZE ,source_filesize,Dst_Filesize=0;/字符频率数组，源文件，目标文件。/处理待压缩与压缩文件文件Initializing(SourceFilename,&in,DestinationFilename,&out);puts(Loading Files.);/处理各个字符的频率，并输出原始文件长度source_filesize=AnalysisFiles(in,frequency); puts(Loading Complete!Now Analysising.);p

10、rintf(Original size:%ld Byte n,source_filesize);/创建Huffman树CreateHuffmanTree(frequency,HUFCODE_SIZE,ht);/Huffman编码puts(Huffman Tree Initialized Successfully,HuffmanCoding Processing.); HuffmanTreeCoding(ht,HUFCODE_SIZE,hc);/计算目标文件长度for(i=0;iHUFCODE_SIZE;i+)/计算位的个数,计算每个字符的频数与其编码长度乘积之和Dst_Filesize+=fr

11、equencyi*hci.len;/将文件主体部分的位个数转换为字节个数;Dst_Filesize=Dst_Filesize%8=0?Dst_Filesize/8:Dst_Filesize/8+1;for(i=0;iHUFCODE_SIZE-1;i+)/huffmantree长度Dst_Filesize+=2*sizeof(short);Dst_Filesize+=strlen(SourceFilename)+1;/源文件名占用空间Dst_Filesize+=sizeof(long);/源文件名长度信息占用空间Dst_Filesize+=UINTSIZE;/文件头长度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);/关

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)/文件打开错误return ERROR;if(*inp=fopen(SourceFilename,rb)=NULL)/文件打开错误return ERROR;return OK;long AnalysisFiles(FILE *in,long frequency)int i,read_len;BYTE bufBUFFERSIZE;/缓冲区long filesize;/文件总长for(i=0;iHUFCODE_SIZE;i+)frequencyi=0;/初始化所有字符频率为0fseek(in,0L,SEEK_SET);/将文件定位符指向

15、文件开头read_len=BUFFERSIZE;/设置读入长度=缓冲区长度while(read_len=BUFFERSIZE)/每当读取字符长度达到缓冲区长度时read_len=fread(buf,1,BUFFERSIZE,in);for(i=0;iread_len;i+)frequency*(buf+i)+;/统计字频for(i=0,filesize=0;iHUFCODE_SIZE;i+)filesize+=frequencyi;/计算文件长度，计算方法是把所有字符的频数相加return filesize;int Search(HTNP ht,int n)int i,x;for(x=0;xn

16、;x+)if(htx.p=UNUSE) break;/找到第一个没有使用的叶子节点，跳出for(i=x;in;i+)if(hti.p=UNUSE&hti.whtx.w)x=i;/找权值最小的叶子节点htx.p=-2;/将叶子节点占用return x;int CreateHuffmanTree(long w,int n,HTNODE ht)int m,i,s1,s2;if (n1) return ERROR;m=2*n-1;/霍夫曼树节点总数=叶子数*2-1if (ht=NULL) return ERROR;for(i=0;in;i+)hti.w=wi,hti.p=hti.l=hti.r=UNU

17、SE;/初始化叶子节点 for(;im;i+)hti.w=hti.p=hti.l=hti.r=UNUSE;/初始化分支节点for(i=n;im;i+)/建立huffman树/循环至m-n个分支节点全部被使用完为止s1=Search(ht,i);s2=Search(ht,i);/找到权值最小的两个节点，这里通过两次调用寻找最小权值的函数search解决问题hts1.p=hts2.p=i;/设置父节点hti.l=s1,hti.r=s2;/设置孩子hti.w=hts1.w+hts2.w;/设置权为两个孩子权之和return OK;int HuffmanTreeCoding(HTNP htp,int

18、n,HFCODE hc)int i,j,p,codelen;/codelen:临时字符数组长度变量BYTE *code=(BYTE*)malloc(n*BYTESIZE);/临时字符数组，为每一个字符的编码申请一个字节的空间for(i=0;in;i+)/从当前节点到根节点逆向求huffman编码，遍历所有叶子节点。for(p=i,codelen=0;p!=2*n-2;p=htpp.p,codelen+)/循环到根节点为止codecodelen=(htphtpp.p.l=p?0:1);/第i位编码：p节点如果是其父亲的：左孩子:0;右孩子:1 if(hci.codestr=(BYTE *)mal

19、loc(codelen)*BYTESIZE)=NULL)return ERROR;/分配叶子节点huffman编码的空间，长度为hci.len=codelen;/该字符编码的码长for(j=0;jcodelen;j+)hci.codestrj=codecodelen-j-1;/反转（因为原来是逆的）free(code);/擦屁股return OK;BYTE Char2Bit(const BYTE charsCHAR_BITS)int i;BYTE bits=0;bits|=chars0;for(i=1;iCHAR_BITS;+i)/将8个字符转换成8个二进制位bits=1;/左移或实现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;/读缓存计数器,写缓存计数器,压缩文件头标BYTE write_char_counter,code_char_counter,copy_char_counter;/写字符计数器,huffman码字符计数器,复制字符计数器BYTEread_bufBUFF

21、ERSIZE,write_bufBUFFERSIZE,write_charsCHAR_BITS;/读缓存,写缓存,转换字符数组,BYTE filename_size=strlen(SourceFilename);/文件名长度HFCODE *Cur_HuffCode;/当前数据的huffman编码指针/预处理fseek(in,0L,SEEK_SET);/定位读文件到文件开始处fseek(out,0L,SEEK_SET);/定位写文件到文件开始处fwrite(&zip_head,UINTSIZE,1,out);/写入文件头标示符fwrite(&filename_size,BYTESIZE,1,ou

22、t);/写入源文件名长度fwrite(SourceFilename,sizeof(char),filename_size,out);/写入源文件名fwrite(&source_filesize,sizeof(long),1,out);/写入源文件长度for(i=HUFCODE_SIZE;iHUFCODE_SIZE*2-1;i+)/写huffman树的左右孩子(前HUFCODE_SIZE个节点无孩子，不写)fwrite(&(hti.l),sizeof(hti.l),1,out);/写入左孩子fwrite(&(hti.r),sizeof(hti.r),1,out);/写入右孩子/写正文Write_

23、Counter=write_char_counter=0;/写缓冲计数器以及写字符计数器清0Read_Counter=BUFFERSIZE;/置读缓存字符数/当读入的缓存字符数不等于缓存时，文件读完，退出循环while(Read_Counter=BUFFERSIZE)Read_Counter=fread(read_buf,1,BUFFERSIZE,in);/读入大小为BUFFSIZE的数据到读缓存/为每个缓存的数据找huffman编码for(i=0;ilen) /获取本次复制字符的长度为 可用写字符长度与可用huffman编码长度中的较小者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);/复制一段字符memcpy(write_chars+write_char_counter,Cur_HuffCode-codestr+code_char_counter,copy_char_counter);write_char_counter+=copy_char_counter;/写字符计数器增加code_char_counter+=copy_

25、char_counter;/编码字符计数器增加/当写字符计算器满=8时if(write_char_counter=CHAR_BITS)write_char_counter=0;/写字符计数器清0/当写缓存满时write_bufWrite_Counter+=Char2Bit(write_chars);/转化写字符为二进制数并存入写缓存if(Write_Counter=BUFFERSIZE)fwrite(write_buf,1,BUFFERSIZE,out);/输出到文件Write_Counter=0;/写缓存清0fwrite(write_buf,1,Write_Counter,out);/写缓存

26、中剩余数据输出到文件,擦屁股/当写字符数组中还有字符未转换if(write_char_counter!=0)write_char_counter=Char2Bit(write_chars);/转化为二级制数据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);/初始化文件处理环境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的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;/不能读文件/读取源文件头,如果读入的文件头与常量不符，报错退出。fread(&zip_head,UINTSIZE,1,*inp);if(zip_head!=TAG_ZIGHEAD)return ERROR;/非法的文件头/处理解压缩文件名if(DestinationFilename=NULL)/如果目标文件名未分配DestinationFilename = temp_filename;fread

30、(&filename_size,BYTESIZE,1,*inp);/得到目标文件名长度fread(DestinationFilename,sizeof(char),filename_size,*inp);/得到目标文件名DestinationFilenamefilename_size=0;/添加结尾字符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节点，0左，1右if(cur_posHUFCODE_SIZE)/如果当前节点位