下一页
计算机软件基础
The software basic
of computer
主讲：刘志强
西安交通大学
计算机教学实验中心
第 5单元
非线性数据结构
图
下一页
上一页
停止放映
第 2 页
教学目标
? 了解有关图的
– 基本概念
– 存储结构及实现
– 遍历算法
下一页
上一页
停止放映
第 3 页
教学要求
? 通过本单元学习，了解、掌握有关图,
– 基本概念
?有向图、无向图、连通图、网
– 存储结构及实现
?邻接矩阵、邻接表
– 遍历及其它操作
?深度优先、广度优先遍历
– 应用
下一页
上一页
停止放映
第 4 页
本单元涉及的内容
? 第 2章
– 2.5图的逻辑结构及其运算
– 2.6图类
– 2.7图的遍历
– 2.8树和图的基本应用
? P73~P90
下一页
上一页
停止放映
第 5 页
一,图及其基本概念
? 图是一种较之线性表和树形结构更为复杂
的非线性数据结构 。 图中各数据元素之间
的关系可以是任意的, 描述的是, 多对多,
的关系 。
– 图的定义
? 有向图, 无向图
– 图的基本概念
? 邻接点, 顶点, 边, 弧, 顶点的度
? 连通图, 强连通图, 连通分量
? 网, 权
下一页
上一页
停止放映
第 6 页
图结构
? 图是对结点的前趋和后继个数不加限制的
数据结构 。 有关图的理论, 在, 离散数学,
的图论中有详细论述和证明 。 在 DS中, 只
讨论图在计算机中的实现和操作 。
? 现实生活中, 图的应用范围很广泛, 涉及：
– 电讯工程, 电网调度, 集成电路设计
– 交通管理, 工程管理, 系统工程等领域
下一页
上一页
停止放映
第 7 页
图（ Graph）的定义
? 图 G = （ V,E ）
其中,V={ v1,v2,……,vn}是非空有穷的结
点集合 ;E 是顶点偶对的集合 。
? 例, 图 G1 = （ V,E）
V={v1,v2,v3,v4}
E={（ v1,v2）, （ v1,v3）,
（ v2,v1）, （ v2,v3）,
（ v2,v4）, （ v3,v1）,
（ v3,v2）, （ v4,v2）
}
o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 8 页
有向图、无向图
? 有向图（ Digraph）
图 G中顶点的偶对若是有向的，形成的图称有向
图。如图 G2所示。
为示区别，其偶对用 <vx,vy>表示。
? 无向图（ Undigraph）
图 G中顶点的偶对若是无向的，形成的图称为无
向图，其偶对用（ vx,vy）表示，如图 G1所示。
? G2=（ V,E）
V={ 1,2,3,4}
E={〈 1,2〉, 〈 1,3〉
,〈 3,4〉, 〈 4,1〉 }
1
3
2
4
G2
下一页
上一页
停止放映
第 9 页
边、弧
? 边 （ Edge）
顶点间的关系可描述为顶点的偶对, 也称为顶点的边 。
记为,（ Vx,Vy） 。 边是无序的, 可以看成是 （ Vx，
Vy）, 也可以看成是 （ Vy,Vx） 。
? 弧 （ Arc）
若顶点间的边是有方向性 （ 有序 ） 的, 则称该偶对为弧 。
记为,〈 Vx,Vy〉 。 弧是有序的, 〈 Vx,Vy〉 表示从
Vx到 Vy。
? 弧头 （ Head）
弧的终点 （ TerminaL Node） 称为弧头 （ 方向前方 ） 。
? 弧尾 （ Tail）
弧的起始点 （ Initial Node） 称为弧尾 （ 方向后方 ） 。
弧 〈 Vx,Vy〉 表示为, Vx Vy
弧尾 弧头
下一页
上一页
停止放映
第 10 页
顶点、邻接点
? 顶点 （ Vertex） 图中的数据元素 （ 结点 ） 称为顶点 。
如图 G1,G2中的Ｖ 1,Ｖ 2,1,2。
? 邻接点 （ Adjacent）
– 无向图中, 若边 （ Ｖ x,Ｖ y） ? E，
则Ｖ x,Ｖ y互为邻接点 。
– 有向图中, 若弧 〈 Ｖ x,Ｖ y〉 ? E，
则Ｖ y是Ｖ x的邻接点, 反之, 不是 。
Vx Vy
Ｖ x、Ｖ y互为邻接点
Vx Vy
Ｖ y是Ｖ x的邻接点
1
3
2
4
G2o o
oo
v1 v2
v3 v4G1
下一页
上一页
停止放映
第 11 页
顶点的度（ Degree）
? 无向图中, 顶点的 度 是以该顶点为一个端点的边
的条数 。 例如, G1中 V2的度为 3,V4的度为 1。
? 有向图中, 以某顶点为弧头的弧的数目称为该顶
点的 入度 （ Indegree） 。 例如 G2中顶点 1的入度
为 1。 以某顶点为弧尾的弧的数目称为该顶点的
出度 （ Outdegree） 。 例如 G2中顶点 1的出度为 2。
该顶点的度 =入度 +出度 。 例如, G2中顶点 1的度
=2+1=3。
o o
oo
v1 v2
v3 v4
G1 1
3
2
4
G2
下一页
上一页
停止放映
第 12 页
路径、长度
? 路径 （ Path）
在图中, 从顶点 Vx到顶点 Vy的顶点序列 （ Vx,V1，
V2,…,Vn,Vy)称为从 Vx到 Vy的路径 。 路径可能是
不唯一的 。 例如, G1中, V1到 V3的路径为：
（ V1V2V3） 或 （ V1V3） ；而 G2中, 1到 4的路径为
<134>。
? 长度 （ Length）
路径的长度是该路径上边或弧的数目 。 例如, G1
中 V1到 V3的长度为 1或 2；而 G2中 1到 4的长度为 2。
1
3
2
4
G2
o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 13 页
连通图、强连通图、连通分 量
1 2? 连通图（ Connected Graph）在无向图中，若每一对顶点间都有
路径，称此图是连通图。如图 G3所
示。
? 连通分量（ Connected Component）
无向图中的极大连通子图称为连通
分量 。
? 强连通图 （ Strongly Connected
Graph）
在有向图中, 若每对顶点 Vx到 Vy
间都存在 Vx到 Vy,及从 Vy到 Vx的路
径, 则称此图是强连通图 。 如图 G4
所示 。
3
4 5
G3
21
3
4 5
G4
下一页
上一页
停止放映
第 14 页
子图、生成树
? 子图
有两个图 G和 G1,若 V1?V,E1 ? E,即 V1中的顶点
G = （ V,E） 都属于 V中的顶点, E1中的关系都
G1 =（ V1,E1） 属于 E中的关系, 则称 G1是 G的子图 。
? 生成树
设 G是一个连通图, G中任一包含 G的所有顶点的子图
称为生成子图 。 如果该子图是树, 则称为 G的生成树 。
G的生成树不是唯一的 。 一棵有 n个顶点的生成树,
有且仅有 n-1条边 （ 弧 ） 。
下一页
上一页
停止放映
第 15 页
网、权
? 权 （ Weight）
若图的边或弧带有与之相关的数, 称此数为
该边或弧的权 。 权通常用来表示从一个顶点
到另一个顶点的距离或费用 。
? 网 （ Network）
带权的图称为网 。 如 G5为带权的网 。
V1 V2
V3V4
G523
5
7
下一页
上一页
停止放映
第 16 页
二、图的存储结构
前面在讨论树和线性表的存储结构时, 用
到两种存储结构：顺序表和链表 。 但图结构
中的结点间没有确定的关系 （ 没根 ）, 任意
两点之间都可能存在联系, 因此无法用顺序
结构来存放图的顶点数据 。 但借助数组可以
用来表示顶点之间的关系 。
实际上, 在图的存储结构中, 常用下面两
种方法：
– 邻接矩阵表示法
– 邻接表表示法
下一页
上一页
停止放映
第 17 页
1、邻接矩阵表示法
? 根据图的定义可知，图的逻辑结构分为两部
分,V和 E的集合。因此，
– 用一个一维数组存放图中所有顶点数据；
– 用一个二维数组存放顶点间关系（边或
弧）的数据，称这个二维数组为 邻接矩
阵 。
– 邻接矩阵又分为 有向图邻接矩阵 和 无向
图邻接矩阵 。
下一页
上一页
停止放映
第 18 页
有向图邻接矩阵
? 定义
设图 G=（ V,E） 是有 n（ n ? 1） 个顶点的图, 则 G的
邻接矩阵是具有下述性质的 nxn的方阵, 元素为：
1 当 〈 Vi,Vj>? E 时
A[ i,j] =
0 当 〈 Vi,Vj>? E 时
例如, G2的邻接矩阵为：
G.nodes=
1
2
3
4
A= G.Arc=
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0 4x4
1
3
2
4
G2
下一页
上一页
停止放映
第 19 页
无向图邻接矩阵
? 定义
设图 G=（ V,E）是有 n（ n ? 1）个顶点的图，则 G的邻
接矩阵是具有下述性质的对称阵，元素为：
1 当 (Vi,Vj） ? E 时
A[ i,j] =A[j,i] =
0 当 (Vi,Vj） ? E 时
例如,G1的邻接矩阵为：
G.nodes =
1
2
3
4
A=G.edge =
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0 4x4
o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 20 页
求图中顶点的度
? 借助邻接矩阵,可以很容易地求出图中顶点
的度 。
– 无向图 邻接矩阵的第 i行 （ 或第 i列 ）
的元素之和是顶点 Vi的度 。 例, G1中 V2
的度是 3。
– 有向图 邻接矩阵第 i行的元素之和为顶
点 Vi的出度；第 j列的元素之和为顶点 Vj
的入度 。 例, G2中, V2的出度为 0（ 第 2
行的元素之和为 0）, V1的入度为 1（ 第 1
列的元素之和为 1） 。
o o
oo
v1 v2
v3 v4
G1
A= G.Arc=
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
1
3
2
4
G2
下一页
上一页
停止放映
第 21 页
网的邻接矩阵
? 定义：
Wij 若 （ Vi,Vj） 或 〈 Vi,Vj〉 ? E
A[i,j] =
? 若 （ Vi,Vj） 或 〈 Vi,Vj〉 ? E
G.nodes=
V1
V2
V3
V4
A=G.Arc=
? 5 ? 3
? ? 2 ?
? ? ? ?
? ? 7 ? 4x4
G5的邻接矩阵。
V1 V2
V3V4
G523
5
7
下一页
上一页
停止放映
第 22 页
2、邻接表表示法
? 邻接表是图的一种链式存储结构 。 对图的每个顶点建立
一个单链表 （ n个顶点建立 n个单链表 ）, 第 i个单链表
中的结点包含顶点 Vi的所有邻接顶点 。
? 在邻接表中, 每个顶点由三个域组成：
? 每个单链表附设一个头结点, 结构为：
adjvex data nextarc
顶点 Vi的邻接点
与边或弧有关的权值
指向 Vi的下一个
邻接点的指针
Vexdata firstarc
指向 Vi单链表的第一个结点存放 Vi信息
下一页
上一页
停止放映
第 23 页
邻接表存储结构描述
C语言描述
#define VTXNUM n
struct arcnode {
int adjvex；
float data；
struct arcnode *nextarc；
}；
typedef struct arcnode ARCNODE ；
struct headnode {
int data ；
ARCNODE * firstarc ；
} adjlist[VTXNUM]；
下一页
上一页
停止放映
第 24 页
无向图 G1的邻接表
V1
V2
V3
V4
^V3V2
V1 V4 ^V3
^V1 V2
^V2
顶点 Vi的度恰好就是
第 i个单链表中的结点数。o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 25 页
有向图 G2的邻接表
1
2
3
4
^23
^4
^1
^
?在有向图中，第 i个单链表中结点的个数
是顶点 Vi的出度；例如,V2的出度为 0。
?为求入度，必须遍历整个邻接表。
1
3
2
4
G2
下一页
上一页
停止放映
第 26 页
逆邻接表
? 为求顶点 Vi的入度, 对每个顶点 Vi,建立一个
链接以 Vi为弧头的邻接点链表, 称该表为逆邻
接表 。 例如 G2的逆邻接表为：
1
2
3
4
4
1
1
3
^
^
^
^
显然逆邻接表的单链表中结点
的个数就是顶点 Vi的入度。
1
3
2
4
G2
下一页
上一页
停止放映
第 27 页
建立邻接表的算法
? 操作步骤：
– step1 初始化邻接表的 n个头结点, 并读入
一条弧或边的偶对 〈 i,j〉 或 （ i,j） 。
– step2 申请一个结点 S的空间, 将 S插入到
第 i个单链表中；
– step3 读下一条弧或边的偶对, 若存在此
弧或边, 则继续执行 step2；否则, 结束 。
下一页
上一页
停止放映
第 28 页
建立邻接表算法的程序
createadjlist(struct headnode G[],int n)
{ int i,j,k; float w; ARCNODE *s;
for (k=1; k<= n ; k++ )
{ scanf(,%d”,&G[k].data);
G[k].firstarc = NULL ;
}
scanf(“%d,%d,%f”,&i,&j,&w );
while (( i >=0 && i <n)&&(j>=0 && j<n))
{ s= (ARCNODDE *)malloc(sizeof(ARCNODE));
s->adjvex = j;
s->info = w;
s->nextarc = G[i].firstarc;
G[i].firstarc = s;
scanf(“%d,%d,%f”,&i,&j,&w);
}
}
下一页
上一页
停止放映
第 29 页
三、图的遍历
? 图的遍历 （ Traversing Graph）
从图中指定顶点出发访问图中每一个顶点, 且
使每个
顶点只被访问一次, 该过程为图的遍历 。
? 图的遍历要比树结构复杂的多 。 出发点不同,
任一顶点的邻接点就不相同, 路径也就不同 。
? 因为图中元素是, 多对多, 的关系, 为避免发
生重复, 设立一个辅助数组 visited[],每访
问一个顶点, 便将其状态 visited[i]置为
,真, 。
? 常用的图的遍历方法有两种：
– 深度优先遍历法
– 广度优先遍历法
下一页
上一页
停止放映
第 30 页
深度优先遍历法
? 深度优先遍历法类似于树的先根遍历法 。
? 算法思想：
– step1 从图中某个顶点 V0出发, 并访问此
顶点；
– step2 从 V0出发, 访问与 V0邻接的顶点 V1
后, 再从 V1出发, 访问与 V1邻接且未被访
问过的顶点 V2。 重复上述过程, 直到不存
在未访问过的邻接点为止 。
– step3 如果是连通图, 从任一顶点 V0出发,
就可以遍历所有相邻接的顶点；如果是非
连通图, 则再选择一个未被访问过的顶点
作为出发点, 重复 step1,step2,直到全
部被访问过的邻接点都被访问为止 。
下一页
上一页
停止放映
第 31 页
深度优先遍历法举例
遍历过程 访问顶点 所过边
?起始顶点 V1 V1
?V1的第 1个邻接点 V3 V3 （ V1,V3）
?V3的第 1个邻接点 V1已访问，取下
一个邻接点 V5 V5 （ V3,V5）
?V5的第 1个邻接点 V3已访问，取下
一个邻接点 V2 V2 （ V5,V2）
?V2的两个邻接点均被访问，
回退到 V5,V5的邻接点均被访问，
回退到 V3,V3的邻接点均被访问,
回退到 V1,V1的另一个邻接点 V4
未被访问 V4 （ V1,V4）
?V4的第一个邻接点 V1已被访问，
另一个邻接点 V6未被访问 V6 （ V4,V6）
?V6的邻接点被访问，回退到 V4
?V4的邻接点均被访问
?回退到 V1，返回到出发点，遍历结束。
V1
V3 V2
V5
V4
V6
G6
下一页
上一页
停止放映
第 32 页
遍历产生的结果
? 深度优先遍历 G6所走过的序列：
V1? V3 ? V5 ? V2 ? V4 ? V6
? 所走过的边：
（ V1,V3）, （ V3,V5）, （ V5,V2）, （ V1,V4）,
（ V4,V6）
? 遍历生成树
V1
V3
V5
V2
V4
V6
下一页
上一页
停止放映
第 33 页
深度优先遍历算法程序 (非递归 )
Traver_dfs(struct headnode G[],int v)
{ int i,stack[N],visited[N],top=-1 ; ARCNODE *p;
for (i=0;i<N;i++) visited[I]=0;
printf(“%d ->”,G[v].data);
visited[v]=1; top ++; stack[top]=v; p=G[v].firstarc;
while((top!=-1)||(p!=NULL))
{ while(p!=NULL)
{ if (visited[p->adjvex]) p=p->nextarc;
else { printf(“%d ->”,G[p->adjvex].data);
visited[p->adjvex]=1; top++; stack[top]=p->adjvex;
p=G[p->adjvex].firstarc; }
if( top !=-1)
{ v=stack[top]; top- -; p=G[v].firstarc;
p=p->nextarc; }
}
}
}
下一页
上一页
停止放映
第 34 页
广度优先遍历算法
? 广度优先遍历法类似于树的按层次遍历的
过程。即先访问第 1个顶点所有邻接点后，
再访问下一个顶点所有未被访问的邻接点。
? 算法思想：
– step1 从图中某个顶点 V0出发，并访问
此顶点；
– step2 从 V0出发，访问 V0的各个未曾访
问的邻接点 W1,W2,…,Wk;然后,依此从
W1,W2,…,Wk出发访问各自未被访问的邻
接点。
– step3 重复 step2，直到全部顶点都被访
问为止。
下一页
上一页
停止放映
第 35 页
广度优先遍历法举例
遍历过程 访问顶点 所过边
?起始顶点 V1 V1
?访问 V1的未被访问过
的所有邻接点 V3,V2,V4 （ V1,V3）
(V1,V2)
(V1,V4)
?访问 V3的未被访问过
的所有的邻接点 V5 （ V3,V5）
?访问 V2的未被访问过
的所有的邻接点 无
?访问 V4的未被访问过
的所有的邻接点 V6 (V4,V6)
?所有顶点已被访问,结束。
V1
V3 V2
V5
V4
V6
G6
下一页
上一页
停止放映
第 36 页
遍历产生的结果
? 广度优先遍历 G6所走过的序列：
V1? V3 ? V2 ? V4 ? V5 ? V6
? 所走过的边：
（ V1,V3）, （ V1,V2）, （ V1,V4）, （ V3,V5）, （ V4,V6）
? 遍历生成树
V1
V3
V5
V2 V4
V6
下一页
上一页
停止放映
第 37 页
四、图的操作
? 图中顶点无序可言
– 任一顶点都可以看作第一个顶点；
– 任一顶点的邻接点间也无序可言；
? 为操作方便, 对图中顶点按人为意志给其
排序；同样, 也可以对某个顶点的所有邻
接点进行排队, 在这个队列中自然形成第
一个或第 K个邻接点 。 若某个顶点的邻接
点个数大于 K,则称第 K+1个邻接点为第 K
个邻接点的下一个邻接点, 而最后一个邻
接点的下一个邻接点为, 空, 。
下一页
上一页
停止放映
第 38 页
图的常用基本操作
? LOC_VERTEX（ G,Vi） 确定顶点 Vi在 G中的位置 。
? GET_VERTEX（ G,i） 求图 G中第 i个顶点 。
? FIRST_VERTEX（ G,i） 求图 G中 Vi的第 1个邻接点 。
? NEXT_ADJ(G,v,w) 已知 w为 G中顶点 v的第 1个邻接
点,求顶点 w的下一个邻接点 。
? INS_VERTEX(G,u) 在图 G中插入一个顶点 u,为图 G
的第 n+1个顶点 。
? INS_ARC(G,v,w) 在图 G中插入一条从顶点 v到顶点
w的弧 。
? DEL_VERTEX(G,Vi) 删除图 G中顶点 Vi,以及与 Vi相
关联的边或弧 。
? DEL_ARC(G,v,w) 删除图 G中从顶点 v到顶点 w的弧 。
下一页
上一页
停止放映
第 39 页
五、图的应用
? 最小生成树
? 拓扑排序
? 关键路径
? 最短路径
下一页
上一页
停止放映
第 40 页
最小生成树
? 该问题是构造连通图的最小代价生成树问题 。
一棵生成树的代价就是树上各边 （ 弧 ） 的代
价之和 。
? 例如, 若要在 n个城市间建立通信联络网,
则只需 n-1条线路 。 但在 n个城市间, 最多可
能架设 n（ n-1） /2条线路, 选择哪 n-1条线
路, 使费用最少 。
– 普里姆 （ Prim） 算法
– 克鲁斯卡尔 （ Kruskal） 算法
下一页
上一页
停止放映
第 41 页
普里姆（ Prim） 算法
? 假设 N=（ V,E） 是连通图, TE是 N上最小生
成树中边的集合 。
– 从 U={u0} （ u0 ? V）, TE= 空开始；
– 重复执行,在所有 u?U,v ?V-U的边
（ u,v） ?E中找一条代价最小的边 （ u0，
v0） 并入 TE,同时 u0并入 U,直到 U=V为
止；
– 此时 TE中必有 n-1条边, 则 T=（ V,TE）
为 N的最小生成树 。
下一页
上一页
停止放映
第 42 页
普里姆（ Prim） 算法举例
1
2
3 4
5
6
8 7
2
1
4
35
7 6
8
11
10
9
12
U={1},V-U={2,3,4,5,6,7,8}
1
2
2
1
2
4
2
1
4 7
3
（ 1）
（ 2） （ 3）
(1) U={1,2},V-U={3,4,5,6,7,8}
(2) U={1,2,4},V-U={3,5,6,7,8}
(3) U={1,2,4,7},V-U={3,5,6,8}
下一页
上一页
停止放映
第 43 页
普里姆（ Prim） 算法举例 (续 )
4 7
5
3
5
（ 4）
7
6
（ 5）
6
（ 6）
4 7
6
3 8
（ 7）
8 3
6
5
4 7
2
2 1
3
6
589
(4) U={1,2,4,7,5},V-U={3,6,8}
(5) U={1,2,4,7,5,6},V-U={3,8}
(6) U={1,2,4,7,5,6,3},V-U={8}
(7) U={1,2,4,7,5,6,3,8),V-U={ }
4 3
6
3
1
下一页
上一页
停止放映
第 44 页
克鲁斯卡尔（ Kruskal）算法
? 操作步骤,
– 假设 N=（ V,E） 是连通图
– 取图中每个顶点自成一个连通分量
– 在 { E }中选择代价最小的边, 若该边所
依附的顶点落在 T中不同的连通分量上,
则将此边加入生成树 T中；否则, 舍去此
边, 再选择下一条代价最小的边 。
– 重复上述步, 直到 T中所有顶点都在同一
连通分量上为止 。
下一页
上一页
停止放映
第 45 页
克鲁斯卡尔（ Kruskal）算法举例
1
2 3 4
5 6
1 5
24
6
63
55
6
1
2 3 4
5 6
(1)
1
3
(2)
1
1
3
1 4
6
2
(3)
2
5
1
3
4
6
1
2
3
(4)
下一页
上一页
停止放映
第 46 页
克鲁斯卡尔（ Kruskal）算法举例 (续）
1
2 3 4
5 6
(5)
1
23 4
1
32
5 6
4
1
243
5 （ 6）
1
2 3 4
5 6
1 5
24
6
63
55
6
下一页
上一页
停止放映
第 47 页
拓扑排序
? 研究一个有机整体中不同个体间的次序问题 。
例如课程间优先关系有向图问题 。
? 软件专业的课程优先关系：
课程编号 课程名称 先决条件
C1 程序设计基础 无
C2 离散数学 C1
C3 汇编语言 C1,C2
……
C9 高等数学 无
下一页
上一页
停止放映
第 48 页
拓扑排序举例
? 方法步骤
– 在有向图中选一个没有前驱的顶点并输出 ;
– 从图中删除该顶点和所有以它为尾的弧 ;
– 重复前 2步,直到全部顶点均输出为止 。
– 输出序列即为拓扑排序序列 。
? 拓扑排序序列不唯一 。
下一页
上一页
停止放映
第 49 页
拓扑排序举例
C1
C9
C4
C2
C3
C5
C7
C12
C10
C11
C6
C8
?C1 C2 C3 C4 C5 C7 C9 C10 C11 C6 C12 C8
?C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C8
下一页
上一页
停止放映
第 50 页
关键路径
? 研究的是在一个有机整体中
不同个体间的次序问题 。
即研究的是工程进度及影响进
度的关键因素问题 。
下一页
上一页
停止放映
第 51 页
最短路径
? 研究的是类似于交通调度一
类的带权有向图问题 。 求路
径最短或费用最省 。
下一页
上一页
停止放映
第 52 页
六、二叉排序树的生成
对给定数列 {a1,a2,…,an},根据二叉排序树特性,逐个将
结点插入到二叉排序中 。
具体操作步骤：
step1 a1是根结点；
step2 若 ai<aj,且 aj的左子为空,则将 ai插入到 aj的左子 ;
若 aj的左子非空,则继续寻找合适的插入位置 。
若 ai?aj,且 aj的右子为空, 则将 ai插入到 aj的右子；
否则继续沿右子树寻找合适的插入位置；
插入 ai 插入到 aj的左子 ai〈 aj
插入到 aj的右子 ai ? aj
step3 重复 step2，直到所有结点插入完为止。
下一页
上一页
停止放映
第 53 页
二叉排序树算法
二叉排序树结点结构：
struct tree {
char info；
struct tree *left, * right ；
}
算法描述,
? 输入结点非空循环,若是第 1个结点,令指针
ROOT指向该结点。
? 打印输出该二叉排序树；
? 输入一个值，在该树中查找，若找到输出该
结点值；否则，显示查找失败。
下一页
上一页
停止放映
第 54 页
二叉排序树生成算法
建立二叉树
Create_btree()
查询结点
Search_btree()
打印二叉树
Print_btree()
主程序
Btree.C
下一页
上一页
停止放映
第 55 页
主程序框图
开始
初始化
输入结点数据
！ ROOT
root=create_btee（） create_btree()
结束?
N
Y
打印该树
查找指定结点
Print_btree()
Search_btree()
下一页
上一页
停止放映
第 56 页
生成二叉排序树程序框图
Create_btree() 开始
r = 0？
Y
申请结点空间
r = 0？显示“溢出”
结束
根结点的处理 N
Y
N
r->left = 0;
r->right = 0;
r->info = info ;
非根结点
info<r->info?Y
t=r->left t=r->right
N
调用本函数
root?
返回
Y N
r->left=0
r->right=0
root->left=r
或
root->right=r
下一页
上一页
停止放映
第 57 页
查询二叉排序树算法框图
开始 Search_btree()
!root
Y
显示“空树”
返回
N
root->info!=key循环
key<root->info?
root=root->left root=root->right
root=0?
NY
查找成功,显示 返回
显示“失败”
root!=0?
循环结束?
N
Y
下一页
上一页
停止放映
第 58 页
打印算法框图
开始 Print_btree()
r=0?
Y
N
调用自身打印左子
打印当前结点值
调用自身打印右子
返回
下一页
上一页
停止放映
第 59 页
主程序 Btree.C
#include,stdio.h”
struct tree {
char info;
struct tree *left,*right;
}
main ( )
{ char *s,*c,key=??;
struct tree *create_btree(),*search_btree(),*root=0;
do {
printf(“Enter a letter:”);
gets(s);
if (!root)
root=create_btree(root,root,*s);
else
create_btrr(root,root,*s);
} while (*s) ;
下一页
上一页
停止放映
第 60 页
主程序 Btree.C(续）
print_btree(root,0);
key=?1?;
while ( key)
{
printf(“Enter a key to find:”);
scanf(“%s”,&c);
key=search_btree(root,c);
printf(“press to continue\n”);
}
} /* Btree。 C 结束 */
下一页
上一页
停止放映
第 61 页
生成二叉排序树程序
struct tree create_btree(root,r,info)
struct tree *root,*r;
char info;
{ if (r = =0 )
{ r=malloc(sizeof(struct tree));
if ( r = = 0)
{ printf(“Out of memory\n”); exit(0); }
r->left= 0; r->right=0; r->info=info;
if (root)
{ if(info<root->info) root -> left=r;
else root->right=r;
}
else
{ r->right=0; r->left = 0; }
return r;
} /* if = = 0 接下页 */
下一页
上一页
停止放映
第 62 页
生成二叉排序树程序 （续）
if (info < r->info)
create_btree(r,r->left,info);
if(info>=r->info)
create_btree(r,r->right,info);
} /* create_btree(root,r,info) */
下一页
上一页
停止放映
第 63 页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Emptu btree\n”); return root; }
while(root->info!=key)
{ if(key<root->info)
root=root->left;
else
root=root->right;
if(root==0)
{ printf(“Search Failure\n”);
break ;
}
} /* while(root->info!=key) */
查询二叉排序树程序
下一页
上一页
停止放映
第 64 页
if (root !=0)
printf(“Successful search\n key=%c\n”,root->info);
return root ;
} /* *search_btree(root,key) */
查询二叉排序树程序（续）
下一页
上一页
停止放映
第 65 页
打印二叉排序树程序
print_btree(r,l)
struct tree *r;
int l;
{ int i;
if (r = = 0) return ;
print_tree(r->left,l+1);
for(i=0;i<l;i++)
printf(“,);
printf(“%c\n”,r->info);
print_btree(r->right,l+1);
}
下一页
上一页
停止放映
第 66 页
程序输入
输入,输出：
h ? b
d ? d
p ? e
r ? h
b ? p
e ? r
?
下一页
上一页
停止放映
第 67 页
举例
对数列 {10,18,3,4,9,13,25},生成二叉排序
树 。
10
（ 7）
10
18
（ 2）
10
3 18
（ 3）
10
3 18
4（ 4）
10
3
4
18
9
10
3
4
9
18
13
（ 6） （ 5）
10
3
9
4
18
13 25
（ 1）
下一页
上一页
停止放映
第 68 页
平衡二叉排序树
在二叉排序树的动态生成过程中, 由于数据本身
的特性, 将影响二叉排序树的性质, 例如 {3,5,7，
9,20}这样的数列, 生成的二叉排序树就是一棵单
枝树 。 因此, 在动态生成二叉排序树的过程中, 要
进行平衡化处理 。
平衡化处理就是在
不影响 二 叉 排序树特性的前题
下, 通过, 旋转, 处理, 使该结点
的平衡因子不大于 2。
旋转分,LL,RR,LR和 RL
四种 。
3
5
7
9
20
下一页
上一页
停止放映
第 69 页
LL平衡化处理
由于在 A的左子树的左子树上插入结点, 使 A
点失去平衡, 需进行一次 LL旋转 （ 顺时针
旋转 ） 操作 。
示意为：
程序实现为：
b = a?.lc
a?.lc = b?.rc
b?.rc = a
a?.bf = 0
b?.bf = 0
b为子树的新根
A
B
C
LL B
C A
下一页
上一页
停止放映
第 70 页
RR平衡化处理
由于在 A的右子树的右子树上插入结点, 使 A点失去平
衡, 需进行一次 RR旋转 （ 逆时针旋转 ） 操作 。
示意为：
程序实现为：
b = a?.rc
a?.rc = b?.lc
b?.lc = a
a?.bf = 0
b?.bf = 0
b为子树新根
A
B
C
RR B
A C
下一页
上一页
停止放映
第 71 页
LR平衡化处理
由于在 A的左子树的右子树上插入结点, 使 A
点失去平衡, 需进行一次 LR旋转 （ 两次旋转 ;
先逆时针,再顺时针旋转 ） 操作 。
示意为：
程序实现为：
b = a?.lc,c = b?.rc,a?.lc =
c?.rc
b?.rc = c?.lc,c?.lc = b,c?.rc = a
A
B
C
C
B A
A
C
B
下一页
上一页
停止放映
第 72 页
RL平衡化处理
由于在 A的右子树的左子树上插入结点, 使 A点失
去平衡, 需进行一次 RL旋转 （ 两次旋转 ;先顺时
针,再逆时针旋转 ） 操作 。
示意为：
程序实现为：
b = a?.rc,c = b?.lc,a?.rc = c?.lc
b?.lc = c?.rc,c?.lc = a,c?.rc = b
A
B
C
C
A B
A
C
B
下一页
上一页
停止放映
第 73 页
平衡化处理举例
有数据序列 {13,24,37,90,53}
? 插入 13,树是平衡的 ;
? 插入 24,树仍为平衡 ;
? 插入 37,树不再平衡,
执行 RR旋转 ;
? 插入 90,树仍平衡 ;
? 插入 53,失去平衡,
执行 RL旋转,
13
13
24
(1) (2)
13
24
37 3713
24
(3)
24
13 37
90
(4)
24
13 37
90
53
24
13 37
53
90
24
13 53
37 90
(5)
下一页
上一页
停止放映
第 74 页
Huffman(哈夫曼）树及应用
? Huffman树的定义
? 构造 Huffman树
? Huffman编码
? Huffman编码的译码
下一页
上一页
停止放映
第 75 页
Huffman树的定义
? Huffman树也称为最优树，是一类带权路径最短
的二叉树。
? 树的带权路径长度定义为：
WPL = ∑ wklk
k = 1
n
其中：
n 是树中叶结点的个数
wi 是第 i个结点的权值
li 是第 i个结点的路径长度
下一页
上一页
停止放映
第 76 页
Huffman树举例
? 以下有三棵树：
（ a） （ b） （ c）
a
b
c d
a b c d
a
c
b
d7
7
7
5
5
52
2
2
4 4
4WPLa =7x2+5x2+2x2+4x2
= 36 WPL
b =7x3+5x3+2x1+4x2
= 46
WPLc =
7x1+5x2+2x3+4x3
= 35 √
? 事实证明按哈夫曼树构造二叉树，可得到很好的特
性，应用于实际问题，可提高处理效率。
下一页
上一页
停止放映
第 77 页
应用举例
? 由统计规律可知，考试成绩的分布符合正态分布：
-1 10
分数 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100
比例数 0.05 0.15 0.40 0.3 0.10
? 根据正态分布规律，在 60 ～ 90之间的分数占 85%，
而不及格和优秀是少数。
下一页
上一页
停止放映
第 78 页
将百分制转换成五分制
? 判定树比较,a<60?
a<70?
a<80?
a<90?
不及格
及格
中等
良好 优秀
Y
Y
Y
Y
N N
N
N
a<80?
a<70? a<90?
a<60?
不及格
优秀良好
中等
中等及格不及格
Y
Y
Y N
N
N NY
(A)
(B)
? 若输入 1万个数据，按 A的判定过程进行操作，约需比较 3.2
万次，而按 B比较,则仅需 2.2万次。
下一页
上一页
停止放映
第 79 页
构造 Huffman树
? 构造 Huffman树算法步骤：
– 1）将 n个带权值 wi（ i≤n）的结点构成 n棵二叉
树的集合 T={T1,T2,……, Tn}，每棵二叉树
只有一个根结点。
– 2）在 T中选取两个权值最小的结点作为左右子
树，构成一个新的二叉树，其根结点的权值取
左右子树权值之和；
– 3）在 T中删除这两棵树，将新构成的树加入到
T中；
– 4）重复 2）,3）步的操作，直到 T中只含一棵
树为止，该树就是 Huffman树。
下一页
上一页
停止放映
第 80 页
构造 Huffman树举例
? 以权值分别为 7,5,2,4的结点 a,b,c,d构造
Huffman树。 T= { a b c d }
（ a） T= { a b c d }
（ b） T= { a b T3 }
（ c） T= { a T2 }
（ d） T={ T1 }
c d
T
3
b T1
T
2
2 4
6
65
11
b
T
2 65
11
c d2 4
18
a T27
11
T
1
18
a7
T
1
b T1
T
2 65
11
18
a7
T
1
b5
11
c d2
6
4
下一页
上一页
停止放映
第 81 页
Huffman编码
? 编码：用二进制数的不同组合来表示字符的方法。
? 前缀编码：一种非等长度的编码。任一个字符的
编码都不是另一个字符编码的前缀。
a
0
b
0
1
c d
0
1
1
编码,A（ 0）
B（ 01）
C（ 011）
D（ 111）
方法约定：
1）左分支为‘ 0’
2）右分支为‘ 1’
3）由根到叶路径上字符组
成的二进制串就是该叶结点
的编码。
? Huffman编码：一种非等长度的编码。以给定权
值的结点构造 Huffman树，按二进制前缀编码的
方式构成的编码为 Huffman编码。
下一页
上一页
停止放映
第 82 页
Huffman编码举例
? 在某系统的通信联络中可能出现 8种字符，其频率
分别为 0.05,0.29,0.07,0.08,0.14,0.23、
0.03,0.11，设权值分别为 {5,29,7,8,14，
23,3,11},n=8，其 Huffman树为：
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 83 页
Huffman编码存储结构
? 由于 Huffman树中没有度为 1的结点，则 n个叶结点
的 Huffman树共有 2n-1个结点。例如,4个结点的
Huffman树，共有 7个结点。因此可以用长度为 2n-1
的一维数组存放。
? 求 Huffman编码,从叶到根的编码。因此要知道每
个结点的父结点。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 84 页
Huffman编码的译码
? 从 Huffman编码树上不难看出，代码全部在叶结
点上，根据 Huffman编码，就能求出相应的字符。
该过程称为“译码”。
? 译码是根据从根到叶的 Huffman编码求相应的字
符。因此要知道每个结点的左右子结点。
? 例如，根据,1111”，就能求出对应的字符是,8”。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
下一页
上一页
停止放映
第 85 页
作业、思考题
1、思考题：
3,4,18
2、第 2章作业
8,13,20
2、作业要求：
– 作业命名方式为：
学号,章数 _序号
下一页
上一页
停止放映
第 86 页
结束语
? 欢迎参加网上讨论，网站的地址：
http,//ctec.xjtu.edu.cn
? 数字化课件的路径,
jec253\user2\tools\lzq\软件基础
谢谢，再见！
计算机软件基础
The software basic
of computer
主讲：刘志强
西安交通大学
计算机教学实验中心
第 5单元
非线性数据结构
图
下一页
上一页
停止放映
第 2 页
教学目标
? 了解有关图的
– 基本概念
– 存储结构及实现
– 遍历算法
下一页
上一页
停止放映
第 3 页
教学要求
? 通过本单元学习，了解、掌握有关图,
– 基本概念
?有向图、无向图、连通图、网
– 存储结构及实现
?邻接矩阵、邻接表
– 遍历及其它操作
?深度优先、广度优先遍历
– 应用
下一页
上一页
停止放映
第 4 页
本单元涉及的内容
? 第 2章
– 2.5图的逻辑结构及其运算
– 2.6图类
– 2.7图的遍历
– 2.8树和图的基本应用
? P73~P90
下一页
上一页
停止放映
第 5 页
一,图及其基本概念
? 图是一种较之线性表和树形结构更为复杂
的非线性数据结构 。 图中各数据元素之间
的关系可以是任意的, 描述的是, 多对多,
的关系 。
– 图的定义
? 有向图, 无向图
– 图的基本概念
? 邻接点, 顶点, 边, 弧, 顶点的度
? 连通图, 强连通图, 连通分量
? 网, 权
下一页
上一页
停止放映
第 6 页
图结构
? 图是对结点的前趋和后继个数不加限制的
数据结构 。 有关图的理论, 在, 离散数学,
的图论中有详细论述和证明 。 在 DS中, 只
讨论图在计算机中的实现和操作 。
? 现实生活中, 图的应用范围很广泛, 涉及：
– 电讯工程, 电网调度, 集成电路设计
– 交通管理, 工程管理, 系统工程等领域
下一页
上一页
停止放映
第 7 页
图（ Graph）的定义
? 图 G = （ V,E ）
其中,V={ v1,v2,……,vn}是非空有穷的结
点集合 ;E 是顶点偶对的集合 。
? 例, 图 G1 = （ V,E）
V={v1,v2,v3,v4}
E={（ v1,v2）, （ v1,v3）,
（ v2,v1）, （ v2,v3）,
（ v2,v4）, （ v3,v1）,
（ v3,v2）, （ v4,v2）
}
o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 8 页
有向图、无向图
? 有向图（ Digraph）
图 G中顶点的偶对若是有向的，形成的图称有向
图。如图 G2所示。
为示区别，其偶对用 <vx,vy>表示。
? 无向图（ Undigraph）
图 G中顶点的偶对若是无向的，形成的图称为无
向图，其偶对用（ vx,vy）表示，如图 G1所示。
? G2=（ V,E）
V={ 1,2,3,4}
E={〈 1,2〉, 〈 1,3〉
,〈 3,4〉, 〈 4,1〉 }
1
3
2
4
G2
下一页
上一页
停止放映
第 9 页
边、弧
? 边 （ Edge）
顶点间的关系可描述为顶点的偶对, 也称为顶点的边 。
记为,（ Vx,Vy） 。 边是无序的, 可以看成是 （ Vx，
Vy）, 也可以看成是 （ Vy,Vx） 。
? 弧 （ Arc）
若顶点间的边是有方向性 （ 有序 ） 的, 则称该偶对为弧 。
记为,〈 Vx,Vy〉 。 弧是有序的, 〈 Vx,Vy〉 表示从
Vx到 Vy。
? 弧头 （ Head）
弧的终点 （ TerminaL Node） 称为弧头 （ 方向前方 ） 。
? 弧尾 （ Tail）
弧的起始点 （ Initial Node） 称为弧尾 （ 方向后方 ） 。
弧 〈 Vx,Vy〉 表示为, Vx Vy
弧尾 弧头
下一页
上一页
停止放映
第 10 页
顶点、邻接点
? 顶点 （ Vertex） 图中的数据元素 （ 结点 ） 称为顶点 。
如图 G1,G2中的Ｖ 1,Ｖ 2,1,2。
? 邻接点 （ Adjacent）
– 无向图中, 若边 （ Ｖ x,Ｖ y） ? E，
则Ｖ x,Ｖ y互为邻接点 。
– 有向图中, 若弧 〈 Ｖ x,Ｖ y〉 ? E，
则Ｖ y是Ｖ x的邻接点, 反之, 不是 。
Vx Vy
Ｖ x、Ｖ y互为邻接点
Vx Vy
Ｖ y是Ｖ x的邻接点
1
3
2
4
G2o o
oo
v1 v2
v3 v4G1
下一页
上一页
停止放映
第 11 页
顶点的度（ Degree）
? 无向图中, 顶点的 度 是以该顶点为一个端点的边
的条数 。 例如, G1中 V2的度为 3,V4的度为 1。
? 有向图中, 以某顶点为弧头的弧的数目称为该顶
点的 入度 （ Indegree） 。 例如 G2中顶点 1的入度
为 1。 以某顶点为弧尾的弧的数目称为该顶点的
出度 （ Outdegree） 。 例如 G2中顶点 1的出度为 2。
该顶点的度 =入度 +出度 。 例如, G2中顶点 1的度
=2+1=3。
o o
oo
v1 v2
v3 v4
G1 1
3
2
4
G2
下一页
上一页
停止放映
第 12 页
路径、长度
? 路径 （ Path）
在图中, 从顶点 Vx到顶点 Vy的顶点序列 （ Vx,V1，
V2,…,Vn,Vy)称为从 Vx到 Vy的路径 。 路径可能是
不唯一的 。 例如, G1中, V1到 V3的路径为：
（ V1V2V3） 或 （ V1V3） ；而 G2中, 1到 4的路径为
<134>。
? 长度 （ Length）
路径的长度是该路径上边或弧的数目 。 例如, G1
中 V1到 V3的长度为 1或 2；而 G2中 1到 4的长度为 2。
1
3
2
4
G2
o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 13 页
连通图、强连通图、连通分 量
1 2? 连通图（ Connected Graph）在无向图中，若每一对顶点间都有
路径，称此图是连通图。如图 G3所
示。
? 连通分量（ Connected Component）
无向图中的极大连通子图称为连通
分量 。
? 强连通图 （ Strongly Connected
Graph）
在有向图中, 若每对顶点 Vx到 Vy
间都存在 Vx到 Vy,及从 Vy到 Vx的路
径, 则称此图是强连通图 。 如图 G4
所示 。
3
4 5
G3
21
3
4 5
G4
下一页
上一页
停止放映
第 14 页
子图、生成树
? 子图
有两个图 G和 G1,若 V1?V,E1 ? E,即 V1中的顶点
G = （ V,E） 都属于 V中的顶点, E1中的关系都
G1 =（ V1,E1） 属于 E中的关系, 则称 G1是 G的子图 。
? 生成树
设 G是一个连通图, G中任一包含 G的所有顶点的子图
称为生成子图 。 如果该子图是树, 则称为 G的生成树 。
G的生成树不是唯一的 。 一棵有 n个顶点的生成树,
有且仅有 n-1条边 （ 弧 ） 。
下一页
上一页
停止放映
第 15 页
网、权
? 权 （ Weight）
若图的边或弧带有与之相关的数, 称此数为
该边或弧的权 。 权通常用来表示从一个顶点
到另一个顶点的距离或费用 。
? 网 （ Network）
带权的图称为网 。 如 G5为带权的网 。
V1 V2
V3V4
G523
5
7
下一页
上一页
停止放映
第 16 页
二、图的存储结构
前面在讨论树和线性表的存储结构时, 用
到两种存储结构：顺序表和链表 。 但图结构
中的结点间没有确定的关系 （ 没根 ）, 任意
两点之间都可能存在联系, 因此无法用顺序
结构来存放图的顶点数据 。 但借助数组可以
用来表示顶点之间的关系 。
实际上, 在图的存储结构中, 常用下面两
种方法：
– 邻接矩阵表示法
– 邻接表表示法
下一页
上一页
停止放映
第 17 页
1、邻接矩阵表示法
? 根据图的定义可知，图的逻辑结构分为两部
分,V和 E的集合。因此，
– 用一个一维数组存放图中所有顶点数据；
– 用一个二维数组存放顶点间关系（边或
弧）的数据，称这个二维数组为 邻接矩
阵 。
– 邻接矩阵又分为 有向图邻接矩阵 和 无向
图邻接矩阵 。
下一页
上一页
停止放映
第 18 页
有向图邻接矩阵
? 定义
设图 G=（ V,E） 是有 n（ n ? 1） 个顶点的图, 则 G的
邻接矩阵是具有下述性质的 nxn的方阵, 元素为：
1 当 〈 Vi,Vj>? E 时
A[ i,j] =
0 当 〈 Vi,Vj>? E 时
例如, G2的邻接矩阵为：
G.nodes=
1
2
3
4
A= G.Arc=
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0 4x4
1
3
2
4
G2
下一页
上一页
停止放映
第 19 页
无向图邻接矩阵
? 定义
设图 G=（ V,E）是有 n（ n ? 1）个顶点的图，则 G的邻
接矩阵是具有下述性质的对称阵，元素为：
1 当 (Vi,Vj） ? E 时
A[ i,j] =A[j,i] =
0 当 (Vi,Vj） ? E 时
例如,G1的邻接矩阵为：
G.nodes =
1
2
3
4
A=G.edge =
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0 4x4
o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 20 页
求图中顶点的度
? 借助邻接矩阵,可以很容易地求出图中顶点
的度 。
– 无向图 邻接矩阵的第 i行 （ 或第 i列 ）
的元素之和是顶点 Vi的度 。 例, G1中 V2
的度是 3。
– 有向图 邻接矩阵第 i行的元素之和为顶
点 Vi的出度；第 j列的元素之和为顶点 Vj
的入度 。 例, G2中, V2的出度为 0（ 第 2
行的元素之和为 0）, V1的入度为 1（ 第 1
列的元素之和为 1） 。
o o
oo
v1 v2
v3 v4
G1
A= G.Arc=
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
1
3
2
4
G2
下一页
上一页
停止放映
第 21 页
网的邻接矩阵
? 定义：
Wij 若 （ Vi,Vj） 或 〈 Vi,Vj〉 ? E
A[i,j] =
? 若 （ Vi,Vj） 或 〈 Vi,Vj〉 ? E
G.nodes=
V1
V2
V3
V4
A=G.Arc=
? 5 ? 3
? ? 2 ?
? ? ? ?
? ? 7 ? 4x4
G5的邻接矩阵。
V1 V2
V3V4
G523
5
7
下一页
上一页
停止放映
第 22 页
2、邻接表表示法
? 邻接表是图的一种链式存储结构 。 对图的每个顶点建立
一个单链表 （ n个顶点建立 n个单链表 ）, 第 i个单链表
中的结点包含顶点 Vi的所有邻接顶点 。
? 在邻接表中, 每个顶点由三个域组成：
? 每个单链表附设一个头结点, 结构为：
adjvex data nextarc
顶点 Vi的邻接点
与边或弧有关的权值
指向 Vi的下一个
邻接点的指针
Vexdata firstarc
指向 Vi单链表的第一个结点存放 Vi信息
下一页
上一页
停止放映
第 23 页
邻接表存储结构描述
C语言描述
#define VTXNUM n
struct arcnode {
int adjvex；
float data；
struct arcnode *nextarc；
}；
typedef struct arcnode ARCNODE ；
struct headnode {
int data ；
ARCNODE * firstarc ；
} adjlist[VTXNUM]；
下一页
上一页
停止放映
第 24 页
无向图 G1的邻接表
V1
V2
V3
V4
^V3V2
V1 V4 ^V3
^V1 V2
^V2
顶点 Vi的度恰好就是
第 i个单链表中的结点数。o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 25 页
有向图 G2的邻接表
1
2
3
4
^23
^4
^1
^
?在有向图中，第 i个单链表中结点的个数
是顶点 Vi的出度；例如,V2的出度为 0。
?为求入度，必须遍历整个邻接表。
1
3
2
4
G2
下一页
上一页
停止放映
第 26 页
逆邻接表
? 为求顶点 Vi的入度, 对每个顶点 Vi,建立一个
链接以 Vi为弧头的邻接点链表, 称该表为逆邻
接表 。 例如 G2的逆邻接表为：
1
2
3
4
4
1
1
3
^
^
^
^
显然逆邻接表的单链表中结点
的个数就是顶点 Vi的入度。
1
3
2
4
G2
下一页
上一页
停止放映
第 27 页
建立邻接表的算法
? 操作步骤：
– step1 初始化邻接表的 n个头结点, 并读入
一条弧或边的偶对 〈 i,j〉 或 （ i,j） 。
– step2 申请一个结点 S的空间, 将 S插入到
第 i个单链表中；
– step3 读下一条弧或边的偶对, 若存在此
弧或边, 则继续执行 step2；否则, 结束 。
下一页
上一页
停止放映
第 28 页
建立邻接表算法的程序
createadjlist(struct headnode G[],int n)
{ int i,j,k; float w; ARCNODE *s;
for (k=1; k<= n ; k++ )
{ scanf(,%d”,&G[k].data);
G[k].firstarc = NULL ;
}
scanf(“%d,%d,%f”,&i,&j,&w );
while (( i >=0 && i <n)&&(j>=0 && j<n))
{ s= (ARCNODDE *)malloc(sizeof(ARCNODE));
s->adjvex = j;
s->info = w;
s->nextarc = G[i].firstarc;
G[i].firstarc = s;
scanf(“%d,%d,%f”,&i,&j,&w);
}
}
下一页
上一页
停止放映
第 29 页
三、图的遍历
? 图的遍历 （ Traversing Graph）
从图中指定顶点出发访问图中每一个顶点, 且
使每个
顶点只被访问一次, 该过程为图的遍历 。
? 图的遍历要比树结构复杂的多 。 出发点不同,
任一顶点的邻接点就不相同, 路径也就不同 。
? 因为图中元素是, 多对多, 的关系, 为避免发
生重复, 设立一个辅助数组 visited[],每访
问一个顶点, 便将其状态 visited[i]置为
,真, 。
? 常用的图的遍历方法有两种：
– 深度优先遍历法
– 广度优先遍历法
下一页
上一页
停止放映
第 30 页
深度优先遍历法
? 深度优先遍历法类似于树的先根遍历法 。
? 算法思想：
– step1 从图中某个顶点 V0出发, 并访问此
顶点；
– step2 从 V0出发, 访问与 V0邻接的顶点 V1
后, 再从 V1出发, 访问与 V1邻接且未被访
问过的顶点 V2。 重复上述过程, 直到不存
在未访问过的邻接点为止 。
– step3 如果是连通图, 从任一顶点 V0出发,
就可以遍历所有相邻接的顶点；如果是非
连通图, 则再选择一个未被访问过的顶点
作为出发点, 重复 step1,step2,直到全
部被访问过的邻接点都被访问为止 。
下一页
上一页
停止放映
第 31 页
深度优先遍历法举例
遍历过程 访问顶点 所过边
?起始顶点 V1 V1
?V1的第 1个邻接点 V3 V3 （ V1,V3）
?V3的第 1个邻接点 V1已访问，取下
一个邻接点 V5 V5 （ V3,V5）
?V5的第 1个邻接点 V3已访问，取下
一个邻接点 V2 V2 （ V5,V2）
?V2的两个邻接点均被访问，
回退到 V5,V5的邻接点均被访问，
回退到 V3,V3的邻接点均被访问,
回退到 V1,V1的另一个邻接点 V4
未被访问 V4 （ V1,V4）
?V4的第一个邻接点 V1已被访问，
另一个邻接点 V6未被访问 V6 （ V4,V6）
?V6的邻接点被访问，回退到 V4
?V4的邻接点均被访问
?回退到 V1，返回到出发点，遍历结束。
V1
V3 V2
V5
V4
V6
G6
下一页
上一页
停止放映
第 32 页
遍历产生的结果
? 深度优先遍历 G6所走过的序列：
V1? V3 ? V5 ? V2 ? V4 ? V6
? 所走过的边：
（ V1,V3）, （ V3,V5）, （ V5,V2）, （ V1,V4）,
（ V4,V6）
? 遍历生成树
V1
V3
V5
V2
V4
V6
下一页
上一页
停止放映
第 33 页
深度优先遍历算法程序 (非递归 )
Traver_dfs(struct headnode G[],int v)
{ int i,stack[N],visited[N],top=-1 ; ARCNODE *p;
for (i=0;i<N;i++) visited[I]=0;
printf(“%d ->”,G[v].data);
visited[v]=1; top ++; stack[top]=v; p=G[v].firstarc;
while((top!=-1)||(p!=NULL))
{ while(p!=NULL)
{ if (visited[p->adjvex]) p=p->nextarc;
else { printf(“%d ->”,G[p->adjvex].data);
visited[p->adjvex]=1; top++; stack[top]=p->adjvex;
p=G[p->adjvex].firstarc; }
if( top !=-1)
{ v=stack[top]; top- -; p=G[v].firstarc;
p=p->nextarc; }
}
}
}
下一页
上一页
停止放映
第 34 页
广度优先遍历算法
? 广度优先遍历法类似于树的按层次遍历的
过程。即先访问第 1个顶点所有邻接点后，
再访问下一个顶点所有未被访问的邻接点。
? 算法思想：
– step1 从图中某个顶点 V0出发，并访问
此顶点；
– step2 从 V0出发，访问 V0的各个未曾访
问的邻接点 W1,W2,…,Wk;然后,依此从
W1,W2,…,Wk出发访问各自未被访问的邻
接点。
– step3 重复 step2，直到全部顶点都被访
问为止。
下一页
上一页
停止放映
第 35 页
广度优先遍历法举例
遍历过程 访问顶点 所过边
?起始顶点 V1 V1
?访问 V1的未被访问过
的所有邻接点 V3,V2,V4 （ V1,V3）
(V1,V2)
(V1,V4)
?访问 V3的未被访问过
的所有的邻接点 V5 （ V3,V5）
?访问 V2的未被访问过
的所有的邻接点 无
?访问 V4的未被访问过
的所有的邻接点 V6 (V4,V6)
?所有顶点已被访问,结束。
V1
V3 V2
V5
V4
V6
G6
下一页
上一页
停止放映
第 36 页
遍历产生的结果
? 广度优先遍历 G6所走过的序列：
V1? V3 ? V2 ? V4 ? V5 ? V6
? 所走过的边：
（ V1,V3）, （ V1,V2）, （ V1,V4）, （ V3,V5）, （ V4,V6）
? 遍历生成树
V1
V3
V5
V2 V4
V6
下一页
上一页
停止放映
第 37 页
四、图的操作
? 图中顶点无序可言
– 任一顶点都可以看作第一个顶点；
– 任一顶点的邻接点间也无序可言；
? 为操作方便, 对图中顶点按人为意志给其
排序；同样, 也可以对某个顶点的所有邻
接点进行排队, 在这个队列中自然形成第
一个或第 K个邻接点 。 若某个顶点的邻接
点个数大于 K,则称第 K+1个邻接点为第 K
个邻接点的下一个邻接点, 而最后一个邻
接点的下一个邻接点为, 空, 。
下一页
上一页
停止放映
第 38 页
图的常用基本操作
? LOC_VERTEX（ G,Vi） 确定顶点 Vi在 G中的位置 。
? GET_VERTEX（ G,i） 求图 G中第 i个顶点 。
? FIRST_VERTEX（ G,i） 求图 G中 Vi的第 1个邻接点 。
? NEXT_ADJ(G,v,w) 已知 w为 G中顶点 v的第 1个邻接
点,求顶点 w的下一个邻接点 。
? INS_VERTEX(G,u) 在图 G中插入一个顶点 u,为图 G
的第 n+1个顶点 。
? INS_ARC(G,v,w) 在图 G中插入一条从顶点 v到顶点
w的弧 。
? DEL_VERTEX(G,Vi) 删除图 G中顶点 Vi,以及与 Vi相
关联的边或弧 。
? DEL_ARC(G,v,w) 删除图 G中从顶点 v到顶点 w的弧 。
下一页
上一页
停止放映
第 39 页
五、图的应用
? 最小生成树
? 拓扑排序
? 关键路径
? 最短路径
下一页
上一页
停止放映
第 40 页
最小生成树
? 该问题是构造连通图的最小代价生成树问题 。
一棵生成树的代价就是树上各边 （ 弧 ） 的代
价之和 。
? 例如, 若要在 n个城市间建立通信联络网,
则只需 n-1条线路 。 但在 n个城市间, 最多可
能架设 n（ n-1） /2条线路, 选择哪 n-1条线
路, 使费用最少 。
– 普里姆 （ Prim） 算法
– 克鲁斯卡尔 （ Kruskal） 算法
下一页
上一页
停止放映
第 41 页
普里姆（ Prim） 算法
? 假设 N=（ V,E） 是连通图, TE是 N上最小生
成树中边的集合 。
– 从 U={u0} （ u0 ? V）, TE= 空开始；
– 重复执行,在所有 u?U,v ?V-U的边
（ u,v） ?E中找一条代价最小的边 （ u0，
v0） 并入 TE,同时 u0并入 U,直到 U=V为
止；
– 此时 TE中必有 n-1条边, 则 T=（ V,TE）
为 N的最小生成树 。
下一页
上一页
停止放映
第 42 页
普里姆（ Prim） 算法举例
1
2
3 4
5
6
8 7
2
1
4
35
7 6
8
11
10
9
12
U={1},V-U={2,3,4,5,6,7,8}
1
2
2
1
2
4
2
1
4 7
3
（ 1）
（ 2） （ 3）
(1) U={1,2},V-U={3,4,5,6,7,8}
(2) U={1,2,4},V-U={3,5,6,7,8}
(3) U={1,2,4,7},V-U={3,5,6,8}
下一页
上一页
停止放映
第 43 页
普里姆（ Prim） 算法举例 (续 )
4 7
5
3
5
（ 4）
7
6
（ 5）
6
（ 6）
4 7
6
3 8
（ 7）
8 3
6
5
4 7
2
2 1
3
6
589
(4) U={1,2,4,7,5},V-U={3,6,8}
(5) U={1,2,4,7,5,6},V-U={3,8}
(6) U={1,2,4,7,5,6,3},V-U={8}
(7) U={1,2,4,7,5,6,3,8),V-U={ }
4 3
6
3
1
下一页
上一页
停止放映
第 44 页
克鲁斯卡尔（ Kruskal）算法
? 操作步骤,
– 假设 N=（ V,E） 是连通图
– 取图中每个顶点自成一个连通分量
– 在 { E }中选择代价最小的边, 若该边所
依附的顶点落在 T中不同的连通分量上,
则将此边加入生成树 T中；否则, 舍去此
边, 再选择下一条代价最小的边 。
– 重复上述步, 直到 T中所有顶点都在同一
连通分量上为止 。
下一页
上一页
停止放映
第 45 页
克鲁斯卡尔（ Kruskal）算法举例
1
2 3 4
5 6
1 5
24
6
63
55
6
1
2 3 4
5 6
(1)
1
3
(2)
1
1
3
1 4
6
2
(3)
2
5
1
3
4
6
1
2
3
(4)
下一页
上一页
停止放映
第 46 页
克鲁斯卡尔（ Kruskal）算法举例 (续）
1
2 3 4
5 6
(5)
1
23 4
1
32
5 6
4
1
243
5 （ 6）
1
2 3 4
5 6
1 5
24
6
63
55
6
下一页
上一页
停止放映
第 47 页
拓扑排序
? 研究一个有机整体中不同个体间的次序问题 。
例如课程间优先关系有向图问题 。
? 软件专业的课程优先关系：
课程编号 课程名称 先决条件
C1 程序设计基础 无
C2 离散数学 C1
C3 汇编语言 C1,C2
……
C9 高等数学 无
下一页
上一页
停止放映
第 48 页
拓扑排序举例
? 方法步骤
– 在有向图中选一个没有前驱的顶点并输出 ;
– 从图中删除该顶点和所有以它为尾的弧 ;
– 重复前 2步,直到全部顶点均输出为止 。
– 输出序列即为拓扑排序序列 。
? 拓扑排序序列不唯一 。
下一页
上一页
停止放映
第 49 页
拓扑排序举例
C1
C9
C4
C2
C3
C5
C7
C12
C10
C11
C6
C8
?C1 C2 C3 C4 C5 C7 C9 C10 C11 C6 C12 C8
?C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C8
下一页
上一页
停止放映
第 50 页
关键路径
? 研究的是在一个有机整体中
不同个体间的次序问题 。
即研究的是工程进度及影响进
度的关键因素问题 。
下一页
上一页
停止放映
第 51 页
最短路径
? 研究的是类似于交通调度一
类的带权有向图问题 。 求路
径最短或费用最省 。
下一页
上一页
停止放映
第 52 页
六、二叉排序树的生成
对给定数列 {a1,a2,…,an},根据二叉排序树特性,逐个将
结点插入到二叉排序中 。
具体操作步骤：
step1 a1是根结点；
step2 若 ai<aj,且 aj的左子为空,则将 ai插入到 aj的左子 ;
若 aj的左子非空,则继续寻找合适的插入位置 。
若 ai?aj,且 aj的右子为空, 则将 ai插入到 aj的右子；
否则继续沿右子树寻找合适的插入位置；
插入 ai 插入到 aj的左子 ai〈 aj
插入到 aj的右子 ai ? aj
step3 重复 step2，直到所有结点插入完为止。
下一页
上一页
停止放映
第 53 页
二叉排序树算法
二叉排序树结点结构：
struct tree {
char info；
struct tree *left, * right ；
}
算法描述,
? 输入结点非空循环,若是第 1个结点,令指针
ROOT指向该结点。
? 打印输出该二叉排序树；
? 输入一个值，在该树中查找，若找到输出该
结点值；否则，显示查找失败。
下一页
上一页
停止放映
第 54 页
二叉排序树生成算法
建立二叉树
Create_btree()
查询结点
Search_btree()
打印二叉树
Print_btree()
主程序
Btree.C
下一页
上一页
停止放映
第 55 页
主程序框图
开始
初始化
输入结点数据
！ ROOT
root=create_btee（） create_btree()
结束?
N
Y
打印该树
查找指定结点
Print_btree()
Search_btree()
下一页
上一页
停止放映
第 56 页
生成二叉排序树程序框图
Create_btree() 开始
r = 0？
Y
申请结点空间
r = 0？显示“溢出”
结束
根结点的处理 N
Y
N
r->left = 0;
r->right = 0;
r->info = info ;
非根结点
info<r->info?Y
t=r->left t=r->right
N
调用本函数
root?
返回
Y N
r->left=0
r->right=0
root->left=r
或
root->right=r
下一页
上一页
停止放映
第 57 页
查询二叉排序树算法框图
开始 Search_btree()
!root
Y
显示“空树”
返回
N
root->info!=key循环
key<root->info?
root=root->left root=root->right
root=0?
NY
查找成功,显示 返回
显示“失败”
root!=0?
循环结束?
N
Y
下一页
上一页
停止放映
第 58 页
打印算法框图
开始 Print_btree()
r=0?
Y
N
调用自身打印左子
打印当前结点值
调用自身打印右子
返回
下一页
上一页
停止放映
第 59 页
主程序 Btree.C
#include,stdio.h”
struct tree {
char info;
struct tree *left,*right;
}
main ( )
{ char *s,*c,key=??;
struct tree *create_btree(),*search_btree(),*root=0;
do {
printf(“Enter a letter:”);
gets(s);
if (!root)
root=create_btree(root,root,*s);
else
create_btrr(root,root,*s);
} while (*s) ;
下一页
上一页
停止放映
第 60 页
主程序 Btree.C(续）
print_btree(root,0);
key=?1?;
while ( key)
{
printf(“Enter a key to find:”);
scanf(“%s”,&c);
key=search_btree(root,c);
printf(“press to continue\n”);
}
} /* Btree。 C 结束 */
下一页
上一页
停止放映
第 61 页
生成二叉排序树程序
struct tree create_btree(root,r,info)
struct tree *root,*r;
char info;
{ if (r = =0 )
{ r=malloc(sizeof(struct tree));
if ( r = = 0)
{ printf(“Out of memory\n”); exit(0); }
r->left= 0; r->right=0; r->info=info;
if (root)
{ if(info<root->info) root -> left=r;
else root->right=r;
}
else
{ r->right=0; r->left = 0; }
return r;
} /* if = = 0 接下页 */
下一页
上一页
停止放映
第 62 页
生成二叉排序树程序 （续）
if (info < r->info)
create_btree(r,r->left,info);
if(info>=r->info)
create_btree(r,r->right,info);
} /* create_btree(root,r,info) */
下一页
上一页
停止放映
第 63 页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Emptu btree\n”); return root; }
while(root->info!=key)
{ if(key<root->info)
root=root->left;
else
root=root->right;
if(root==0)
{ printf(“Search Failure\n”);
break ;
}
} /* while(root->info!=key) */
查询二叉排序树程序
下一页
上一页
停止放映
第 64 页
if (root !=0)
printf(“Successful search\n key=%c\n”,root->info);
return root ;
} /* *search_btree(root,key) */
查询二叉排序树程序（续）
下一页
上一页
停止放映
第 65 页
打印二叉排序树程序
print_btree(r,l)
struct tree *r;
int l;
{ int i;
if (r = = 0) return ;
print_tree(r->left,l+1);
for(i=0;i<l;i++)
printf(“,);
printf(“%c\n”,r->info);
print_btree(r->right,l+1);
}
下一页
上一页
停止放映
第 66 页
程序输入
输入,输出：
h ? b
d ? d
p ? e
r ? h
b ? p
e ? r
?
下一页
上一页
停止放映
第 67 页
举例
对数列 {10,18,3,4,9,13,25},生成二叉排序
树 。
10
（ 7）
10
18
（ 2）
10
3 18
（ 3）
10
3 18
4（ 4）
10
3
4
18
9
10
3
4
9
18
13
（ 6） （ 5）
10
3
9
4
18
13 25
（ 1）
下一页
上一页
停止放映
第 68 页
平衡二叉排序树
在二叉排序树的动态生成过程中, 由于数据本身
的特性, 将影响二叉排序树的性质, 例如 {3,5,7，
9,20}这样的数列, 生成的二叉排序树就是一棵单
枝树 。 因此, 在动态生成二叉排序树的过程中, 要
进行平衡化处理 。
平衡化处理就是在
不影响 二 叉 排序树特性的前题
下, 通过, 旋转, 处理, 使该结点
的平衡因子不大于 2。
旋转分,LL,RR,LR和 RL
四种 。
3
5
7
9
20
下一页
上一页
停止放映
第 69 页
LL平衡化处理
由于在 A的左子树的左子树上插入结点, 使 A
点失去平衡, 需进行一次 LL旋转 （ 顺时针
旋转 ） 操作 。
示意为：
程序实现为：
b = a?.lc
a?.lc = b?.rc
b?.rc = a
a?.bf = 0
b?.bf = 0
b为子树的新根
A
B
C
LL B
C A
下一页
上一页
停止放映
第 70 页
RR平衡化处理
由于在 A的右子树的右子树上插入结点, 使 A点失去平
衡, 需进行一次 RR旋转 （ 逆时针旋转 ） 操作 。
示意为：
程序实现为：
b = a?.rc
a?.rc = b?.lc
b?.lc = a
a?.bf = 0
b?.bf = 0
b为子树新根
A
B
C
RR B
A C
下一页
上一页
停止放映
第 71 页
LR平衡化处理
由于在 A的左子树的右子树上插入结点, 使 A
点失去平衡, 需进行一次 LR旋转 （ 两次旋转 ;
先逆时针,再顺时针旋转 ） 操作 。
示意为：
程序实现为：
b = a?.lc,c = b?.rc,a?.lc =
c?.rc
b?.rc = c?.lc,c?.lc = b,c?.rc = a
A
B
C
C
B A
A
C
B
下一页
上一页
停止放映
第 72 页
RL平衡化处理
由于在 A的右子树的左子树上插入结点, 使 A点失
去平衡, 需进行一次 RL旋转 （ 两次旋转 ;先顺时
针,再逆时针旋转 ） 操作 。
示意为：
程序实现为：
b = a?.rc,c = b?.lc,a?.rc = c?.lc
b?.lc = c?.rc,c?.lc = a,c?.rc = b
A
B
C
C
A B
A
C
B
下一页
上一页
停止放映
第 73 页
平衡化处理举例
有数据序列 {13,24,37,90,53}
? 插入 13,树是平衡的 ;
? 插入 24,树仍为平衡 ;
? 插入 37,树不再平衡,
执行 RR旋转 ;
? 插入 90,树仍平衡 ;
? 插入 53,失去平衡,
执行 RL旋转,
13
13
24
(1) (2)
13
24
37 3713
24
(3)
24
13 37
90
(4)
24
13 37
90
53
24
13 37
53
90
24
13 53
37 90
(5)
下一页
上一页
停止放映
第 74 页
Huffman(哈夫曼）树及应用
? Huffman树的定义
? 构造 Huffman树
? Huffman编码
? Huffman编码的译码
下一页
上一页
停止放映
第 75 页
Huffman树的定义
? Huffman树也称为最优树，是一类带权路径最短
的二叉树。
? 树的带权路径长度定义为：
WPL = ∑ wklk
k = 1
n
其中：
n 是树中叶结点的个数
wi 是第 i个结点的权值
li 是第 i个结点的路径长度
下一页
上一页
停止放映
第 76 页
Huffman树举例
? 以下有三棵树：
（ a） （ b） （ c）
a
b
c d
a b c d
a
c
b
d7
7
7
5
5
52
2
2
4 4
4WPLa =7x2+5x2+2x2+4x2
= 36 WPL
b =7x3+5x3+2x1+4x2
= 46
WPLc =
7x1+5x2+2x3+4x3
= 35 √
? 事实证明按哈夫曼树构造二叉树，可得到很好的特
性，应用于实际问题，可提高处理效率。
下一页
上一页
停止放映
第 77 页
应用举例
? 由统计规律可知，考试成绩的分布符合正态分布：
-1 10
分数 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100
比例数 0.05 0.15 0.40 0.3 0.10
? 根据正态分布规律，在 60 ～ 90之间的分数占 85%，
而不及格和优秀是少数。
下一页
上一页
停止放映
第 78 页
将百分制转换成五分制
? 判定树比较,a<60?
a<70?
a<80?
a<90?
不及格
及格
中等
良好 优秀
Y
Y
Y
Y
N N
N
N
a<80?
a<70? a<90?
a<60?
不及格
优秀良好
中等
中等及格不及格
Y
Y
Y N
N
N NY
(A)
(B)
? 若输入 1万个数据，按 A的判定过程进行操作，约需比较 3.2
万次，而按 B比较,则仅需 2.2万次。
下一页
上一页
停止放映
第 79 页
构造 Huffman树
? 构造 Huffman树算法步骤：
– 1）将 n个带权值 wi（ i≤n）的结点构成 n棵二叉
树的集合 T={T1,T2,……, Tn}，每棵二叉树
只有一个根结点。
– 2）在 T中选取两个权值最小的结点作为左右子
树，构成一个新的二叉树，其根结点的权值取
左右子树权值之和；
– 3）在 T中删除这两棵树，将新构成的树加入到
T中；
– 4）重复 2）,3）步的操作，直到 T中只含一棵
树为止，该树就是 Huffman树。
下一页
上一页
停止放映
第 80 页
构造 Huffman树举例
? 以权值分别为 7,5,2,4的结点 a,b,c,d构造
Huffman树。 T= { a b c d }
（ a） T= { a b c d }
（ b） T= { a b T3 }
（ c） T= { a T2 }
（ d） T={ T1 }
c d
T
3
b T1
T
2
2 4
6
65
11
b
T
2 65
11
c d2 4
18
a T27
11
T
1
18
a7
T
1
b T1
T
2 65
11
18
a7
T
1
b5
11
c d2
6
4
下一页
上一页
停止放映
第 81 页
Huffman编码
? 编码：用二进制数的不同组合来表示字符的方法。
? 前缀编码：一种非等长度的编码。任一个字符的
编码都不是另一个字符编码的前缀。
a
0
b
0
1
c d
0
1
1
编码,A（ 0）
B（ 01）
C（ 011）
D（ 111）
方法约定：
1）左分支为‘ 0’
2）右分支为‘ 1’
3）由根到叶路径上字符组
成的二进制串就是该叶结点
的编码。
? Huffman编码：一种非等长度的编码。以给定权
值的结点构造 Huffman树，按二进制前缀编码的
方式构成的编码为 Huffman编码。
下一页
上一页
停止放映
第 82 页
Huffman编码举例
? 在某系统的通信联络中可能出现 8种字符，其频率
分别为 0.05,0.29,0.07,0.08,0.14,0.23、
0.03,0.11，设权值分别为 {5,29,7,8,14，
23,3,11},n=8，其 Huffman树为：
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 83 页
Huffman编码存储结构
? 由于 Huffman树中没有度为 1的结点，则 n个叶结点
的 Huffman树共有 2n-1个结点。例如,4个结点的
Huffman树，共有 7个结点。因此可以用长度为 2n-1
的一维数组存放。
? 求 Huffman编码,从叶到根的编码。因此要知道每
个结点的父结点。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 84 页
Huffman编码的译码
? 从 Huffman编码树上不难看出，代码全部在叶结
点上，根据 Huffman编码，就能求出相应的字符。
该过程称为“译码”。
? 译码是根据从根到叶的 Huffman编码求相应的字
符。因此要知道每个结点的左右子结点。
? 例如，根据,1111”，就能求出对应的字符是,8”。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
下一页
上一页
停止放映
第 85 页
作业、思考题
1、思考题：
3,4,18
2、第 2章作业
8,13,20
2、作业要求：
– 作业命名方式为：
学号,章数 _序号
下一页
上一页
停止放映
第 86 页
结束语
? 欢迎参加网上讨论，网站的地址：
http,//ctec.xjtu.edu.cn
? 数字化课件的路径,
jec253\user2\tools\lzq\软件基础
谢谢，再见！
