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