程序设计报告(哈夫曼压缩).docVIP

软件工程学院 《程序设计实践(下)》设计报告 （哈夫曼压缩） 姓名 求春磊 学号专业班级 软件3班 提交日期 12.30 成绩 指导教师 问题解析（对问题的分析、解题思路与解题方法） 经整理后原问题可以分解为： 文件读入、统计字符频率、构造哈夫曼树 由哈夫曼树得出每个字符的编码 图形化输出哈夫曼树、哈夫曼编码 压缩、解压和比较 本人负责压缩、解压和比较部分。 解题思路： 压缩只需要将原文件内容中的每一个字符转换为相对应的编码即可，压缩也只需要将编码转换为原来的字符内容即可。比较这一步也很简单，一个是对原文件与压缩后文件的大小比较并得出压缩率；另一个是将原文与经过压缩解压后的文件内容进行比较，检查压缩与解压的正确性。当然，比较这一步可以很好的验证我之前的压缩与解压步骤的正确性。 解题方法： 以上是从刚开始就明确的解决思路，不过后来在实现的时候遇到一点小问题——没学过二进制的存储，因此也就没法直接将字符转换为二进制内容转换文件。同样的也不能将压缩后的文件进行解压，当然...这只是个小问题。在比较这方面，遇到的问题是：文件的读取与写入。表示不擅长，百度了好久，又调试了很久才找到一个可靠的函数。囧。 关于二进制的问题，其实也很容易解决，只要联想到char型的字符是一个字节，而且更关键的是它完全符合ascii码。于是利用char轻松完成压缩步骤。解压与压缩大同小异，不过是在读取的时候进行一下控制就可以马上搞定的。至此，第一个问题基本上可以解决了。 至于第二个问题，文件的读写。不知是技术性问题还是之前找的函数真的行不通，找了好久，排除了很多函数。最后选定使用fgetc（）函数。对于这个函数...虽然不太明白为什么它可以一直读下去而不是每次都从头开始读写。不过目前能用就行。 任务分工及进度计划 小组成员：王倩，求春磊，章力挺，张琪 分工： 王倩：文件的读写操作 求春磊：文件的压缩、解压和比较 章力挺：构造哈弗曼树，获取哈弗曼编码 张祺：图形、界面的美化及其余三人的编码联接 进度计划： 由王倩、章力挺和张琪先完成各自的部分，然后我根据所构造的哈夫曼树和哈夫曼编码进行文件的压缩、解压和比较。最后，再由张祺将我的部分插入写好的主题文件中。任务完成。 数据结构选择、算法设计（伪代码，算法思想） 结构： 哈夫曼树。 算法设计： 之前其他组员已经完成了哈夫曼树的构建和哈弗曼编码的获取，我只要进行字符与编码的转化就行了。 其中，已完成的哈夫曼树结构采用的是数组模拟的形式，但与树结构大同小异，在向负责构造的组员了解原理后便进行压缩过程。 void yasuo( ){ c = fgetc( fq );//这里就是百度到的那个让我觉得神奇的函数 while( c != EOF ){ for( i=0 ; hafucode[c][i] ; i++ ){//读取哈夫曼编码 flag++;//标记已有长度 x = x*2 + hafucode[c][i] - 0; if( flag == 7 )//当长度满足一个ascii长度时进行写入 { fprintf( fq2, %c, x); flag = 0; x = 0;//初始化操作 } }c = fgetc( fq ); } if( flag != 7 ){ x = x 7-flag; fprintf( fq2, %c, x); }//当最后一个编码不能满足一个ascii长度的时候采用填充的方式 }//压缩文件的函数yasuo( ); void jieya( ) { c = fgetc( fq );//文件读取 flag = Max;//初始化，将flag初始化为哈夫曼树的头结点所在位置 while( c != EOF ) { for( i = 6; i =0 ; i-- ) {//压缩是设置为按七位ascii码压缩，所以解压是也是对应七位解压 d = ( c i ) % 2; //判断左孩子还是右孩子 if( d == 0 )//左孩子 flag = node[flag].left_child; Else//右孩子 fl