英文文件的压缩和解压缩-数据结构与算法课程设计报告

1、合肥学院计算机科学与技术系课程设计报告20092010学年第 二 学期课程 数据结构与算法课程设计名称英文文件的压缩和解压缩学生姓名李洋学号0804012035专业班级08计科(2)指导教师王昆仑2010年6月7日题目: 英文文件的压缩和解压缩1、问题分析和任务定义采用哈夫曼编码思想实现文件的压缩和解压缩功能，并提供压缩前后的占用空间之比。要求：（1）压缩原文件的规模应不小于5K。（2）提供解压缩后文件与原文件的相同性比较功能，对于一篇文章，首先要打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，注意编码表设计及其数据结构，编码完成后再对其编码进行译码

2、。压缩过程就是以读的方式打开原来的英文文件A.txt，把其中出现的所有字符在文中出项的频率作为权值建立哈弗曼编码。以写的方式打开一个新的文件，把它作为英文文件压缩后的文本文件，在扫描英文文本文件的所有字符，把其经过一定的转换后存C.txt中。在扫描C.txt这个文件里的字符把其转换为二进制文件，在把二进制还原为初始的字符。存入D.txt中。任务定义是 通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 深刻理解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力。 在程序设计方法以及上机操作等

3、基本技能和科学作风方面进行比较系统和严格的训练。2、数据结构的选择和概要设计 此程序选择的存储结构为顺序存储结构，而使用的哈弗曼树是二叉树的一种特殊结构，可以首先把叶子节点按顺序存放在存储结构中，可以不用任何附加信息就直接寻得其左右孩子节点和父节点，方便建立哈弗曼树。 对于英文文章的压缩和解压缩只要定义生成哈弗曼树和哈弗曼编码的数据类型即可。即struct head unsigned char b; long count; long parent,lch,rch; char bits256; header512,tmp;header【512】中的每个节点包括如下信息：unsigned char

4、 b存放的是节点信息Long count 每个字符的权值Long parent父节点Long lch左孩子Long rch右孩子Char bits每个字符的哈弗曼编码程序中包含的函数及其功能：Void yasuo（）压缩函数，压缩文本文件Void jieya（）解压缩文本文件Void out（）输出压缩后的编码Void main（）主函数其中b是存放英文文章中的各个字符，count存放每个字符对应的权值，也就是每个字符在一篇文章中出现的次数，parent，lch，rch是某叶子节点的父节点，和左右孩子节点，bits存放各自字符的哈弗曼编码。tmp则是在生成哈弗曼编码时需要寻找最小权和次小权来作

5、为哈弗曼的树的头两个叶子节点，把它们的和作为根节点，加入到之前的字符编码中去，另外删除最小权和次小权，继续以这种方法生成哈弗曼编码，当到最后一个节点时结束，哈弗曼树生成完毕。而后就是对文章进行压缩。Fseek()函数把文件的指针调到ifp待读文件的开始端，与此同时，在把读取的字符经过处理写入ifp文件中，c=fgetc（）读取，如果c=headeri.b,即buf中存放的二进制转化为字符与字符中的字符相同，则记录于c.txt中，并把相同的部分给删除。如此往复，在继续读取由字符的哈弗曼编码所构成的顺序表中的8位，转化为整数，在强制转化为字符型变量，写入c.txt，另外注意的是，当最后的由哈弗曼所

6、构成的二进制文档的字符读取到最后的时候，如果不够8位，的话，则在末尾补零，不然就会出现错误。while(headeri.bits0!=0) c=0; for(j=0;j<8;j+) if(headeri.bitsj='1') c=(c<<1)|1; else c=c<<1; 文章压缩成功后，就需要对文档文档进行解压缩，先读取c.txt中的字符文档，是一个一个字符的读取，然后再把读取的一个字符先强制转化为整数，这是根据ASCII码来转化的，最后在将整数转化为二进制编码，是8位的编码，并把这编码存入buf中，在不断读取不断存储，在此过程，用字符中的编码

7、与以读取中的编码进行比较，即if(memcmp(headeri.bits,bx,headeri.count)=0) break; if判断语句来判断，如果相等的话，也就是memcmp（）函数的值取零，那么就记录这个编码所对应的字符值，即c=header【i】. b，并且写入D.txt中，即fwrite(&c,1,1,ofp);，不断重复这一过程，知道C.txt中的字符都读取完毕，那么存入D.txt的文档也就结束，是源文件一致的英文文件。3、详细设计和编码 首先，要完成此程序，首先就要建立哈弗曼树，来建立哈弗曼编码，采用顺序表存储结构，即struct head unsigned char

8、 b; long count; long parent,lch,rch; char bits256; header512,tmp;首先定义文件指针ifp，ifp=fopen(“A。txt”)，定义flength=0；统计这篇文章的所有的字符的长度，然后在用feof（）读取全文信息，用fread（）函数一个一个读取字符，headerc.count记录的是每个字符的出现的频率，然后初始化数组，加入headeri.count不为0，即某个字符出现在文中，用ascii码统计headeri.count的数值，如果不为0，那就说明此字符在文中又出现，那么就把它赋值给headeri.b，用强制类型转换。然后

9、把它的左右孩子和父节点都赋为-1，即为空。然后寻找最小权和次小权，for（i=n；i<n;i+）,定义min1为一个很大的数，以便和文章的某个字符的最大权值进行比较，不断筛选，确定最小权，pt1=j是记录最小权的位置，min1=header【j】.count是记录最小权的值，就是频率。然后建树，以最小两个的权值相加作为一个新的节点，在放入之前的各个节点中去，在把之前的那两个最小权给删除掉，继续以这种方式，知道把树建成功为止，在确定哈弗曼编码，从叶子节点开始不断寻找它的父节点，直到寻找到根结点，然后将这些0，1构成一段编码就是哈弗曼编码了。有了哈弗曼编码就可以实现文件的压缩和解压缩了。 其

10、次，要实现文件的压缩过程，就要从文本中读入一个字符，如果读入的是第i个字符，则把第i个字符的编码写在buf的结尾，buf【0】=0；用于存放所有的字符的哈弗曼编码，即是一连串的二进制编码，当buf的长度大于等于8的时候，把前八位的编码强制转换为整数，之后在把这个整数强制转换为字符，把字符串写入压缩文件，最后把buf中已经转换为整数的那8为编码去除，继续读入哈弗曼编码。当buf中最后的字符串小于8位时，转换为字符写入压缩文件，在写入压缩文件之后要注意把英文的字符以及其的编码一起写入文件。 最后，要实现的是解压缩过程，解压缩之前必须依靠字符的权值重新进行哈弗曼编码，首先定义一个字符串bx，当bx的

11、长度小于p时，从C.txt中读入一个字符，把字符转换为整数，把整数在转换为二进制码的字符串buf，统计buf中的长度，当小于8位时，补o，然后把字符串buf接着bx末尾。然后在把bx的部分编码与字符编码比较，若相同，去掉相同的编码，并把程序写入解压后文件。4、上机调试问题1：在文件中一个字符只是占去一个字节，给字符编码后，其编码要如何存入压缩文件才能应道压缩的作用。解决:若直接存储，编码只可以用字符串，这样存储空间不仅没有减少反而增大了，所以必须把多个编码存在一个字节中，一字符的形式写入文件。即：多个编码->一个八位二进制编码->ascii码->字符（写入到C.txt）问题2

12、：生成了压缩文件，可以实现文件的 压缩，但不能实现解压.原因是：在解压的过程中，吧从压缩文件中读取的字符转化为整数在转化为二进制编码时没有给编码补零。在开始写程序，一开始在就觉得自己会把各种细节都会考虑到，做了准备，但是在具体实现时却发现真的不是那么回事，是自己没有充分考虑问题。不知道怎么解压和解压缩。5、测试结果及其分析 运行程序，进入主菜单选择页面，有四个选项，1。压缩文档，2。解压缩文档，3、输出压缩后的文档，4。退出。选择第一个时首先输出每个字符以及对应的权值和对应的哈弗曼编码。而后在输出压缩比，最后生成讲压缩后的文档存放在C.txt中，第二个是实现解压缩功能，将解压缩的文档存放在D.

13、txt中，第三个选项是读取D.txt中的文章，在屏幕中显示。最后一个选项退出程序。这是一个主菜单选择界面，确定你要选择的选项，界面清晰明了，1是压缩文档，2是解压缩文档，3是输出解压缩后面的文档，最后是退出。这个是第一个选项实现的结果，首先输出英文文章的出现的所有的字符，并且输出它们的权值以及哈弗曼编码。并且将压缩后的文件放入C.txt中这是运行第二个选项后出现的结果，是解压缩文件后将其存放在D.txt中，其实和源文件是一样的。输出的是解压缩后的文件。原英文文件文章截屏如上图所示，也就是需要进行压缩和解压缩的源文件。压缩后的文件，由于经过处理，就是先将所有的字符的哈弗曼编码顺序存到一个数组bu

14、f中，而后每8位提取一下，先转化为整数，然后根据ASCII码表转化为字符，所以出现的是乱码。解压缩后的文件，与源文件一致，压缩成功。6、用户使用说明 首先要在和源程序在同一个目录的文件中建立一个英文文本文件A.txt，而后运行程序，第一个是生成一个压缩后的编码，第二个是生成一个解压缩后的编码，也就是和原来的文章一样的文件。第三个输出解压后文件，最后的是退出程序。7、参考文献(1).王昆仑，李红，数据结构与算法：c语言版北京：中国铁道出版社，2007(2)何钦铭 颜晖c语言程序设计北京：高等教育出版社，20088、附录源程序：#include "stdio.h"#includ

15、e "string.h"#include "stdlib.h"struct head unsigned char b; long count; long parent,lch,rch; char bits256; header512,tmp;/header记录英文文章中共有多少字符void yasuo() char buf512; unsigned char c,sum=0; long i,j,m,n,f; long min1,pt1,flength; FILE *ifp,*ofp;/定义文件指针ifp用于读，ofp用于写 ifp=fopen("

16、;A.txt","rb");if(ifp=NULL) printf("open error!n"); return;ofp=fopen("C.txt","wb");/创建新文件，存放压缩后的英文文章 if(ofp=NULL) printf("open error!n");return; flength=0;/英文文章的长度 while(!feof(ifp)/文章读取结束，feof返回1，否则返回0fread(&c,1,1,ifp); headerc.count+;/记录每个字符

17、的权值，构建哈弗曼树 flength+;/记录的是一篇文章的长度 flength-;headerc.count-;for(i=0;i<512;i+) /初始化数组 if(headeri.count!=0) headeri.b=(unsigned char)i;/header【i】.b存放字符 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+)/选择法排序，header【0】存放的是最权值最大的 if(headeri.coun

18、t<headerj.count) tmp=headeri; headeri=headerj; headerj=tmp; for(i=0;i<256;i+) if(headeri.count=0) break; n=i;m=2*n-1; /一篇文章中有n个字符，则占取2n-1个空间来存储 for(i=n;i<m;i+)/哈弗曼树除了叶子节点外的节点，即生成节点，进行n-1次合并，产生n-1个新节点 min1=999999999; for(j=0;j<i;j+)/找最小权 if(headerj.parent!=-1) continue; if(min1>headerj

19、.count) pt1=j; min1=headerj.count;/最小权赋值给min1 continue; headeri.count=headerpt1.count;/最小权 headerpt1.parent=i;headeri.lch=pt1;min1=999999999;/min1取值这么大是与header【i】.count的值比较，从而找出最小权 for(j=0;j<i;j+) /循环，找出次小权 if(min1>headerj.count) pt1=j; min1=headerj.count; continue;/此过程找出的是次小权进行建树 headeri.coun

20、t+=headerpt1.count; headeri.rch=pt1;/确定headeri的左孩子 headerpt1.parent=i;/i就是开始两个最小的权值的值的和 printf("字符统计 对应权值 哈弗曼编码n"); for(i=0;i<n;i+)/循环， printf(" %c ",headeri.b); /输出的是每个字符的权值 printf(" %d t",headeri.count); /输出每个字符的哈弗曼编码 f=i; headeri.bits0=0;先确定初始情况， while(headerf.par

21、ent!=-1)/不断去找某个叶子节点的父节点，知道寻找到哈弗曼树的根节点为止 j=f;/记录根节点 f=headerf.parent; if(headerf.lch=j) j=strlen(headeri.bits);/记录的是节点i距离根节点的路径长度 memmove(headeri.bits+1,headeri.bits,j+1);/将headeri.bits中移动j+1个字符给headeri.bits+1 headeri.bits0='0'/回到初始情况，继续需找某个叶子节点的父节点，求它的哈弗曼编码 else/headeri的右孩子是j的情况 j=strlen(hea

22、deri.bits);/求headeri.bits的长度，为了确定哈佛吗编码的长度 memmove(headeri.bits+1,headeri.bits,j+1);/移动j+1个字符从headeri到headeri+1的位置 headeri.bits0='1'/规定某个根节点的右子树编码路径是1 for(f=0;f<n;f+)/循环，输出的是某个节点的哈弗曼编码 printf("%c",headeri.bitsf); printf("n"); fseek(ifp,0,SEEK_SET);/压缩过程，将文件指针移到ifp的开始处 f

23、write(&flength,sizeof(int),1,ofp);/准备向文件指针ofp所指向的文件也就是D.txt中写入字符 fseek(ofp,8,SEEK_SET);/将文件移动至距离开始8个字符处，因为根据ascii码每个字符的编码时一个整数，可以用二进制的编码来表示 buf0=0; f=0; pt1=8; while(!feof(ifp)/文件读取没有结束，就继续读取，知道结束 c=fgetc(ifp);f+;/读取字符 for(i=0;i<n;i+) if(c=headeri.b) break;/将从D.txt中的读取的字符的编码与字符编码进行比较，如果相等，则用c

24、记录，存储 strcat(buf,headeri.bits);/把前面比较过的二进制编码删除 j=strlen(buf);/求字符串buf中的二进制的长度 c=0; while(j>=8)/如果buf中字符的长度大于8位时候，就读取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);/删除之前处理过的8位编码 j=strlen(buf); if(f=flength) break；

25、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(i=0;i<n;i+) fwrite(&a

26、mp;(headeri.b),1,1,ofp); c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0) for(f=j%8;f<8;f+) strcat(headeri.bits,"0"); while(headeri.bits0!=0) c=0; for(j=0;j<8;j+) if(headeri.bitsj='1') c=(c<<1)|1; else c=c<<1; strcpy(headeri.bits,

27、headeri.bits+8); fwrite(&c,1,1,ofp); fclose(ifp); fclose(ofp); printf("n压缩比:"); printf("%f",(float)4/6); printf("n文档压缩成功!见C.txtn");void jieya()/解压函数 char buf255,bx255;/定义buf，bx存放二进制编码 unsigned char c; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp;/定义文件指针，进行文件的读写操

28、作，其中，ifp用于读取c.txt中的字符，ofp用于向D.txt中写入字符 ifp=fopen("C.txt","rb");/文件处理的具体操作 if(ifp=NULL) printf("source file open error!n"); return; ofp=fopen("D.txt","wb"); if(ofp=NULL) printf("destination file open error!n"); return; fread(&flength,siz

29、eof(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,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

30、); f=c; itoa(f,buf,2);/二进制把f变成字符型变量，保存在buf中 f=strlen(buf); for(l=8;l>f;l-) strcat(headeri.bits,"0"); strcat(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(hea

31、dern-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); for(l=8;l>f;l-) 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(&c,1,1,ofp); m+; if(m=flength) break; fclose(ifp); fclose(ofp); printf("压缩文档解压成功!见D.txtn");int out()FILE *fp;char tmpstr128;fp