实验四 实现Huffman 编码
一．实验目的
进一步掌握以二叉链表表示二叉树的实现方法，加深对Huffman 树的理解，掌握
Huffman 编码的实现方法，进一步练习对文件的操作和使用。
二． 问题描述与要求
Huffman 树在编码、优化判定过程以及算法设计等方面有着广泛的应用，Huffman 编
码就是利用Huffman 树实现前缀编码的很好例子。
现有字符序列(包含8 种字符，共38 个字符)：d c e d t e r n r s r j r e j r c r s n r e r d c e r j
e d c e d s j d c e，它们存放于文本文件中；现要求统计出各字符在该序列中出现的频度，根
据统计结果建立Huffman 编码树，并利用Huffman 编码树得到各字符的Huffman 编码。
实验要求：
1. 由键盘输入上述字符序列，并将其写入文本文件H_string.txt 中。
2. 从文本文件H_string.txt 中逐个读入字符，同时分别统计出各字符出现的次数（频
度）。
3. 根据统计结果建立以上述字符结点为叶子的Huffman 编码树。
9
4. 利用所建立的Huffman 编码树，求得各字符的Huffman 编码，并以：
形式将各字符的Huffman 编码记录于编码表（字符编码数组）中。
5. 将各字符的Huffman 编码写入文件Hufm_coding.txt 中。
三． 求解方法说明
1. 定义一个字符数组，用于存放从键盘读入的给定字符序列，数组长度不小于39 。
2. 从键盘读入给定的字符(38 个)到字符数组中，检查字符输入的正确性，并将字符写
入文本文件（ASCII 文件）H_string.txt 中。
3. 从H_string.txt 文件中逐个读入字符，并统计、记录各种（共8 种）字符在该序列中
出现的次数（频度），可以用
的形式记录统计结果。
4. 以各个字符的频度为结点权值，构造以序列中出现的8 种字符为叶子结点的Huffman
树，若采用动态结点，结点结构为（非叶子结点字符名为空）：
5. 从Huffman 编码树的根结点出发，遍历所有叶子结点，并判断遍历过程中每一步所
经过的分支是左分支还是右分支，若经过的是左分支该位编码记为0，若经过右分支则记该
位编码为1；每遇到一个叶子结点，则将已得到的二进制码复制到编码表中。
6. 逐行输出编码表（字符编码数组）的“字符名”与“Huffman 编码”；同时将各字
符的编码写入文件Hufm_coding.txt 中。
四． 算法提示
1. 构造Huffman 编码树可以采用动态结点或静态结点。若采用动态结其结点结构如“求
解方法说明”中4 所示，可以用结构体类型定义；构造Huffman 编码树的算法可以参考4.2.3
节中构造Huffman 树的算法。
2. 若采用静态结点结构，则结点中需要增加一个指向其父亲的指针域“parent”；因为
具有n 个叶子结点的Huffman 树共有2n-1 个结点，因此用于实现静态结点的数组长度不能
小于2n-1。即针对本问题，该数组长度应不小于15。其中，开始n 个数组元素用于存放n
个叶子结点，其余n-1 个数组元素用于合并子树过程中产生的分支结点。初始，8 个叶子结
点的父亲域都为空（以0 表示），静态结点空间的状态如图4-1 所示。
数组下标 字符名 权值 parent lchild rchild
0
1 c 0
2 d 0
﹕
﹕
﹕
﹕
15
3. 若采用动态结点结构，求各字符的Huffman 编码可以从根结点出发，沿所有分支遍
字符名 Huffman 编码
字符名 频度
左孩子指针 字符名 权值(频度) 右孩子指针
10
历每一个叶子结点，并分别记录所经过的左分支（0）和右分支(1)，每到达一个叶子结点就
把当前已记录的“0”、“1”串存放到编码表的相应字符（由结点中的字符名可以知道）的编
码中。该过程可以用递归实现，算法参考思路如下：
void HfmCode (BTreeNode *HMT, int n) // HMT 编码树根结点指针, n 初值0
{ static int hc[leaf_num] ； // hc 存放字符编码，其长度等于树的深度
if (HMT!=NULL)
{ if (HMT->left==NULL && HMT->right==NULL)
{ // 将得到的字符编码存放于编码表的相应域中 }
else
{ hc[n]=0 ；
HfmCode (HMT->left, n+1) ； // 对左子树搜索
hc[n]=1 ；
HfmCode (HMT->right, n+1) ； // 对右子树搜索
}
}
}
4. 若采用静态结点结构，可以从每个字符结点出发搜索到根结点，同时记录所经过的
左、右分支来得到各字符的编码；此时只要根据结点数组的下标对1～n 号结点对其作到根
结点的搜索即可，这样很方便采用循环来实现。各字符的编码位数不会超过编码数的结点数
n，因此可以定义记录编码串的数组长度为n；因为是从后向前记录各编码位，而各字符编
码长度不同，因此需要记录各字符码串的起始位（搜索每个字符编码开始时，第n 位是起始
位，以后逐位向前移动）。从起始位开始到最后一位是相应字符的Huffman 编码，将其存入
该字符的编码表中。编码表的结构可以参考如下定义：
#define leaf_num 8 // Huffman 树叶子结点数目
#define huf_num 2*leaf_num // Huffman 树总结点数目
struct Hfm_table
{ char code_str[leaf_num]; // 存放字符编码位串的数组
int start_bit ; // 编码在位串中的起始位置
char ch ; // 字符名
};
定义该结构体类型的数组为存储各字符编码的“Huffman 编码表”。