文档介绍：《用哈夫曼编码实现文件压缩》
实验报告
课程名称《数据结构B》
实验学期 2014 至 2014 学年第 1 学期
学生所在系部计算机系
年级 2010 专业班级网络B10-3
学生姓名学号
任课教师
实验成绩
一、实验题目:
用哈夫曼编码实现文件压缩
二、实验目的:
了解文件的概念。
掌握线性链表的插入、删除等算法。
3、掌握Huffman树的概念及构造方法。
4、掌握二叉树的存储结构及遍历算法。
5、利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理。
三、实验设备与环境:
微型计算机、Windows 系列操作系统、Visual C++
四、实验内容:
根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩。
五、概要设计:
在文件存储时,一个整型的字符要占用一个字节的空间,对于某些不常用的字符这样会造成空间的浪费,但如果用位来存储数据,可以将字符重新编码,使那些常用的字符存储空间相对短的,不常用的字符相对长些,可以节约空间。哈夫曼编码即是这样一个过程。
用哈夫曼编码进行文件压缩,首先应对所用的字符进行哈夫曼变编码,在这之前应先对所用字符进行权值统计。在编码哈夫曼树的时候,选取两个权值最小的依次构造哈夫曼树,进行哈夫曼编码时,使哈夫曼树的左孩子上的分支编码为0,右孩子上的分支编码为1。
然后对文件进行压缩。压缩过程用到了文件的读写。
六、详细设计:
头文件的构造:
头文件首先应用宏定义,对文件要用到的数据进行定义,然后定义了结构体类型,将所要到字符的权值,数据,双亲编号与孩子编号放在结构体中,使程序间的关系变得紧密。定义第二个结构体,其中包含结构体数组和树根的编号。定义指针,使其指向第二个结构体。接着类型定义,定义了结构体,其中包含字符原码值,哈夫曼编码值和哈夫曼编码值的长度,并将其取名为HaffCode。将程序所用到的函数包含在头文件里。
哈夫曼树的构造:
在程序开头先对程序所用到的变量进行定义,包括指向结构体的指针,整型变量,权值最小的结点的编号,第二小的结点的编号,权值最小的结点的权值,第二小的结点的权值。
接着为哈夫曼树分配空间,然后调用asserF函数对条件进行判断,看是否满足构造哈夫曼树的条件。对含有m个字符的结点构造哈夫曼树时,将产生(2m-1)个结点。为了便于程序进行,先利用循环结构对每个结点里的左右孩子及双亲编号进行初始化,然后将m个字符中的数据从0位开始依次存入各个结点中,用pht->ht[i].ww=w[i]实现字符权值的存储, 用pht->ht[i]. info=i实现字符数据的存储;剩下结点的权值全赋值为-1。
构造哈夫曼树是这个程序的核心,也是文件是否能压缩成功的关键。从结点中选择权值最小的结点的编号分别赋给firstMinIndex和secondMinIndex,权值也进行相应赋值,将两结点的权值相加后放到未放元素的结点处m+i;将这两个权值最小的结点的双亲编号都替换为m+i,而m+i处的左孩子放第一小的结点的编号,右孩子放第二小的结点的编号。然后从产生的m+i个结点中再找权值最小的两个,重复上述操作,直到所有的结点构成一棵树。文件在对字符进行哈夫曼编码时用到了位的运算,并且使用了递归的算法。
统计权值:
在统计权值时定义了两个数组,一个是字符型的数组,用于输入数据时的使用,另一个是结构体类型的数组,其中包括字符域和权值域,用于统计权值时使用。
首先输入数据,并将数据存储在字符类型的数组中,然后从第一个字符开始,使第一个数组中的数据与第二个数组中的字符进行比较,若相等,则字符相应的权值加1,若不相等,则将字符放入第二个数组中未放字符的数据域,权值加1。直到将第一个数组中的所有字符遍历完为止。(假设两数组分别为s1和s2,s1中含3n个字符,s2中含n个字符;s2定义如下所示)
Struct tongji
{
Char data;
Int w;
};
主函数:
程序在运行的时候运用了文件的读写。和大多数程序一样,这个程序在最开始对所需的变量进行了定义,包括哈夫曼数组,输入文件名数组,输出文件名数组,指向文件的指针等。
首先根据条件判断文件是否已打开,若没有打开则输出please enter your file address.\n。若打开则将argv赋给inputFileName和outputFileName,然后计算文件名的长度;,以此来区分程序运行前后的文件。
assertF函数的流程图:
由主函数传来condition和 errorMsg的值
C