武汉理工大学数据结构与算法综合实验哈夫曼树(1)

1、学生学号 Xxx实验课成绩学 生 实 验 报 告 书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名xxx学生姓名xxx学生专业班级xxxx2015-2016学年第2学期8实验课程名称： 数据结构与算法综合实验 实验项目名称二叉树与赫夫曼图片压缩报告成绩实验者xx专业班级xxx组别同组者 完成日期2016年5月2日第一部分：实验分析与设计（可加页）一、 实验目的和要求1.目的 = 掌握树的存储结构 = 掌握二叉树的三种遍历方法 = 掌握 Huffman 树、Huffman 编码等知识和应用 = 使用 C+、文件操作和 Huffman 算法实现“图片压缩程序”专题编程。

2、2.要求=针对一幅 BMP 格式的图片文件，统计 256 种不同字节的重复次数，以每 种字节重复次数作为权值，构造一颗有 256 个叶子节点的哈夫曼二叉树。 =利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。=压缩后的文件与原图片文件同名，加上后缀.huf（保留原后缀），如 pic.bmp 压缩后 pic.bmp.huf二、 分析与设计依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为： 读取图片文件、统计权值 生成 Huffman 树 生成 Huffman 编码 压缩图片文件 保存压缩的文件1. 数据结构的设计l 记录统计256种不同字节的重复次数使用整型数组。 i

3、nt weight256 = 0 ;l 二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方式存储二叉树。l Huffman编码存储结构 struct HTNodeint weight;/权值int parent;int lchild;int rchild;char zifu;string bianma;l 压缩文件的算法的数据结构 为正确解压文件，除了要保存原文件长度外，还要保存原文件中256种字节重复的次数，即权值。定义一个文件头，保存相关的信息： struct HEADchar type4;int length;int weight256;压缩文件时，定义一个内

4、存缓冲区： typedef char * pBuffer; /其大小视原文件压缩后的大小2.核心算法设计(1)生成Huffman树和Huffman编码的算法void Select(HTNode huffTree,int m)int min,min2,i;min=min2=1000;for(i=0;ihuffTreei.weight )min2=min;min=huffTreei.weight ;x2=x1;x1=i;else if(min2huffTreei.weight )min2=huffTreei.weight ;x2=i;void creatHuffman(int huff)int i

5、;int s=256;for(i=0;i2*s-1;i+)HuffmanTreei.parent =-1;HuffmanTreei.lchild =-1;HuffmanTreei.rchild =-1;for(int i1=0;i1s;i1+)HuffmanTreei1.weight=huffi1;for(int k=s;kn-1;i-)huffTreehuffTreei.lchild .bianma =0;huffTreehuffTreei.rchild .bianma =1;for(i=0,j=0;jn;j+)while(huffTreei.parent !=-1)huffTreej.bi

6、anma =huffTreehuffTreei.parent.bianma +huffTreej.bianma ;i=huffTreei.parent ;i=j+1;(2)压缩编码算法struct HEADchar type4;int length;int weight256;char Str2byte(const char * pBinStr)char b=0x00;for(int i=0;i8;i+)b=b1;if(pBinStri=1)b=b|0x01;return b;bool InitHead(const char *pFilename,HEAD &sHead)char ch;/初始

7、化文件strcpy(sHead.type,HUF);sHead.length=0;for(int i=0;i256;i+)sHead.weighti=0;ifstream in;in.open(pFilename,ios:binary);while(in.get(ch) sHead.weight(unsigned char)ch+;sHead.length+; coutsHead.length字节endl;return true;int Encode(const char *pFilename,char * &pBuffer,const int nSize) pBuffer=(char *)m

8、alloc(nSize * sizeof(char)+10);if(!pBuffer)cout开辟缓冲区失败=8)/coutcd Str2byte(cd) ;pBufferpos+=Str2byte(cd);/coutpBufferpos-1endl;for(int i=0;i0)pBufferpos+=Str2byte(cd);return 1;int WriteFile(const char * pFilename ,const HEAD sHead, char * pBuffer,const int nSize)/生成文件名char filename256=0;strcpy(filena

9、me,pFilename);int i;for( i=strlen(filename);filenamei!=.;i-); filenamei=0;strcat(filename,.huf);/以二进制流的形式打开文件FILE *out =fopen(filename ,wb);/写文件头fwrite( & sHead,sizeof(HEAD),1,out);/写压缩后的编码fwrite(pBuffer,sizeof(char),nSize,out);/关闭文件释放文件指针fclose(out);out=NULL;cout生成压缩文件filenameendl;int len=sizeof(HE

10、AD)+strlen(pFilename)+1+nSize;return len;int compress(const char *pFilename,int weight256,const HEAD sHead)/计算缓冲区的大小int nSize=0;for(int i=0;i256;i+)nSize+=weighti*HuffmanTreei.bianma.length();nSize=(nSize%8)?nSize/8+1:nSize/8;/coutnSizenSizeendl;char *pBuffer=NULL;Encode(pFilename,pBuffer,nSize);/if

11、(pBuffer=NULL)/ cout wrongendl;if(!pBuffer)return 0;int result=WriteFile(pFilename,sHead,pBuffer,nSize);return result;3.测试用例设计l 使用一个文本文件作为压缩的例，观察其压缩比； l 通过屏幕截图形成一个BMP图片文件，观察其压缩比； l 在互联网上搜索下载任意格式的图片文件，观察其压缩比。三、主要仪器设备及耗材1.安装了Windows 10或其它版本的Windows操作系统的PC机1台2.PC机系统上安装了Microsoft Visual Studio 2010开发环境第

12、二部分：实验过程和结果（可加页）一、 实现说明在Microsoft Visual Studio 2010集成开发环境中新建一个Win32控制台应用程序工程HfmCompressConsole。 HfmCompressConsole工程中新建2组相关文件。第1组是实现依据图片文件构建其Huffman编码的头文件Huffman.h和源程序文件Huffman.cpp。第2组是实现图片文件压缩编码和写磁盘等功能的头文件Compress.h和源程序文件Compress.cpp。 Huffman.h存放与Huffman.cpp相关函数需要的数据类型的定义，函数原型的声明等。Compress.h存放与Com

13、press.cpp相关函数需要的数据类型的定义，函数原型的声明等。 最后新建一个main.cpp源文件，实现main函数按分析与设计中规定的流程调用Huffman.cpp和Compress.cpp的功能函数。二、 调试说明（调试手段、过程及结果分析）调试主要内容为编写程序的语法正确性与否，程序逻辑的正确性与否。调试手段主要采用了Microsoft Visual Studio 2010集成开发环境中“调试（D）”菜单中的调试方法或手段。即：F5：启动调试；F11：逐语句调试；F12：逐过程调试；F9：切换断点；ctrl+B：新建断点等。 例如在统计图片文件中0-255取值的256个字节出现的次数

14、函数中，设置断点并使用简单的文本文件进行测试，发现了“没有扫描完整个文件而是中途跳出”的问题。通过断点出查看weight数组的值以及通过逐语句跳出的处定位错误所在之处。找出问题的原因是以流的形式读入的字符定义问题，char ch；ch=fgetc（in）；Weightch+;字符变量ch在转换成int时出现了负数。当将ch的定义修改Unsigned char ch；问题解决。 再例：文件编码压缩Encode（）函数会产生编码后的一个缓冲区char *pBuffer；写文件函数会使用它直接写磁盘文件。调试过程中并没发现任何问题，就是不能成功地写后缀为.huf的文件。在相关函数中设置断点，观察缓冲区的情况，且编写屏幕输出缓冲区数据的程序段，发现缓冲区是空的。通过在Encode函数中以及WriteFile函数中做同样的跟踪调试，发现在Encode函数中建立的缓冲区数据并没有带出来，通过分析发现是缓冲区空间构建位置的问题，即不能放在Encode函数中。三、 软件测试（测试效果.界面、综合分析和结论）1测试效果.界面2综合分析和结论试验在压缩txt文件的时候没有问题，可以通过