计算机软件基础：15第四章数据结构图

《计算机软件基础》多媒体教程

第十五讲

第四章数据结构

4.8最优二叉树(哈夫曼树)

※编码问题

一段报文为“GOOD_GOOD_GOODGODGO"，字符集合是{O,G,D},将字符用“0”

和T编码，可获得报文同编码。

例如，将字符按等长编码：

0:00G:10_:01D:11

可得到报文的编码：

10000011011000001101100000111000111000

GOOD_GOOD_GOODGODGO

由于各个字符出现的蕨度(次数)是{0:8,G:5,_:2,D:4},

因此编码总长度为(8+5+2+4)x2=38

编码问题：如何使编码总长度最短？

※最优二叉树

假设二叉树的n个叶结点给定一个带权值Wk,那么从根结点到各个叶结点的路径长度

Lk与结点的权值Wk乘积之和叫做二叉树的带权路径长度(WPL,权路径长度)。

WPL=^WkxLk

k=1

给定一组带权值的叶结点，可以构成不同形式的二叉树。在这些所有的二叉树中，权路

径长度WPL最小的二叉树称为最优二叉树(哈夫曼树，HuffmanTree)。

例如，叶结点：{7,5,3,1},WPL(A)>WPL(B)。__________________________________

二叉树AC

XV-二叉树BQ

c(@*-3=2C(@L5=2

@L7=3\5)L5=30LI=3(3)L2=3

WPL(A)=7x3+5x3+3x2+1x1=43WPL(B)=7x1+5x2+3x3+1x3=29

※哈夫曼树构造算法

1.根据给定的n个权值(wi,W2,wn),构成n棵二叉树的集合F={TI,T2,…,Tn},其中

每个丁中只有一个权值为Wi的根结点。

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

点的权值为其左右子树权值之和。

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

4.重复2,3,直到F中只含一棵二叉树为止，即为哈夫曼树。

初始：F={{7},{5},{3},。}}Step1：合并{3}{1},得F={{7},{5},{4}}

⑦⑤③①

⑦⑤@

Step2：合并{5}{4},得尸={{9},{7}}Step3：合并{9}{7},得F={16},构造结束

⑦氏

※哈夫曼树生成示例

根据报文“GOOD_GOOD_GOODGODGO”生成哈夫曼树。

字符集合为{0:8,&5,_:2,D:4}。

初始：F={{8},{5},{4},{2}}Step1：合并{2}{4}，F={{8},{6},{5}}

⑧。⑤G②一④D

⑧。⑤

Step2：合并{6}{5},F={{11},{8}}Step3：合并{11}{8},F={19},构造结束

o@刑

G®J©

©-@D(gA?

D

※哈夫曼树编码算法

令哈夫曼树的左子路径编码'0'，右子路径编码T,从根到叶结点的路径编码的合成称为

叶结点的哈夫曼编码(Huffman码)，这是一种不等长的前缀编码，其特征是没有一个编码是

另一个编码的前缀，使得解码时不会混淆。

例如，报文为："GOOD_GOOD_GOODGODGO”，

字符集合为：{O:8,G:5,_:2,D:1}

叶结点的哈夫曼编码为：0:0G:10_:110D:111

报文的哈夫曼编码为：

1000111110100011111010001111001111000

GOOD_G00DGOODGODGOO

贝ij总编码长度(权路径长度)为：WPL=8X1+5X2+4X3+2X3=36

而采用等长编码的总长度=38。

4.9图

4.9.1图的定义

※图

设B=(K,R)是数据结构,K={ki,k2，…，％},R只有一个关系R={r},r={(ks,kt),|ks,kyK},

则称B为图。

※顶点

在图的术语中，把结点node称为顶点vertex.

因此，在图中结点集合记为V={V1,V2，…,Vn}o

※边

对于r中的(ks,kt),ks>kteK,记为(vs,vt),vs,vtev«称为从Vs,到vt存在一条边，记

为ei=(vs,vt)。

所有的边组成边的集合(边集)E,即

E={ei,em,|©=(vs,vt),vs,vteV},

因而可将图记为G=(V,E)o

※有向边

在图G=(V,E)中，若u,veV,(u,v)eE,且(u,v)W(v,u),则称(u,v)为有向边，记为e=<u,

v>,并称u由起点，v为终点。

※无向边

若u,vcV,(u,v)和(v,u)eE,且(u,v)=(v,u),则称e=(u,v)为无向边。

同时在图形表示时，用双向箭头或者用无箭头线表示e=(u,v)。

<u,v>

(u,V)

在图中，若VGV,(v,v)GE,则称(v,v)为自向边。(在本课程中，不考虑自向边。)

※无向图

在G=(V,E)图中，若对所有的u,vwv,e=(u,v)£E,同时存在e'=(v,u)WE,且6=6’,

则称G为无向图。

有向图

若有任一边e=(u,v)GE,而(V,U)E,或者存在e=(v,u)eE,e'=(u,v)6E,但eHe',

则称G为有向图。

※子图

设G'=(V',E'),G=(V,E),若成立V'V,E'E(称V'包含于V,E'包含于E),即对所

有的u,v£V.都存在u,vGV,同时对所有的e=(u,v)GE')都存在e=(u,v)WE,则称G'

为G的子图。

※完全图

在无向图G中,若对任何两个顶点u和v,都存在无向边，称G为无向完全图。

在有向图G中,若对任何两顶点u和v,都存在边e=<u,v>和e'=<v,u>,称G为有向

完全图。

无向完全图无向完全图有向完全图有向完全图

※通路

在图G=(V,E)中，如果存在一个顶点序列(vo,vi,v2，…,Vk),所有的(％,vi+1)eE|i=0,

k-1,而且vo=u,Vk=v,则称在u和v之间存在通路。

※回路

则这个顶点序列称为回路。

※连通图

在无向图G=(V,E)中，如果任何两个顶点之间都存在通路，则称G为连通图。

非连通图

4.9.2图的基本操作和应用举例

※图的基本操作

0查找顶点或查找子图。删除顶点或子图

。寻找通路或回路。遍历全部顶点

0添加顶点或合并两个图本课程我们将只介绍几种图的遍历方法。

※图的应用举例

(-)最短路径问题

E.W.Dijkstra于1959年提出，又称为

Dijkstra算法。定义一个带权图G=(V,E,

w),对所有的边e=(u,v)eE|ueV,veV,

w(u,v)是边e的权(w可以是边e的路程，

费用等)。给定一个起点u和一个终点V,

求从u出发到v的一条最短路径。例如从a

出发，寻找到达z的最短路径,如右图所示。

(-)欧拉回路问题

1736年，欧拉写出了第一篇图论的论文，回答了朋友提出的一个问题：在哥尼斯堡的

匹格河上有七座桥，能否从任何一个地方出发通过每座桥一次且仅一次后回到原地?该问题

称为著名的哥尼斯堡七桥问题。

哥尼斯堡七桥问题等价于在图中寻找一条回路，使得它的每一条边出现一次且仅一次,

也就是如何一笔画的问题，如下图所示。

(三)哈密顿回路

哈密顿②爵士在1859年发明了一种“环球世界”的游戏。要求游戏者沿着顶点在标有

城市名称的正十二面体的棱线行走，寻找一条通过每个城市恰好一次的回路。

哈密顿回路问题等价于在图中寻找一条回路，使得它的每一个顶点出现一次且仅一次，

也是如何一笔画的问题，如下图所示。

(四)巡回售货员问题

巡回售货员问题(TSP,TravellingSalesmanProblem)又称为货郎担问题。设有n个城

市，已知每两个城市间的距离。一个货郎自某个城市出发巡回售货。问这个货郎应该如何选

择路线，使得每个城市经过一次且仅一次，并且总的行程最短。

货郎担问题实际上是在一个带权完全图中寻找一条总的权最小的哈密顿回路。

(五)地图的四色问题

1852年英国青年弗兰西斯•格思里(FrancisGuthrie)在画地图时发现：如果相邻的两国

着上不同的颜色，那么画任何一张地图只要四种颜

色就够To这就是地图的四色(MapColorring)]nj题。

100多年来，许多科学家的证明都失败了。直

到1976年美国伊利诺大学的阿佩尔(K.Appel)和

哈根(W.Haken)两位教授用计算机化了1200多个

小时才得以证明。但是至今仍没有能够用通常的证

明方法来论证四色问题。

印刷电路板的分层问题是地图四色问题的应用。将图中的边对应于导线，顶点对应于接

点，没有导线连接的两个接点间可能要装配元件。由于同一层上导线不允许交叉，问如何设

计具有最少层数的印刷电路板？

(六)迷宫问题

迷宫(Maze)问题可描述为：从A到B间存在障碍，如何找到最佳的路径？

B0

0

0

0

00000

0

0

0

0

AO00

00

00

0000

在集成电路和印刷电路板的布线时，用Lee氏算法求解迷宫问题是一个最基本也是最

有效的算法。

(七)皇后问题

皇后问题是一个古老而著名的问题,

是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯①1850年提出：在8X8格的

国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列

或同一斜线上，问有多少种摆法。

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,

后来有人用图论的方法解出92种结果。

4.9.3图的存储

图的存储有多种形式，这里只讨论两种常用的形式，即邻接矩阵和邻接表。

※邻接矩阵

设G=(V,E)是图，V={vi,V2，…，vn},则可定义一个nxn的邻接矩阵A。

矩阵元素A[i,j](i,j=1，…,n)被定义为

若(4v,GE

若(M，Vj)gE

01100、0000

1011000110

1101111001

0110001100

lo010ojlo010oj

邻接矩阵

A1邻接矩阵A2

例如，无向图Gi和有向图G2可以分别用邻接矩阵Al和邻接矩阵A2表示，A2中的粗

体数字表示非对称的有向边，称为非对称元素。

※邻接表

在图G=(V,E)中，若(s,Vj)£E,Vi,Vj£V,则称甘是s的邻接顶点。邻接表是指仅仅存

储各顶点的邻接顶点的信息。

邻接表由表头和表链组成，表头用于存放所有顶点的数据场，表链用于存放每个Vi的邻

接顶点的地址。表头单元含有两个指针场piv和P2V,通常用pw指向表头的下一顶点，用

p2V指向各个表链。表链单元也含有两个指针场P1V和P2V,通常用PW存放顶点的表头地

址，用P2V指向表链的下一结点。___________

表头av5vPlVP2V表链avPRp2V

>av>av

av1V1av2-i2r-~l3

Iavv2av

23*|ayjJ-qaVgj_*|ay4

v

Lav33av4

,*jaViaV2r_>]aV4aV5

-',1

LavV4av

45,*jav

2av3

L0CV5V5

(PAIM

※邻接表存储单元示例

表头的存储单元：用next存放表头中下一单元的地址，用link存放表链的首地址。

表链的存储单元：用vertex存放顶点在表头中的地址，用next存放表链中下一单元的

地址。图G的邻接表及存储单元如下图所示。

※用数组存储的邻接表

表链

存储邻接表的数据定义表头

#defineM1000avkeylinklink[0]link[1]link[2]link[3]

#defineVERTEXstructvertex

0%F16012

v匚ri匚八/仪六外憎/

1F240___023

(v2

----------A

longkey;2v3F3100134

short*link;/*表链首地址7

3v4F430-1-►12

)；4vF560

VERTEXVertex[M];53

其中，表头用结构数组Vertex实现存储，表链用动态数组Vertex[i]」ink实现存储。

※用链表存储的邻接表

存储邻接表的数据定义

#defineVERTEXstructvertex

#defineLINKstructlink

VERTEX/*表头结构*/

(

longkey;/*数据场*/

VERTEX*next;I*表头中下一顶点指针*/

LINK*link;I*顶点的表链指针*/

};

LINK/*表链结构*/

(

VERTEX*vertex;/*表头中的顶点指针*/

LINK*next;/*表链中下一结点指针*/

}；

VERTEXWertex;

VERTEX

key

next—►

link-►

表头和表链分别是VERTEX和LINK类型的链表，因而称为用链表存储的邻接表。Vertex

指向表头，表头的成员指针link指向各个表链。

※用链表存储邻接表的图形表示

11101120

VertexF110广F210TF310

F110T»ViF21011101120NULL

121012201230

F210F110F310F410

1220T1230,rNULL

T»V2F3101210J

1310132013301340

F31C)F110F210F410TF510

T>V3F41013101320T1330j1340NULL

14101420

F410F210F310

HV4F51014101420TNULL

1510

F510r*F310

►v|NULL

51510NULL

4.9.4图的遍历

※遍历的定义

从某一顶点出发开始访问，沿着边逐个访问顶点，直至遍及全图。

当图为连通时，遍历是可能的。

※常用的遍历方法

DFS：深度优先搜索法(DepthFirstSearch)

BFS：广度优先搜索法(BreadthFirstSearch)

对树来说，树的DFS就是树的前序遍历，树的BFS就是树的层次遍历

XDFS(深度优先搜索法)

。算法描述

0)初始化：所有顶点标记为未访问。

1)指定一个顶点V,开始DFS。

2)对给定的一个顶点V：

如果该点已访问过，则跳过。

如果该点未访问过，则访问之，并加注己访问的标记;

然后对于V的所有邻接顶点逐个执行DFS。

※用数组存储的邻接表实现DFS算法

。数据定义表头表链

#defineM1000av|key|flagnlinklink[0]..

#defineUNVISITEDV

#defineVISITED'U)

#defineVERTEXstructvertex

VERTEX

(

longkey;

charflag;/*访问标记7表头表链

shortn;/*表链数组长度*/0Viflag3link125

short*link;/*表链动态数组*/

1v2flag2link04

｝；2V3flag2link03

VERTEXVertex[M];

3V4flag3link245

假定图G已经存储，即用数组存储的邻接表如图所示。

4V5flag3link

ODFS程序135

voiddfs(shortv)5V6flag3link034

short*link,i;

HM

printf(vertex=%ld\nJVertex[v].key);

Vertex[v].flag=VISITED;

for(i=0,link=Vertex[v].link;i<Vertex[v].n;i++)

if(Vertex[link[i]].flag==UNVISITED)

dfs(link[i]);

)

如果选Vertex⑼为首个遍历的顶点，则dfs函数的调用形式为:

dfs（O）;

。DFS算法演示

为简化起见，演示中以V[v]

替代Vertex[v],用link[k]表示

Vertex[k].link.用实线表示函数

调用，用虚线表示函数返回。

遍历的结果：

125436

0Vl125

1v204

2v303

3v4245

4v5135

5v6034

XBFS（广度优先搜索法）

。算法描述

0）初始化：所有顶点标记为未访问。

1）指定一个顶点，送入队列。

2）只要队列非空，从队列中取出一个顶点V,

重复执行：

如果V已访问，跳过；

如果V未访问，加访问标记，打印；

将V的所有未访问过的邻接顶点送入队列。

当队列空时结束遍历。

（DBFS算法演示

※用链表存储的邻接表实现BFS算法

0数据定义

#defineUNVISITED0/*未访问*/

#defineVISITED1/*已访问7

#defineVERTEXstructvertex

#defineLINKstructlink

VERTEX1*表头结构*/

(

longkey；/*顶点数据值7

shortflag；/*访问标记，初始为未