《数据结构(5)_文件压缩讲义》由会员分享,可在线阅读,更多相关《数据结构(5)_文件压缩讲义(14页珍藏版)》请在金锄头文库上搜索。
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=fopen(DestinationFilename,wb)=NULL)/文件打开错误return ERROR;if(*inp=fopen(SourceFilename,rb)=NULL)/