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

学生学号Xxx实验课成绩学生实验报告书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名xxx学生姓名xxx学生专业班级xxxx2015-2016 学年 第 2 学期实验课程名称：数据结构与算法综合实验实验项目名称二叉树与赫夫曼图片压缩报告成绩实验者xx专业班级xxx组别同组者完成日期2016年5月2日第一部分：实验分析与设计（可加页）实验目的和要求1. 目的掌握树的存储结构掌握二叉树的三种遍历方法掌握Huffman树、Huffman编码等知识和应用使用C+、文件操作和Huffman算法实现“图片压缩程序”专题编程2. 要求针对一幅BMP格式的图片文件，统计256种不同字节的重复次数，以每 种字节重复次数作为权值，构造一颗有 256个叶子节点的哈夫曼二叉树。 利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。压缩后的文件与原图片文件同名，加上后缀.huf （保留原后缀），如pic.bmp压缩后 pic.bmp.huf二、分析与设计依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为： 读取图片文件、统计权值 生成Huffman树 生成Huffman编码 压缩图片文件 保存压缩的文件1. 数据结构的设计记录统计256种不同字节的重复次数使用整型数组。int weight256 = 0 ;二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方 式存储二叉树。Huffma n编码存储结构struct HTNodeint weight;/ 权值int pare nt;int Ichild;int rchild;char zifu;stri ng bia nma;；压缩文件的算法的数据结构256种字节重复的次数,为正确解压文件，除了要保存原文件长度外，还要保存原文件中 即权值。定义一个文件头，保存相关的信息：struct HEADchar type4;int len gth;int weight256;压缩文件时，定义一个内存缓冲区：typedef char * pBuffer;/其大小视原文件压缩后的大小2. 核心算法设计生成Huffman树和Huffman编码的算法void Select(HTNode huffTree,i nt m)int mi n, mi n2,i;min=mi n2=1000;for(i=0;ihuffTreei.weight)mi n2=mi n;min=huffTreei.weight ;x2=x1;x1=i;else if(mi n2huffTreei.weight)min 2=huffTreei.weight ;x2=i;void creatHuffma n(i nt huff)int i;int s=256;for(i=0;i2*s-1;i+)Huffma nTreei.pare nt =-1;Huffma nTreei.lchild =-1;Huffma nTreei.rchild =-1;for(int i1=0;i1s;i1+)Huffma nTreei1.weight=huffi1;for(i nt k=s;k n-1;i-)huffTreehuffTreei.lchild .bia nma =0; huffTreehuffTreei.rchild .bia nma =1;for(i=0,j=0;j n ;j+)while(huffTreei.pare nt !=-1)huffTreej.bia nma =huffTreehuffTreei.pare nt.bia nma+huffTreej.bia nma ;i=huffTreei.pare nt ;i=j+1;(2)压缩编码算法struct HEADchar type4;int len gth;int weight256;char Str2byte(co nst char * pBi nStr)char b=OxOO;for(int i=0;i8;i+)b=b1;if(pBi nStri=1) b=b|0x01;return b;bool In itHead(co nst char *pFile name,HEAD & sHead)char ch;/初始化文件strcpy(sHead.type,HUF);sHead .len gth=0;for(int i=0;i256;i+)sHead.weighti=0;ifstream in;in. ope n(pFile name,ios:bi nary);while(i n.get(ch) sHead.weight( un sig ned char)ch+;sHead .len gth+;coutsHead .len gth字节e ndl;return true;int En code(c onst char *pFile name,char * & pBuffer,c onst int n Size)pBuffer=(char *)malloc( nSize * sizeof(char)+10);if(!pBuffer)cout开辟缓冲区失败=8)/coutvvcdvv Str2byte(cd)vv; pBufferpos+=Str2byte(cd);/coutvpBufferpos-1vve ndl; for(int i=0;i0) pBufferpos+=Str2byte(cd);return 1;int WriteFile(const char * pFilename ,const HEAD sHead, char * pBuffer,const int nSize) /生成文件名char file name256=0;strcpy(file name,pFile name);int i;for( i=strle n(filen ame);file namei!=.;i-);file namei=0;strcat(file name,.huf);/以二进制流的形式打开文件FILE *out =fope n( file name ,wb);/写文件头fwrite( & sHead,sizeof(HEAD),1,out);/写压缩后的编码fwrite(pBuffer,sizeof(char), nSize,out);/关闭文件释放文件指针fclose(out);out=NULL;cout生成压缩文件vvfilenameendl;int len=sizeof(HEAD)+strle n( pFile name)+1+ nSize;return len;int compress(c onst char *pFile name,i nt weight256,co nst HEAD sHead)/计算缓冲区的大小int n Size=O;for(int i=0;i256;i+)n Size+=weighti*Huffma nTreei.bia nm a.le ngth();n Size=( nSize%8)? nSize/8+1: nSize/8;/cout n Size n Sizee ndl;char *pBuffer=NULL;En code(pFile name,pBuffer, nSize);/if(pBuffer=NULL)/ cout wron ge ndl; if(!pBuffer)return 0;int result=WriteFile(pFilename,sHead,pBuffer,nSize); return result;3. 测试用例设计使用一个文本文件作为压缩的例，观察其压缩比； 通过屏幕截图形成一个BM图片文件，观察其压缩比； 在互联网上搜索下载任意格式的图片文件，观察其压缩比。三、主要仪器设备及耗材1. 安装了 Windows 10或其它版本的 Windows操作系统的PC机1台2. PC机系统上安装了 Microsoft Visual Studio 2010开发环境第二部分：实验过程和结果(可加页)一、实现说明在Microsoft Visual Studio 2010集成开发环境中新建一个Win32控制台应用程序工程HfmCompressC on soleHfmCompressConsole工程中新建2组相关文件。第1组是实现依据图片文件构建其 Huffman编码 的头文件Huffman.h和源程序文件Huffman.cpp。第2组是实现图片文件压缩编码和写磁盘等功能 的头文件Compress.h和源程序文件Compress.cpp。Huffman.h存放与Huffman.cpp相关函数需要的数据类型的定义，函数原型的声明等。Compress.h存放与Compress.cpp相关函数需要的数据类型的定义，函数原型的声明等。最后新建一个main.cpp源文件，实现main函数按分析与设计中规定的流程调用Huffman.cpp和Compress.cpp的功能函数。二、调试说明(调试手段、过程及结果分析)调试主要内容为编写程序的语法正确性与否，程序逻辑的正确性与否。调试手段主要采用了 Microsoft Visual Studio 2010集成开发环境中 调试（D）”菜单中的调试方法或手段。即：F5:启动调试；F11:逐语句调试；F12：逐过程调试；F9:切换断点；ctrl+B :新建断点等。例如在统计图片文件中0-255取值的256个字节出现的次数函数中，设置断点并使用简单的文 本文件进行测试，发现了 没有扫描完整个文件而是中途跳出”的问题。通过断点出查看weight数 组的值以及通过逐语句跳出的处定位错误所在之处。找出问题的原因是以流的形式读入的字符定 义问题，char ch ； ch=fgetc （in ）；Weightch+;字符变量ch在转换成int时出现了负数。当将ch的定义修改Un sig ned char ch ；问 题解决。再例：文件编码压缩Encode（）函数会产生编码后的一个缓冲区 char *pBuffer ;写文件函 数会使用它直接写磁盘文件。调试过程中并没发现任何问题，就是不能成功地写后缀为.huf的文件。在相关函数中设置断点，观察缓冲区的情况，且编写屏幕输出缓冲区数据的程序段，发现缓 冲区是空的。通过在 Encode函数中以及 WriteFile 函数中做同样的跟踪调试，发现在 Encode函 数中建立的缓冲区数据并没有带出来，通过分析发现是缓冲区空间构建位置的问题，即不能放在 En code函数中。三、软件测试（测试效果.界面、综合分析和结论）1.测试效果界面2.综合分析和结论试验在压缩txt文件的时候没有问题，可以通过编译生成可执行文件，但是在进行图片的压 缩时出了问题，导致程序出错，所以我编写的哈夫曼树压缩文件不能正确压缩图片。第三部分：实验小结、收获与体会通过这次试验，我对 Huffman树的创建和Huffman编码的产生有了更深的理解，同时对于文 件的压缩有了更进一步的认识也更加理解了数据结构在实际应用中的作用。通过本次试验也使我感到自身编程能力的欠缺，在数据结构课程的学习中还有很多知识没有 熟练掌握，动手能力不强，在以后的学习中要不断加强知识的积累，提高自己的动手能力，