基于哈夫曼编码实现文本文件的压缩和解压缩实验报告模板

本科学生设计性实验报告

软件工程技能实践Ⅰ

项目组长 陈启 学号＿ 0154225 专 业 软件工程 班级＿15软件 7 班 成 员 陈启 杨林昌 邓志远 万胜 实验项目名称＿

指导教师及职称＿ ＿讲师 ＿ ＿ 开课学期 2015 至 2016 学年 第二 学期

一、 实验设计方案

实验名称：基于哈夫曼编码实现文本文件的压缩和解压缩 实验时间：2016-7-1—2016-7-7 实验场地：H113 成员角色：程序员：陈启 杨林昌 测试员：万胜 邓志远 文档员：杨林昌 邓志远 软件环境：Windows XP、VC++6.0

1、 实验任务与目的（简单介绍实验内容，说明实验任务和目的） 1.1实验内容

根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。对于给定的一组字符，可以根据其权值进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。能够分析文件，统计文件中出现的字符，再对文件进行编码，实现文件的压缩和解压缩，能够对于文件的压缩，比例进行统计，能够打印文件。分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩得到解压文件。

1.2实验任务和目的 1.2.1了解文件的概念。

1.2.2掌握线性链表的插入、删除等算法。 1.3.3掌握Huffman树的概念及构造方法。 1.4.4掌握二叉树的存储结构及遍历算法。

1.5.5利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

2、实验思路（详细描述解决问题的整体思路、涉及的算法思想及数据结构等） 2.1整体思路

统计字符，得出统计出字符的权值 n 生成哈夫曼树

2.2涉及的算法思想及数据结构： 2.2.1输入要压缩的文件

首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的 项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。若打不开，则继续输入。 2.2.2读文件并计算字符频率

文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间， 用读取的字符减去字符结束符作为下标记录字符的频率。 2.2.3根据字符的频率，利用Huffman编码思想创建Huffman树

将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为

生成二进制文件 生成对应文件 根据哈夫曼树编码 根据哈夫曼树解码 建立哈夫曼树 对编码进行压缩 对二进制文件进行解码 左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结

点。

2.2.4由创建的Huffman树来决定字符对应的编码，进行文件的压缩

根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1。读取文件，依次将每个字符用他们的编码表示，即完成一次编码。 2.2.5解码压缩即根据Huffman树进行译码

读取编码文件，依据创建的Huffman树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是‘1’时，指针指向当前所指结点的右孩子，当读取的字符是‘0’时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时）。将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件 2.2.6Huffman算法

（1）根据给定的n个权值{}构成n棵二叉树的集合F={}，其中每棵二叉树中只有一个带权为的根结点，其左右子树为空。

（2）在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 （3）在F中删除这两棵树，同时将新达到的二叉树加入F中。 （4）重复（2）和（3），直到F只含一棵树为止。 2.2.7Huffman编码

假设每种字符在电文中出现的次数为，其编码长度为，电文中只有n种字符，则电文总长为。对应到二叉树上，若置为叶子结点的权，恰为从根到叶子结点的路径长度，则恰为二叉树上的带权路径长度。由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率做权，设计一棵Huffman树的问题，由此得到的二进制前缀编码即为Huffman编码。 2.2.8 压缩过程

前提：与输入的路径对应的文件为txt格式。 （1）构造Huffman树：算法如3.2.1所示。

（2）将Huffman树编码：初始化编码数组，并遍历Huffman树，得到各个字符的编码，并保存为.txt文件。

（3）将.txt文件中的内容读取出来，找到对应的Huffman编码，并将相应的Huffman编码写入.txt文件中。

2.2.9 解压过程

前提：与输入的路径对应的文件为txt格式，且输入的路径对应的xxx.cod文件有对应的Huffman编码文件xxx.txt存在。

（1）由.txt文件载入Huffman编码的数组。

（2）读取.txt文件的内容，并找到其对应的字符写入新的.txt文件。

二、实验结果与分析

1、程序结构（程序结构图，主要函数的功能描述，算法实现的细节等）

1.1主函数流程图： 弹出“打开”对话框等待用户选择 开始 主函数 压缩文件 解压文件 单击按钮 帮助 弹出“打开”对话框等待用户选择 否

路径合法？ 输出程序介绍指南，为用户提供帮助 否 路径合法？ 弹出错误信息“请选择txt文本文件” 是 aa=0 输出字符、哈弗曼编码、压缩前后文件长度、压缩率、压缩时间 是 aa=1 弹出错误信息“请选择cod文件” 结束

2.2主要函数的功能描述，算法实现的细节

—————————————————————————————————————— 2、测试设计与数据（设计充足合理的测试用例，说明测试策略）

—————————————————————————————————————— 3、实验现象及结果（应用文字和程序运行的截图说明测试现象，并解释结果）

—————————————————————————————————————— 4、实验分析与探讨（对测试现象和观察结果进行分析，探讨算法，提出见解）

—————————————————————————————————————— 5、实验结论（算法设计是否得到实现，测试结果表明程序是否成功解决问题等）

—————————————————————————————————————— 6、实验总结（成败得失，实验关键，算法改进，程序改善，自我评价）

指导老师评语： 得分： 签名： 年 月 日

本文来源：https://www.bwwdw.com/article/ewqp.html