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

本科学生设计性实验报告软件工程技能实践Ⅰ项目组长陈启学号＿0154225专业软件工程班级＿15软件7班成员陈启杨林昌邓志远万胜实验项目名称＿指导教师及职称＿＿讲师＿＿开课学期2015至2016学年第二学期一、实验设计方案实验名称：基于哈夫曼编码实现文本文件的压缩和解压缩实验时间：2016-7-1—2016-7-7实验场地：H113成员角色：程序员：陈启杨林昌测试员：万胜邓志远文档员：杨林昌邓志远软件环境：WindowsXP、VC++6.01、实验任务与目的（简单介绍实验内容，说明实验任务和目的）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整体思路2.2涉及的算法思想及数据结构：2.2.1输入要压缩的文件首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。若打不开，则继续输入。2.2.2读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间，用读取的字符减去字符结束符作为下标记录字符的频率。2.2.3根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结生成对应文件生成哈夫曼树根据哈夫曼树编码对编码进行压缩生成二进制文件统计字符，得出统计出字符的权值n建立哈夫曼树对二进制文件进行解码根据哈夫曼树解码点。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主函数流程图：帮助否主函数输出字符、哈弗曼编码、压缩前后文件长度、压缩率、压缩时间压缩文件弹出“打开”对话框等待用户选择解压文件弹出“打开”对话框等待用户选择输出程序介绍指南，为用户提供帮助结束单击按钮开始路径合法？是aa=0弹出错误信息“请选择txt文本文件”否弹出错误信息“请选择cod文件”路径合法？是aa=12.2主要函数的功能描述，算法实现的细节——————————————————————————————————————2、测试设计与数据（设计充足合理的测试用例，说明测试策略）——————————————————————————————————————3、实验现象及结果（应用文字和程序运行的截图说明测试现象，并解释结果）——————————————————————————————————————4、实验分析与探讨（对测试现象和观察结果进行分析，探讨算法，提出见解）——————————————————————————————————————5、实验结论（算法设计是否得到实现，测试结果表明程序是否成功解决问题等）——————————————————————————————————————6、实验总结（成败得失，实验关键，算法改进，程序改善，自我评价）指导老师评语：得分：签名：年月日