数据结构实验报告.docx

《用哈夫曼编码实现文件压缩》
实验报告
课程名称数据结构
实验学期 2015 至 2016 学年第一学期
学生所在系部计算机学院
年级 2014 专业班级物联B142班
学生姓名杨文铎学号 201407054201
任课教师白磊
实验成绩
实验题目:
用哈夫曼编码实现文件压缩
二、实验目的:
1、了解文件的概念。
2、掌握线性表的插入、删除的算法。
3、掌握Huffman树的概念及构造方法。
4、掌握二叉树的存储结构及遍历算法。
5、利用Haffman树及Haffman编码,掌握实现文件压缩的一般原理。
三、实验设备与环境:
微型计算机、Windows系列操作系统、Visual C++
四、实验内容:
根据ascii码文件中各ascii字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩。
五、概要设计:
本次实验采用将字符用长度尽可能短的二进制数位表示的方法,即对于文件中出现的字符,无须全部都用S为的ascii码进行存储,根据他们在文件中出现的频率不同,我们利用Haffman算法使每个字符能以最短的二进制数字符进行存储,已达到节省存储空间,压缩文件的目的,解决了压缩需要采用的算法,程序的思路已然清晰:
1、统计需压缩文件中的每个字符出现的频率
2、将每个字符的出现频率作为叶子节点构建Haffman树,然后将树中结点引向其左孩子的分支标“0”,引向其右孩子的分支标“1”;每个字符的编码即为从根到每个叶子的路径上得到的0、1序列,这样便完成了Haffman编码,将每个字符用最短的二进制字符表示。
3、打开需压缩文件,再将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出。
文件压缩结束。
详细设计:
(1)构造haffman树的方法一haffman算法
构造haffman树步骤:
根据给定的n个权值{w1,w2,w3…….wn},构造n棵只有根结点的二叉树,令起权值为wj。
在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和。
在森林中删除这两棵树,同时将得到的二叉树加入森林中。
重复上述两步,知道只含一棵树为止,这棵树即哈夫曼树。
对于haffman的创建算法,有以下几点说明:
这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式,这种空间上的消耗带来了算法实现上的便捷。
由于对于最后生成的Haffman树,所有叶子结点均为从一个内部树扩充出去的,所以,当外部叶子节点数为m个时,内部结点数为m-1,整个Haffman树的需要的结点数为2m-1。
初始化Haffman树分两步进行,现将所有结点赋值,再将前m个叶子结点赋初值。
在查找权值最小并且父结点为空的两个结点时,通过逐个比较,将两结点的位置下标与权值分别保存。方便在与其父结点建立联系时调用。
开始
定义Haffman树
i++
初始化Haffman树
将下标为m+i的结点作为所找出的两节点的父结点,建立联系
i=0
i<m-1
在前m+i个结点中找出权值最小且父结点为空的两结点
Haffman创建完毕
(2)压缩过程的实现