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

本文格式为Word版，下载可任意编辑——基于哈夫曼编码实现文本文件的压缩和解压缩试验报告模板

本科学生设计性试验报告

软件工程技能实践Ⅰ

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

指导教师及职称＿＿讲师＿＿开课学期2023至2023学年其次学期

一、试验设计方案

试验名称：基于哈夫曼编码实现文本文件的压缩和解压缩试验时间：2023-7-1—2023-7-7试验场地：H113成员角色：程序员：陈启杨林昌测试员：万胜邓志远文档员：杨林昌邓志远软件环境：WindowsXP、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、试验结论（算法设计是否得到实现，测试结果说明程序是否成功解决问题等）