英文文件的压缩和解压缩程序

合肥学院计算机科学与技术系一、问题分析和任务定义1、 题目 采用哈夫曼编码思想实现英文文本的压缩与解压缩，并提供压缩前后的占用空间比。要求 1）压缩原文件规模不小于5K 2) 提供解压缩文件后文件与原文件的相同性比较功能2、问题分析压缩过程 news.txt news1.txt1、以读的形式打开需要压缩的一个英文本文件，把其中出现的所有字符按其在文本中出现的频率利用哈夫曼树进行编码。2、以写的形式打开一个新的文本文件，把它作为英文文本压缩后的文本文件，扫描需要压缩的英英文本文件（ new.txt ）中所有字符，把其对应的编码通过转换后存入新的文本文件( new1.txt )中。3、把需要压缩的英文文本（ new.txt ）中所出现的字符及其编码等原始文件的信息保存在新的文本文件中。解压缩过程 news1.txt news2.txt1、以读的形式打开一个压缩文件 news1.txt，按其中保存的原始文件的信息还原哈夫曼树及字符编码。2、 以写的形式打开一个新的文本文件，作为解压后的英文文本 news2.txt ，逐个扫描压缩文件 news1.txt中的所有字符，把其中所有转换后的编码再转换回来并与哈夫曼树中存储的字符编码比较，把其对应的字符写入news2.txt 中。一个字符在文本文件中存储时占一个字节，而其二进制编码若直接存入文本文件其所占的空间不会少于一个字节。例如：假设字符E的编码为001，若把001直接存入文件只能用字符串的形式，其所占用的空间为三个字节。达不到文件压缩的目的，所以必须对编码的存储空间进行转换。3 编码转换在文本文件中字符之间是连续的，所以在文本文件中存储编码也是连续的。可以把连续的不同字符的编码存入同一个字节，再把这一个字节的二进制码转换成一个字符，把转换后的字符存储在文本文件中。二、数据结构的选择和概要设计：1 此程序采用的数据结构为顺序表。哈夫曼树是二叉树的一种，二叉树的顺序存储结构中可以把结点间的关系放在其存储位置中，无需附加任何信息就能在这种结构中找到每个结点的双亲结点和孩子结点，这正是哈夫曼编码所需要的。哈夫曼树顺序表：结构体header512,表中每个结点包括以下信息unsigned char b 字符名long count 在文件中出现次数long parent 父结点Long lch 左孩子结点Long rch 右孩子结点char bits256 字符编码 压缩文件new1.txt解压后New2.txt原文件new.txtCompressUncompress内容相同 图1 程序的实现过程表1 程序中所包括的函数及其功能 函数名 所实现的功能 compress( )实现 文件压缩 （被主函数调用） uncompress( )实现 文件解压缩 （被主函数调用） huffman() 对文件中出现的字符进行编码（被以上两函数调用）Main()compresshuffamuncompress图2 程序模块间的调用关系2、算法流程 （假如 原文件中只有一句话 I am here ）1） 压缩过程 （主函数调用 compress( )函数 ） 扫描文档知 alcount=9 n=6 权值：count 表2 利用权值进行编码eIamhrcount 2 2 1111 1 parent 10 7 7 8 8 9 bits 10 11 0000 0001 010 011 001h4Ia2r3e 5 9m2 图3 进行哈夫曼树的构造 0000110001010110111000110 12 86 227 0 因为八位的二进制码转化为的整数完全可以用ASCLL码值对应的字符来代替在原文件（new.txt）中一共占用了9个字节，而如果按上图的存储方式存入文件则只要4个字节2)解压缩过程 12 86 227 0把以字符的形式存储在文件（new1.txt）中的编码还原0000110001010110111000110依次把还原后的存储编码与字符的编码比较，若相同则把字符写入文件（new2.txt）1100010101101110001100001010110111000110010110111000110110111000110011100011010001100011010图4 哈夫曼编码的还原过程二、 详细设计和编码1要完成对文件的压缩和解压缩，首先要建立哈夫曼编码的算法，而要建立哈夫曼编码的算法，就要定义哈夫曼树采用的顺序表结构以下是基本的数据结构的定义哈夫曼树采用顺序表的结构 struct head /结构体 unsigned char b; /存储字符int count; /权值long parent,lch,rch;char bits256; /编码 header512,tmp;2/文件压缩过程a.要实现文件的压缩过程，首先要从文本中读入一个字符，若读入的是哈夫曼树中的第i个字符，则把第i个字符的编码接在之前定义过的字符串buf的未尾Buf0=0；while(q!=alcount) fread(&c,1,1,ifp); / 从文本中读入一个字符q+; for(i=0;i=8) /当字符串buf的长度大于或等于8时 f=0; for(p=7;p=0;p-) /把前8位的编码转化为整数（调用了 if(bufp=1) shuxue函数求2的 次方） f=shuxue(7-p)+f; c=(unsigned char)f; /把这个整数变为字符串 fwrite(&c,1,1,ofp); / 写入压缩文件 pt1+; strcpy(buf,buf+8); /把已经写入文件的编码从buf中去掉 j=strlen(buf); / j用来统计字符串的长度 c. 当buf中最后的字符串小于8位时,把它变成整数，转化为字符写入压缩文件,英文文本文件正文内容写入文件后，还必顺把字符的基本信息（字符名，权值）写入压缩文件，以便文件的解压缩。 if(j0) / 当buf中最后的字符串小于8位时 f=0; for(p=j-1;p=0;p-) / 把它变成整数，转化为字符写入压缩文件 if(bufp=1) f=shuxue(j-p-1)+f; c=(unsigned char)f; fwrite(&c,1,1,ofp);pt1+;在解压缩前必顺依靠字符的权值班重新对字符进行哈夫曼编码（调用huffman函数）3.文件的解压缩过程a.若要实现文件的解压缩，在解压缩前必顺依靠字符的权值班重新对字符进行哈夫曼编码（调用huffman函数），首先定义一个字符串，当字符串bx 的长度小于p时，从压缩文件读入一字符（8位），并把字符转化为整数，之后再把整数转化为二进制码的字符串存入字符串buf，统计字符串buf的长度，如果小于8位，则给编码补零，并把字符串buf接在字符串bx末abx0=0;while(1)while(strlen(bx)(unsigned int)p) /p为编码最长的字符的编码长度 /当字符串bx 的长度小于p时fread(&c,1,1,ifp); / 从压缩文件读入一字符（8位）f=c; 把字符转化为整数itoa(f,buf,2); / 把整数转化为二进制码的字符串存入字符串buf f=strlen(buf); / 统计字符串buf的长度if(f8) / 如果小于8位 for(i=0;i8-f;i+) / 给编码补零memmove(buf+1,buf,f+1); buf0=0; strcat(bx,buf); / 把字符串buf接在字符串bx末b.当完成上面步骤时，把bx的部分编码与字符的编码进行比较，若相同，则去掉bx中这部分相同的编码，并把找到的字符写入解压文件。for(i=0;i一个八位二进制码ASCLL码(整数)字符(写入) 问题2：生成了压缩文件，可以实现文件的压缩，但不能解压缩。 原因：在解压过程中，把从压缩文件中读出的字符转化为整数进而再转化为二进制编码时没有给编码补零。 解释： 对于前面的例子 I am here eIamhrcount 2 2 1111 1 parent 10 7 7 8 8 9 bits 10 11 0000 0001 010 011 001解压缩时从压缩文件中读出的字符转化为整数时为 12 86 227 0若不补零，转化成的编码为11001010110111000110而正确的编码为0000110001010110111000110 不把流失掉的零补齐的话，解压后的文件轻则出现乱码，重则根本读不出来。在开始编写这个程序的时候，以为自己把各种可能的情况以及细节的问题考虑得很全面了，也做了充分的准备。真正做起来才发现原来不是这么回事，出现的问题是一个接着一个。原因还是自己在做之前，没有充分的考虑细节问题。五、测试结果及其用例 图5 程序调试后，分别对压缩功能和解压缩功能实现后的截屏图6 压缩过后的文本文件的截屏图7 解压缩过后的文本文件的截屏六、用户使用说明 运行程序，按提示输入文件名（必须为Txt格式），程序运行结束后可在相应的根目录下查看压缩文件和解压缩文件。七、参考文献 1）王昆仑 李红色 数据结构与算法 中国铁道出版社 20072）谭浩强 C程序设计 （第三版） 清华大学出版社 2005八、附录#include #include #include #include struct head /结构体 unsigned char b; /存储字符int count; /权值long parent,lch,rch;char bits256; /编码 header512,tmp;void huffman(int n,int m) /用哈夫曼树进行编码 int i,j,p1,p2,f; int small1,small2; i=n;while(i512) p2=p1=0; small2=small1=1000; for(j=0;j=i-1;j+) if(headerj.parent=-1) if(headerj.countsmall1) small2=small1; small1=headerj.count; p2=p1; p1=j; else if(headerj.countsmall2) small2=headerj.count; p2=j; headerp1.parent=headerp2.parent=i; headeri.count=small1+small2; headeri.lch=p1; headeri.rch=p2; i+;for(i=0;in;i+) f=i;while(headerf.parent!=-1) j=f; f=headerf.parent; if(headerf.rch=j)j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);headeri.bits0=1; else if(headerf.lch=j)j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);headeri.bits0=0; printf(n输出字符及其编码：n); for(i=0;in;i+) printf(%c,%s),headeri.b,headeri.bits);int shuxue(int i) /用于计算2的i次方的函数int j,k=1; for(j=1;j=i;j+) k=2*k; return k;void compress() /压缩文件char filename30,outputfile30,buf512;unsigned char c; long i,j,f,p,q,n,m,alcount=0,pt1; FILE *ifp,*ofp; printf(请输入文件名:); scanf(%s,&filename);printf(请为压缩后的文件命名:); scanf(%s,&outputfile); if(ifp=fopen(filename,r)=NULL)/打开英文本文件 printf(不能打开文件!); return; if(ofp=fopen(outputfile,w)=NULL)/新建压缩文件printf(不能打开文件!);return; printf(文件打开n);while(!feof(ifp)/统计英文文本文件字数及每个字符出现的次数fread(&c,1,1,ifp);printf(%c,c);headerc.count+;alcount+;alcount-;headerc.count-;for(i=0;i0)headeri.b=(unsigned char)i;elseheaderi.b=0;for(i=0;i256;i+)for(j=i+1;j256;j+) if(headeri.countheaderj.count) tmp=headeri; headeri=headerj; headerj=tmp; for(i=0;i256;i+) if(headeri.count=0)break;n=i;m=2*n-1; huffman(n,m); /调用哈夫曼编码函数 fseek(ifp,0,SEEK_SET); fwrite(&alcount,sizeof(long),1,ofp);/把字符总数写入文件 fseek(ofp,8,SEEK_SET); pt1=8; buf0=0; q=0; while(q!=alcount) /文件压缩过程fread(&c,1,1,ifp);q+;for(i=0;i=8) f=0; for(p=7;p=0;p-) if(bufp=1) f=shuxue(7-p)+f; c=(unsigned char)f; fwrite(&c,1,1,ofp); pt1+; strcpy(buf,buf+8); j=strlen(buf); if(j0) f=0; for(p=j-1;p=0;p-) if(bufp=1) f=shuxue(j-p-1)+f; c=(unsigned char)f; 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+) /把结点信息存入文件 fprintf(ofp,%c,headeri.b); fprintf(ofp,%d,headeri.count); fclose(ifp);fclose(ofp);printf(compress successfully!n);return; void uncompress() /解压缩函数 char filename255,outputfile255,buf255,bx255;unsigned char c;long i,j,m,n,f,p,pt1;long alcount;FILE *ifp,*ofp;printf(请输入文件名:); scanf(%s,&filename);printf(请为压缩后的文件命名:); scanf(%s,&outputfile); if(ifp=fopen(filename,r)=NULL)/打开压缩文件 printf(不能打开文件!); return; if(ofp=fopen(outputfile,wb)=NULL)/新建解压缩文件printf(不能打开文件!);return;fread(&alcount,sizeof(long),1,ifp);fread(&pt1,sizeof(long),1,ifp);fseek(ifp,pt1,SEEK_SET);fread(&n,sizeof(long),1,ifp);m=2*n-1;for(i=0;in;i+)fscanf(ifp,%c,&headeri.b); fscanf(ifp,%d,&headeri.count); huffman(n,m); /调用哈夫曼函数重新载入编码for(i=0;in;i+) /按从小到大排序 for(j=i+1;jstrlen(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);f=c;itoa(f,buf,2);f=strlen(buf);if(f8) for(i=0;i8-f;i+)memmove(buf+1,buf,f+1); buf0=0; strcat(bx,buf);for(i=0;in;i+) f=strlen(headeri.bits); if(memcmp(headeri.bits,bx,f)=0) break;strcpy(bx,bx+f);c=headeri.b;fwrite(&c,1,1,ofp);m+;if(m=alcount) break; fclose(ifp);fclose(ofp);printf(Uncompress successfully!n);return;void main() int choose;int i; for(i=0;i512;i+) headeri.parent=-1; headeri.lch=-1; headeri.rch=-1; headeri.count=0; printf (1 压缩文件n); printf(2 解压缩文件n); scanf(%d,&choose); if(choose=1) compress(); if(choose=2) uncompress();