用哈夫曼树实现压缩解压.doc

用哈夫曼树实现压缩解压程序是用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 chars8);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_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()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(请输入待压缩文件路径：);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,压缩文件:%sn,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_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_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;i256;i+) obj_filesize+=frequencyi*hci.len; obj_filesize=obj_filesize%8=0?obj_filesize/8:obj_filesize/8+1; for(i=0;i256-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);doscanf(%s,&ch);switch(ch)case Y: puts(以下是哈夫曼树：);for(i=256;i0)printf(%-10d%-10d%-10d%-10d%-10dn,i,hti.w,hti.p,hti.l,hti.r);puts(以下是哈夫曼编码：);for(i=0;i256;i+)if(frequencyi=0)i+;elseprintf(%dt,frequencyi);for(j=0;jhci.len;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;i256;i+) free(hci.codestr); return 0; long frequency_data(FILE *in,long frequency) int i,read_len; unsigned char buf256; long filesize; for(i=0;i256;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;iread_len;i+) frequency*(buf+i)+; for(i=0,filesize=0;i256;i+) filesize+=frequencyi; return filesize; int search_set(htnp ht,int n,int *s1, int *s2) int i,x; long minValue = 1000000,min = 0; for(x=0;xn;x+) if(htx.p=-1) break; for(i=0;in;i+) if(hti.p=-1 & hti.w minValue) minValue = hti.w; min=i; *s1 = min; minValue = 1000000,min = 0; for(i=0;in;i+) if(hti.p=-1 & hti.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 (n1) return -1; m=2*n-1; if (ht=NULL) return -1; for(i=0;in;i+) hti.w=wi;hti.p=hti.l=hti.r=-1; for(;im;i+) hti.w=hti.p=hti.l=hti.r=-1; for(i=n;im;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;in;i+) for(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;jcodelen;j+) hci.codestrj=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;i8;+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 char 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 char),1,out); fwrite(source_filename,sizeof(char),filename_size,out); fwrite(&source_filesize,sizeof(long),1,out); for(i=256;i256*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;ilen) 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_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) 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=1) cur_pos=(read_bufread_counter&convert_bit)=0?mini_htcur_pos0:mini_htcur_pos1); if(cur_pos256) 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_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,&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(