2015
学生学号
-- 2016
Xxx
实验课成绩
学生实验报告书
实验课程名称
数据结构与算法综合实验 开课学院 计算机科学与技术学院
指导教师姓名
xxx 学生姓名
xxx 学生专业班级
xxxx
学年
第 2 学期
1
实验课程名称：
实验项目名称
实验者 同组者
数据结构与算法综合实验
二叉树与赫夫曼图片压缩
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 weight[256] = { 0 };
二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方 式存储二叉树。
Huffman编码存储结构
struct HTNode
{
int weight;// int parent;
权值
1
武汉理工大学数据结构与算法综合实验哈夫曼树(1)
