用哈夫曼压缩文件(C语言)

用哈夫曼压缩文件(C语言）2007-12-2921:09:15|分类：编程|标签：|字号大中小订阅利用哈夫曼编码制作压缩软件，内容如下：#includestdio.h#includestring.h#includestdlib.h#includeconio.hstructhead{unsignedcharb;//记录字符在数组中的位置longcount;//字符出现频率（权值）longparent,lch,rch;//定义哈夫曼树指针变量charbits[256];//定义存储哈夫曼编码的数组}header[512],tmp;/*压缩*/voidcompress(){charfilename[255],outputfile[255],buf[512];unsignedcharc;longi,j,m,n,f;longmin1,pt1,flength,length1,length2;doublediv;FILE*ifp,*ofp;printf(\t请您输入需要压缩的文件：);gets(filename);ifp=fopen(filename,rb);if(ifp==NULL){printf(\n\t文件打开失败!\n\n);return;}printf(\t请您输入压缩后的文件名：);gets(outputfile);ofp=fopen(strcat(outputfile,.hub),wb);if(ofp==NULL){printf(\n\t压缩文件失败!\n\n);return;}flength=0;while(!feof(ifp)){fread(&c,1,1,ifp);header[c].count++;//字符重复出现频率+1flength++;//字符出现原文件长度+1}flength--;length1=flength;//原文件长度用作求压缩率的分母header[c].count--;for(i=0;i512;i++){if(header[i].count!=0)header[i].b=(unsignedchar)i;/*将每个哈夫曼码值及其对应的ASCII码存放在一维数组header[i]中，且编码表中的下标和ASCII码满足顺序存放关系*/elseheader[i].b=0;header[i].parent=-1;header[i].lch=header[i].rch=-1;//对结点进行初始化}for(i=0;i256;i++)//根据频率（权值）大小，对结点进行排序，选择较小的结点进树{for(j=i+1;j256;j++){if(header[i].countheader[j].count){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}for(i=0;i256;i++)if(header[i].count==0)break;n=i;//外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1.m=2*n-1;for(i=n;im;i++)//构建哈夫曼树{min1=999999999;//预设的最大权值，即结点出现的最大次数for(j=0;ji;j++){if(header[j].parent!=-1)continue;//parent!=-1说明该结点已存在哈夫曼树中，跳出循环重新选择新结点*/if(min1header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count=header[pt1].count;header[pt1].parent=i;//依据parent域值（结点层数）确定树中结点之间的关系header[i].lch=pt1;//计算左分支权值大小min1=999999999;for(j=0;ji;j++){if(header[j].parent!=-1)continue;if(min1header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count+=header[pt1].count;header[i].rch=pt1;//计算右分支权值大小header[pt1].parent=i;}for(i=0;in;i++)//哈夫曼无重复前缀编码{f=i;header[i].bits[0]=0;//根结点编码0while(header[f].parent!=-1){j=f;f=header[f].parent;if(header[f].lch==j)//置左分支编码0{j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);//依次存储连接“0”“1”编码header[i].bits[0]='0';}else//置右分支编码1{j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);header[i].bits[0]='1';}}}fseek(ifp,0,SEEK_SET);//从文件开始位置向前移动0字节，即定位到文件开始位置fwrite(&flength,sizeof(int),1,ofp);/*用来将数据写入文件流中，参数flength指向欲写入的数据地址，总共写入的字符数以参数size*int来决定，返回实际写入的int数目1*/fseek(ofp,8,SEEK_SET);buf[0]=0;//定义缓冲区,它的二进制表示00000000f=0;pt1=8;/*假设原文件第一个字符是A，8位2进制为01000001，编码后为0110识别编码第一个'0'，那么我们就可以将其左移一位，看起来没什么变化。下一个是'1'，应该|1，结果00000001同理4位都做完，应该是00000110，由于字节中的8位并没有全部用完，我们应该继续读下一个字符，根据编码表继续拼完剩下的4位，如果字符的编码不足4位，还要继续读一个字符，如果字符编码超过4位，那么我们将把剩下的位信息拼接到一个新的字节里*/while(!feof(ifp)){c=fgetc(ifp);f++;for(i=0;in;i++){if(c==header[i].b)break;}strcat(buf,header[i].bits);j=strlen(buf);c=0;while(j=8)//对哈夫曼编码位操作进行压缩存储{for(i=0;i8;i++){if(buf[i]=='1')c=(c1)|1;elsec=c1;}fwrite(&c,1,1,ofp);pt1++;//统计压缩后文件的长度strcpy(buf,buf+8);//一个字节一个字节拼接j=strlen(buf);}if(f==flength)break;}if(j0)//对哈夫曼编码位操作进行压缩存储{strcat(buf,00000000);for(i=0;i8;i++){if(buf[i]=='1')c=(c1)|1;elsec=c1;}fwrite(&c,1,1,ofp);pt1++;}fseek(ofp,4,SEEK_SET);fwrite(&pt1,sizeof(long),1,ofp);fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp);for(i=0;in;i++){fwrite(&(header[i].b),1,1,ofp);c=strlen(header[i].bits);fwrite(&c,1,1,ofp);j=strlen(header[i].bits);if(j%8!=0)//若存储的位数不是8的倍数，则补0{for(f=j%8;f8;f++)strcat(header[i].bits,0);}while(header[i].bits[0]!=0){c=0;for(j=0;j8;j++)//字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接{if(header[i].bits[j]=='1')c=(c1)|1;//|1不改变原位置上的“0”“1”值elsec=c1;}strcpy(header[i].bits,header[i].bits+8);//把字符的编码按原先存储顺序连接fwrite(&c,1,1,ofp);}}length2=pt1--;div=((double)length1-(double)length2)/(double)length1;//计算文件的压缩率fclose(ifp);fclose(ofp);printf(\n\t压缩文件成功!\n);printf(\t压缩率为%f%%\n\n,div*100);return;}/*解压缩*/voiduncompress(){charfilename[255],outputfile[255],buf[255],bx[255];unsignedcharc;longi,j,m,n,f,p,l;longflength;FILE*ifp,*ofp;printf(\t请您输入需要解压缩的文件：);gets(filename);ifp=fopen(strcat(filename,.hub),rb);if(ifp==NULL){printf(\n\t文件打开失败!\n);return;}printf(\t请您输入解压缩后的文件名：);gets(outputfile);ofp=fopen(outputfile,wb);if(ofp==NULL){printf(\n\t解压缩文件失败!\n);return;}fread(&flength,sizeof(long),1,ifp);//读取原文件长度，对文件进行定位fread(&f,sizeof(long),1,ifp);fseek(ifp,f,SEEK_SET);fread(&n,sizeof(long),1,ifp);for(i=0;in;i++){fread(&header[i].b,1,1,ifp);fread(&c,1,1,ifp);p=(long)c;//读取原文件字符的权值header[i].count=p;header[i].bits[0]=0;if(p%80)m=p/8+1;elsem=p/8;for(j=0;jm;j++){fread(&c,1,1,ifp);f=c;itoa(f,buf,2);//将f转换为二进制表示的字符串f=strlen(buf);for(l=8;lf;l--){strcat(header[i].bits,0);}strcat(header[i].bits,buf);}header[i].bits[p]=0;}for(i=0;in;i++)//根据哈夫曼编码的长短，对结点进行排序{for(j=i+1;jn;j++){if(strlen(header[i].bits)strlen(header[j].bits)){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}p=strlen(header[n-1].bits);fseek(ifp,8,SEEK_SET);m=0;bx[0]=0;while(1)//通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储{while(strlen(bx)(unsignedint)p){fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;lf;l--)//在单字节内对相应位置补0{strcat(bx,0);}strcat(bx,buf);}for(i=0;in;i++){if(memcmp(