武汉工程大学计算机科学与工程学院 综合设计报告
第二章 设计简介及设计方案论述
2.1 设计简介
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试设计一个哈夫曼编码/译码系统。通过本课程设计，应使学生掌握哈夫曼编码的特点、存储方法和基本原理，培养学生利用C++语言正确编写程序及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
内容：分两个层次
层次一：用表中给出的字符和频度数据编程建立哈夫曼树，并实现对以下报文进行编码/译码。THIS PROGRAM IS MY FAVORITE
层次二：编程从文件任意输入一段报文，首先统计字符的频度，然后建立哈夫曼树，并给出报文的编码/译码。
2.2 问题分析
功能：对已知的字符频度建立哈夫曼树，可实现输入一段报文，并进行编码/译码。 对任意从文件中输入一段报文，计算每个字符频度，建立哈夫曼树，给出报文的编码/译码可存储在另一个txt文件中。
内部结构：首先应声明一个结构类型结点，结点存储包含：字符，频度，编码，双亲，左孩子，右孩子。利用已知的字符频度建立哈夫曼树。或是输入一段字符串后，把每个字符作为叶节点建立哈夫曼树。
输出形式：能体现出哈夫曼树以建立；每个字符的频度值；翻译出输入报文编码；根据已给出的频度进行译码。
- 2 -
武汉工程大学计算机科学与工程学院 综合设计报告
2.3设计方案
本程序是用最优二叉树即哈夫曼树来实现哈夫曼编码译码的功能。根据所输入的报文进行分析，建立哈夫曼树。统计输入字符串的长度，并对每个字符的频度进行计算。对每个字符及相应的频度作为叶节点建立哈夫曼树。哈夫曼树的建立过程采用把结点看做树每次选最小的两个建立树，并把他们的频度相加，再继续选取最小的两个数建立，直到所有结点建立完，才形成完整的哈夫曼树。接下来是对每个叶节点进行编码，从第一个叶结点开始，查看它的双亲，若它是双亲的做左孩子则记0，若是双亲的右孩子则记1，以此往上推，直到哈夫曼的根结点为止。并记录编码存入结点中。即每个结点要存入它的字符，频度，编码，双亲，左孩子，右孩子。再输出报文字符串所对应的编码。根据编码所建立的哈夫曼树，输入一段编码，进行译码。译码过程由根结点往下，若是0则找它的左孩子，若是1找它的右孩子，直到找到叶节点为止，并输出它的字符。
主程序基本思路如下：
输入一段报文 输入要译码的编码
- 3 -
对报文进行频度，长度分析 构造哈夫曼树 根据哈夫曼树进行编码 输出编码 根据哈夫曼树译码 输出译码 图2-1 主要流程
武汉工程大学计算机科学与工程学院 综合设计报告
第三章 详细设计
3.1 主要函数流程图
（1）构建哈夫曼树
开始
输入报文计算频度
并令i=0,t=长度
N i<2*t-1
Y 找出根结点频度最小及 次小树 p1,p2 合并成新树T[i]
i++
结束
图3-1 构建流程图
- 4 -
武汉工程大学计算机科学与工程学院 综合设计报告
(2)哈夫曼编码 开始
第一个字符i=0
N i Y 结点是 根结点 N 夫结点的左结 点==该结点？ N Y 编码记0 编码记 i++ 结束 图3-2 编码流程图 存储编码 - 5 - 武汉工程大学计算机科学与工程学院 综合设计报告 （3）哈夫曼译码 开始 输入编码，长度p 第一个字符 pare=0 N T[pare]为根 Y i 开始 Y 结点是叶节 Y 点？ N 输出叶子结点 代表的字符 编码序列号 为0？ N Y 向左孩子移 向右孩子移 结束 图3-3 译码流程图 - 6 -