数据结构文件压缩

数据结构实验报告

实验名称：文件压缩 实验类型：综合性试验 班级：20112111 学号：2011211107 姓名：冯若航

实验日期：2003.6.19 下午4:00

1.问题描述

文件压缩 ①基本要求

哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。

 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，

并将该哈夫曼树保存到文件HufTree.dat中。

 根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并

将字符编码保存到HufCode.txt文件中。

 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。  解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。 2.数据结构设计

此类问题，应设计文件的数据结构。

* * * * * *

赫夫曼树节点的数据结构 typedef struct node {

long w;

//权

//父亲，左孩子，右孩子 //霍夫曼树的结点

short p,l,r; 4 1 4

压缩头标记 文件名长度 文件名 源文件长度 huffman树 文件内容

ns 1020

1021~EOF

}HTNODE,*HTNP;

.

精品文档

赫夫曼编码数组元素的数据结构设计 typedef struct huffman_code {

BYTE len;

//长度 //字符串

BYTE *codestr;

}HFCODE; //霍夫曼编码数组元素

3.算法设计 源代码

#define _CRT_SECURE_NO_DEPRECATE #include #include #include

typedef unsigned int UINT; typedef unsigned char BYTE; typedef struct node {

long w;

//权

//父亲，左孩子，右孩子 //霍夫曼树的结点

short p,l,r;

}HTNODE,*HTNP; {

BYTE len;

typedef struct huffman_code

//长度 //字符串

BYTE *codestr;

}HFCODE; //霍夫曼编码数组元素

#define OK 1 #define ERROR -1 #define UNUSE -1

//未链接节点标志

#define CHAR_BITS 8 #define INT_BITS 32 #define BUFFERSIZE 256

//一个字符中的位数 //一个整型中的位数 //霍夫曼编码个数

//缓冲区大小大小

#define HUFCODE_SIZE 256

#define UINTSIZE sizeof(UINT) #define BYTESIZE sizeof(BYTE) #define TAG_ZIGHEAD 0xFFFFFFFF #define MAX_FILENAME 512 //函数声明 //压缩模块

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 chars[CHAR_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_ht[][2]);

//从待解压缩文件中读取huffman树

//写解压缩文件

//报错

int WriteDeZipFiles(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,long Dst_Filesize);

//函数定义 //函数实现 //压缩

int Compress(char *SourceFilename,char *DestinationFilename) {

//处理各个字符的频率，并输出原始文件长度 //处理待压缩与压缩文件文件

Initializing(SourceFilename,&in,DestinationFilename,&out); puts(\"Loading Files...\"); FILE *in,*out; int i;

//输入输出流 //计数变量

void ErrorReport(int error_code);

float Compress_rate; //存放压缩率

//存放256个字符的huffman编码

HFCODE hc[HUFCODE_SIZE];

HTNODE ht[HUFCODE_SIZE*2-1]; //256个字符的huffman树需要2*256-1=511个节点。 long frequency[HUFCODE_SIZE ],source_filesize,Dst_Filesize=0;//字符频率数组，源文件，

目标文件。

.

精品文档

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;i{//计算位的个数,计算每个字符的频数与其编码长度乘积之和

Dst_Filesize+=frequency[i]*hc[i].len; }//将文件主体部分的位个数转换为字节个数;

Dst_Filesize=Dst_Filesize%8==0?Dst_Filesize/8:Dst_Filesize/8+1; for(i=0;iDst_Filesize+=strlen(SourceFilename)+1; Dst_Filesize+=sizeof(long); Dst_Filesize+=UINTSIZE;

//源文件名占用空间

//源文件名长度信息占

Dst_Filesize+=2*sizeof(short);

用空间

//文件头长度 //压缩率

Compress_rate=(float)Dst_Filesize/source_filesize;

puts(\"Coding Successfully.Now producing zip files...\"); printf(\"Compressed File Size:%ld Byte,radiation: %%%.2lf //生成压缩文件

WriteZipFiles(in,out,ht,hc,SourceFilename,source_filesize); puts(\"Compress Complete!\"); //擦屁股 fclose(in);

fclose(out);//关闭文件 for(i=0;ireturn OK;

free(hc[i].codestr);

\\n\",Dst_Filesize,Compress_rate*100);

.

精品文档

}

int Initializing(char *SourceFilename,FILE **inp,char *DestinationFilename,FILE **outp) { }

long AnalysisFiles(FILE *in,long frequency[]) { 加

for(i=0;ifseek(in,0L,SEEK_SET); read_len=BUFFERSIZE; { }

for(i=0,filesize=0;ifilesize+=frequency[i];

//计算文件长度，计算方法是把所有字符的频数相

read_len=fread(buf,1,BUFFERSIZE,in); for(i=0;ifrequency[*(buf+i)]++;

//统计字频

//将文件定位符指向文件开头 //设置读入长度=缓冲区长度

//每当读取字符长度达到缓冲区长度时

frequency[i]=0;

//初始化所有字符频率为0

int i,read_len; BYTE buf[BUFFERSIZE]; long filesize;

//缓冲区 //文件总长

return OK;

if((*outp=fopen(DestinationFilename,\"wb\"))==NULL) {//文件打开错误 }

if((*inp=fopen(SourceFilename,\"rb\"))==NULL) {//文件打开错误 }

return ERROR; return ERROR;

if(strcmp(SourceFilename,DestinationFilename)==0) {//重名判断 }

printf(\"Source File:%s,Destination File:%s\\n\",SourceFilename,DestinationFilename);

return ERROR;

while(read_len==BUFFERSIZE)

.

精品文档

}

}

return filesize;

int Search(HTNP ht,int n) { }

int CreateHuffmanTree(long w[],int n,HTNODE ht[]) {

int m,i,s1,s2;

if (n<1) return ERROR; m=2*n-1;

//霍夫曼树节点总数=叶子数*2-1

if (ht==NULL) return ERROR; for(i=0;ifor(;ifor(i=n;i//循环至m-n个分支节点全部被使

ht[i].w=ht[i].p=ht[i].l=ht[i].r=UNUSE;

//初始化分支节点

ht[i].w=w[i],ht[i].p=ht[i].l=ht[i].r=UNUSE; //初始化叶子节点 int i,x;

for(x=0;xfor(i=x;iht[x].p=-2; return x;

//将叶子节点占用

if(ht[i].p==UNUSE&&ht[i].wx=i;

//找权值最小的叶子节点

if(ht[x].p==UNUSE) break; //找到第一个没有使用的叶子节点，跳出

用完为止

s1=Search(ht,i); s2=Search(ht,i);

//找到权值最小的两个节点，这里通过//设置父节点 //设置孩子

//设置权为两个孩子权之和

两次调用寻找最小权值的函数search解决问题

ht[s1].p=ht[s2].p=i; ht[i].l=s1,ht[i].r=s2;

ht[i].w=ht[s1].w+ht[s2].w;

.

精品文档

}

return OK;

int HuffmanTreeCoding(HTNP htp,int n,HFCODE hc[]) { 量 }

BYTE Char2Bit(const BYTE chars[CHAR_BITS]) { }

int WriteZipFiles(FILE *in,FILE *out,HTNP ht,HFCODE hc[],char* SourceFilename,long

bits|=chars[0];

for(i=1;ireturn bits;

bits<<=1;

//左移或实现

bits|=chars[i]; int i; BYTE bits=0; for(i=0;i{//从当前节点到根节点逆向求huffman编码，遍历所有叶子节点。 }

free(code);//擦屁股 return OK;

for(p=i,codelen=0;p!=2*n-2;p=htp[p].p,codelen++) {//循环到根节点为止

code[codelen]=(htp[htp[p].p].l==p?0:1);//第i位编码：p节点如果是其父亲的：左

BYTE *code=(BYTE*)malloc(n*BYTESIZE);

//临时字符数组，为每一个字符的编码

申请一个字节的空间

int i,j,p,codelen;

//codelen:临时字符数组长度变

孩子:0;右孩子:1

}

if((hc[i].codestr=(BYTE *)malloc((codelen)*BYTESIZE))==NULL) { }

hc[i].len=codelen; { }

hc[i].codestr[j]=code[codelen-j-1];

//反转（因为原来是逆的）

//该字符编码的码长

for(j=0;jreturn ERROR;

//分配叶子节点huffman编码的空间，长

度为

.

精品文档

source_filesize) {

//预处理

fseek(in,0L,SEEK_SET);

fseek(out,0L,SEEK_SET);

//定位读文件到文件开始处

//定位写文件到文件开始处

UINT i,Read_Counter,Write_Counter,zip_head=TAG_ZIGHEAD;

//读缓存计数器,写缓存计数器,压缩文件头标

//

//写字符计数器,huffman码字符计数器,复制字符计数器

BYTE write_char_counter,code_char_counter,copy_char_counter;

BYTE read_buf[BUFFERSIZE],write_buf[BUFFERSIZE],write_chars[CHAR_BITS]; BYTE filename_size=strlen(SourceFilename);

//文件名长度

//当前数据的huffman编码指针 HFCODE *Cur_HuffCode;

读缓存,写缓存,转换字符数组,

fwrite(&zip_head,UINTSIZE,1,out);

//写入文件头标示符 //写入源文件名长度 //写入源文件名

fwrite(&filename_size,BYTESIZE,1,out);

fwrite(SourceFilename,sizeof(char),filename_size,out); fwrite(&source_filesize,sizeof(long),1,out); //写入源文件长度

for(i=HUFCODE_SIZE;i//写正文

Write_Counter=write_char_counter=0;

//写缓冲计数器以及写字符计数器清0

Read_Counter=BUFFERSIZE;

//置读缓存字符数

//写huffman树的左右孩子(前HUFCODE_SIZE个节点无孩子，不写)

fwrite(&(ht[i].l),sizeof(ht[i].l),1,out);//写入左孩子 fwrite(&(ht[i].r),sizeof(ht[i].r),1,out);//写入右孩子

//当读入的缓存字符数不等于缓存时，文件读完，退出循环 while(Read_Counter==BUFFERSIZE) {

Read_Counter=fread(read_buf,1,BUFFERSIZE,in); //读入大小为BUFFSIZE的数据到读缓存

.

精品文档

者

//为每个缓存的数据找huffman编码 for(i=0;iCur_HuffCode=&hc[read_buf[i]]; code_char_counter=0;

//当前数据的huffman编码位置

//当前数据huffman编码字符的计数器清0

//当huffman编码字符的计数器等于码长时，转换完毕退出 while(code_char_counter!=Cur_HuffCode->len)

{ //获取本次复制字符的长度为 可用写字符长度与可用huffman编码长度中的较小

copy_char_counter= (CHAR_BITS-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_ }

fwrite(write_buf,1,Write_Counter,out);//写缓存中剩余数据输出到文件,擦屁股 //当写字符数组中还有字符未转换 if(write_char_counter!=0) {

}

}

write_char_counter+=copy_char_counter; code_char_counter+=copy_char_counter; //当写字符计算器满=8时

if(write_char_counter==CHAR_BITS) { }

write_char_counter=0;//写字符计数器清0 //当写缓存满时

write_buf[Write_Counter++]=Char2Bit(write_chars); if(Write_Counter==BUFFERSIZE) { }

fwrite(write_buf,1,BUFFERSIZE,out);//输出到文件 Write_Counter=0;//写缓存清0

char_counter);

//写字符计数器增加 //编码字符计数器增加

//转化写字符为二进制数并存入写缓存

.

精品文档

}

}

write_char_counter=Char2Bit(write_chars);//转化为二级制数据 fwrite(&write_char_counter,1,1,out);//输出到文件

return OK;

//解压缩

int DeCompress(char *SourceFilename,char *DestinationFilename) { }

int Initializing_Dezip(char *SourceFilename,FILE **inp,char *DestinationFilename,FILE **outp) {

UINT zip_head; BYTE filename_size;

char temp_filename[MAX_FILENAME];

//处理源文件

printf(\"Source Files:%s,\",SourceFilename); if ((*inp=fopen(SourceFilename,\"rb\"))==NULL) {

Initializing_Dezip(SourceFilename,&in,DestinationFilename,&out); puts(\"File open Successfully...\"); fread(&Dst_Filesize,sizeof(long),1,in);

//

//初始

化文件处理环境

FILE *in,*out;

//

定义输入输出流

short mini_ht[HUFCODE_SIZE*2-1][2]; long Dst_Filesize;

读取解压缩文件长度

printf(\"Expected Length: %ld\\n\",Dst_Filesize); puts(\"Establishing HuffmanTree...\"); ReadHuffmanTree(in,mini_ht);

//

生成mini的huffmantree

puts(\"Rebuild Successfully.Now Decompressing...\"); WriteDeZipFiles(in,out,mini_ht,ftell(in),Dst_Filesize); puts(\"Decompress Complete!\");

//擦屁股 fclose(in); fclose(out); return OK;

//

解码压缩文件并生成解压缩文件

.

精品文档

}

}

return ERROR;//不能读文件

//读取源文件头,如果读入的文件头与常量不符，报错退出。 fread(&zip_head,UINTSIZE,1,*inp); if(zip_head!=TAG_ZIGHEAD) { }

//处理解压缩文件名

if(DestinationFilename==NULL)//如果目标文件名未分配 { } else { }

printf(\"Decompress Files:%s\\n\",DestinationFilename); if((*outp=fopen(DestinationFilename,\"wb\"))==NULL) { }

return OK;

return ERROR;//不能写文件

fread(&filename_size,BYTESIZE,1,*inp);

fseek(*inp,filename_size,SEEK_CUR);//若分配了，直接跳过文件名信息 DestinationFilename = temp_filename; fread(&filename_size,BYTESIZE,1,*inp);

//得到目标文件名

return ERROR;//非法的文件头

长度

fread(DestinationFilename,sizeof(char),filename_size,*inp); //得到目标文件名 DestinationFilename[filename_size]='\\0';

//添加结尾字符

void ReadHuffmanTree(FILE* in,short mini_ht[][2]) { }

int WriteDeZipFiles(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,long Dst_Filesize) {

long cur_size;

BYTE read_buf[BUFFERSIZE],write_buf[BUFFERSIZE],convert_bit; UINT Read_Counter,Write_Counter,cur_pos; int i;

for(i=0;ifread(mini_ht[i],sizeof(short),2*(HUFCODE_SIZE-1),in);//得到非叶子节点的孩子信息

mini_ht[i][0]=mini_ht[i][1]=UNUSE;//叶子节点无孩子

.

精品文档

}

void ErrorReport(int error_code) { }

printf(\"Error\");

fseek(in,bits_pos,SEEK_SET);//定位到写文件压缩码开始处 fseek(out,0L,SEEK_SET);//定位到写文件头部 //解码开始

Read_Counter=BUFFERSIZE-1;//置写缓存计数器

cur_size=Write_Counter=0;//当前写入文件长度与写缓存计数器为0 cur_pos=HUFCODE_SIZE*2-2;//当前huffman节点为根节点 //如果写入文件长度达到目标文件长度，文件写入完毕，退出 while(cur_size!=Dst_Filesize) { //若读缓存计数器满

cur_pos=((read_buf[Read_Counter]&convert_bit)==0?mini_ht[cur_pos][0]:mini_ht[cur_po }

fwrite(write_buf,1,Write_Counter,out);//将写缓存中未输出的数据输出 return OK;

}

if(cur_poswrite_buf[Write_Counter]=(BYTE)cur_pos;//缓存一个byte if(++Write_Counter==BUFFERSIZE)//如果当前输出缓存满 { }

cur_pos=HUFCODE_SIZE*2-2;//当前节点重置为最后根节点 if(++cur_size==Dst_Filesize) { }

break;//如果当前写入文件长度到达预定值，跳出 fwrite(write_buf,1,BUFFERSIZE,out);//输出到文件 Write_Counter=0;//输入缓存计数器清0

if(++Read_Counter==BUFFERSIZE) { }

//一次循环处理8位，即1字节

for(convert_bit=128;convert_bit!=0;convert_bit>>=1) {

fread(read_buf,1,BUFFERSIZE,in);//读入到读缓存 Read_Counter=0;//读缓存计数器清0

s][1]);//按位查找huffmantree节点，0左，1右

.

精品文档

int main() { }

return OK; case 'c': }

{//压缩

printf(\"Input Source file: \"); gets(SRC); fflush(stdin);

printf(\"\\nInput destination file：\"); gets(DST); fflush(stdin); Compress(SRC,DST); system(\"pause\");

char SRC[MAX_FILENAME],DST[MAX_FILENAME],choice='\\0'; printf(\"c for Compress,d for Decompress: \"); scanf(\"%c\",&choice); fflush(stdin); switch(choice) {

};break; {//解压

printf(\"Input Source file: \"); gets(SRC); fflush(stdin);

printf(\"Input destination file：\"); gets(DST); fflush(stdin); DeCompress(SRC,DST); system(\"pause\");

case 'd':

}break;

default:{ErrorReport(ERROR);}break;

四．界面设计

本实验提供基本的输入输出提示，包括压缩率的计算。

五．测试与分析

.

精品文档

压缩过程：

解压缩过程：

实际测试中压缩率达到了惊人的45%。对于某些文件。实际测试这是一个非常实用有效的工具。 六．实验收获及思考 收获：

确实是一个很有挑战的问题。关于文件写入部分有部分借鉴参考之处。

本代码的编写经历对知识的巩固有着巨大的作用。是一次很好的锻炼与实践。

.