资源预览内容
第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
第9页 / 共13页
第10页 / 共13页
亲,该文档总共13页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
合肥学院计算机科学与技术系课程设计报告20092010 学年第二学期课程 数据结构与算法课程设计名称 英文文件的压缩和解压缩学生姓名学号专业班级指导教师 李红 沈亦军2010 年 6 月题目:(采用哈夫曼编码思想实现文件的压缩和解压缩功能,并提供压缩前后的占用空间之比)(1)压缩原文件的规模应不小于 5K。(2)提供解压缩后文件与原文件的相同性比较功能。 一、问题分析和任务定义。1.1 问题分析本实验是利用哈夫曼编码思想,设计对一个文本文件中的字符进行哈夫曼编码,生成编码文件(压缩文件) ;反过来,可将一个压缩文件译码还原为一个文本文件(.txt)。要解决以上问题,需从以下几个方面着手: (1)如何读入待压缩的文本文件,统计文本文件中各字符的频数及出现的字符个数; (2)如何构造 huffman 树,进行 huffman 编码,生成压缩文件(后缀名 .txt(3)如何读入待解压的压缩文件名,并利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码,对文件进行解压,生成解压文件(后缀名为.txt) ; (4)如何提供 压缩前后的占用空间之比1.2 输入、输出数据的形式、值的范围,算法(程序)所能达到的功能本实验的数据主要是以字符型为主,还有一些自定义的整形和浮点型变量,该实验室对文件进行压缩和解压(被压缩文件容量要求大于5KB) ,通过该算法程序可以大致上满足实验所要求的功能,即压缩原文件的规模不小于 5KB,提供了压缩后的文件与原文件的压缩比例,也即提供了性能比较功能1.3 测试用的数据本实验的数据是通过读入一个名为 huffman.txt 的文本文档,文档中内容为字符型数据。所测试的部分数据: 图 1.原文档二、数据结构的选择和概要设计为了完成实验所要求的任务,解决的问题及方法如下:1.文件的读取及统计字符出现的个数和频率(1)文件的读取void read_file_count()char c;ifstream infile;infile.open(huffman.txt);/打开 huffman.txt 文件if(!infile)/检查文件是否打开。coutinchar;if(inchar=1)ptr=huffmanptr.rchild;ptr=huffmanptr.lchild;if(huffmanptr.lchild=0&huffmanptr.lchild=0)fp2图 4.huffman 解码流程四、上机调试开始考虑问题是,要对文件进行压缩,如何才能达到比较好的效果,那就是 huffman编码是采用等长编码还是采用不等长问题,采用不等长编码要避免译码的二义性或多义性。假设用 0 表示字符 D,用 01 表示字符 C 则当接受到编码串“01” ,并译到字符 0 时,是立即译出对应的字符 D,还是接着与下一个字符 1 一起译为对应的字符 C,这就产生了二义性。因此,若对某一个字符集进行不等长编码,则要求字符集合中任一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码,这从等长编码所对应的编码二叉树也可以直接看出,任何一个叶子结点都不可能是其它叶子结点的双亲,也就是说,只有当一个结点是另一个结点的双亲时,该结点的字符编码才会是另一个结点的字符编码的前缀。为了使不等长编码为前缀编码,可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树,为了获得文件的最短长度,特将每个字符的出现频率作为字符结点的权值赋予该结点上,求出此树的最小带权路径长度就等于文件的最短长度。因此,对文件进行压缩,就可以转化字符集中的所有字符作为叶子结点,字符出现的频率作为权值所产生的huffman 树的问题。基本思路大致有了后,接下来是对程序的编写工作,程序初步形成后,对其测试,发现了一些变量还没有声明的错误,对遗漏的变量进行了声明后,再次调试,发现一个比较大的问题,就是字符都能读入,但是不能进行编码,也即不能构造 huffman 树,最后经过检查发现原来是结点方面存在问题,最后加入 sum=2*count-1;语句,问题得到解决。 (该语句的作用是:例如提供了 3 个权值不同的结点,现在要构造 huffman 树,那就需要 5 个结点。 )五、测试结果 图 5(与图 6 同为测试结果) 图 6(与图 5 同为测试结果)被编码(部分字符):图 7.被编码后的文档被解码(部分文件):图 8.被解码后的文档六、用户使用说明用户运行本程序前,首先要在起工程文件下建立一个名字为 Huffman.txt 文本文档,再运行本程序后,第一步,按任意键来读取建立的 Huffman.txt 文本文档,再据程序中提示完成第二步操作,也即是讲压缩的文件以 Huffman 编码放入一个由用户自己建立的文本文档中,接着再根据提示完成第三步操作,即对要压缩的文件解压后放入由用户建立的任意名的文本文档中,由此完成操作。七、参考文献1 王昆仑,李红. 数据结构与算法. 北京:中国铁道出版社,2006 年 5 月。2 郑莉等.c+语言程序设计(第三版)M.北京:清华大学出版社,2003 年 12 月八、附录#include#include#include#includeusing namespace std;string remfile600000; /存放原文件字符的数组int remcount=0; /记录元素个数float bitecount=0; /记录二进制码的个数typedef struct /存放读入字符的类int count; /字符出现的个数char data; /字符 huffchar;int count=1; /记录 huff 数组中字符实际出现的个数 huffchar huff1000; /类的对象/文件读入部分和统计字符出现的频率bool char_judge(char c) /判断字符出现的函数for(int i=1;istr;fp.open(str.c_str();if(!fp) /检查文件是否打开cout0;k-)fps1;fp2.open(s1.c_str();if(!fp2) /检查文件是否打开coutinchar;if(inchar=1)ptr=huffmanptr.rchild;/查找相应编码对应 huffman 树中的位置else ptr=huffmanptr.lchild;if(huffmanptr.lchild=0&huffmanptr.rchild=0)/判断是否为叶子结点fp2huffptr.data;ptr=sum;/是叶子结点,将该结点的对应字符输入到文件中coutendl 请检查原文件huffman.txt与解压缩文件s1endlendlendl;cout*请检查*endl;/解压缩文件部分结束 /计算压缩比例void evaluating()float y1;y1=bitecount/8/remcount*100;cout压缩比例是:y1%endl;void main()cout 数据结构课程设计 endl;cout Huffman 树文件压缩与解压缩 endl;cout*endl;system(pause);read_file_count();creathuffman(); huffmancode();code_huffman_file();code_file_out();evaluating();coutendlendl 文件的压缩与解压缩完成endl;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号