非线性数据结构

非线性数据结构第一页，共一百页，编辑于2023年，星期五3.1数组

3.1.1引言

数组是大家已经很熟悉的一种数据类型，几乎所有的程序设计语言都把数组类型设定为固有类型。

数组(array)可看成是线性表的推广，是最常用的数据结构之一。数组是有限个数组元素的集合；数组的每个元素与一组下标相对应；和线性表一样，数组中所有数组元素的数据类型必须一致。

第二页，共一百页，编辑于2023年，星期五

3.1.2数组的逻辑结构

逻辑关系是非线性的，实质上是多个线性关系的组合。Amn=a11a12...a1na21a22...a2n

am1am2...amn

如下所示，就是一个m行n列的二维数组(也称为矩阵)，记作A[m,n]。第三页，共一百页，编辑于2023年，星期五矩阵A可以看成是由m个行向量组成的向量，也可以看成是由n个列向量组成的向量。

在矩阵A中，每个元素aij都属于两个线性表。一个是第i行的行表(ai1，ai2，...，aij，...，ain)，另一个是第j列的列表(a1j，a2j，...，aij，...，amj)。这种行表(行向量)和列表(列向量)都相当于线性表。所以说，数组可看作是线性表的推广，将线性表推广到二维或高维，就是我们所说的数组。第四页，共一百页，编辑于2023年，星期五

3.1.3数组的存储结构数组的顺序分配就是用向量作为数组的存储结构。但是二维以上的多维数组，不像一维数组那样，所有的元素已经排成一个序列，所以要把多维数组顺序地存储到一维顺序的存储器中，则必须对多维数组里的元素存放顺序做出一些规定。通常数组采用两种顺序存储方式。第五页，共一百页，编辑于2023年，星期五

1)行优先顺序存储

行优先顺序存储就是数组元素按行表次序进行存储，即第i+1个行表紧跟在第i个行表后面进行存储。在C、BASIC、PASCAL、COBOL等高级语言中均采用这种方法。以二维数组Am×n为例，按行优先顺序存储的数组元素次序为：

a11，a12，…，a1n，a21，a22，…，a2n，…，am1，am2，…，amn

第六页，共一百页，编辑于2023年，星期五

2)列优先顺序存储

列优先顺序存储就是数组元素按列表次序进行存储，即第j+1个列表紧跟在第j个列表后面进行存储。在FORTRAN语言中，数组是按列优先顺序组织存储。以二维数组Am×n为例，按列优先顺序存储的数组元素次序为：

a11，a21，…，am1，a12，a22，…，am2，…，a1n，a2n，…，amn

第七页，共一百页，编辑于2023年，星期五二维数组的两种存储方式第八页，共一百页，编辑于2023年，星期五同样，对n维数组也有上述两种不同的顺序分配的存储结构。当把n维数组的元素这样顺序地存放在存储器里，则每个元素的存储地址可以用公式计算出来。这些计算公式称为“地址公式”。假设每个数据元素占k个存储单元，则可得（1）一维数组的地址公式为：

Loc(ai)=Loc(a1)+(i-1)*k

（2）若存储分配采用行优先顺序分配，则二维数组Am×n的地址公式为：

Loc(aij)=Loc(a11)+[(i-1)*n+(j-1)]*k第九页，共一百页，编辑于2023年，星期五同理，可写出三维数组、n维数组的数组元素存储地址的计算公式。（3）若存储分配采用列优先顺序分配，则二维数组Am×n的地址公式为：

Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*L

同理，可写出三维数组、n维数组的数组元素存储地址的计算公式。第十页，共一百页，编辑于2023年，星期五

3.1.4特殊矩阵的压缩存储

假若值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵。像三角矩阵，对称矩阵、三对角矩阵等都属于特殊矩阵。通常在实际计算中经常出现一些阶数很高的矩阵，同时矩阵中有许多值相同的元素或者零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元素不分配空间。第十一页，共一百页，编辑于2023年，星期五

1）三角矩阵例：下三角矩阵An×n，当i<j时，aij=0。A=a110 …0a21a22…0

an1an2…ann

在下三角矩阵中，对角线以上元素全部为0，我们只需存储下三角的元素。第十二页，共一百页，编辑于2023年，星期五

特殊矩阵的压缩存储实际上就是把二维数组的数据元素压缩到一维数组上，即要在下标[i,j]与下标[k]之间建立一个映像关系，使得对二维数组的存取操作通过一维数组来完成。

假设以一维数组Sa(1：n(n+1)/2)作为n阶下三角矩阵A的存储结构，则Sa[k]和矩阵元素aij之间存在着一一对应关系：k=i（i-1）/2+j第十三页，共一百页，编辑于2023年，星期五

n阶对称矩阵A的压缩存储如下图所示。Loc(aij)=Loc(a11)+i(i−1)/2+(j−1)其地址公式为：对称矩阵A的压缩存储

第十四页，共一百页，编辑于2023年，星期五

2)稀疏矩阵

如果一个矩阵中大多数元素为零，非零元素较少且分布无一定规律，这类矩阵称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然的方法就是只存非零元素。由于每个矩阵元素可由它的行号和列号惟一地确定，这样稀疏矩阵中的每个非零元素就由一个三元组(i，j，val)惟一确定。其中，i是行号；j是列号；val是非零元的数值。整个稀疏矩阵可用一个三元组表表示。三元组表以非零元行号递增的顺序排列。第十五页，共一百页，编辑于2023年，星期五例如，有一个稀疏矩阵A如下：行号列号元素值46513315121234-6424第十六页，共一百页，编辑于2023年，星期五3.1.5数组的应用——迷宫问题0000011000010001101111011000011111100111011011010010101000001100110101000001100111011000100000110111001100001111110101000第十七页，共一百页，编辑于2023年，星期五i,j东k=0i=i,j=j+1南k=1i=i+1,j=j西k=2i=i,j=j-1北k=3i=i-1,j=jg=i+move[k][0]h=j+move[k][1]第十八页，共一百页，编辑于2023年，星期五3.2树3.2.1引言

数（tree）是一种应用广泛的非线性数据结构。从形态上看，它很类似与自然界中的数，是一个以分支关系定义的具有明显层次结构的数据结构。树结构被广泛应用于分类、检索、数据库、人工智能等方面。第十九页，共一百页，编辑于2023年，星期五3.2.2树的定义及逻辑结构树的定义树(Tree)是n(n≥0)个结点的有限集合。当n=0时称为空树，否则在任一非空树中：

(1)有且仅有一个特定的称为根的结点；

(2)除根结点之外，其余结点可分为m(m≥0)个互不相交的集合T1，T2，…，Tm，且其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

这是一个递归定义，即在树的定义中又用到了树，它显示了树的固有特性。树中的每一个结点都是该树中某一棵子树的根。第二十页，共一百页，编辑于2023年，星期五

A为根结点，其余的结点分为三个互不相交的有限集合：

T1={B，E，F}，

T2={C，G，J}，

T3={D，H，I}。T1、T2和T3都是A的子树，而它们本身也是一棵树。例如，T1是一棵以B为根的树，其余结点分为互不相交的两个集合{E}和{F}，而{E}和{F}本身又是仅有一个根结点的树。第二十一页，共一百页，编辑于2023年，星期五

2.常用术语

结点的度：一个结点拥有的子树数目。如A结点的度为3，它有三个子树T1、T2和T3。E、F结点的度为0，它们没有子树。

叶子：度为零的结点称叶子或终端结点。 树的度：一棵树上所有结点的度的最大值就是这棵树的度。 结点的层次：根结点的层数为1，其它任何结点的层数等于它的父结点的层数加1。

树的深度：一棵树中，结点的最大层次值就是树的深度。下图中树的深度为4。

森林：森林是m(m≥0)棵互不相交的树的集合。

孩子(child)：某结点子树的根称为该结点的孩子结点。第二十二页，共一百页，编辑于2023年，星期五

双亲(parent)：一个结点是它的那些子树的根的双亲结点。

兄弟(sibling)：同一个双亲的孩子之间互为兄弟。如A是B、C、D的双亲；B、C、D是A的孩子；B、C、D互为兄弟。

堂兄弟(cousins)：其双亲在同一层的结点互为堂兄弟。如G与E、F、H、I互为堂兄弟。

森林：有m(m≥0)棵互不相交的树构成的集合。

有序树：树中每个结点的各个子树从左到右依次有序，即不能互换。

在计算机中表示一棵树时，就隐含着一种确定的相对次序，所以后面我们讨论的都是有序树。第二十三页，共一百页，编辑于2023年，星期五3.2.3二叉树

3.2.3.1二叉树的定义及其性质

1．二叉树的定义二叉树是一个有限结点的集合，该集合或者为空，或由一个根结点和两棵互不相交的被称为该根的左子树和右子树的二叉树组成。这是一个递归定义，由定义可知二叉树有下面两个主要特点：

(1)每个结点最多只能有两个孩子，即二叉树中不存在度大于2的结点。

(2)有序树，即每个结点的子树有左、右之分，不能交换。第二十四页，共一百页，编辑于2023年，星期五二叉树可以有五种基本形态

空树、只有根结点、只有左子树、只有右子树和兼有左右子树注意：树和二叉树的区别主要是二叉树的结点的子树要区分左子树和右子树，即使在结点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。第二十五页，共一百页，编辑于2023年，星期五2．二叉树的性质二叉树具有下列重要特性。性质1：在二叉树中，第i层的结点数最多有2i-1(i≥1)个。例如：层次i 第i层最多结点数

120=1221=2322=4

k 2k−1

此性质可以用数学归纳法证明。第二十六页，共一百页，编辑于2023年，星期五性质2：在深度为k的二叉树中结点总数最多有2k–1个。由性质1可见，深度为k的二叉树的最大结点数为：=2k−1性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：

(1)

由于在二叉树中，任一结点的度数小于或等于2，所以其结点总数

n=n0+n1+n2第二十七页，共一百页，编辑于2023年，星期五

(2)设B为二叉树中总的分支数目，由于二叉树中除了根结点之外，其余结点都有一个分支进入，所以

B=n−1 即 n=B+1而这些分支只能是由度数为1或2的结点所发出，所以

B=n1+2n2于是得：

n=n1+2n2+1(3)由(1)和(2)得：

n0+n1+n2=n1+2n2+1所以

n0=n2+1 证毕第二十八页，共一百页，编辑于2023年，星期五3.2.3.2特殊的二叉树1、满二叉树如果一棵二叉树的深度为k，并且含有2k–1个结点，则称此二叉树为满二叉树。下图是一棵深度为4的满二叉树。第二十九页，共一百页，编辑于2023年，星期五2、完全二叉树 深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1到n的结点一一对应时，称之为完全二叉树。如图3-8所示是一棵深度为4的完全二叉树。第三十页，共一百页，编辑于2023年，星期五图3-8深度为4的完全二叉树第三十一页，共一百页，编辑于2023年，星期五

可以看出，完全二叉树有下面的特点：

(1)叶子只可能在层次最大的两层上出现。

(2)最下面一层的结点都集中在该层最左边的若干位置上。完全二叉树是一个十分重要的概念，在许多算法和算法分析中，都明显或隐含地用到了完全二叉树的概念。下面介绍完全二叉树的两个重要特性。

性质1：具有n个结点的完全二叉树的深度为第三十二页，共一百页，编辑于2023年，星期五

性质2：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有

(1)如果i=1，则i是二叉树的根，无双亲；如果i>1，则其双亲是结点。

(2)如果2i>n，则结点i无左孩子；否则其左孩子是2i。

(3)如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。证明从略。第三十三页，共一百页，编辑于2023年，星期五3、满二叉树和完全二叉树的关系 满二叉树=〉完全二叉树 满二叉树≠〉完全二叉树4、平衡二叉树二叉树上任一结点的左子树深度减去右子树深度的差值，称为此结点的平衡因子。若一棵二叉树中，每个结点的平衡因子之绝对值都不大于1，则称这棵二叉树为平衡二叉树。是平衡二叉树不是平衡二叉树第三十四页，共一百页，编辑于2023年，星期五

3.2.3.3二叉树的存储结构对于二叉树，我们既可采用顺序存储，又可采用链式存储。

1．顺序存储结构顺序存储就是将一棵二叉树的所有结点按照一定的次序顺序存放到一组连续的存储单元中，为此，必须把二叉树中所有结点构成一个适当的线性序列，以使各个结点在这个序列中的相互位置能反映出结点之间的逻辑关系。第三十五页，共一百页，编辑于2023年，星期五对于完全二叉树，按图的编号顺序，就能得到一个足以反映整个二叉树结构的线性序列。因此，可将完全二叉树中所有结点按编号顺序依次存储到一组连续的存储单元(即向量)中，这样既不浪费内存，又可以利用地址公式确定其结点的位置。1234567ABDEFCJ第三十六页，共一百页，编辑于2023年，星期五但对于一般的二叉树，顺序分配常会造成内存的浪费，因为一般的二叉树也必须按完全二叉树的形式来存储。1234567891011ABDEFCJGH第三十七页，共一百页，编辑于2023年，星期五

2．链式存储结构因为树型结构是非线性的结构，所以在存储器里表示树型结构的最自然的方法是链式存储。根据二叉树的特性，任何一个结点最多有左、右两棵子树，所以每个结点至少设有三个域：数据域和左、右指针域。其结点结构为：lchilddatarchild第三十八页，共一百页，编辑于2023年，星期五第三十九页，共一百页，编辑于2023年，星期五二叉链表结点的类型定义typedefstructnode{datatypedata;structnode*lchild,*rchild;}bstree;第四十页，共一百页，编辑于2023年，星期五3.2.3.4二叉树的遍历

遍历二叉树就是按一定的次序，系统地访问树中的所有结点，使每个结点恰好被访问一次。所谓访问结点，其含义是很广的，可以理解为对结点的增、删、修改等各种运算的抽象。在本节讨论中，假定访问结点即为输出结点数据域值。二叉树的遍历是最重要和最基本的运算，二叉树的许多操作都是以遍历为基础的。 按照对二叉树中根结点、左子树和右子树访问的先后顺序，共有三种遍历二叉树的方法： 根、左、右；左、根、右；左、右、根 根据这三种方法中根结点被访问的先后，分别称之为二叉树的先序(根)遍历，中序(根)遍历和后序(根)遍历。第四十一页，共一百页，编辑于2023年，星期五(1)先序遍历： 若二叉树为空，则空操作；否则 ①访问根结点； ②先序遍历左子树； ③先序遍历右子树。遍历序列：ABDEGHCF第四十二页，共一百页，编辑于2023年，星期五先序遍历的算法voidpreorder(bstree*p){if(p!=NULcL){printf(“%5”,p->data);preorder(p->lchild);preorder(p->rchild);}}第四十三页，共一百页，编辑于2023年，星期五(2)中序遍历：若二叉树为空，则空操作；否则①中序遍历左子树；②访问根结点；③中序遍历右子树。遍历序列：DBGEHACF第四十四页，共一百页，编辑于2023年，星期五中序遍历算法voidpreorder(bstree*p){if(p!=NULcL){inorder(p->lchild);printf(“%5”,p->data);inorder(p->rchild);}}第四十五页，共一百页，编辑于2023年，星期五(3)后序遍历： 若二叉树为空，则空操作；否则 ①后序遍历左子树； ②后序遍历右子树。 ③访问根结点；遍历序列：DGHEBFCA第四十六页，共一百页，编辑于2023年，星期五后序遍历算法voidposorder(bstree*p){if(p!=NULcL){posorder(p->lchild);posorder(p->rchild);printf(“%5”,p->data);}}第四十七页，共一百页，编辑于2023年，星期五3.2.4树的存储结构树在计算机内存储，可以用顺序存储方式、也可以用链式存储方式，这主要取决于要对树结构进行什么运算。这里主要介绍链式分配的存储结构。 孩子-兄弟表示法的链式存储结构表示如下：firstdatanext链表中结点的两个指针域分别指向该结点的第一个孩子和下一个兄弟结点。第四十八页，共一百页，编辑于2023年，星期五RADEFCBGKHRADECHFGBK第四十九页，共一百页，编辑于2023年，星期五

3.2.5树的遍历

树的遍历有两种次序：一种是先序遍历树；另一种是后序遍历树。

(1)先序遍历树：先访问树的根结点，然后从左到右依次先序遍历根的每棵子树。如先序遍历右图所示的树，得到的结点序列为：RADEBCFGHK

。

(2)后序遍历树：先从左到右依次后根遍历每棵子树，然后访问根结点。如后序遍历右图所示的树，得到的结点序列为：DEABGHKFCR。RADEFCBGKH第五十页，共一百页，编辑于2023年，星期五3.2.6树、森林与二叉树的转换由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到惟一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。图3-15给出了树与二叉树之间的对应关系。第五十一页，共一百页，编辑于2023年，星期五图3-15树与二叉树的对应关系第五十二页，共一百页，编辑于2023年，星期五下面给出树与二叉树之间的转换规则。

1．一般树转换为二叉树步骤：

(1)加线：亲兄弟之间加一虚连线。

(2)抹线：抹掉(除最左一个孩子外)该结点到其余孩子之间的连线。

(3)旋转：新加上去的虚线改实线且均向右斜(rchild)，原有的连线均向左斜(lchild)。第五十三页，共一百页，编辑于2023年，星期五图3-16一般树转换为二叉树的操作过程(a)一般树；(b)加线后；(c)抹线后；(d)旋转后第五十四页，共一百页，编辑于2023年，星期五

2．森林转换为二叉树森林是树的有限集合，利用树的转换思想，可以实现森林到二叉树的转换。步骤：

(1)将各棵树分别转换为二叉树。

(2)按给出森林中树的次序，依次将后一棵二叉树作为前一棵二叉树根结点的右子树，则第一棵树的根结点是转换后二叉树的根。第五十五页，共一百页，编辑于2023年，星期五图3-17森林转换成对应的二叉树的过程(a)森林；(b)各棵树对应的二叉树；(c)转换成的二叉树第五十六页，共一百页，编辑于2023年，星期五3.2.7树的应用树结构被广泛地用于分类、检索、数据库及人工智能等方面。二叉排序树

二叉排序树是一种动态树表。

二叉排序树的定义：二叉排序树或者是一棵空树，

或者是一棵具有如下性质的二叉树：

⑴若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

⑵若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

⑶左、右子树本身又各是一棵二叉排序树。二叉排序树的性质：按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。第五十七页，共一百页，编辑于2023年，星期五（1）二叉排序树生成：

从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。

插入一个结点的操作按下述方法完成：

①若原二叉排序树为空，则将待插结点作为此数的根结点。

②若原二叉排序树不为空，则比较待插结点和根结点的关键字值；若待插元素的关键字值小于根结点的的关键字值，则将其插入到左子数中；否则，将其插入到右子树中；

③在二叉排序树的左右子树中的插入过程同上。例：对于一组关键字{51，34，79，18，45，86}，生成对应的二叉排序树第五十八页，共一百页，编辑于2023年，星期五（2）二叉排序树的删除:

假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论：⑴若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可.⑵若结点*p只有左子树PL或者只有右子树PR，则只要使PL或PR成为其双亲结点的左子树即可。⑶若结点*p的左、右子树均非空，先找到*p的中序前趋结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：①令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。②以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。第五十九页，共一百页，编辑于2023年，星期五本节结束！第六十页，共一百页，编辑于2023年，星期五3.3图3.3.1引言

图是一种重要的，比树更复杂的非线性数据结构。在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系。但在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。图的应用极为广泛，特别是近年来发展迅速，已渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其它分支中。第六十一页，共一百页，编辑于2023年，星期五3.3.2图的定义及逻辑结构

1、图的定义

图G由两个集合V(G)和E(G)所组成，记作G=(V, E)。其中，V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。 有向图。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括号括起一对顶点表示。

无向图。如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用圆括号括起的两个相关顶点来表示。第六十二页，共一百页，编辑于2023年，星期五图G1的顶点集合为：

V(G1)={V1,V2,V3,V4}边集合为：E(G1)={(V1,V2),(V1,V3),(V1,V4),(V2,V4),(V3,V4)}第六十三页，共一百页，编辑于2023年，星期五图G2的顶点集合为：

V(G2)={V1,V2,V3}边集合为：E(G2)={<V1,V3>,<V2,V1>,<V2,V3>,<V3,V1>}第六十四页，共一百页，编辑于2023年，星期五

2、图的有关术语

邻接：在无向图中，若边(Ｖx,Ｖy)E，则Ｖx、Ｖy互为邻接点；在有向图中，若弧<Ｖx,Ｖy>E，则Ｖy是Ｖx的邻接点。 度：VxVyＶx、Ｖy互为邻接点VxVyＶy是Ｖx的邻接点第六十五页，共一百页，编辑于2023年，星期五

度：无向图中:顶点的度是连接该顶点的边的条数。例如，G1中V2的度为3，V4的度为1。有向图中:入度:以某顶点为弧头的弧的数目G2中顶点1的入度为1。出度:以某顶点为弧尾的弧的数目。顶点1的出度为2。顶点的度=入度+出度。顶点1的度=2+1=3。213

G24oooov1v2v3v4

G1第六十六页，共一百页，编辑于2023年，星期五子图有两个图G=(V,{E})和图G’=(V’,{E’}),若V’V且E’E,则称图G’为G的子图。第六十七页，共一百页，编辑于2023年，星期五路径图中从顶点Vx到顶点Vy的顶点序列称为从Vx到Vy的路径,路径可能是不唯一的。例如:G1中V1到V3的路径为:(V1V2V3)或(V1V3);G2中，1到4的路径为<134>。oooov1v2v3v4G1213

G24第六十八页，共一百页，编辑于2023年，星期五路径的长度路径上边或弧的数目。例如，G1中V1到V3的长度为1或2；

G2中1到4的长度为2。oooov1v2v3v4G1213

G24第六十九页，共一百页，编辑于2023年，星期五连通图

在无向图G中，若从顶点V到顶点V’有路径，则称V和V’是连通的。无向图中任意两个顶点都连通，则称G是连通图。第七十页，共一百页，编辑于2023年，星期五强连通图有向图每对顶点之间都存在路径第七十一页，共一百页，编辑于2023年，星期五完全无向图 若一个具有n个顶点的无向图共有n(n-1)/2条边，即每一对顶点之间都有边相连，则称其为完全无向图完全有向图 若一个具有n个顶点的无向图共有n(n-1)条边，即每一对顶点之间都有两条方向不同的边相连，则称其为完全有向图第七十二页，共一百页，编辑于2023年，星期五网： 边或弧上带有权值的图 权值是与边或弧有关的书，可以表示从一个顶点到另一定点的距离或耗费等。第七十三页，共一百页，编辑于2023年，星期五3.3.3图的存储结构图的结构比较复杂，存储的方法也很多，需要根据具体的图形和将来所要做的运算选取适当的存储结构。这里只讨论两种最常用的表示方法：邻接矩阵表示法和邻接表表示法。

第七十四页，共一百页，编辑于2023年，星期五

1、顺序存储结构

邻接矩阵：可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集合E)。这个二维数组称之为邻接矩阵。 邻接矩阵是表示顶点之间的邻接关系的矩阵。设G=(V，E)是有n(n≥1)个顶点的图，则G的邻接矩阵A是一个具有下列性质的n×n阶矩阵第七十五页，共一百页，编辑于2023年，星期五无向图邻接矩阵 定义:设图G=(V,E)是有n(n1)个顶点的图，则G的邻接矩阵是具有下述性质的对称阵：

1(Vi，Vj）EA[i][j]=A[j][i]= 0(Vi，Vj）EG1的邻接矩阵为：oooov1v3v4G1A=G.edge=

01101011110001004x4G.nodes=

1234第七十六页，共一百页，编辑于2023年，星期五有向图邻接矩阵 定义:设图G=（V，E）是有n（n1）个顶点的图，则G的邻接矩阵是具有下述性质的nxn的方阵：

1〈Vi，Vj>EA[i][j]=0〈Vi，Vj>E

例如，G2的邻接矩阵为：G.nodes=1234A=G.Arc=

01100000000110004x41324

G2第七十七页，共一百页，编辑于2023年，星期五借助于邻接矩阵，可以很容易地求出图中顶点的度。从上例可以很容易看出，邻接矩阵有如下结论：

(1)无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。对无向图可考虑只存下三角(或上三角)元素。

(2)对于无向图，邻接矩阵第i行(或第i列)的元素之和是顶点Vi的度。

(3)对于有向图，邻接矩阵第i行元素之和为顶点Vi的出度；第i列的元素之和为顶点Vi的入度。第七十八页，共一百页，编辑于2023年，星期五

2、链式存储结构

图的链式存储结构是通过为每一个顶点建立一个相应的单链表来实现的，这种存储结构被称为邻接链表。 邻接链表是一种顺序分配和链式分配相结合的存储结构。它包括两个部分：一部分是链表；另一部分是向量。

第七十九页，共一百页，编辑于2023年，星期五 在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点Vi的所有邻接顶点。每个结点由三个域组成：adjvex、data和nextarc，如下图所示。第八十页，共一百页，编辑于2023年，星期五为便于邻接表操作，在每个单链表上附设一个头结点，在头结点中有两个域：vexdata和firstarc。如下图所示。第八十一页，共一百页，编辑于2023年，星期五第八十二页，共一百页，编辑于2023年，星期五图的邻接链表数据类型定义如下：structadjnode{intadjv;structadjnode*next;};structvernode{charver;structadjnode*first;}adjlist[N+1];第八十三页，共一百页，编辑于2023年，星期五有向图建立邻接链表的算法structvernodeg[N+1]voidcreatadjlist(){inti,j,k;adjnode*s;for(i=1;i<=N;i++){g[i].ver=getchar();g[i].first=NULL;}

for(k=1;k<=E;k++){scanf(“%d,%d”,&i,&j);s=(structadjnode*)mallov(sizeof(adjnode));s->adjv=j;s->next=g[i].first;g[i].first=s;}}

第八十四页，共一百页，编辑于2023年，星期五

对一个图来说，邻接链表不是惟一的，它取决于建立邻接链表时，结点在每个单链表中的插入策略。另外，对于有向图，其邻接链表中第i个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第i个单链表的结点个数就是此结点的度。第八十五页，共一百页，编辑于2023年，星期五3.3.4图

的

遍

历 图的遍历(traversinggraph)是指从图中某一顶点出发，沿着一定的搜索路径，对图中各个顶点进行访问，使每个顶点都被访问且仅被访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。第八十六页，共一百页，编辑于2023年，星期五然而，图的遍历要比树的遍历复杂得多，因为图中任一顶点都可能和其余的顶点相邻接，所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，设一个辅助数组visited[n]，它的初值为“假”或者零，一旦访问了顶点Vi，便置visited[i]为“真”或者为被访问时的次序号。通常有两种遍历图的方法，深度优先搜索和广度优先搜索。第八十七页，共一百页，编辑于2023年，星期五

1．深度优先搜索

图的深度优先搜索遍历(depth-firstsearch)类似于树的先序遍历，是树的先序遍历的推广。特点：遍历时尽可能向纵深的方向搜索。 步骤（从Vi出发）

1)访问Vi，并将其对应的访问标志为visited[i]置为1；

2)搜索出Vi的一个未访问过的邻接点Vj。

3)从Vj出发，按以上步骤继续进行深度优先搜索，直到所有顶点均访问完毕。第八十八页，共一百页，编辑于2023年，星期五显然，这个遍历过程是个递归过程。在设计具体算法时，首先要确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。例连通图G6的邻接表表示如下图所示，以顶点V1为始点，按深度优先搜索遍历图中所有顶点，写出顶点的遍历序列。第八十九页，共一百页，编辑于2023年，星期五解：先访问V1，再访问与V1邻接的V2，再访问V2的第一个邻接点，因V1已被访问过，则访问V2的下一个邻接点V4，然后依次访问V8，V5。这时，与V5相邻接的顶点均已被访问，于是反向回到V8去访问与V8相邻接且尚未被访问的V6，接着访问V3，V7，至此，全部顶点均被访问。相应的访问序列为：V1→V2→V4→V8→V5→V6→V3→V7。第九十页，共一百页，编辑于2023年，星期五深度优先搜索的递归算法（邻接矩阵存储结构）#defineNULL0intg[N+1][N+1];charver[N+1];intvisited[N+1];

voiddfsm(i)inti;{intj;printf(“%c”,ver[i]);visited[i]=1;for(j=1;j<=N;j++)if((g[i][j]==1)&&(!visited[j]))

dfsm(j);}第九十一页，共一百页，编辑于2023年，星期五

structvernodeg[N+1];intvisited[N+1];

voiddfsa(i)inti;{intj;structadjnode*p;printf(“%c”,g[i].ver);visited[i]=1;p=g[i].first;

while(p!=NULL){if!Visited[p->adjv])

dfsa(p->adjv);

p=p->next;}