西安郵電學院
软件工程课程设计报告书
系 部 名 称 ：
学 生 姓 名 ：
指 导 老 师
专 业 名 称 ：
班 级 ：
学 号 ：
时 间 ：
2008 年 12 月 8 日至 2008 年 12 月 12 日
PARTⅠ：哈夫曼树及其应用
一、 题目与要求：
哈夫曼编码：哈夫曼编码是哈夫曼树的一个应用。哈夫曼树又称最优二叉树，是一种带
权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上
其到根结点的路径长度（若根结点为 0 层，叶结点到根结点的路径长度为叶结点的层
数）。哈夫曼编码应用广泛，如 JPEG 中就应用了哈夫曼编码。
程序要求：
基本功能：根据给定的一个文本文件，读出其内容，统计各个字符出现的频度，建立
哈夫曼树，求出各个字符的哈夫曼码；然后对文件进行编码；最后，对编码后的文件在解
码，对哈夫曼算法进行验证。
扩展功能：将算法移植到对任意给定的文件进行压缩、解压缩。
二、 算法描述：
1．总述：本程序将基本功能与扩展功能一起实现，主要包括编码和解码两大模块。核心
算法包括：
（1） 编码：统计字符频度算法；构造哈夫曼树算法（其中包括选择两个最小权值树
的子算法）；求各字符哈夫曼码算法；压缩算法；
（2） 解码：解码算法；
2．核心算法分述：
（1） 读取文件并统计字符频度算法：
需要用到的变量：字符数组 sign,类型为含有两个 int 型变量的结构体，其中 cha 表示
不同的字符，num 表示该字符的数量；字符总数 n,类型为 int 型。
算法流程：1. 打开要压缩文件，初始化 sign，n。
2．读取文件一个字符，搜索 sign 中是否存在此字符，若存在，则相应字
符数量加一；否则 sign 中加入新的字符，并设定数量为一，字符总数
n 加一。
3．重复步骤 2 直至到达文件结尾。
（2） 构造哈夫曼树算法：
需要用到的变量：（2*n-1）*(4)的二维字符数组 HT,该二维数组即哈夫曼树。HT 第 1
列代表字符，第 2 列代表父亲节点，第 3，4 列分别代表左右孩子。n 由（1）得到。
算法流程：1. 根据由（1）得到的 n 个字符形成 n 个节点存入 HT 前 n 行中，父亲节
点，左右孩子均设成空。
2．利用 select 函数选择两个权值最小的节点作为左右孩子构造一个新的节点，
且置新的权值为其左右子树德权值之和，并插入 HT 中。
3．重复第 2 步，直至 HT 满了为止。
（3）求各字符哈夫曼码算法：
需要用到的变量：n*n 的字符编码 2 位数组 HC,临时变量一维数组 cd;
算法流程：1. 从 sign 中读取一个字符，在哈夫曼树 HT 中找到该字符并设为当前节
点；
2. 如果当前节点是其父亲的左孩子，把字符 0 存入 cd 中，如果是其父亲的右
孩子，则把字符 1 存入 cd 中，当前节点设为该节点的父亲节点。
3．继续 2 直至到达根节点。
