哈夫曼树和哈夫曼编码(数据结构程序设计)

2021年1月25日发(作者：firerate)




课

程

设

计


（数据结构

）

哈夫曼树和哈夫曼编码
















二○○九

年

六

月

二十六

日






课程设计任务书及成绩评定




课题名称

表达式求值

哈夫曼树和哈夫曼编码


Ⅰ、题目的目的和要求
：





巩固 和加深对数据结构的理解，
通过上机实验、
调试程序，
加深对课本知识的理解，
最终使学生能够熟练应用数据结构的知识写程序。

（
1
）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（
2
）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的
正确求解过程并编写代码实现。




Ⅱ、设计进度及完成情况


日


期

内















容

6.8-6.10
6.15
和
6.19
6.22~6.25
6.26

选取参考书，查阅有关文献资料，完成资料搜集和系统分析工
作。

创建相关数据结构
,
录入源程序。

调试程序并记录调试中的问题，初步完成课程设计报告。

上交课程设计报告并进行课 程设计答辩，
要求每个同学针对自
己的设计回答指导教师
3-4
个问题。
考核结束后将课程设计报告和源程序的电子版交班长统一刻
光盘上交。










Ⅲ、主要参考文献及资料

[1]
严蔚敏

数据结构（
C
语言版）清华大学出版社
1999


[2]
严蔚敏

数据结构题集（
C
语言版）清华大学出版社
1999
[3]
谭浩强
C
语言程序设计

清华大学出版社

[4]
与所用编程环境相配套的
C
语言或
C++
相关的资料




Ⅳ、成绩评定：










设计成绩：

指导老师：





（教师填写）
（签字）

二○○

九

年

六

月

二十六

日





目

录


第一章

概述…………………………………………………………
1
第二章

系统分析……………………………………………………
2
第三章

概要设计……………………………………………………
3
第四章

详细设计及实现代码………………………………………
8
第五章

调试过程中的问题及系统测试情况……………………
12
第六章

结束语……………………………………………………
13
参考文献……………………………………………………………
13


第一章

概述


课程设计是实践性教学中的一个重要环节 ，它以某一课程为基础，可以涉及和课程
相关的各个方面，是一门独立于课程之外的特殊课程。课程设计 是让同学们对所学的课
程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的 专业
基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计，要求学生在 数据结构的逻辑特性和物理表示、数据结构的选择
和应用、算法的设计及其实现等方面，加深对课程基本 内容的理解。同时，在程序设计
方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练 。

在这次的课程设计中我选择的题目是表达式求值和哈夫曼树及哈夫曼编码。
这里我
们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。哈夫曼树又称最优
树，是一 类带权路径长度最短的树，有着广泛的应用。

功能
：表达式求值以栈为存储结构，实现输入的表达式的求值；


哈夫曼树和哈夫曼编码是实现最优二叉树的构造，
并能通过最优二叉树进行编
码，应用 到电文中，并以此来译码。

利用键盘，输入相应的数值，通过程序实现表达式的求值；再利用 键盘，输入各个
顶点，通过程序构造最优二叉树以及为此编码。




1

第二章

系统分析

一、表达式求值

根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相 同的项，对应
系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式所
有指数不相同的项，则分别复抄到“和多项式”中去。

在此，安装上述抽象数据类型
Polynomial
中基本操作的定义，“和多项式”链表中
的结点无需另生成，而应该从两 个多项式的链表中摘取。其运算规则如下：假设指
着
qa
和
qb
分别 指向多项式
A
和多项式
B
中当前进行比较的某个结点，则比较两个
结 点中的指数项，有下列
3
种情况：①指针
qa
所指结点的指数值
<< br>指针
qb
所指结点
的指数值，则应摘取
qa
指针所指结点插入 到“和多项式”链表中去；②指针
qa
所
指结点的指数值
>
指针qb
所指结点的指数值，
则应摘取指针
qb
所指结点插入到
“和
多项式”链表中去；③指针
qa
所指结点的指数值
=
指针
q b
所指结点的指数值，则将
两个结点中的系数相加，
若和数不为零，
则修改< br>qa
所指结点的系数值，
同时释放
qb
所指结点；反之，从多项式A
的链表中删除相应结点，并释放指针
qa
和
qb
所指结
点。

二、
哈夫曼树和哈夫曼编码




建立哈夫曼树的算法思想是：

1)

根据给定的几个权值
{w
1
，
w
2
，……，
w
n
}
构 成
n
颗二叉树的集合
F={T
1
，
T
2
， ……，
T
n
}
，其中每颗二叉树
T
i
中只有一个带 权为
w
i
的根结点，其左右子树均空。

2)

在
F
中选取两棵根结点的权值最小作为左右子树构造一棵新的二叉树，且置新的二
叉树的 根结点的权值为其左、右子树上根结点的权值之和。

3)

在
F
中删除这两棵树，同时将新得到的二叉树加入
F
中。

4)

重复（
2
）和（
3
），直到
F只含一棵树为止。这棵树便是哈夫曼树。


1

第三章

概要设计

Ⅰ
.
以下算法描述了这个求值过程：

int

cmp(term a, term b);
//
依
a
的指数值< br><(
或
=)(
或
>)b
的指数值，分别返回
-1、
0
、
+1
void CreatPolyn(polynomail&p,int m){
//
输入
m
项的系数和指数，建立表示一元多项式的有序链表
p
InitList(p);

h =GetHead(p);
=0.0;

= -1;

SetCurElem(h,e);

//
设置头结点的数据元素

for (i=1; i<=m ++i){

//
依次输入
m
个非零项

scanf (, );
if (!LocateElem(P,e,q(*cmp)())){

//
当前链表中不存在该指数项

if(MakeNode(s,e))

InsFirst(q,s);

//
生成结点并插入链表

}
}

}


//CreatPolyn
void AddPolyn(polynomai &Pa, polynomai &Pb){
//
多项式加法：
Pa=Pa+Pb
，利用两个多项式的结点构成“和多项式”。

ha =GetHead(Pa);

hb =GetHead(Pb);//ha
和
hb
分别指向
Pa
和
Pb
中当前结点

while(qa&&qb){//qa
和
qb
均非空

a=GetCurElem(qa);

b=GetCurElem(qb);// a
和
b
为两表中当前比较元素

switch(*cmp(a,b)) {
case -1://
多项式
PA
中当前结点的指数值小

ha=qa; qa=NextPos(pa,qa);break;
case 0:

//
两者的指数值相等

sum=+;
if(sum!=0.0) {//
修改多项式
PA
中当前结点的系数值

SetCurElem(qa,sum);ha=qa;}
else{//
删除多项式
PA
中当前结点

DelFirst(ha,qa); FreeNode(qa);}
DelFirst(hb,qb); FreeNode(qb); qb=NextPos(Pb,hb);
qa=NextPos(Pa,ha);break;
case 1:

//
多项式
PB
中当前结点的指数值小

DelFirst(hb,qb); InsFirst(ha,qb);
qb=Nextpos(Pb,hb); ha=NextPos(Pa,ha);break;
}//switch
}//while
if(!ListEmpty(Pb)) Append(Pa,qb);

//
链接
pb
中剩余结点

FreeNode(Pb): //
释放
Pb
的头结点

}//AddPolyn
Ⅱ
.
哈夫曼树及哈夫曼编码

ADT BinaryTree
{
数据对象
:D
是具有相同特性的数据元素的集合。

数据关系：
R
：

若
D=
Φ，则
R=Φ，称
BinaryTree
为空二叉树；


1

若
D
≠Φ，则
R=
｛
H
｝，
H
是 如下二元关系：

（
1
）

在
D
中存在惟 一的称为根的数据元素
root
，它在关系
H
下无前驱；

（
2
）

若
D-
｛
root
｝≠ Φ，则存在
D-
｛
root
｝
=
｛
D1
，
Dr
｝，且
D1
∩
Dr=
Φ；

（
3
）

若
D1
≠Φ，则
D1
中 存在惟一的元素
X1
，

∈
H,
且存在< br>D1
上的关系
H1
∈
H;
若
Dr
≠Φ
,
则
Dr
中存在惟一的元素
Xr,
∈
H,
且存在
Dr
上的关系
Hr
∈
H;H={,,H1,Hr};

（
4
）

( D1,{H1})
是一颗符合本定义的二叉树
,
称为根的左子树
,(Dr,{ Hr})
是一颗符合本
定义的二叉树
,
称为根的右子树。

基本操作
P
：

Initqueue(&q)
；


操作结果：构造空二叉树
T
。

Destroyqueue(&q)
；


初始条件：二叉树
T
已存在。


操作结果：销毁二叉树
T
。

CreateBiTree(&T,definition)
；


初始条件：
definition
给出二叉树
T
的定义。


操作结果：按
definition
构造二叉树
T
。

ClearBiTree(&T)
；


初始条件：二叉树
T
已存在。


操作结果
:
将二叉树
T
清为空树。

BiTreeEmpty(T)
；


初始条件：二叉树
T
已存在。


操作结果
:
若
T
为空二叉树，则返回
TRUE
，否则
FALSE
。

BiTreeDepth(T)
；


初始条件：二叉树
T
已存在。


操作结果
:
返回
T
的深度。

Root(T)

初始条件：二叉树
T
已存在。


操作结果
:
返回
T
的根。

Value
（
T
，
e
）；


1