数据结构课程设计报告--huffman编码与文件压缩

《数据结构课程设计报告--huffman编码与文件压缩》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计报告题目：题目三哈夫曼编码与文件压缩课程名称：数据结构专业班级：计算机科学与技术1003班学号：姓名：鲁辰指导教师：报告日期：2012.09.26计算机科学与技术学院14目录1任务书32绪言42.1课题背景42.2课题研究的目的和意义42.3国内外概况42.4课题的主要研究工作43系统设计方案的研究53.1系统的控制特点与性能要求53.2系统实现的原理53.2.1Huffman算法53.2.2Huffman编码53.2.3压缩过程53.2.4解压过程63.3系统实现方案分析63.3.1实现Hu

2、ffman编码及压缩所需的变量63.3.2文件名处理73.3.3实现Huffman编码及压缩过程所需要的函数73.3.4实现解压缩过程所需要的函数83.3.5输入输出84基于Huffman编码的文件压缩程序的设计94.1主模块功能介绍95系统的实现105.1目标程序运行截图105.2测试及测试数据分析105.2.1测试数据105.2.2测试数据分析116总结与展望12参考文献13附录英文缩写词14141任务书题目三哈夫曼编码与文件压缩p设计目的：掌握二叉树、哈夫曼树的概念，性质与存储结构，能够利用哈夫

3、曼算法实现哈夫曼编码，并应用于文件压缩，从而提高学生综合运用知识的技能与实践能力。p设计内容：分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩得到解压文件。有兴趣的同学可以查阅资料实现Lempel-Zivslidingwindow压缩方法，并与之比较。p设计要求：（1）要求界面友好，输入文本文件可带路径（如：D:docoriginal.txt），哈夫曼算法所得到的压缩文件名为*.cod，哈夫曼树也以文件形式保存，

4、文件名为*.hfm。（2）显示压缩比、压缩时间、解压时间与对应的编码表。p设计提示：统计文本文件中各字符的频度并作为权值生成哈夫曼树，并利用哈夫曼树进行二进制编码。p参考文献：[1]严蔚敏,吴伟民.数据结构（C语言版）.北京:清华大学出版社,1997[2]王晓东.计算机算法设计与分析.北京:电子工业出版社,2007[3]严蔚敏,吴伟民,米宁.数据结构题集（C语言版）.北京:清华大学出版社,1999142绪言2.1课题背景在计算机软件应用领域，文件压缩是一项重要的技术。为了减少传输数据量或者减少存储空间

5、，都需要将大型文件压缩成较小的文件。2.2课题研究的目的和意义Huffman编码具有速度快、简单等优点，是一种很好的压缩方法。2.3国内外概况1952年，DavidA.Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文。2.4课题的主要研究工作（1）通过查阅书籍并在网上查看相关论文，对Huffman编码算法有一个清晰的认识。（2）使用MicrosoftVisual

6、Studio2010实现基于Huffman编码的文件压缩程序。（3）通过使用各种不同的测试文件对该程序进行测试，记录并分析压缩算法的压缩比、压缩时间等数据。（4）分析测试数据，并根据需要对代码进行优化。143系统设计方案的研究3.1系统的控制特点与性能要求本系统是使用VS2010开发的MFC应用程序，对话框是使用MFC生成的，而对文件读写操作以及Huffman编码的算法部分是用C语言实现的。本系统的特点是图形界面，使用简单，便于操控。本系统不要求使用者安装VisualStudio或者MFC类库（？）。

7、3.2系统实现的原理3.2.1Huffman算法（1）根据给定的n个权值{ω1,ω2,…,ωn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为ωi的根结点，其左右子树为空。（2）在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。（3）在F中删除这两棵树，同时将新达到的二叉树加入F中。（4）重复（2）和（3），直到F只含一棵树为止。3.2.2Huffman编码假设每种字符在电文中出现的次数为ω

8、i，其编码长度为li，电文中只有n种字符，则电文总长为i=1nωili。对应到二叉树上，若置ωi为叶子结点的权，li恰为从根到叶子结点的路径长度，则i=1nωili恰为二叉树上的带权路径长度。由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率做权，设计一棵Huffman树的问题，由此得到的二进制前缀编码即为Huffman编码。3.2.3压缩过程前提：与输入的路径对应的文件为txt格式。（1）构造Huffman树：算法如3.2.1所示。（2