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

合肥学院 计算机科学与技术系 课程设计报告 2009～2010学年第 二 学期 课程 数据结构与算法 课程设计名称 英文文件的压缩和解压缩 学生姓名 李洋 学号 0804012035 专业班级 08计科(2) 指导教师 王昆仑 2010年6月7日 题目: 英文文件的压缩和解压缩 1、问题分析和任务定义 采用哈夫曼编码思想实现文件的压缩和解压缩功能，并提供压缩前后的占用空间之比。要求：（1）压缩原文件的规模应不小于5K。（2）提供解压缩后文件与原文件的相同性比较功能，对于一篇文章，首先要打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，注意编码表设计及其数据结构，编码完成后再对其编码进行译码。 压缩过程就是以读的方式打开原来的英文文件A.txt，把其中出现的所有字符在文中出项的频率作为权值建立哈弗曼编码。以写的方式打开一个新的文件，把它作为英文文件压缩后的文本文件，在扫描英文文本文件的所有字符，把其经过一定的转换后存C.txt中。在扫描C.txt这个文件里的字符把其转换为二进制文件，在把二进制还原为初始的字符。存入D.txt中。 任务定义是⑴ 通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。⑵ 深刻理解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力。⑶ 在程序设计方法以及上机操作等基本技能和科学作风方面进行比较系统和严格的训练。 2、数据结构的选择和概要设计 此程序选择的存储结构为顺序存储结构，而使用的哈弗曼树是二叉树的一种特殊结构，可以首先把叶子节点按顺序存放在存储结构中，可以不用任何附加信息就直接寻得其左右孩子节点和父节点，方便建立哈弗曼树。 对于英文文章的压缩和解压缩只要定义生成哈弗曼树和哈弗曼编码的数据类型即可。即struct head { unsigned char b; long count; long parent,lch,rch; char bits[256]; } header[512],tmp; header【512】中的每个节点包括如下信息： unsigned char 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则是在生成哈弗曼编码时需要寻找最小权和次小权来作为哈弗曼的树的头两个叶子节点，把它们的和作为根节点，加入到之前的字符编码中去，另外删除最小权和次小权，继续以这种方法生成哈弗曼编码，当到最后一个节点时结束，哈弗曼树生成完毕。 而后就是对文章进行压缩。 Fseek()函数把文件的指针调到ifp待读文件的开始端，与此同时，在把读取的字符经过处理写入ifp文件中，c=fgetc（）读取，如果c==header[i].b,即buf中存放的二进制转化为字符与字符中的字符相同，则记录于c.txt中，并把相同的部分给删除。如此往复，在继续读取由字符的哈弗曼编码所构成的顺序表中的8位，转化为整数，在强制转化为字符型变量，写入c.txt，另外注意的是，当最后的由哈弗曼所构成的二进制文档的字符读取到最后的时候，如果不够8位，的话，则在末尾补零，不然就会出现错误。while(header[i].bits[0]!=0) { c=0; for(j=0;j8;j++) { if(header[i].bits[j]==1) c=(c1)|1; else c=c1; } 文章压缩成功后，就需要对文档文档进行解压缩，先读取c.txt中的字符文档，是一个一个字符的读取，然后再把读取的一个字符先强制转化为整数，这是根据ASCII码来转化的，最后在将整数转化为二进制编码，是8位的编码，并把这编码存入buf中，在不断读取不断存储，在此过程，用字符中的编码与以读取中的编码进行比较，即if(memcmp(header[i].bi