桂林电子科技大学综合设计说明书用纸
课程设计说明书
题 目:1、哈夫曼树编码 / 译码器
2、表达式的求值
学 院: 计算机科学与工程学院
专 业: 信息管理与信息系统
姓 名:
学 号:
指导教师:
2010 年 7 月 13 日
桂林电子科技大学综合设计说明书用纸
目 录
桂林电子科技大学综合设计说明书用纸 第 1 页
引言
随着现在科技的发达,人们的生活、学习等越来越依赖于网络、科技。但是我们在利
用网络进行通讯以及其他的一些活动的时候。我们的信息可能会被他人不法的截获。所
以我们的信息的安全越来越重要。数据加密就是一种很好的保护用户信息安全的一种方
法。其中,哈夫曼树的应用是最典型的加密算法。
1 系统概述
利用 human 算法进行编码。然后再对输入的数据进行译码。还可以输出编码表,
查看每个字符所对应的编码。
2 需求分析
2.1 系统需求
1、功能需求:
① 可以通过给定的字符和字符出现的频率,构造哈夫曼树
②然后利用构造好的哈夫曼树对输入的二进制进行译码,翻译成字符串的形式。
③编码完成后,可以输出编码表,即每个字符所对应的二进制编码
2、 使用范围:
只适用于从内存中读取数据,不可以读写文件
3、 用户界面
有良好的提示语句,每一步均可按提示进行。利用 while 循环,可以多次重复的使
用某项功能,直到输入终止条件为止。对于用户的每一次键盘的输入都用 do-while 循环
监听,并适当的提示用户输入的不规范,以及下一步应该的操作。
4、 故障处理
对一些简单的违反操作的地方进行提醒,并交给用户重新输入或输入相应的数进行
处理。否则,不允许进入到下一步。一直在等待用户的响应,很好的体现了人机交互的
意义。
2.2 开发环境
所使用的开发的工具是 VC++6.0,用 C 语言在 XP 系统下进行开发。
3 详细设计
3.1 数据结构
由于哈夫曼树中的叶子结点的个数为 N,所以分支节点的数目为 N-1,所以总共结点
数为 2N-1 个。在已知结点总数的情况下,不必采用动态的方式一个一个地去申请空间来
建立完整的哈夫曼树,而可以直接用一个相应大小的数组 ht 来表示它。这个数组共有
2N-1 个元素,每个元素表示哈夫曼树中的一个结点。前 N 个结点,记录叶子结点的个数;
另一个是 root,记录根结点在数组 ht 中的下标。
桂林电子科技大学综合设计说明书用纸 第 2 页
为了方便实现节省选择两个权最小的扩充二叉树的检查时间,在每个结点的表示中,
除了一般二叉树结点需要的 llink,rlink 字段外,还增加了一个父结点的下标 parent,
和记录该结点和父结点关系的字段 rlparent。因此,在数组中每个结点的结构有下面四
部分组成。
ww parent llink rlink rlparent
其中,ww 存放以该结点为根的二叉树中,叶子结点的权值之和。对于叶子结点,它
就是本结点的权值;对于分支节点,它是以该节点为根的左右子树 ww 的值的和。
parent 存放结点的父结点在数组中的下标,根结点无父结点,其 parent 字段为-1。
llink 存放结点的左子节点在数组中的下标,叶子结点无左子结点,则 llink 字段为-
1。
rlink 存放结点的右子节点在数组中的下标,叶子结点无右子结点,则 rlink 字段为-
1。
rlparent 存放的结点与父结点直接的关系,是父结点的左孩子则 rlparent=0;是父
结点的右孩子则 rlparent=1。
综上所述:每个结点的结构和哈夫曼树可用 C 语言定义为:
struct HtNode /*哈夫曼树结点的结构*/
{
int ww; /*权值*/
int parent,llink,rlink,rlparent;/*rlparent 是记录该结点是父结点的左孩子还是右
孩子*/
char a; /*记录编码字符的信息*/
};
typedef struct HtNode * PHtNode;
struct HtTree /*哈夫曼树结构*/
{
int m; /*外部结点的个数*/
int root; /*哈夫曼树在数组中的下标*/
struct HtNode *ht; /*存放 2*m-1 个结点的数组*/
};
typedef struct HtTree * PHtTree;/*哈夫曼树类型的指针类型*/
3.2 human 算法
算法的思想:
1、 首先创建空的哈夫曼树,然后置空,初始化哈夫曼树,将 2N-1 个结点的所有结
构体的成员变量赋初值