综合实验实验报告书示例.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 weight[256]; 二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态 二叉链表方式存储二叉树。 Struct HTNode{ Unsigned int weight; Int parent; Int lchild; Int rchild; }; Typedef HTNode *HuffmanTree; 1 Huffman编码存储结构 定义一二维数组：char HufCode[256][];因考虑每个字节的 Huffman 编码长度 不一样，可使用字符串指针数组： Char *HuffmanCode[256]; 压缩文件的算法的数据结构 为正确解压文件，除了要保存原文件长度外，还要保存原文件中 256 种字节重 复的次数，即权值。定义一个文件头，保存相关的信息： Struct fHEAD { Char type[4]; //文件类型 Unsigned int length; //原文件的长度 Unsigned char weight[256]; //权值 } 压缩文件时，定义一个内存缓冲区： Unsigned char *pBuffer; //其大小视原文件压缩后的大小 2.核心算法设计 1）生成Huffman树算法 Input: Unsigne