(数据结构课程设计报告Huffman编码与文件压缩.docxVIP

课程设计报告题目：题目三哈夫曼编码与文件压缩课程名称：数据结构专业班级：计算机科学与技术1003班学号：姓名：鲁辰指导教师：报告日期：2012.09.26计算机科学与技术学院任务书题目三哈夫曼编码与文件压缩设计目的：掌握二叉树、哈夫曼树的概念，性质与存储结构，能够利用哈夫曼算法实现哈夫曼编码，并应用于文件压缩，从而提高学生综合运用知识的技能与实践能力。设计内容：分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩得到解压文件。有兴趣的同学可以查阅资料实现Lempel-Ziv sliding window压缩方法，并与之比较。设计要求：（1）要求界面友好，输入文本文件可带路径（如：D:\doc\original.txt），哈夫曼算法所得到的压缩文件名为*.cod，哈夫曼树也以文件形式保存，文件名为*.hfm。（2）显示压缩比、压缩时间、解压时间与对应的编码表。设计提示：统计文本文件中各字符的频度并作为权值生成哈夫曼树，并利用哈夫曼树进行二进制编码。参考文献：[1] 严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社,1997[2] 王晓东. 计算机算法设计与分析. 北京: 电子工业出版社, 2007[3] 严蔚敏, 吴伟民, 米宁. 数据结构题集（C语言版）. 北京: 清华大学出版社,19992绪言2.1 课题背景在计算机软件应用领域，文件压缩是一项重要的技术。为了减少传输数据量或者减少存储空间，都需要将大型文件压缩成较小的文件。2.2 课题研究的目的和意义Huffman编码具有速度快、简单等优点，是一种很好的压缩方法。2.3 国内外概况1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。2.4 课题的主要研究工作（1）通过查阅书籍并在网上查看相关论文，对Huffman编码算法有一个清晰的认识。（2）使用Microsoft Visual Studio 2010实现基于Huffman编码的文件压缩程序。（3）通过使用各种不同的测试文件对该程序进行测试，记录并分析压缩算法的压缩比、压缩时间等数据。（4）分析测试数据，并根据需要对代码进行优化。3系统设计方案的研究3.1 系统的控制特点与性能要求本系统是使用VS2010开发的MFC应用程序，对话框是使用MFC生成的，而对文件读写操作以及Huffman编码的算法部分是用C语言实现的。本系统的特点是图形界面，使用简单，便于操控。本系统不要求使用者安装Visual Studio 或者 MFC类库（？）。3.2 系统实现的原理3.2.1 Huffman算法（1）根据给定的n个权值{}构成n棵二叉树的集合F={}，其中每棵二叉树中只有一个带权为的根结点，其左右子树为空。（2）在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。（3）在F中删除这两棵树，同时将新达到的二叉树加入F中。（4）重复（2）和（3），直到F只含一棵树为止。3.2.2 Huffman编码假设每种字符在电文中出现的次数为，其编码长度为，电文中只有n种字符，则电文总长为。对应到二叉树上，若置为叶子结点的权，恰为从根到叶子结点的路径长度，则恰为二叉树上的带权路径长度。由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率做权，设计一棵Huffman树的问题，由此得到的二进制前缀编码即为Huffman编码。3.2.3 压缩过程前提：与输入的路径对应的文件为txt格式。（1）构造Huffman树：算法如3.2.1所示。（2）将Huffman树编码：初始化编码数组，并遍历Huffman树，得到各个字符的编码，并保存为.hfm文件。（3）将.txt文件中的内容读取出来，找到对应的Huffman编码，并将相应的Huffman编码写入.cod文件中。3.2.4 解压过程前提：与输入的路径对应的文件为txt格式，且输入的路径对应的xxx.cod文件有对应的Huffman编码文件xxx.hfm存在。（1）由.hfm文件载入Huffman编码的数组。（2）读取.cod文件的内容，并找到其对应的字符写入新的.txt文件。3.3 系统实现方案分析3.3.1 实现Huffman编码及压缩所需的变量表3. 1实现Huffman编码所需变量列表（均为全局变量）名称声明语句or类型功能Huffman_Nodetypedefstruct Huffman_Node{unsignedchar char_va