综合实验报告格式--哈弗曼树--数据结构

《综合实验报告格式--哈弗曼树--数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华北科技学院《用哈夫曼编码实现文件压缩》实验报告《用哈夫曼编码实现文件压缩》实验报告课程名称《数据结构B》实验学期2014至2014学年第1学期学生所在系部计算机系年级2010专业班级网络B10-3学生姓名学号任课教师实验成绩华北科技学院《用哈夫曼编码实现文件压缩》实验报告一、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。三、实验设备与环境：微型计算机、Windows系列操

2、作系统、VisualC++6.0软件四、实验内容：根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。五、概要设计：在文件存储时，一个整型的字符要占用一个字节的空间，对于某些不常用的字符这样会造成空间的浪费，但如果用位来存储数据，可以将字符重新编码，使那些常用的字符存储空间相对短的，不常用的字符相对长些，可以节约空间。哈夫曼编码即是这样一个过程。用哈夫曼编码进行文件压缩，首先应对所用的字符进行哈夫曼变编码，在这之前应先对所用字符进行权值统计。在编码哈夫曼树的时候，选取两个权值最小的依次构造哈夫曼树，进行哈夫

3、曼编码时，使哈夫曼树的左孩子上的分支编码为0，右孩子上的分支编码为1。然后对文件进行压缩。压缩过程用到了文件的读写。六、详细设计：头文件的构造：头文件首先应用宏定义，对文件要用到的数据进行定义，然后定义了结构体类型，将所要到字符的权值，数据，双亲编号与孩子编号放在结构体中，使程序间的关系变得紧密。定义第二个结构体，其中包含结构体数组和树根的编号。定义指针，使其指向第二个结构体。接着类型定义，定义了结构体，其中包含字符原码值，哈夫曼编码值和哈夫曼编码值的长度，并将其取名为HaffCode。将程序所用到的函数包含在头文件里。哈夫曼树的构造：华北科技学院《用哈夫曼编码实现文件压缩》实验

4、报告在程序开头先对程序所用到的变量进行定义，包括指向结构体的指针，整型变量，权值最小的结点的编号，第二小的结点的编号，权值最小的结点的权值，第二小的结点的权值。接着为哈夫曼树分配空间，然后调用asserF函数对条件进行判断，看是否满足构造哈夫曼树的条件。对含有m个字符的结点构造哈夫曼树时，将产生(2m-1)个结点。为了便于程序进行，先利用循环结构对每个结点里的左右孩子及双亲编号进行初始化，然后将m个字符中的数据从0位开始依次存入各个结点中，用pht->ht[i].ww=w[i]实现字符权值的存储，用pht->ht[i].info=i实现字符数据的存储；剩下结点的权值全赋值为-1。

5、构造哈夫曼树是这个程序的核心，也是文件是否能压缩成功的关键。从结点中选择权值最小的结点的编号分别赋给firstMinIndex和secondMinIndex，权值也进行相应赋值，将两结点的权值相加后放到未放元素的结点处m+i；将这两个权值最小的结点的双亲编号都替换为m+i,而m+i处的左孩子放第一小的结点的编号，右孩子放第二小的结点的编号。然后从产生的m+i个结点中再找权值最小的两个，重复上述操作，直到所有的结点构成一棵树。文件在对字符进行哈夫曼编码时用到了位的运算，并且使用了递归的算法。统计权值：在统计权值时定义了两个数组，一个是字符型的数组，用于输入数据时的使用，另一个是结构

6、体类型的数组，其中包括字符域和权值域，用于统计权值时使用。首先输入数据，并将数据存储在字符类型的数组中，然后从第一个字符开始，使第一个数组中的数据与第二个数组中的字符进行比较，若相等，则字符相应的权值加1，若不相等，则将字符放入第二个数组中未放字符的数据域，权值加1。直到将第一个数组中的所有字符遍历完为止。（假设两数组分别为s1和s2，s1中含3n个字符，s2中含n个字符；s2定义如下所示）Structtongji{Chardata;Intw;};主函数：程序在运行的时候运用了文件的读写。和大多数程序一样，这个程序在最开始对所需的变量进行了定义，包括哈夫曼数组，输入文件名数组，输

7、出文件名数组，指向文件的指针等。首先根据条件判断文件是否已打开，若没有打开则输出pleaseenteryourfileaddress.。若打开则将argv赋给inputFileName和outputFileName，然后计算文件名的长度；将.rer连接到outputFileName的后面，以此来区分程序运行前后的文件。华北科技学院《用哈夫曼编码实现文件压缩》实验报告assertF函数的流程图：由主函数传来condition和errorMsg的值Condition的值为真？FT