利用哈夫曼编码实现文件压缩

1、用哈夫曼压缩文件(C语言）2007-12-29 21:09利用哈夫曼编码制作压缩软件，内容如下：#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>struct headunsigned char b; /记录字符在数组中的位置 long count; /字符出现频率（权值） long parent,lch,rch; /定义哈夫曼树指针变量char bits256; /定义存储哈夫曼编码的数组 header512,tmp;/*压缩*/void comp

2、ress()char filename255,outputfile255,buf512; unsigned char c;long i,j,m,n,f;long min1,pt1,flength,length1,length2;double div;FILE *ifp,*ofp;printf("t请您输入需要压缩的文件：");gets(filename);ifp=fopen(filename,"rb");if(ifp=NULL)printf("nt文件打开失败!nn");return;printf("t请您输入压缩后的文件名

3、：");gets(outputfile);ofp=fopen(strcat(outputfile,".hub"),"wb"); if(ofp=NULL)printf("nt压缩文件失败!nn");return;flength=0;while(!feof(ifp)fread(&c,1,1,ifp);headerc.count+; /字符重复出现频率+1flength+; /字符出现原文件长度+1flength-;length1=flength; /原文件长度用作求压缩率的分母headerc.count-;for(i=0

4、;i<512;i+)if(headeri.count!=0) headeri.b=(unsigned char)i;/*将每个哈夫曼码值及其对应的ASCII码存放在一维数组headeri中， 且编码表中的下标和ASCII码满足顺序存放关系*/else headeri.b=0;headeri.parent=-1;headeri.lch=headeri.rch=-1; /对结点进行初始化for(i=0;i<256;i+) /根据频率（权值）大小，对结点进行排序，选择较小的结点进树for(j=i+1;j<256;j+)if(headeri.count<headerj.coun

5、t)tmp=headeri;headeri=headerj;headerj=tmp;for(i=0;i<256;i+) if(headeri.count=0) break;n=i; /外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1.m=2*n-1;for(i=n;i<m;i+) /构建哈夫曼树min1=999999999; /预设的最大权值，即结点出现的最大次数 for(j=0;j<i;j+)if(headerj.parent!=-1) continue;/parent!=-1说明该结点已存在哈夫曼树中，跳出循环重新选择新结点*/ if(m

6、in1>headerj.count)pt1=j;min1=headerj.count;continue;headeri.count=headerpt1.count;headerpt1.parent=i; /依据parent域值（结点层数）确定树中结点之间的关系headeri.lch=pt1; /计算左分支权值大小min1=999999999;for(j=0;j<i;j+)if(headerj.parent!=-1) continue;if(min1>headerj.count)pt1=j;min1=headerj.count;continue;headeri.count+=h

7、eaderpt1.count;headeri.rch=pt1; /计算右分支权值大小headerpt1.parent=i;for(i=0;i<n;i+) /哈夫曼无重复前缀编码f=i;headeri.bits0=0; /根结点编码0while(headerf.parent!=-1)j=f;f=headerf.parent;if(headerf.lch=j) /置左分支编码0j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);/依次存储连接“0”“1”编码headeri.bits0='0'else

8、/置右分支编码1j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);headeri.bits0='1'fseek(ifp,0,SEEK_SET); /从文件开始位置向前移动0字节，即定位到文件开始位置fwrite(&flength,sizeof(int),1,ofp);/*用来将数据写入文件流中，参数flength指向欲写入的数据地址，总共写入的字符数以参数size*int来决定，返回实际写入的int数目1*/ fseek(ofp,8,SEEK_SET);buf0=0; /定义缓冲区,它的二进制

9、表示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

10、(i=0;i<n;i+)if(c=headeri.b) break;strcat(buf,headeri.bits);j=strlen(buf);c=0;while(j>=8) /对哈夫曼编码位操作进行压缩存储for(i=0;i<8;i+)if(bufi='1') c=(c<<1)|1;else c=c<<1;fwrite(&c,1,1,ofp);pt1+; /统计压缩后文件的长度strcpy(buf,buf+8); /一个字节一个字节拼接j=strlen(buf);if(f=flength) break;if(j>0)

11、/对哈夫曼编码位操作进行压缩存储strcat(buf,"00000000");for(i=0;i<8;i+)if(bufi='1') c=(c<<1)|1;else c=c<<1;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;i<n;i+)fwrite(&(he

12、aderi.b),1,1,ofp);c=strlen(headeri.bits);fwrite(&c,1,1,ofp);j=strlen(headeri.bits);if(j%8!=0) /若存储的位数不是8的倍数，则补0for(f=j%8;f<8;f+)strcat(headeri.bits,"0");while(headeri.bits0!=0)c=0;for(j=0;j<8;j+) /字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接if(headeri.bitsj='1') c=(c<<1)|1; /|1不

13、改变原位置上的“0”“1”值else c=c<<1;strcpy(headeri.bits,headeri.bits+8); /把字符的编码按原先存储顺序连接fwrite(&c,1,1,ofp);length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /计算文件的压缩率fclose(ifp);fclose(ofp);printf("nt压缩文件成功!n");printf("t压缩率为 %f%nn",div*100);return;/*解压缩*/void un

14、compress()char filename255,outputfile255,buf255,bx255;unsigned char c;long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;printf("t请您输入需要解压缩的文件：");gets(filename);ifp=fopen(strcat(filename,".hub"),"rb");if(ifp=NULL)printf("nt文件打开失败!n");return;printf("t请您输入解压缩后的

15、文件名：");gets(outputfile);ofp=fopen(outputfile,"wb");if(ofp=NULL)printf("nt解压缩文件失败!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;i<n;i+)fread(&headeri.b

16、,1,1,ifp);fread(&c,1,1,ifp);p=(long)c; /读取原文件字符的权值headeri.count=p;headeri.bits0=0;if(p%8>0) m=p/8+1;else m=p/8;for(j=0;j<m;j+)fread(&c,1,1,ifp);f=c;itoa(f,buf,2); /将f转换为二进制表示的字符串f=strlen(buf);for(l=8;l>f;l-)strcat(headeri.bits,"0");strcat(headeri.bits,buf);headeri.bitsp=0;

17、for(i=0;i<n;i+) /根据哈夫曼编码的长短，对结点进行排序for(j=i+1;j<n;j+)if(strlen(headeri.bits)>strlen(headerj.bits)tmp=headeri;headeri=headerj;headerj=tmp;p=strlen(headern-1.bits);fseek(ifp,8,SEEK_SET);m=0;bx0=0;while(1) /通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储while(strlen(bx)<(unsigned int)p)fread(&c,1,1,ifp);

18、f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;l>f;l-) /在单字节内对相应位置补0strcat(bx,"0");strcat(bx,buf);for(i=0;i<n;i+)if(memcmp(headeri.bits,bx,headeri.count)=0) break;strcpy(bx,bx+headeri.count); /*从压缩文件中的按位存储还原到按字节存储字符，字符位置不改变*/c=headeri.b;fwrite(&c,1,1,ofp);m+; /统计解压缩后文件的长度if(m=flength) b

19、reak; /flength是原文件长度fclose(ifp);fclose(ofp);printf("nt解压缩文件成功!n");if(m=flength) /对解压缩后文件和原文件相同性比较进行判断（根据文件大小）printf("t解压缩文件与原文件相同!nn");else printf("t解压缩文件与原文件不同!nn");return;/*主函数*/int main()int c;while(1) /菜单工具栏printf("t _n"); printf("n");printf("t * 压缩、解压缩 小工具 * n"); printf("t _n"); printf("t _n"); printf("t| |n"); printf("t| 1.压缩 |n"); printf("t| 2.解压缩 |n"); printf("t| 0.退出 |n&quo