用哈夫曼树实现压缩解压

1、用哈夫曼树实现压缩解压程序是用 VC+6.0 编译完成的，可以完成对任意文件的压缩解 压（为方便寻找，压缩出的文件与待压缩文件在同一文件夹中） ，但 压缩文件夹还不可以， 另外该程序还能打印出压缩时所建立的哈夫曼 树及哈夫曼编码。源代码如下：#include <stdio.h>#include <string.h>#include <stdlib.h>#include <windows.h>typedef struct nodelong w;short p,l,r;htnode,*htnp;typedef struct huffman_codeu

2、nsigned 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 *

3、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 chars8);int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc,char* source_filename,long source_f

4、ilesize);int decompress(char *source_filename,char *obj_filename);void get_mini_huffmantree(FILE* in,short mini_ht2);int write_decompress_file(FILE *in,FILE* out,short mini_ht2,long bits_pos,long obj_filesize);int d_initial_files(char *source_filename,FILE *inp,char *obj_filename,FILE *outp);main()i

5、nt s;char filename10;system("color 3F");printf("*、iHprintf("菜单：*n");压缩-解压缩退出printf(" * 1. *n");printf("* 2. - *n");printf("* 0. *n");printf("*n");scanf("%d",&s);while(s!=0)getchar();switch(s)case 1:puts(" 请输入待压缩文件路径：

6、 ");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(&

7、quot;* 2. - *n");printf("* 0. *n");printf("*n");scanf("%d",&s);*inp,charint initial_files(char *source_filename,FILE *obj_filename,FILE *outp)if(fopen(source_filename,"rb")=NULL)return -1;if(obj_filename=NULL)if(obj_filename=(char*)malloc(256*sizeof(c

8、har)=NULL)return -1; create_filename(source_filename,obj_filename); if(strcmp(source_filename,obj_filename)=0)return -1;printf(" 待 压 缩 文 件 :%s, 压 缩 文件:sn",source_file name,obj_file name);if(*outp=fopen(obj_filename,"wb")=NULL)return -1;if(*inp=fopen(source_filename,"rb"

9、)=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");elsestrncpy(obj_filename,source_filename,temp-source_file

10、name);obj_filenametemp-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 hc256;htnode ht256*2-1;long frequency256,source_filesize,obj_filesiz

11、e=0;error_code=initial_files(source_filename,&in,obj_filename,&ou t);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(erro

12、r_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+=frequencyi*hci.len;obj_filesize=obj_filesize%8=0?obj_filesize/8:obj_filesize/8+1;for(i=0;i<256-1;i+)obj

13、_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_fi

14、le(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");doscanf("%s",&ch);switch(ch)case 'Y

15、9;:puts(" 以下是哈夫曼树： ");for(i=256;i<256*2-2;i+)if(hti.w>0)printf("%-10d%-10d%-10d%-10d%-10dn",i,hti.w,hti.p,hti.l,hti.r);puts(" 以下是哈夫曼编码： ");for(i=0;i<256;i+)if(frequencyi=0)i+;elseprintf("%dt",frequencyi);for( j=0;j<hci.len;j+)printf(" %d"

16、,hci.codestrj);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(hci.codestr);return 0;long frequency_data(FILE *in,long frequency)inti,read_len;unsigned ch

17、ar buf256;long filesize;for(i=0;i<256;i+)frequencyi=0;fseek(in,0L,SEEK_SET);read_len=256;while(read_len=256)read_len=fread(buf,1,256,in); for(i=0;i<read_len;i+)frequency*(buf+i)+;for(i=0,filesize=0;i<256;i+)filesize+=frequencyi;return filesize;int search_set(htnp ht,int n,int *s1, int *s2)i

18、nt i,x;long minValue = 1000000,min = 0;for(x=0;x<n;x+)if(htx.p=-1) break;for(i=0;i<n;i+)if(hti.p=-1 && hti.w < minValue)minValue = hti.w;min=i;*s1 = min;minValue = 1000000,min = 0;for(i=0;i<n;i+)if(hti.p=-1 && hti.w < minValue && i != *s1) minValue = hti.w;min=

19、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<n;i+)hti.w=wi;hti.p=hti.l=hti.r=-1;for(;i<m;i+)hti.w=hti.p=hti.l=hti.r=-1;for(i=n;i<m;i+)search_set(ht,i,&s1,&s2);hts1.p = hts2.p = i;hti.l = s1;h

20、ti.r = s2;hti.w = hts1.w + hts2.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<n;i+)for(p=i,codelen=0;p!=2*n-2;p=htpp.p,codelen+)codecodelen=(htphtpp.p.l=p?0:1);if(hci.c

21、odestr=(unsigned char*)malloc(codelen)*sizeof(unsigned char)=NULL)return -1;hci.len=codelen;for( j=0;j<codelen;j+)hci.codestr j=codecodelen-j-1;free(code);return 0;unsigned char chars_to_bits(const unsigned char chars8)int i;unsigned char bits=0;bits|=chars0;for(i=1;i<8;+i)bits<<=1;bits|

22、=charsi;return bits;int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc,char* source_filename,long source_filesize)intcharunsignedi,read_counter,write_counter,zip_head=0xFFFFFFFF;unsignedwrite_char_counter,code_char_counter,copy_char_counter,read_buf256,write_buf256,write_chars8,filename_s

23、ize=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,

24、out); for(i=256;i<256*2-1;i+)fwrite(&(hti.l),sizeof(hti.l),1,out);fwrite(&(hti.r),sizeof(hti.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<read_counter;i+)cur_hufcode=&hcread_bufi; code_char_coun

25、ter=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);writ

26、e_char_counter+=copy_char_counter; code_char_counter+=copy_char_counter;if(write_char_counter=8)write_char_counter=0;write_bufwrite_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)w

27、rite_char_counter=chars_to_bits(write_chars);fwrite(&write_char_counter,1,1,out);return 0;void get_mini_huffmantree(FILE* in,short mini_ht2) int i; for(i=0;i<256;i+) mini_hti0=mini_hti1=-1; fread(mini_hti,sizeof(short),2*(256-1),in);int write_decompress_file(FILEmini_ht2,long bits_pos,long ob

28、j_filesize)*in,FILE*out,shortlong cur_size;unsignedread_buf256,write_buf256,convert_bit;charunsigned intread_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)

29、fread(read_buf,1,256,in);read_counter=0;for(convert_bit=128;convert_bit!=0;convert_bit>>=1)cur_pos=(read_bufread_counter&convert_bit)=0?mini_htcur_pos0:mini_htcur_pos1);if(cur_pos<256)write_bufwrite_counter=(unsignedchar)cur_pos;if(+write_counter=256)fwrite(write_buf,1,256,out);write_co

30、unter=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_ht256*2-12;long obj_filesize;error_code=d_initial_files(source_filename,&in,obj_filename,& ou

31、t);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_f ilesize);if(error_code!=0)puts(" 解压缩失败！ ");return error_code;puts(" 解压缩完成 !");fclose(in);fclose(out)