(完整word版)用哈夫曼压缩文件(C语言)

1、用哈夫曼压缩文件(C语言)2007-12-29 21:09:15| 分类： 缅蔓|标签：|字号大中小 订阅利用哈夫曼编码制作压缩软件，内容如下：#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,t

2、mp;/*压缩*/ void compress()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

3、("t请您输入压缩后的文件名：");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;/原文件长度用作求压缩率的分母heade

4、rc.count-;for(i=0;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.coun

5、t<headerj.count)tmp=headeri;headeri=headerj;headerj=tmp;for(i=0;i<256;i+) if(headeri.count=0) break;2*n-1.n=i; /外部叶子结点数为n 个时，内部结点数为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 说明该结点已存在哈夫曼树中，

6、跳出循环重新选择新结点*/if(min1>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

7、;headeri.count+=headerpt1.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=

8、'0'else/置右分支编码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);b

9、uf0=0;/定义缓冲区,它的二进制表示00000000f=0;pt1=8;/*假设原文件第一个字符是"A"， 8 位 2 进制为 01000001 ，编码后为0110 识别编码第一个'0'，那么我们就可以将其左移一位，看起来没什么变化。下一个是'1'，应该 |1，结果 00000001同理 4 位都做完，应该是00000110 ，由于字节中的8 位并没有全部用完，我们应该继续读下一个字符，根据编码表继续拼完剩下的4 位，如果字符的编码不足4 位，还要继续读一个字符，如果字符编码超过4 位，那么我们将把剩下的位信息拼接到一个新的字节里*/wh

10、ile(!feof(ifp)c=fgetc(ifp);f+;for(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);

11、if(f=flength) break;if(j>0)/对哈夫曼编码位操作进行压缩存储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

12、(i=0;i<n;i+)fwrite(&(headeri.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='

13、;1') c=(c<<1)|1;/|1 不改变原位置上的“ 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&qu

14、ot;,div*100);return;/*解压缩*/void uncompress()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&q

15、uot;);return;printf("t 请您输入解压缩后的文件名：");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);fo

16、r(i=0;i<n;i+)fread(&headeri.b,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(

17、headeri.bits,buf);headeri.bitsp=0;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)<

18、(unsigned int)p) fread(&c,1,1,ifp); f=c;itoa(f,buf,2); f=strlen(buf);for(l=8;l>f;l-) / 在单字节内对相应位置补0 strcat(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(&

19、amp;c,1,1,ofp); m+;/统计解压缩后文件的长度if(m=flength) break; /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. 退出