用哈夫曼树实现压缩解压

用哈夫曼树实现压缩解压

程序是用VC++6.0编译完成的，可以完成对任意文件的压缩解压（为方便寻找，压缩出的文件与待压缩文件在同一文件夹中），但压缩文件夹还不可以，另外该程序还能打印出压缩时所建立的哈夫曼树及哈夫曼编码。源代码如下：

#include

#include

#include

#include

typedef struct node

{

long w;

short p,l,r;

}htnode,*htnp;

typedef struct huffman_code

{

unsigned char len;

unsigned char *codestr;

}hufcode;

typedef char **huffmancode;

int initial_files(char *source_filename,FILE **inp,char *obj_filename,FILE **outp);

char *create_filename(char *source_filename,char* obj_filename);

int compress(char *source_filename,char *obj_filename);

long frequency_data(FILE *in,long fre[]);

int search_set(htnp ht,int n,int *s1, int *s2);

int create_hftree(long w[],int n,htnode ht[]);

int encode_hftree(htnp htp,int n,hufcode hc[]);

unsigned char chars_to_bits(const unsigned char chars[8]);

int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc[],char* source_filename,long source_filesize);

int decompress(char *source_filename,char *obj_filename);

void get_mini_huffmantree(FILE* in,short mini_ht[][2]);

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

int d_initial_files(char *source_filename,FILE **inp,char *obj_filename,FILE **outp);

main()

{

int s;

char filename[10];

system("color 3F");

printf(" ***************************************\n");

printf(" * 菜单： *\n");

printf(" * 1.——————压缩—————— *\n");

printf(" * 2.—————-解压缩—————- *\n");

printf(" * 0.——————退出—————— *\n");

printf(" ***************************************\n");

scanf("%d",&s);

while(s!=0)

{

getchar();

switch(s)

{

case 1:

puts("请输入待压缩文件路径：");

gets(filename);

compress(filename,NULL);

break;

case 2:

puts("请输入待解压文件路径：");

gets(filename);

decompress(filename,NULL);

break;

default :

printf("指令错误！请重新输入指令：\n");

}

puts(" ");

printf(" ***************************************\n");

printf(" * 菜单： *\n");

printf(" * 1.——————压缩—————— *\n");

printf(" * 2.—————-解压缩—————- *\n");

printf(" * 0.——————退出—————— *\n");

printf(" ***************************************\n");

scanf("%d",&s);

}

}

int initial_files(char *source_filename,FILE **inp,char *obj_filename,FILE **outp)

{

if(fopen(source_filename,"rb")==NULL)

{

return -1;

}

if(obj_filename==NULL)

{

if((obj_filename=(char*)malloc(256*sizeof(char)))==NULL)

{

return -1;

}

create_filename(source_filename,obj_filename);

}

if(strcmp(source_filename,obj_filename)==0)

{

return -1;

}

printf("待压缩文件:%s,压缩文件:%s\n",source_filename,obj_filename);

if((*outp=fopen(obj_filename,"wb"))==NULL)

{

return -1;

}

if((*inp=fopen(source_filename,"rb"))==NULL)

{

return -1;

}

free(obj_filename);

return 0;

}

char *create_filename(char *source_filename,char* obj_filename)

{

char *temp;

if((temp=strrchr(source_filename,'.'))==NULL)

{

strcpy(obj_filename,source_filename);

strcat(obj_filename,".zip");

}

else

{

strncpy(obj_filename,source_filename,temp-source_filename);

obj_filename[temp-source_filename]='\0';

strcat(obj_filename,".zip");

}

return obj_filename;

}

int compress(char *source_filename,char *obj_filename)

{

FILE *in,*out;

char ch;

int error_code,i,j;

float compress_rate;

hufcode hc[256];

htnode ht[256*2-1];

long frequency[256],source_filesize,obj_filesize=0;

error_code=initial_files(source_filename,&in,obj_filename,&out);

if(error_code!=0)

{

puts("文件打开失败！请重新输入文件路径：");

return error_code;

}

source_filesize=frequency_data(in,frequency);

printf("文件大小 %ld 字节\n",source_filesize);

error_code=create_hftree(frequency,256,ht);

if(error_code!=0)

{

puts("建立哈夫曼树失败！");

return error_code;

}

error_code=encode_hftree(ht,256,hc);

if(error_code!=0)

{

puts("建立哈夫曼编码失败！");

return error_code;

}

for(i=0;i<256;i++)

obj_filesize+=frequency[i]*hc[i].len;

obj_filesize=obj_filesize%8==0?obj_filesize/8:obj_filesize/8+1;

for(i=0;i<256-1;i++)

obj_filesize+=2*sizeof(short);

obj_filesize+=strlen(source_filename)+1;

obj_filesize+=sizeof(long);

obj_filesize+=sizeof(unsigned int);

compress_rate=(float)obj_filesize/source_filesize;

printf("压缩文件大小:%ld字节,压缩比例:%.2lf%%\n",obj_filesize,compress_rate*100);

error_code=write_compress_file(in,out,ht,hc,source_filename,source_filesize);

if(error_code!=0)

{

puts("写入文件失败！");

return error_code;

}

puts("压缩完成!");

puts(" ");

puts("是否打印该文件中字符对应的huffman树及编码？");

puts(" Please input Y OR N");

do{

scanf("%s",&ch);

switch(ch)

{

case 'Y':

puts("以下是哈夫曼树：");

for(i=256;i<256*2-2;i++)

{

if(ht[i].w>0)

printf("%-10d%-10d%-10d%-10d%-10d\n",i,ht[i].w,ht[i].p,ht[i].l,ht[i].r);

}

puts("以下是哈夫曼编码：");

for(i=0;i<256;i++)

{

if(frequency[i]==0)

i++;

else

{

printf("%d\t",frequency[i]);

for(j=0;j

printf(" %d",hc[i].codestr[j]);

printf("\n");

}

}

break;

case 'N': break;

default :

printf("指令错误！请重新输入指令：\n");

}

}while(ch!='Y'&&ch!='N');

fclose(in);

fclose(out);

for(i=0;i<256;i++)

{

free(hc[i].codestr);

}

return 0;

}

long frequency_data(FILE *in,long frequency[])

{

int i,read_len;

unsigned char buf[256];

long filesize;

for(i=0;i<256;i++)

{

frequency[i]=0;

}

fseek(in,0L,SEEK_SET);

read_len=256;

while(read_len==256)

{

read_len=fread(buf,1,256,in);

for(i=0;i

{

frequency[*(buf+i)]++;

}

}

for(i=0,filesize=0;i<256;i++)

{

filesize+=frequency[i];

}

return filesize;

}

int search_set(htnp ht,int n,int *s1, int *s2)

{

int i,x;

long minValue = 1000000,min = 0;

for(x=0;x

{

if(ht[x].p==-1) break;

}

for(i=0;i

{

if(ht[i].p==-1 && ht[i].w < minValue)

{

minValue = ht[i].w;

min=i;

}

}

*s1 = min;

minValue = 1000000,min = 0;

for(i=0;i

{

if(ht[i].p==-1 && ht[i].w < minValue && i != *s1)

{

minValue = ht[i].w;

min=i;

}

}

*s2 = min;

return 1;

}

int create_hftree(long w[],int n,htnode ht[])

{

int m,i,s1,s2;

if (n<1) return -1;

m=2*n-1;

if (ht==NULL) return -1;

for(i=0;i

{

ht[i].w=w[i];

ht[i].p=ht[i].l=ht[i].r=-1;

}

for(;i

{

ht[i].w=ht[i].p=ht[i].l=ht[i].r=-1;

}

for(i=n;i

{

search_set(ht,i,&s1,&s2);

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 0;

}

int encode_hftree(htnp htp,int n,hufcode hc[])

{

int i,j,p,codelen;

unsigned char *code=(unsigned char*)malloc(n*sizeof(unsigned char));

if (code==NULL) return -1;

for(i=0;i

{

for(p=i,codelen=0;p!=2*n-2;p=htp[p].p,codelen++)

{

code[codelen]=(htp[htp[p].p].l==p?0:1);

}

if((hc[i].codestr=(unsigned char *)malloc((codelen)*sizeof(unsigned char)))==NULL)

{

return -1;

}

hc[i].len=codelen;

for(j=0;j

{

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

}

}

free(code);

return 0;

}

unsigned char chars_to_bits(const unsigned char chars[8])

{

int i;

unsigned char bits=0;

bits|=chars[0];

for(i=1;i<8;++i)

{

bits<<=1;

bits|=chars[i];

}

return bits;

}

int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc[],char* source_filename,long source_filesize)

{

unsigned int i,read_counter,write_counter,zip_head=0xFFFFFFFF;

unsigned char write_char_counter,code_char_counter,copy_char_counter,

read_buf[256],write_buf[256],write_chars[8],filename_size=strlen(source_filename);

hufcode *cur_hufcode;

fseek(in,0L,SEEK_SET);

fseek(out,0L,SEEK_SET);

fwrite(&zip_head,sizeof(unsigned int),1,out);

fwrite(&filename_size,sizeof(unsigned char),1,out);

fwrite(source_filename,sizeof(char),filename_size,out);

fwrite(&source_filesize,sizeof(long),1,out);

for(i=256;i<256*2-1;i++)

{

fwrite(&(ht[i].l),sizeof(ht[i].l),1,out);

fwrite(&(ht[i].r),sizeof(ht[i].r),1,out);

}

write_counter=write_char_counter=0;

read_counter=256;

while(read_counter==256)

{

read_counter=fread(read_buf,1,256,in);

for(i=0;i

{

cur_hufcode=&hc[read_buf[i]];

code_char_counter=0;

while(code_char_counter!=cur_hufcode->len)

{

copy_char_counter= (8-write_char_counter > cur_hufcode->len-code_char_counter ?

cur_hufcode->len-code_char_counter : 8-write_char_counter);

memcpy(write_chars+write_char_counter,cur_hufcode->codestr+code_char_counter,copy_char_counter);

write_char_counter+=copy_char_counter;

code_char_counter+=copy_char_counter;

if(write_char_counter==8)

{

write_char_counter=0;

write_buf[write_counter++]=chars_to_bits(write_chars);

if(write_counter==256)

{

fwrite(write_buf,1,256,out);

write_counter=0;

}

}

}

}

}

fwrite(write_buf,1,write_counter,out);

if(write_char_counter!=0)

{

write_char_counter=chars_to_bits(write_chars);

fwrite(&write_char_counter,1,1,out);

}

return 0;

}

void get_mini_huffmantree(FILE* in,short mini_ht[][2])

{

int i;

for(i=0;i<256;i++)

{

mini_ht[i][0]=mini_ht[i][1]=-1;

}

fread(mini_ht[i],sizeof(short),2*(256-1),in);

}

int write_decompress_file(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,long obj_filesize)

{

long cur_size;

unsigned char read_buf[256],write_buf[256],convert_bit;

unsigned int read_counter,write_counter,cur_pos;

fseek(in,bits_pos,SEEK_SET);

fseek(out,0L,SEEK_SET);

read_counter=256-1;

cur_size=write_counter=0;

cur_pos=256*2-2;

while(cur_size!=obj_filesize)

{

if(++read_counter==256)

{

fread(read_buf,1,256,in);

read_counter=0;

}

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

{

cur_pos=((read_buf[read_counter]&convert_bit)==0?mini_ht[cur_pos][0]:mini_ht[cur_pos][1]);

if(cur_pos<256)

{

write_buf[write_counter]=(unsigned char)cur_pos;

if(++write_counter==256)

{

fwrite(write_buf,1,256,out);

write_counter=0;

}

cur_pos=256*2-2;

if(++cur_size==obj_filesize)

{

break;

}

}

}

}

fwrite(write_buf,1,write_counter,out);

return 0;

}

int decompress(char *source_filename,char *obj_filename)

{

int error_code;

FILE *in,*out;

short mini_ht[256*2-1][2];

long obj_filesize;

error_code=d_initial_files(source_filename,&in,obj_filename,&out);

if(error_code!=0)

{

puts("打开文件失败！请重新输入文件路径：");

return error_code;

}

fread(&obj_filesize,sizeof(long),1,in);

printf("解压文件大小:%ld字节\n",obj_filesize);

get_mini_huffmantree(in,mini_ht);

error_code=write_decompress_file(in,out,mini_ht,ftell(in),obj_filesize);

if(error_code!=0)

{

puts("解压缩失败！");

return error_code;

}

puts("解压缩完成!");

fclose(in);

fclose(out);

return 0;

}

int d_initial_files(char *source_filename,FILE **inp,char *obj_filename,FILE **outp)

{

unsigned int zip_head;

unsigned char filename_size;

if ((*inp=fopen(source_filename,"rb"))==NULL)

{

return -1;

}

printf("待解压缩文件:%s,",source_filename);

fread(&zip_head,sizeof(unsigned int),1,*inp);

if(zip_head!=0xFFFFFFFF)

{

return -1;

}

if(obj_filename==NULL)

{

if((obj_filename=(char*)malloc(256*sizeof(char)))==NULL)

{

return -1;

}

fread(&filename_size,sizeof(unsigned char),1,*inp);

fread(obj_filename,sizeof(char),filename_size,*inp);

obj_filename[filename_size]='\0';

}

else

{

fread(&filename_size,sizeof(unsigned char),1,*inp);

fseek(*inp,filename_size,SEEK_CUR);

}

printf("解压缩文件:%s\n",obj_filename);

if((*outp=fopen(obj_filename,"wb"))==NULL)

{

return -1;

}

free(obj_filename);

return 0;

}

运行结果：

待压缩文件位置：

运行结果：

压缩出的文件：

本文来源：https://www.2haoxitong.net/k/doc/8422df22dd36a32d737581a5.html