数据结构——哈夫曼编码 完整代码

/*** *huffmanCode.cpp - 压缩软件的代码文件 * * *题目：压缩软件的实现 * *班级：软件1班 * *姓名：陈润资 * *学号：200801001 * ****/ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> #include "huffmanCode.h" /*------------------------------------------------------------ 操作目的： 字符串匹配 初始条件： 两个字符串 操作结果： 是否匹配成功 函数参数： const char *p 压缩文件的字符串 char *q 码表 返回值： 无 ------------------------------------------------------------*/ bool isPartof(const char *p,char *q)//判断q是否是p的一部分 { int i=0; while(*(p+i)!='\0'&&*(p+i)==*(q+i)){ i++; } if(*(q+i)=='\0') return true; else return false; } /*------------------------------------------------------------ 操作目的： 字符串拷贝 初始条件： 两个已经存在的字符串 操作结果： 将字符串q拷贝到字符串*p中 函数参数： char **p *p为拷贝的目的串 char *q q为被拷贝的串 返回值： 无 -------------------------------------------------------------*/ void strcpy(char **p,char *q) { int i=0; do{ *(*p+i)=*(q+i); i++; }while(*(q+i-1)!='\0'); } /*------------------------------------------------------------ 操作目的： 字符串连接 初始条件： 两个已经存在的字符串 操作结果： 将字符串q连接到字符串*p的后边 函数参数： char **p *p为连接的目的串 char *q q为被连接的串 返回值： 无 -------------------------------------------------------------*/ void strcat_chen(char **p,char *q) { int i=0; while(*(*p+i)!='\0'){ i++; } int j=0; do{ *(*p+i)=*(q+j); i++; j++; }while(*(q+j-1)!='\0'); } /*------------------------------------------------------------ 操作目的： 选择双亲值为0且权值最小的两个节点 初始条件： 数组A已存在 操作结果： 得到这两个节点的下标 函数参数： HuffmanTree ht //待选择的树 int n //选择的范围 int *s1 //保存两个最小权值节点的下标 int *s2 返回值： 无 ------------------------------------------------------------*/ void select(HuffmanTree ht,int n, int *s1, int *s2) { *s1=0; *s2=0; for(int i=1;i<=n;i++){ HTNode *p=ht; ht->weight=62531;//让数组空间的第一个节点(没用的)的权值很大； if((p+*s1)->weight>(p+*s2)->weight){//总是让检测值和比较大的那个比较； if((p+i)->parent==0&&(p+i)->weight<(p+*s1)->weight) *s1=i; } else{ if((p+i)->parent==0&&(p+i)->weight<(p+*s2)->weight) *s2=i; } } } /*------------------------------------------------------------ 操作目的： huffman编码 初始条件： 已知各个节点的权值 操作结果： 得到一棵Huffman树，以及各个叶子节点的huffman编码 函数参数： HuffmanTree *ht //分配的存储huffman节点的首地址 HuffmanCode *hc //指向各个编码的首地址 int *w //各个待编码节点的权值 返回值： 无 ------------------------------------------------------------*/ void HuffmanCoding(HuffmanTree *ht,HufCode_pointer *hc, NodeWeight *w) { int n=w->len; if(n<=1) return ; int m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//下标为0的空间没有用。 HuffmanTree p; int i=0; int s1,s2; for(p=*ht+1,i=1;i<=n;i++,p++){ p->weight=(w+i-1)->weight; p->ch=(w+i-1)->ch; p->parent=0; p->lch=0; p->rch=0; }; for(;i<=m;i++){ p->parent=0; p->lch=0; p->rch=0; p->weight=0; p++; }; for(i=n+1;i<=m;i++){ select(*ht,i-1,&s1,&s2); (*ht+s1)->parent=i; (*ht+s2)->parent=i; (*ht+i)->lch=s1; (*ht+i)->rch=s2; (*ht+i)->weight=(*ht+s1)->weight+(*ht+s2)->weight; }; *hc = (HufCode_pointer)malloc((n+1)*sizeof(HuffmanCode)); char * cd; cd=(char *)malloc(n*sizeof(char)); *(cd+n-1)='\0'; for(i=1;i<=n;i++){ int start=n-1; int c=i; int f=0; for(f=(*ht+i)->parent;f!=0;c=f,f=(*ht+f)->parent) if((*ht+f)->lch==c){ start--; *(cd+start)='0'; } else if((*ht+f)->rch==c){ start--; *(cd+start)='1'; }; (*hc+i)->ch_pointer=(char*)malloc((n-start)*sizeof(char)); //保证实际参数cd中的无效内容不会被传入strcpy函数； strcpy(&(*hc+i)->ch_pointer,cd+start); //加上数据信息； (*hc+i)->ch=(*ht+i)->ch; }; free(cd); } void zip(){//压缩 HuffmanTree htree; //hufman树 HufCode_pointer hcode; //码表 NodeWeight * ww=NULL; int flength; unsigned char c=0; struct char_weight { unsigned char b; //记录字符在数组中的位置 long count; //字符出现频率（权值） } char_weight[512]={{'a',0}}; char filename[50],outputfile[50],outcodefile[50]; FILE *ifp,*ofp_zip,*ofp_code; //请输入要压缩的文件名; printf("\t请您输入需要压缩的文件:"); gets(filename); ifp=fopen(filename,"rb"); if(ifp==NULL) { printf("\n\t文件打开失败!\n\n"); return; } //请输入压缩后的文件名； printf("\t请您输入压缩后的文件名:"); gets(outputfile); ofp_zip=fopen(strcat(outputfile,".txt"),"wb"); if(ofp_zip==NULL) { printf("\n\t压缩文件指定失败!\n\n"); return; } //请输入压缩文件的字符码表保存文件名； printf("\t请您输入保存码表文件名："); gets(outcodefile); ofp_code=fopen(strcat(outcodefile,".txt"),"wb"); if(ofp_code==NULL) { printf("\n\t压缩码表文件指定失败!\n\n"); return; } //读文件统计各个字符的权重; flength=0; while(!feof(ifp)) { fread(&c,1,1,ifp); char_weight[c].count++; //字符重复出现频率+1 flength++; //字符出现原文件长度 } int diff_char=0; for(int i=0;i<512;i++) { if(char_weight[i].count!=0) { char_weight[i].b=(unsigned char)i; diff_char++; } else char_weight[i].b=0; } ww=(NodeWeight*)malloc(diff_char*sizeof(NodeWeight)); int jj=0; for( i=0;i<512;i++) { if(char_weight[i].count!=0) { ww[jj].ch=char_weight[i].b; ww[jj].weight=char_weight[i].count; jj++; } } ww->len=jj; //编码； HuffmanCoding(&htree,&hcode,ww); //压缩； fseek(ifp,0,SEEK_SET); //从文件开始位置向前移动0字节，即定位到文件开始位置 char *buf=(char *)malloc(50*sizeof(char));//假设每个字符的编码长度不超过25； int sum_zip=0,sum_total=0; int j=0; buf[0]=0; //定义缓冲区,它的二进制表示00000000，初始值为空--陈润资； unsigned char c_if; while(!feof(ifp)) { c_if=fgetc(ifp); sum_total++; for(i=0;i<ww->len;i++) { if(c_if==ww[i].ch) break; } if(i==ww->len) break; strcat_chen(&buf,(hcode+i+1)->ch_pointer); j=strlen(buf); c=0; while(j>=8) //对哈夫曼编码位操作进行压缩存储 { for(i=0;i<8;i++) { if(buf[i]=='1') c=(c<<1)|1; else c=c<<1; } fwrite(&c,1,1,ofp_zip); sum_zip++; //统计压缩后文件的长度 strcpy(&buf,buf+8); //一个字节一个字节拼接 j=strlen(buf); } } if(j>0) //对哈夫曼编码位操作进行压缩存储 { strcat(buf,"00000000"); for(i=0;i<8;i++) { if(buf[i]=='1') c=(c<<1)|1; else c=c<<1; } fwrite(&c,1,1,ofp_zip); sum_zip++; } sum_total--; double div=((double)sum_zip/sum_total)*100;//计算文件的压缩率 //保存码表； fwrite(&(ww->len),sizeof(int),1,ofp_code); for(i=1;i<=ww->len;i++) { char ch=(hcode+i)->ch; fwrite(&(ch),sizeof(char),1,ofp_code); int i_01=0; do{ char ch_01=(hcode+i)->ch_pointer[i_01]; fwrite(&(ch_01),sizeof(char),1,ofp_code); i_01++; }while((hcode+i)->ch_pointer[i_01-1]!='\0');//将'\0'也保存起来 } fwrite(&sum_zip,sizeof(int),1,ofp_code); //压缩文件的长度保存在码表中 fwrite(&sum_total,sizeof(int),1,ofp_code); //原文件的长度保存在码表中 fclose(ifp); fclose(ofp_zip); fclose(ofp_code); printf("\n\t压缩文件成功!\n"); printf("\t压缩率为 %f%%\n\n",div); } void unzip(){ HufCode_pointer hcode; //码表 int char_diff,len_zip=0; //flength;char_diff,是不同的字符数，也是编码的条数。 unsigned char c=0; char filename_zip[50],filename_code[50],outfile_unzip[50]