Question

静态哈夫曼编码的C++实现

Answer 1

一、 分析待编码文件，对文件中每个字符编码
1、 读取并记录文件中每个字符出现的频率。
2、
① 首先把每个字符及其频率记为节点序列。
② 重复选取频率最小的两个部分，将这两个部分作为左右子树构建新的树，将左右部分的频率加起来作为父节点的频率，并将该树重新放入序列中。
③ 直到序列中只剩下一个部分，即为最终形成的哈夫曼树。
3、 遍历哈夫曼树，左子树就编码0，右子树就编码1，叶子结点就输出对应字符的编码，记录在字符编码字典中。
二、 利用字符编码字典对源文件进行编码
1、 对源文件中每一个字符在字符编码字典中找到对应的编码，连接成01编码串。
2、 将01编码串每8位转化为一个字符写入到编码文件中。因为最后的01位数不一定刚好是8位，所以用0补齐，并在编码文件开头用一个字符记录编码最后有多少个无效位。
三、 利用哈夫曼树对编码文件进行译码
1、 读出编码文件的字符转化为01编码串，根据第一个字符删去01编码串最后的无效位。
2、 根据01编码串搜索哈夫曼树，遇到0就找左子树，遇到1就找右子树，当左右子树都不存在时表示该节点为一个字符结点，输出该字符重新从根节点开始找下一个字符。最后得到完整的译码结果。