用哈夫曼树实现压缩解压

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

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

4、_filesize);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(

5、)int s;char filename10;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(&qu

6、ot;请输入待压缩文件路径：");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")

7、;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=(cha

8、r*)malloc(256*sizeof(char)=NULL) return -1; create_filename(source_filename,obj_filename); if(strcmp(source_filename,obj_filename)=0) return -1; printf("待压缩文件:%s,压缩文件:%sn",source_filename,obj_filename); if(*outp=fopen(obj_filename,"wb")=NULL) return -1; if(*inp=fopen(source_filen

9、ame,"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,sou

10、rce_filename,temp-source_filename); 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 fre

11、quency256,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=crea

12、te_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+=frequencyi*hci.len; obj_filesize=obj_filesize%8=0?obj_filesize/8:o

13、bj_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*1

14、00); 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");doscanf("%s",&a

15、mp;ch);switch(ch)case 'Y': 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.le

16、n;j+)printf(" %d",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 freq

17、uency) int i,read_len; unsigned char 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; i

18、nt search_set(htnp ht,int n,int *s1, int *s2) int 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.

19、w < minValue && i != *s1) minValue = hti.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<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&

20、lt;m;i+) search_set(ht,i,&s1,&s2); hts1.p = hts2.p = i; hti.l = s1;hti.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+) f

21、or(p=i,codelen=0;p!=2*n-2;p=htpp.p,codelen+) codecodelen=(htphtpp.p.l=p?0:1); if(hci.codestr=(unsigned char *)malloc(codelen)*sizeof(unsigned char)=NULL) return -1; hci.len=codelen; for(j=0;j<codelen;j+) hci.codestrj=codecodelen-j-1; free(code); return 0; unsigned char chars_to_bits(const unsigne

22、d char chars8) int i; unsigned char bits=0; bits|=chars0; for(i=1;i<8;+i) bits<<=1; bits|=charsi; 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 ch

23、ar write_char_counter,code_char_counter,copy_char_counter, read_buf256,write_buf256,write_chars8,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 cha

24、r),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(&(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=

25、256) read_counter=fread(read_buf,1,256,in); for(i=0;i<read_counter;i+) cur_hufcode=&hcread_bufi; 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-w

26、rite_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_bufwrite_counter+=chars_to_bits(write_chars); if(w

27、rite_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_ht2) int i; for(i=0;i<25

28、6;i+) mini_hti0=mini_hti1=-1; fread(mini_hti,sizeof(short),2*(256-1),in); int write_decompress_file(FILE *in,FILE* out,short mini_ht2,long bits_pos,long obj_filesize) long cur_size; unsigned char read_buf256,write_buf256,convert_bit; unsigned int read_counter,write_counter,cur_pos; fseek(in,bits_pos

29、,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_bufread_counter&convert_bit)=0?

30、mini_htcur_pos0:mini_htcur_pos1); if(cur_pos<256) write_bufwrite_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_fil

31、ename,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,&out); if(error_code!=0) puts("打开文件失败！请重新输入文件路径："); return error_code; fread(&obj_filesize,sizeof(long),1,in); printf("解压文件大小:%ld字节n",obj_filesize); get_mini_huffma