综合实验实验报告书示例

学生学号实验课成绩学生实验报告书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名伍新华学生姓名学生专业班级2015--2016学年第2学期11实验课程名称：数据结构与算法综合实验实验项目名称二叉树与赫夫曼图片压缩报告成绩实验者专业班级组别同组者完成日期年月日第一部分：实验分析与设计（可加页）一、实验目的和要求1.目的z掌握树的存储结构z掌握二叉树的三种遍历方法z掌握Huffman树、Huffman编码等知识和应用z使用C++、文件操作和Huffman算法实现“图片压缩程序”专题编程。2.要求z针对一幅BMP格式的图片文件，统计256种不同字节的重复次数，以每种字节重复次数作为权值，构造一颗有256个叶子节点的哈夫曼二叉树。z利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。z压缩后的文件与原图片文件同名，加上后缀.huf（保留原后缀），如pic.bmp压缩后pic.bmp.huf二、分析与设计依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为：①读取图片文件、统计权值②生成Huffman树③生成Huffman编码④压缩图片文件⑤保存压缩的图片文件1.数据结构的设计z记录统计256种不同字节的重复次数使用整型数组。Unsignedintweight[256];z二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方式存储二叉树。StructHTNode{Unsignedintweight;Intparent;Intlchild;Intrchild;};TypedefHTNode*HuffmanTree;2zHuffman编码存储结构定义一二维数组：charHufCode[256][];因考虑每个字节的Huffman编码长度不一样，可使用字符串指针数组：Char*HuffmanCode[256];z压缩文件的算法的数据结构为正确解压文件，除了要保存原文件长度外，还要保存原文件中256种字节重复的次数，即权值。定义一个文件头，保存相关的信息：StructfHEAD{Chartype[4];//文件类型Unsignedintlength;//原文件的长度Unsignedcharweight[256];//权值}压缩文件时，定义一个内存缓冲区：Unsignedchar*pBuffer;//其大小视原文件压缩后的大小2.核心算法设计1）生成Huffman树算法Input:Unsignedintweight[256];//权值Output:HuffmanTreepHT[512];//哈夫曼树，静态二叉链表Introot；//树的根节点指针Process:intCreateHuffmanTree(HuffmanTree&pHT[],Unsignedintweight[]){pHT=(HuffmanTree)malloc((512)*sizeof(HTNode));for(p=pHT+1,i=1;i256;++i,++p)*p={weight[i-1],0,0,0};for(;i=511;++i,++p)*p={0,0,0,0};for(i=256;i=511;++i){//构造n-1个分支结点Select(pHT,i-1,s1,s2);//pHT[1..i-1]中parent为0的w最小的2个结点HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}Return511;}2）生成Huffman编码算法Input:HuffmanTreepHT[512];n;//n为叶子节点数Output:Char*HuffmanCode[256];Process:intHuffmanCoding(HuffmanCode&pHC,HuffmanTree&pHT，intn){pHC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=“\0”;3for(i=1;i=n;++i){//为n个叶子结点编码start=n–1;for(c=i,f=pHT[i].parent;f!=0;c=f,f=pHT[f].parent)if(pHT[f].lchild==c)cd[--start]=“0”;elsecd[--start]=“1”;//判断c是f的左还是右孩子pHC[i]=(char*)malloc((n-start)*sizeof(char));Strcpy(pHC[i],&cd[start]);}free(cd);}3）压缩编码算法Input:pFileName（磁盘文件名串）;HuffmanCodepHC(哈夫曼编码);Output:pBuffer(压缩编码的缓冲区)Process:intEncode(constchar*pFileName,constHuffmanCodepHC,char*pBuffer){//压缩编码//以二进制流形式打开文件FILE*in=fopen(pFileName,rb);//开辟缓冲区pBuffer=(char*)malloc(nSize*sizeof(char));if(!pBuffer){return0;}charcd[SIZE]={'\0'};//工作区intpos=0;//缓冲区指针unsignedcharch;//扫描文件，根据Huffman编码表对其进行压缩，压缩结果暂存缓冲区while(!feof(in)){ch=fgetc(in);strcat(cd,pHC[ch]);//从pHC复制编码串到cdwhile(strlen(cd)=8){//截取字符串左边的8个字符，编码成字节//Str2Byte将由8个1、0组成的组成的串转换成一个字节pBuffer[pos++]=Str2Byte(cd);//删除已编码成字节的8个字符for(inti=0;iSIZE-8;i++)cd[i]=cd[i+8];}}if(strlen(cd)0)pBuffer[pos++]=Str2Byte(cd);fclose(in);//关闭文件}3.测试用例设计4z使用一个文本文件作为压缩的例，观察其压缩比；z通过屏幕截图形成一个BMP图片文件，观察其压缩比；z在互联网上搜索下载任意格式的图片文件，观察其压缩比。三、主要仪器设备及耗材1．安装了WindowsXP或Windows7或其它版本的Windows操作系统的PC机1台2．PC机系统上安装了MicrosoftVisualStudio2010开发环境第二部分：实验过程和结果（可加页）一、实现说明在MicrosoftVisualStudio2010集成开发环境中新建一个Win32控制台应用程序工程HfmCompressConsole。HfmCompressConsole工程中新建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的功能函数。二、调试说明（调试手段、过程及结果分析）调试主要内容为编写程序的语法正确性与否，程序逻辑的正确性与否。调试手段主要采用了MicrosoftVisualStudio2010集成开发环境中“调试（D）”菜单中的调试方法或手段。即：F5：启动调试；F11：逐语句调试；F12：逐过程调试；F9：切换断点；ctrl+B：新建断点等。例如在统计图片文件中0-255取值的256个字节出现的次数函数中，设置断点并使用简单的文本文件进行测试，发现了“没有扫描完整个文件而是中途跳出”的问题。通过断点出查看weight数组的值以及通过逐语句跳出的处定位错误所在之处。找出问题的原因是以流的形式读入的字符定义问题，charch；ch=fgetc（in）；Weight[ch]++;字符变量ch在转换成int时出现了负数。当将ch的定义修改为Unsignedcharch；问题解决。再例：文件编码压缩Encode（）函数会产生编码后的一个缓冲区char*pBuffer；写文件函数会使用它直接写磁盘文件。调试过程中并没发现任何问题，就是不能成功地写后缀为.huf的文件。在相关函数中设置断点，观察缓冲区的情况，且编写屏幕输出缓冲区数据的程序段，发现缓冲区是空的。通过在Encode函数中以及WriteFile函数中做同样的跟踪调试，发现在Encode函数中建立的缓冲区数据并没有带出来，通过分析发现是缓冲区空间构建位置的问题，即不能放在Encode函数中。三、软件测试（测试效果.界面、综合分析和结论）1．测试效果.界面使用屏幕截图编辑成bmp图片文件pic.bmp测试哈夫曼压缩程序效果截图如下各图。图1为程序的文件名输入界面；图2为对本例pic.bmp文件依据其不同字节出现的次数为权（Weight列）进行哈夫曼编码（得到的部分编码信息HuffmanCode列），Byte列为编码的字节编号；图3为其压缩比相关信息。图4为一文本文件例的压缩比相关信息。图1：输入文件名界面图2：针对pic.bmp产生的部分不同权值字节的哈夫曼编码信息5图3：pic.bmp压缩文件写磁盘及压缩比情况图4：文本文件（本程序的main函数）压缩比信息2．综合分析和结论通过上述测试用例的效果截图，可以看出：使用哈夫曼编码对格式为bmp的图片文件的压缩比在50%左右，但对已经压缩的图片文件或文本文件的压缩情况不佳。实际测试还使用了jpg格式的文件，限于篇幅没有截图过来，其压缩比为100%，即没有压缩。Main.cpp的压缩比为213%，主要有两个原因，一是文件本身很小，另一个是压缩文件要存储相关的压缩信息（原文件各字节的权值及其他），相比一个小文件，其长度比例成了很重要的因素。第三部分：实验小结、收获与体会6