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

《英文文件的压缩和解压缩-数据结构与算法课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、的能力。⑶在程序设计方法以及上机操作等基本技能和科学作风方面进行比较系统和严格的训练。2、数据结构的选择和概要设计此程序选择的存储结构为顺序存储结构，而使用的哈弗曼树是二叉树的一种特殊结构，可以首先把叶子节点按顺序存放在存储结构中，可以不用任何附加信息就直接寻得其左右孩子节点和父节点，方便建立哈弗曼树。对于英文文章的压缩和解压缩只要定义生成哈弗曼树和哈弗曼编码的数据类型即可。即structhead{unsignedcharb;longcount;longparent,lch,rch;charbits[256];}header[512],tmp;header【512】中的每

4、个节点包括如下信息：unsignedcharb存放的是节点信息Longcount每个字符的权值Longparent父节点Longlch左孩子Longrch右孩子Charbits每个字符的哈弗曼编码程序中包含的函数及其功能：Voidyasuo（）压缩函数，压缩文本文件Voidjieya（）解压缩文本文件Voidout（）输出压缩后的编码Voidmain（）主函数其中b是存放英文文章中的各个字符，count存放每个字符对应的权值，也就是每个字符在一篇文章中出现的次数，parent，lch，rch是某叶子节点的父节点，和左右孩子节点，bits[]存放各自字符的哈弗曼编码。tmp

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

6、数，在强制转化为字符型变量，写入c.txt，另外注意的是，当最后的由哈弗曼所构成的二进制文档的字符读取到最后的时候，如果不够8位，的话，则在末尾补零，不然就会出现错误。while(header[i].bits[0]!=0){c=0;for(j=0;j<8;j++){if(header[i].bits[j]=='1')c=(c<<1)

7、1;elsec=c<<1;}文章压缩成功后，就需要对文档文档进行解压缩，先读取c.txt中的字符文档，是一个一个字符的读取，然后再把读取的一个字符先强制转化为整数，这是根据ASCII码来转化的，最后在将整数转化为二进制编码，是8位的编码，并把

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