220
字符NOPQRSTUVWXYZ
频度5763151485180238181161
2概要设计
1
f计算机学院《数据结构》课程设计报告
21抽象数据类型定义
ADTStack数据对象：Daiai∈ElemSeti12
≥0数据关系：若D为空集，则称为空树。若D仅为一个数据元素，则R为空集，否则RH，H是如下的二元关系：（1）再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。（2）若Droot空集，则存在一个划分D1，D2，，Dm（m0）。（3）对应于Droot的划分，Hroot，X1，，root，Xm有唯一的一个划分
H1，H2，，Hm（m0）。
基本操作：I
itTreeT操作结果：构造空树T。DestroyTreeT初始条件：树T已存在。操作结果：树T被销毁。ClearTreeT初始条件：树T已存在。操作结果：将树T清为空栈。TreeEmptyT初始条件：树T已存在。操作结果：若树T为空，则返回TRUE，否则FALSE。TreeDepthT初始条件树T已存在。操作结果：返回T的深度。Root（T）初始条件：树T已存在。操作结果：返回树T的根。
22模块划分
本程序包括三个模块：1主程序模块
voidmai
初始化；构造哈夫曼树；求哈夫曼编码；哈夫曼编码输出；（2）哈夫曼模块实现哈夫曼树的抽象数据类型
1
f计算机学院《数据结构》课程设计报告
（3）求哈夫曼编码模块实现求哈夫曼编码算法的数据类型
3设计过程及代码
31设计过程
1、数据类型的定义（1）哈夫曼树类型
typedefstruct构造树chardata结点权值i
tweight权重i
tpare
t双亲结点i
tlchild左孩子i
trchild右孩子HTNodeHTNodeht30（2）求哈夫曼编码类型
typedefstructcharcd30存放当前结点的哈弗曼编码i
tstartcdstartcd
存放哈弗曼码HCodeHCodehcd30
1
f计算机学院《数据结构》课程设计报告
2、主要模块的算法描述开始
I
tIfcI
tI
I0i
I
Sca
f“d”httwe
i
结束
主函数流程图图311
Hcstart
ciF1
multiplexHcstart
I
哈弗曼编码算法流程图图312
1
f32代码
计算机学院《数据结构》课程设计报告
i
cludestdiohdefi
e
27叶子数目defi
em2
1结点总数defi
emaxval100000defi
emaxsize100哈夫曼编码的最大位数
typedefstruct
charchfloatweighti
tlchildrchildpare
thufmtreetypedefstructcharbits
位串i
tstart编码在位串中的起始位置charch字符codetype
voidhuffma
hufmtreetree建立哈夫曼树
voidhuffma
codecodetypecodehufmtreetree根据哈夫曼树求出哈夫曼编码
voiddecodehufmtreetree依次读入字符，根据哈夫曼树译码
i
tmai


pri
tf