压缩图片实验实验报告书示例.pdf

学生学号 实验课成绩 学 生 实 验 报 告 书 实验课程名称 数据结构与算法综合实验 开课学院 计算机科学与技术学院 指导教师姓名 伍新华 学生姓名 学生专业班级 2015 - 2016 学年 第 2 学期 1 实验课程名称： 数据结构与算法综合 实验 实验项目名称 二叉树与赫夫曼图片压缩 报告 成绩 实验者 专 业 班 级 组别 同组者 完成 日期 年 月 日 第一部分：实验分析与设计（可加页） 一、 实验目的和要求 1.目的 掌握树的存储结构 掌握二叉树的三种遍历方法 掌握 Huffman 树、 Huffman 编码等知识和应用 使用 C+、文件操作和 Huffman 算法实现 “图片压缩程序 ”专题编程。 2.要求 针对一幅 BMP 格式的图片文件，统计 256 种不同字节的重复次数，以每种字 节重复次数作为权值，构造一颗有 256 个叶子节点的哈夫曼二叉树。 利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。 压缩后的文件与原图片文件同名，加上后缀 .huf（保留原后缀），如 pic.bmp 压缩后 pic.bmp.huf 二、 分析与设计 依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流 程为： 读取图片文件、统计权值 生成 Huffman 树 生成 Huffman 编码 压缩图片文件 保存压缩的图片文件 1.数据结构的设计 记录统计 256 种不同字节的重复次数使用整型数组。 Unsigned int weight256; 二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态 二叉链表方式存储二叉树。 Struct HTNode Unsigned int weight; Int parent; Int lchild; Int rchild; ; Typedef HTNode *HuffmanTree; 1 Huffman 编码存储结构 定义一二维数组： char HufCode256;因考虑每个字节的 Huffman 编码长度 不一样，可使用字符串指针数组： Char *HuffmanCode256; 压缩文件的算法的数据结构 为正确解压文件，除了要保存原文件长度外，还要保存原文件中 256 种字节重 复的次数，即权值。定义一个文件头，保存相关的信息： Struct fHEAD Char type4; /文件类型 Unsigned int length; /原文件的长度 Unsigned char weight256; /权值 压缩文件时，定义一个内存缓冲区： Unsigned char *pBuffer; /其大小视原文件压缩后的大小 2.核心算法设计 1）生成 Huffman 树算法 Input: Unsigned int weight256; / / 权 值 Output: HuffmanTree pHT512; / / 哈 夫 曼 树 ， 静 态 二 叉 链 表 Int root； / / 树 的 根 节 点 指 针 Process: int CreateHuffmanTree(HuffmanTree for ( p = pHT+1, i = 1; i =8) /截取字符串左边的 8 个字符，编码成字节 /Str2Byte 将由 8 个 1、 0 组成的组成的串转换成一个字节 pBufferpos+=Str2Byte(cd); /删除已编码成字节的 8 个字符 for(int i=0;i0)pBufferpos+=Str2Byte(cd); fclose(in); /关闭文件 3.测试用例设计 3 使用一个文本文件作为压缩的例，观察其压缩比； 通过屏幕截图形成一个 BMP 图片文件，观察其压缩比； 在互联网上搜索下载任意格式的图片文件，观察其压缩比。 三、主要仪器设备及耗材 1 安装了 Windows XP 或 Windows 7 或其它版本的 Windows 操作系统的 PC 机 1 台 2 PC 机系统上安装了 Microsoft Visual Studio 2010 开发环境 第二部分：实验过程和结果（可加页） 一、 实现说明 在 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 存放与 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 的定义修改为 Unsigned char ch；问题解决。 再例：文件编码压缩 Encode（）函数会产生编码后的一个缓冲区 char *pBuffer； 写文件函数会使用它直接写磁盘文件。调试过程中并没发现任何问题，就是不能成 功地写后缀为 .huf 的文件。在相关函数中设置断点，观察缓