淮 阴 工 学 院
数据结构课程设计报告
选题名称: 哈夫曼编码 / 译码器
2
系（院）: 计算机工程学院
专 业: 计算机科学与技术
班 级:
姓 名: 学 号:
指导教师:
学年学期: 2009 ~ 2010 学年 第 2 学期
2010 年 6 月 20 日
设计任务书
课题
名称
哈夫曼编码/译码器 2
设计
目的
1. 调研并熟悉哈夫曼编码/译码器 2 的基本功能、数据流程与工作规程；
2. 学习哈夫曼编码/译码相关算法和基于 VC++集成环境的编程技术；
3. 通过实际编程加深对基本原理的理解，提高实践能力；
4. 学习开发资料的收集与整理，学会撰写课程设计报告。
实验
环境
1. 微型电子计算机（PC）；
2. 安装 Windows 2000 以上操作系统，Visual C++6.0 开发工具。
任务
要求
1. 利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及
设计要求，注意材料收集与整理；
2. 在第 18 周末之前完成预设计，并请指导教师审查，通过后方可进行下一
步工作；
3. 本课题主要实现对指定文件中字符进行哈夫曼编码译码并生成结果文
件，要求原文件为文本文件，编码结果文件是二进制文件，显示操作结
果。
4. 结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内
容完整、结论正确，正文字数不少于 5000 字。
工作进度计划
序号 起止日期 工 作 内 容
1 2010.06.21
在预设计的基础上，进一步查阅资料，完善设计方
案，形成书面材料。
2 2010.06.22~2010.06.23
设计总体方案，构建绘制流程框图，编写代码，上
机调试。
3 2010.06.24
测试程序，优化代码，增强功能，参加答辩。
4 2010.06.25~2010.06.27
提交软件代码、设计报告，根据教师反馈意见，修
改、完善设计报告。
指导教师：
2010 年 6 月 10 日
摘要：
在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存
储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一
种应用广泛且非常有效的数据压缩技术。文本由字符组成，字符以某种编码形
式存储在计算机中。每个字符的编码可以是相等长度的，也可以是不等长度的。
我们熟知的 ASCII 编码是等长编码。为了提高存储和处理文本的效率，在一些
计算机应用场合，如数据通信，常采用不等长的编码，对常用的字符用较少的
码位编码，不常出现的字符用较多的码位编码，从而减少文本的存储长度。哈
夫曼编码就是用于此目的的不等长编码方法。当然，编码的对面就有译码。本
课题中，首先是构造哈夫曼树。给定一组权值，以此作为叶结点的权值，可以
构造多棵扩充二叉树，它们通常具有不同的加权路径长度。其中具有最小加权
路径长度的扩充二叉树，用于构造高效的不等长编码。哈夫曼给出了构造具有
最小加权路径长度的扩充二叉树的算法，称位哈夫曼算法。用哈夫曼算法构造
的扩充二叉树称为哈夫曼编码树或哈夫曼树。当然，还有编码和译码部分。本
系统的前端开发工具是 Visual C++6.0。本程序经过测试后，功能均能实现，运
行稳定。
关键词：数据结构；二叉树；哈夫曼树；编码/译码
目 录
1 需求分析 1
1.1 课题来源.........................................................................................................................................1
1.2 问题描述.........................................................................................................................................1
1.3 课程设计的任务及要求.................................................................................................................1
1.4 课程设计的思想.............................................................................................................................2
1.5 软件运行环境及开发工具.............................................................................................................2
2 概要设计 3
2.1 设计思路及方案..............................................................................................................................3
2.2 模块的设计及介绍..........................................................................................................................3
2.3 数据结构的选用.............................................................................................................................5
2.4 流程图.............................................................................................................................................6
3 详细设计和实现 6
3.1 开始部分.........................................................................................................................................6
3.2 结点的定义.....................................................................................................................................7
3.3 构造哈夫曼树.................................................................................................................................8
3.4 哈夫曼编码...................................................................................................................................10
3.5 哈夫曼译码...................................................................................................................................14
3.6 主函数...........................................................................................................................................16
4 调试与操作说明 17
5 运行结果与测试 18
5.1 主程序............................................................................................................................................18
5.2 哈夫曼编码译码............................................................................................................................19
总 结 21
致 谢 22
参考文献 23
1 需求分析
1.1 课题来源
哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构
造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如 JPEG
中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出
现概率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，
就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律
的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼
树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编
码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都
不是另一个字符的编码的前缀，否则，编码就不能进行翻译。
1.2 问题描述
哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称
为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：
指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的
“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时
间，降低传输成本。本次设计就是这样的一个哈夫曼编码/译码器，要求从指定
原文件中读取字符并统计字符的出现频数，由此建哈夫曼树对字符进行二进制
编码，产生编码结果文件，然后再对结果文件进行解码，产生解码结果文件，
并将其与原文件比较是否一致。要求原文件为文本文件，编码结果文件是二进
制文件或文本文件，而解码结果文件为文本文件。
1.3 课程设计的任务及要求
一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计
能力；
1
