霍夫曼编码与解码问题
实验报告
化学实验报告单总流体力学实验报告观察种子结构实验报告观察种子结构实验报告单观察种子的结构实验报告单
3
——霍夫曼编码与解码问题
1、 问题描述与
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
描述:
(1) 读取源文本文件，对里面的字符频率进行统计，然后进行霍夫曼编码，产生编码后
的文件，和编码规则文件。
(2) 能够读取编码文件及对应的编码规则文件，产生解码文件。
(3) 对源文本文件和解码文件进行校验，验证译码的正确性。
分析:
霍夫曼编码问题的核心就是一个霍夫曼树创建的问题。这个是个典型的能够利用贪心准则的问题。
初始时每个字符代表一个根节点，权值是字符在文本中出现的频率。那么贪心准则可以选择为:每次选择两棵根的权值最小的二叉树，进行合并。
2、 基本算法
该问题分解为3个方面的问题:
(1) 霍夫曼树的建立
A. 统计文本中出现的字符及字符出现的个数。
int Hufuman::scan(char *s)
B. 选择权值最小的两个根节点的算法。
void Hufuman::select(HuffmanTree ht, int k, int &s1, int &s2)
C. 构造霍夫曼树。(核心)
void Hufuman::creatHuffmanTree(HuffmanTree ht, HuffmanCode hc, int weight[MAX], int
str[MAX])
具体的实现思想略，参见代码中具体的函数。
(2) 霍夫曼编码的生成
A. 编码算法，产生编码规则文件
(就是对霍夫曼树遍历)
B. 根据编码规则文件进行编码
(将要编码的字符串中的字符逐一与预先生成的编码规则文件中字符编码对照表
进行比较，找到之后将该字符对应的编码写入编码文件，直到所有的字符处理完。)
(3) 编码文件的译码
(读编码文件中的编码，与编码规则文件中字符编码对照表比较，遇到相等的时候
取出对应的字符存入字符串，解码完后将字符串写入解码文件。具体的实现见代码。)
3、 实验环境和运行平台
WindowsXP ， Visual C++6.0
4、 测试情况
测试效果如下图:
1. 点击“编码”按钮会弹出打开文件的对话框，选择要编码的文件。
执行的结果将产生两个文件:codefile.txt(编码后的文件) 和 hc.txt(编码规则文件，
该程序中是表示叶节点的结构体数组的数据，这个文件是串行化存入的，看不到明文，
是二进制代码)，左边显示框将显示原文件的字符和频率。如图:
2. 点击“解码”按钮，将弹出打开文件的对话框，选择编码规则文件，对codefile.txt进行
解码。执行的结果将产生一个文件:decodefile.txt，左边的对话框将显示解码规则及霍
夫曼编码，如图:
3. 点击“校验”按钮，将将弹出打开文件的对话框，选择编码的原文件，执行的结果是与
decodefile.txt进行比较，左边显示比较结果。
注:该程序编码，解码，校验的过程是独立的。也就是说一次运行程序后可以只编码，或只解码，只校验。解码时只要有编码产生的编码规则文件就可以解码。
5、 源码
详细源码见所附的压缩包。
浙公网安备 33021202002483