非线性数据结构优秀课件.ppt

《非线性数据结构优秀课件.ppt》由会员分享，可在线阅读，更多相关《非线性数据结构优秀课件.ppt（100页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、非线性数据结构非线性数据结构第1页，本讲稿共100页3.1数数组组3.1.1 引言数组是大家已经很熟悉的一种数据类型，几乎所有的程序设计语言都把数组类型设定为固有类型。数组(array)可看成是线性表的推广，是最常用的数据结构之一。数组是有限个数组元素的集合；数组的每个元素与一组下标相对应；和线性表一样，数组中所有数组元素的数据类型必须一致。第2页，本讲稿共100页3.1.2数组的逻辑结构数组的逻辑结构逻辑关系是非线性的，实质上是多个线性关系的组合。逻辑关系是非线性的，实质上是多个线性关系的组合。Amn =a11 a12 .a1n a21 a22 .a2n am1 am2 .amn 如下所示，

2、就是一个如下所示，就是一个m行行n列的二维数组列的二维数组(也称为矩阵也称为矩阵)，记作记作Am,n。第3页，本讲稿共100页矩矩阵阵A可可以以看看成成是是由由m个个行行向向量量组组成成的的向向量量，也也可可以以看看成是由成是由n个列向量组成的向量。个列向量组成的向量。在在矩矩阵A A中中，每每个个元元素素a aijij都都属属于于两两个个线性性表表。一一个个是是第第i i行行的的行表(a(ai1i1，a ai2i2，.，a aijij，.，a ainin)，另另一一个个是是第第j j列列的的列表(a(a1j1j，a a2j2j，.，a aijij，.，a amjmj)。这种种行行表表(行行向

3、向量量)和和列表列表(列向量列向量)都相当于都相当于线性表性表。所所以以说说，数组可看作是线性表的推广，将将线线性性表表推推广广到二维或高维，就是我们所说的数组。到二维或高维，就是我们所说的数组。第4页，本讲稿共100页3.1.3数组的存储结构数组的存储结构数数组组的的顺顺序序分分配配就就是是用用向向量量作作为为数数组组的的存存储储结结构构。但但是是二二维维以以上上的的多多维维数数组组，不不像像一一维维数数组组那那样样，所所有有的的元元素素已已经经排排成成一一个个序序列列，所所以以要要把把多多维维数数组组顺顺序序地地存存储储到到一一维维顺顺序序的的存存储储器器中中，则则必必须须对对多多维维数数

4、组里的元素存放顺序做出一些规定。组里的元素存放顺序做出一些规定。通常数组采用通常数组采用两种顺序存储方式。第5页，本讲稿共100页1)行优先顺序存储行优先顺序存储行优先顺序存储就是就是数组元素按行表次序进行存储，数组元素按行表次序进行存储，即第即第i+1i+1个行表紧跟在第个行表紧跟在第i i个行表后面进行存储个行表后面进行存储。在在C、BASIC、PASCAL、COBOL等高级语言中均采用这种方法。等高级语言中均采用这种方法。以以二二维维数数组组Amn为为例例，按按行行优优先先顺顺序序存存储储的的数数组组元元素素次次序为：序为：a11，a12，a1n，a21，a22，a2n，am1，am2，

5、amn第6页，本讲稿共100页2)列优先顺序存储列优先顺序存储列优先顺序存储就是就是数组元素按列表次序进行存储，数组元素按列表次序进行存储，即第即第j+1j+1个列表紧跟在第个列表紧跟在第j j个列表后面进行存储个列表后面进行存储。在。在FORTRAN语言中，数组是按列优先顺序组织存储。语言中，数组是按列优先顺序组织存储。以以二二维维数数组组Amn为为例例，按按列列优优先先顺顺序序存存储储的的数数组组元元素素次次序为：序为：a11，a21，am1，a12，a22，am2，a1n，a2n，amn第7页，本讲稿共100页二维数组的两种存储方式二维数组的两种存储方式第8页，本讲稿共100页同同样样，

6、对对n维数组也也有有上上述述两两种种不不同同的的顺顺序序分分配配的的存存储储结结构构。当当把把n n维维数数组组的的元元素素这这样样顺顺序序地地存存放放在在存存储储器器里里，则则每每个个元元素素的的存存储储地地址址可可以以用用公公式式计计算算出出来来。这些计算公式称为这些计算公式称为“地址公式”。假设每个数据元素占假设每个数据元素占k个存储单元，则可得个存储单元，则可得（1）一维数组的地址公式为：的地址公式为：Loc(ai)=Loc(a1)+(i-1)*k（2）若若存存储储分分配配采采用用行优先顺顺序序分分配配，则则二维数组Amn的地址公式为：的地址公式为：Loc(aij)=Loc(a11)+

7、(i-1)*n+(j-1)*k第9页，本讲稿共100页同同理理，可可写写出出三维数组、n维数组的的数数组组元元素素存存储地址的计算公式。储地址的计算公式。（3）若若存存储储分分配配采采用用列优先顺顺序序分分配配，则则二维数组Amn的地址公式为：的地址公式为：Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*L同同理理，可可写写出出三维数组、n维数组的的数数组组元元素素存存储地址的计算公式。储地址的计算公式。第10页，本讲稿共100页3.1.4特殊矩阵的压缩存储特殊矩阵的压缩存储假假若若值值相相同同的的元元素素或或零零元元素素在在矩矩阵阵中中的的分分布布有有一一定定规规律律，则则称

8、称此此类类矩矩阵阵为为特殊矩阵。像像三三角角矩矩阵阵，对对称称矩矩阵阵、三对角矩阵等三对角矩阵等都属于特殊矩阵。都属于特殊矩阵。通通常常在在实实际际计计算算中中经经常常出出现现一一些些阶阶数数很很高高的的矩矩阵阵，同同时时矩矩阵阵中中有有许许多多值值相相同同的的元元素素或或者者零零元元素素。有有时时为为了了节节省省存存储储空空间间，可可以以对对这这类类矩矩阵阵进进行行压压缩缩存存储储。所所谓谓压缩存储是是指指：为为多多个个值值相相同同的的元元素素只只分分配配一一个个存存储储空空间间；对对零零元元素素不不分配空间分配空间。第11页，本讲稿共100页1）三角矩阵）三角矩阵例：下三角矩阵例：下三角矩

9、阵Ann，当，当i1，则则其双亲是结点。其双亲是结点。(2)如果如果2in，则结点，则结点i无左孩子；否则其左孩子是无左孩子；否则其左孩子是2i。(3)如如果果2i+1n，则则结结点点i无无右右孩孩子子；否否则则其其右右孩孩子子是是结点结点2i+1。证明从略。证明从略。第33页，本讲稿共100页3、满二叉树和完全二叉树的关系、满二叉树和完全二叉树的关系满二叉树满二叉树=完全二叉树完全二叉树满二叉树满二叉树完全二叉树完全二叉树4、平衡二叉树、平衡二叉树二二叉叉树树上上任任一一结结点点的的左左子子树树深深度度减减去去右右子子树树深深度度的的差差值值，称称为为此此结结点的平衡因子。点的平衡因子。若若

10、一一棵棵二二叉叉树树中中，每每个个结结点点的的平平衡衡因因子子之之绝绝对对值值都都不不大大于于1，则则称称这这棵棵二叉树为平衡二叉树。二叉树为平衡二叉树。(a)是平衡二叉树是平衡二叉树(b)不是平衡二叉树不是平衡二叉树第34页，本讲稿共100页 3.2.3.3 二叉树的存储结构二叉树的存储结构对对于于二二叉叉树树，我我们们既既可可采采用用顺顺序序存存储储，又又可可采采用用链链式存储。式存储。1顺序存储结构顺序存储结构顺顺序序存存储储就就是是将将一一棵棵二二叉叉树树的的所所有有结结点点按按照照一一定定的的次次序序顺顺序序存存放放到到一一组组连连续续的的存存储储单单元元中中，为为此此，必必须须把把

11、二二叉叉树树中中所所有有结结点点构构成成一一个个适适当当的的线线性性序序列列，以以使使各各个个结结点点在在这这个个序序列列中中的的相相互互位位置置能能反反映映出出结结点点之之间的逻辑关系。间的逻辑关系。第35页，本讲稿共100页对于完全二叉树，按图的编号顺序，就能得到一对于完全二叉树，按图的编号顺序，就能得到一个足以反映整个二叉树结构的线性序列。因此，可将个足以反映整个二叉树结构的线性序列。因此，可将完全二叉树中所有结点按编号顺序依次存储到一组连完全二叉树中所有结点按编号顺序依次存储到一组连续的存储单元续的存储单元(即向量即向量)中，这样既不浪费内存，又可以中，这样既不浪费内存，又可以利用地址

12、公式确定其结点的位置。利用地址公式确定其结点的位置。1234567ABDEFCJ第36页，本讲稿共100页但对于一般的二叉树，顺序分配常会造成内存的浪费，但对于一般的二叉树，顺序分配常会造成内存的浪费，因为一般的二叉树也必须按完全二叉树的形式来存储。因为一般的二叉树也必须按完全二叉树的形式来存储。1234567891011ABDEFCJGH第37页，本讲稿共100页 2链式存储结构链式存储结构因为树型结构是非线性的结构，所以在存储器里因为树型结构是非线性的结构，所以在存储器里表示树型结构的最自然的方法是链式存储。根据二叉表示树型结构的最自然的方法是链式存储。根据二叉树的特性，任何一个结点最多有

13、左、右两棵子树，所树的特性，任何一个结点最多有左、右两棵子树，所以每个结点至少设有三个域：数据域和左、右指针域。以每个结点至少设有三个域：数据域和左、右指针域。其结点结构为：其结点结构为：lchilddatarchild第38页，本讲稿共100页第39页，本讲稿共100页二叉链表结点的类型定义二叉链表结点的类型定义typedefstructnodedatatypedata;structnode*lchild,*rchild;bstree;第40页，本讲稿共100页3.2.3.4 二叉树的遍历二叉树的遍历遍历二叉树就是按一定的次序，系统地访问树中的所有结点，使每个结点恰好被访问一次。所谓访问结点

14、，其含义是很广的，可以理解为对结点的增、删、修改等各种运算的抽象。在本节讨论中，假定访问结点即为输出结点数据域值。二叉树的遍历是最重要和最基本的运算，二叉树的许多操作都是以遍历为基础的。按照对二叉树中根结点、左子树和右子树访问的先后顺序，共有三种遍历二叉树的方法：根、左、右；左、根、右；左、右、根根据这三种方法中根结点被访问的先后，分别称之为二叉树的先序(根)遍历，中序(根)遍历和后序(根)遍历。第41页，本讲稿共100页(1)先序遍历：先序遍历：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则访问根结点；访问根结点；先序遍历左子树；先序遍历左子树；先序遍历右子树。先序遍历右子树。遍历

15、序列：ABDEGHCF第42页，本讲稿共100页先序遍历的算法先序遍历的算法voidpreorder(bstree*p)if(p!=NULcL)printf(“%5”,p-data);preorder(p-lchild);preorder(p-rchild);第43页，本讲稿共100页(2)中序遍历：中序遍历：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则中序遍历左子树；中序遍历左子树；访问根结点；访问根结点；中序遍历右子树。中序遍历右子树。遍历序列：遍历序列：DBGEHACF第44页，本讲稿共100页中序遍历算法中序遍历算法voidpreorder(bstree*p)if(p!=N

16、ULcL)inorder(p-lchild);printf(“%5”,p-data);inorder(p-rchild);第45页，本讲稿共100页(3)后序遍历：后序遍历：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则后序遍历左子树；后序遍历左子树；后序遍历右子树。后序遍历右子树。访问根结点；访问根结点；遍历序列：DGHEBFCA第46页，本讲稿共100页后序遍历算法后序遍历算法voidposorder(bstree*p)if(p!=NULcL)posorder(p-lchild);posorder(p-rchild);printf(“%5”,p-data);第47页，本讲稿共10

17、0页3.2.4 树的存储结构树的存储结构树树在在计计算算机机内内存存储储，可可以以用用顺顺序序存存储储方方式式、也也可可以以用用链链式式存存储储方方式式，这这主主要要取取决决于于要要对对树树结结构构进进行行什什么么运算。这里主要介绍链式分配的存储结构。运算。这里主要介绍链式分配的存储结构。孩子孩子-兄弟表示法的链式存储结构表示如下：兄弟表示法的链式存储结构表示如下：firstdatanext链表中结点的两个指针域分别指向该结点的第一链表中结点的两个指针域分别指向该结点的第一个孩子和下一个兄弟结点。个孩子和下一个兄弟结点。第48页，本讲稿共100页RADEFCBGKHR A DE C HF GB

18、K第49页，本讲稿共100页 3.2.5 树的遍历树的遍历树树的的遍遍历历有有两两种种次次序序：一一种种是是先先序序遍遍历历树树；另一种是后序遍历树。另一种是后序遍历树。(1)先先序序遍遍历历树树：先先访访问问树树的的根根结结点点，然然后后从从左左到到右右依依次次先先序序遍遍历历根根的的每每棵棵子子树树。如如先先序序遍遍历历右右图图所所示示的的树树，得得到到的的结结点点序序列列为为：RADEBCFGHK。(2)后序遍历树：先从左到右依次后根后序遍历树：先从左到右依次后根遍历每棵子树，然后访问根结点。如后序遍历每棵子树，然后访问根结点。如后序遍历右图所示的树，得到的结点序列为：遍历右图所示的树，

19、得到的结点序列为：DEABGHKFCR。RADEFCBGKH第50页，本讲稿共100页3.2.6 树、森林与二叉树的转换树、森林与二叉树的转换由由于于二二叉叉树树和和树树都都可可用用二二叉叉链链表表作作为为存存储储结结构构，则则以以二二叉叉链链表表作作为为媒媒介介可可导导出出树树与与二二叉叉树树之之间间的的一一个个对对应应关关系系。也也就就是是说说，给给定定一一棵棵树树，可可以以找找到到惟惟一一的的一一棵棵二二叉叉树树与与之之对对应应，从从物物理理结结构构来来看看，它它们们的的二二叉叉链链表表是是相相同同的的，只只是是解解释释不不同同而而已已。图图3-15给给出出了了树树与与二叉树之间的对应关

20、系。二叉树之间的对应关系。第51页，本讲稿共100页图3-15 树与二叉树的对应关系第52页，本讲稿共100页下面给出树与二叉树之间的转换规则。下面给出树与二叉树之间的转换规则。1一般树转换为二叉树一般树转换为二叉树步骤步骤：(1)加线：亲兄弟之间加一虚连线。加线：亲兄弟之间加一虚连线。(2)抹抹线线：抹抹掉掉(除除最最左左一一个个孩孩子子外外)该该结结点点到到其其余余孩孩子之间的连线。子之间的连线。(3)旋转：新加上去的虚线改实线且均向右斜旋转：新加上去的虚线改实线且均向右斜(rchild)，原有的连线均向左斜，原有的连线均向左斜(lchild)。第53页，本讲稿共100页图3-16 一般树

21、转换为二叉树的操作过程(a)一般树；(b)加线后；(c)抹线后；(d)旋转后第54页，本讲稿共100页 2森林转换为二叉树森林转换为二叉树森森林林是是树树的的有有限限集集合合，利利用用树树的的转转换换思思想想，可可以以实实现森林到二叉树的转换。现森林到二叉树的转换。步骤步骤：(1)将各棵树分别转换为二叉树。将各棵树分别转换为二叉树。(2)按按给给出出森森林林中中树树的的次次序序，依依次次将将后后一一棵棵二二叉叉树树作作为为前前一一棵棵二二叉叉树树根根结结点点的的右右子子树树，则则第第一一棵棵树树的的根根结结点是转换后二叉树的根。点是转换后二叉树的根。第55页，本讲稿共100页图3-17 森林转

22、换成对应的二叉树的过程(a)森林；(b)各棵树对应的二叉树；(c)转换成的二叉树第56页，本讲稿共100页3.2.7树的应用树的应用树结构被广泛地用于分类、检索、数据库及人工智能等方面。树结构被广泛地用于分类、检索、数据库及人工智能等方面。二叉排序树二叉排序树二叉排序树是一种动态树表。二叉排序树是一种动态树表。二叉排序树的定义：二叉排序树或者是一棵空树，二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的或者是一棵具有如下性质的二叉树：二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则

23、右子树上所有结点的值均大于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。二叉排序树的性质：左、右子树本身又各是一棵二叉排序树。二叉排序树的性质：按中序遍历按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。二叉排序树，所得到的中序遍历序列是一个递增有序序列。第57页，本讲稿共100页（1）二叉排序树生成：）二叉排序树生成：从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。序树。插入一个结点的操作按下述方法完成：插入一个结点的操作按下述

24、方法完成：若原二叉排序树为空，则将待插结点作为此数的根结点。若原二叉排序树为空，则将待插结点作为此数的根结点。若原二叉排序树不为空，若原二叉排序树不为空，则比较待插结点和根结点的关键字值；若则比较待插结点和根结点的关键字值；若待插元素的关键字值小于根结点的的关键字值，则将其插入到左子数中；待插元素的关键字值小于根结点的的关键字值，则将其插入到左子数中；否则，将其插入到右子树中；否则，将其插入到右子树中；在二叉排序树的左右子树中的插入过程同上。在二叉排序树的左右子树中的插入过程同上。例：对于一组关键字例：对于一组关键字51，34，79，18，45，86，生成，生成对应的二叉排序树对应的二叉排序树

25、第58页，本讲稿共100页（2）二叉排序树的删除）二叉排序树的删除:假设被删结点是假设被删结点是*p，其双亲是，其双亲是*f，不失一般性，设，不失一般性，设*p是是*f的左孩子，下面分的左孩子，下面分三种情况讨论：三种情况讨论：若结点若结点*p是叶子结点，则只需修改其双亲结点是叶子结点，则只需修改其双亲结点*f的指针即可的指针即可.若结点若结点*p只有左子树只有左子树PL或者只有右子树或者只有右子树PR，则只要使，则只要使PL或或PR成为其双亲成为其双亲结点的左子树即可。结点的左子树即可。若结点若结点*p的左、右子树均非空，先找到的左、右子树均非空，先找到*p的中序前趋结点的中序前趋结点*s（

26、注意（注意*s是是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：的左子树中的最右下的结点，它的右链域为空），然后有两种做法：令令*p的左子树直接链到的左子树直接链到*p的双亲结点的双亲结点*f的左链上的左链上,而而*p的右子树链到的右子树链到*p的中的中序前趋结点序前趋结点*s的右链上。的右链上。以以*p的中序前趋结点的中序前趋结点*s代替代替*p（即把（即把*s的数据复制到的数据复制到*p中），将中），将*s的左子的左子树链到树链到*s的双亲结点的双亲结点*q的左（或右）链上。的左（或右）链上。第59页，本讲稿共100页本节结束！本节结束！第60页，本讲稿共100页3.3

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

28、页，本讲稿共100页3.3.2图的定义及逻辑结构图的定义及逻辑结构1、图的定义、图的定义图图G由两个集合由两个集合V(G)和和E(G)所组成，记作所组成，记作G=(V,E)。其中，。其中，V(G)是图中顶点的非空有限集合，是图中顶点的非空有限集合，E(G)是图中边的有限集合。是图中边的有限集合。有向图有向图。如果图中每条边都是顶点的有序对，即每条边都用箭头。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括号尖括号括起括起一对顶点表示。一对顶点表示。无向图无向图。如果图中每条边都是顶点的无

29、序对，则称此图为无向图。如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用无向边用圆括号圆括号括起的两个相关顶点来表示。括起的两个相关顶点来表示。第62页，本讲稿共100页图图G1的顶点集合为：的顶点集合为：V(G1)=V1,V2,V3,V4边集合为：边集合为：E(G1)=(V1,V2),(V1,V3),(V1,V4),(V2,V4),(V3,V4)第63页，本讲稿共100页图图G2的顶点集合为：的顶点集合为：V(G2)=V1,V2,V3边集合为：边集合为：E(G2)=,第64页，本讲稿共100页2、图的有关术语、图的有关术语邻邻接接：在在无无向向图图中中，若若边边(x,x,y)y)E

30、 E，则则x x、y y互互为为邻邻接接点点；在在有有向向图图中中，若若弧弧 y E E，则则y y是是x x的邻接点。的邻接点。度：度：VxVyx、y互为邻接点互为邻接点VxVyy是是x的邻接点的邻接点第65页，本讲稿共100页度：无向图中:顶点的度是连接该顶点的边的条数。例如，G1中V2的度为3，V4的度为1。有向图中:入度:以某顶点为弧头的弧的数目G2中顶点1的入度为1。出度:以某顶点为弧尾的弧的数目。顶点1的出度为2。顶点的度=入度+出度。顶点1的度=2+1=3。213G24oooov1v2v3v4G1第66页，本讲稿共100页子图子图有两个图有两个图G=(V,E)和和图图G=(V,E

31、),若若V V且且E E,则称则称图图G为为G的子图的子图。第67页，本讲稿共100页路径路径图中从顶点图中从顶点Vx到顶点到顶点Vy的顶的顶点序列称为从点序列称为从Vx到到Vy的路径的路径,路径可能是不唯一的。路径可能是不唯一的。例如例如:G1中中V1到到V3的路径为的路径为:(V1V2V3)或或(V1V3);G2中，中，1到到4的路径为的路径为。oooov1v2v3v4G1213G24第68页，本讲稿共100页路径的长度路径的长度路径上边或弧的数目。路径上边或弧的数目。例例如如，G1中中V1到到V3的的长度为长度为1或或2；G2中中1到到4的长度为的长度为2。oooov1v2v3v4G12

32、13G24第69页，本讲稿共100页连通图连通图在无向图在无向图G中，若从顶点中，若从顶点V到顶点到顶点V有路径，则称有路径，则称V和和V是连通的。是连通的。无向图中任意两个顶点都连无向图中任意两个顶点都连通，则称通，则称G是连通图。是连通图。第70页，本讲稿共100页强连通图强连通图有向图每对顶点之间都存在路径有向图每对顶点之间都存在路径第71页，本讲稿共100页完全无向图完全无向图若一个具有若一个具有n个顶个顶点的无向图共有点的无向图共有n(n-1)/2条边，即每一对顶条边，即每一对顶点之间都有边相连，点之间都有边相连，则称其为完全无向图则称其为完全无向图完全有向图完全有向图若一个具有若一

33、个具有n个顶个顶点的无向图共有点的无向图共有n(n-1)条边，即每一对顶点条边，即每一对顶点之间都有两条方向不之间都有两条方向不同的边相连，则称其同的边相连，则称其为完全有向图为完全有向图第72页，本讲稿共100页网：网：边或弧上带有权值的图边或弧上带有权值的图权值是与边或弧有关的书，可以表示从一个顶点权值是与边或弧有关的书，可以表示从一个顶点到另一定点的距离或耗费等。到另一定点的距离或耗费等。第73页，本讲稿共100页3.3.3 图的存储结构图的存储结构图图的的结结构构比比较较复复杂杂，存存储储的的方方法法也也很很多多，需需要要根根据据具具体体的的图图形形和和将将来来所所要要做做的的运运算算

34、选选取取适适当当的的存存储储结结构构。这这里里只只讨讨论论两两种种最最常常用用的的表表示示方方法法：邻邻接接矩矩阵阵表表示示法法和和邻接表邻接表表示法。表示法。第74页，本讲稿共100页 1、顺序存序存储结构构 邻接矩阵：邻接矩阵：可用一个一维数组存放图中所有顶点的信息；可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集即边或弧的集合合E)。这个二维数组称之为邻接矩阵。这个二维数组称之为邻接矩阵。邻邻接接矩矩阵阵是是表表示示顶顶点点之之间间的的邻邻接接关关系系的的矩矩阵阵。设设G=(V，E)是是有有n(

35、n1)个个顶顶点点的的图图，则则G的的邻邻接接矩矩阵阵A是是一一个个具具有有下下列列性性质质的的nn阶矩阵阶矩阵第75页，本讲稿共100页无向图邻接矩阵无向图邻接矩阵定义定义:设图设图G=(V,E)是有是有n(n 1)个顶点的图，则个顶点的图，则G的的邻接矩阵是具有下述性质的对称阵：邻接矩阵是具有下述性质的对称阵：1(Vi，Vj）EAij=Aji=0(Vi，Vj）EG1的邻接矩阵为：的邻接矩阵为：oooov1v3v4G1A=G.edge=0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 4x4G.nodes=1234第76页，本讲稿共100页有向图邻接矩阵定义:设图G=（V，E）

36、是有n（n 1）个顶点的图，则G的邻接矩阵是具有下述性质的nxn的方阵：1 Vi，Vj E Aij=0 Vi，Vj E 例如，G2的邻接矩阵为：G.nodes=1234A=G.Arc=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 04x41324G2第77页，本讲稿共100页借助于邻接矩阵，可以很容易地求出图中顶点的度。借助于邻接矩阵，可以很容易地求出图中顶点的度。从上例可以很容易看出，邻接矩阵有如下结论：从上例可以很容易看出，邻接矩阵有如下结论：(1)无无向向图图的的邻邻接接矩矩阵阵是是对对称称的的，而而有有向向图图的的邻邻接接矩矩阵阵不不一一定定对对称称。对对无无向向图图可可

37、考考虑虑只只存存下下三三角角(或或上上三三角角)元素。元素。(2)对对于于无无向向图图，邻邻接接矩矩阵阵第第i行行(或或第第i列列)的的元元素素之之和和是顶点是顶点Vi的度。的度。(3)对对于于有有向向图图，邻邻接接矩矩阵阵第第i行行元元素素之之和和为为顶顶点点Vi的的出度；第出度；第i列的元素之和为顶点列的元素之和为顶点Vi的入度。的入度。第78页，本讲稿共100页 2、链式存式存储结构构图图的的链链式式存存储储结结构构是是通通过过为为每每一一个个顶顶点点建建立立一一个个相相应的单链表来实现的，这种存储结构被称为应的单链表来实现的，这种存储结构被称为邻接链表邻接链表。邻邻接接链链表表是是一一

38、种种顺顺序序分分配配和和链链式式分分配配相相结结合合的的存存储储结结构。它包括两个部分：一部分是链表；另一部分是向量。构。它包括两个部分：一部分是链表；另一部分是向量。第79页，本讲稿共100页在邻接表中，对图中每个顶点建立一个单链表，第在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点个单链表中的结点包含了顶点Vi的所有邻接顶点。每个结点的所有邻接顶点。每个结点由三个域组成：由三个域组成：adjvex、data和和nextarc，如下图所示。，如下图所示。第80页，本讲稿共100页为为便便于于邻邻接接表表操操作作，在在每每个个单单链链表表上上附附设设一一个个头头结结点点

39、，在在头头结结点点中中有有两两个个域域：vexdata和和firstarc。如如下下图图所示。所示。第81页，本讲稿共100页第82页，本讲稿共100页图的邻接链表数据类型定义如下：图的邻接链表数据类型定义如下：structadjnodeintadjv;structadjnode*next;structvernodecharver;structadjnode*first;adjlistN+1;第83页，本讲稿共100页有向图建立邻接链表的算法有向图建立邻接链表的算法structvernodegN+1voidcreatadjlist()inti,j,k;adjnode*s;for(i=1;i=N

40、;i+)gi.ver=getchar();gi.first=NULL;for(k=1;kadjv=j;s-next=gi.first;gi.first=s;第84页，本讲稿共100页对对一一个个图图来来说说，邻邻接接链链表表不不是是惟惟一一的的，它它取取决决于于建建立立邻邻接接链链表表时时，结结点点在在每每个个单单链链表表中中的的插插入入策策略略。另另外外，对对于于有有向向图图，其其邻邻接接链链表表中中第第i个个单单链链表表的的结结点点个个数数就就是是此此结结点点的的出出度度；对对于于无无向向图图，其其邻邻接接表表中中第第i个个单链表的结点个数就是此结点的度。单链表的结点个数就是此结点的度。第

41、85页，本讲稿共100页3.3.4 图图 的的 遍遍 历历图图的的遍遍历历(traversinggraph)是是指指从从图图中中某某一一顶顶点点出出发发，沿沿着着一一定定的的搜搜索索路路径径，对对图图中中各各个个顶顶点点进进行行访访问问，使使每每个个顶顶点点都都被被访访问问且且仅仅被被访访问问一一次次。图图的的遍遍历历算算法法是是求求解解图图的的连连通通性性问问题题、拓拓扑扑排排序序和和求求关关键键路路径径等等算算法的基础。法的基础。第86页，本讲稿共100页然然而而，图图的的遍遍历历要要比比树树的的遍遍历历复复杂杂得得多多，因因为为图图中中任任一一顶顶点点都都可可能能和和其其余余的的顶顶点点

42、相相邻邻接接，所所以以在在访访问问了了某某个个顶顶点点之之后后，可可能能沿沿着着某某条条路路径径搜搜索索之之后后，又又回回到到该该顶顶点点上上。为为避避免免同同一一顶顶点点被被访访问问多多次次，在在遍遍历历图图的的过过程程中中，必必须须记记下下每每个个已已访访问问过过的的顶顶点点。为为此此，设设一一个个辅辅助助数数组组visitedn，它它的的初初值值为为“假假”或或者者零零，一一旦旦访访问问了了顶顶点点Vi，便便置置visitedi为为“真真”或或者者为为被被访访问问时的次序号。时的次序号。通常有两种遍历图的方法，通常有两种遍历图的方法，深度优先搜索深度优先搜索和和广度广度优先搜索优先搜索。

43、第87页，本讲稿共100页 1深度优先搜索深度优先搜索图图的的深深度度优优先先搜搜索索遍遍历历(depth-firstsearch)类类似似于于树树的的先序遍历，是树的先序遍历的推广。先序遍历，是树的先序遍历的推广。特点：遍历时尽可能向纵深的方向搜索。特点：遍历时尽可能向纵深的方向搜索。步骤（从步骤（从Vi出发）出发）1)访访问问Vi，并并将将其其对对应应的的访访问问标标志志为为visitedi置置为为1；2)搜索出搜索出Vi的一个未访问过的邻接点的一个未访问过的邻接点Vj。3)从从Vj出出发发，按按以以上上步步骤骤继继续续进进行行深深度度优优先先搜搜索索，直到所有顶点均访问完毕。直到所有顶点

44、均访问完毕。第88页，本讲稿共100页显显然然，这这个个遍遍历历过过程程是是个个递递归归过过程程。在在设设计计具具体体算算法法时时，首首先先要要确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。例例连连通通图图G6的的邻邻接接表表表表示示如如下下图图所所示示，以以顶顶点点V1为为始始点点，按按深深度优先搜索遍历图中所有顶点，写出顶点的遍历序列。度优先搜索遍历图中所有顶点，写出顶点的遍历序列。第89页，本讲稿共100页解：解：先访问先访问V1，再访问与，再访问与V1邻接的邻接的V2，再访问，再访问V2的的第一个邻接点，因第一个邻接点，

45、因V1已被访问过，则访问已被访问过，则访问V2的下一个的下一个邻接点邻接点V4，然后依次访问，然后依次访问V8，V5。这时，与。这时，与V5相邻接相邻接的顶点均已被访问，于是反向回到的顶点均已被访问，于是反向回到V8去访问与去访问与V8相邻相邻接且尚未被访问的接且尚未被访问的V6，接着访问，接着访问V3，V7，至此，全部，至此，全部顶点均被访问。相应的访问序列为：顶点均被访问。相应的访问序列为：V1V2V4V8V5V6V3V7。第90页，本讲稿共100页深度优先搜索的递归算法（邻接矩阵存储结构）#defineNULL0intgN+1N+1;charverN+1;intvisitedN+1;vo

46、iddfsm(i)inti;intj;printf(“%c”,veri);visitedi=1;for(j=1;jadjv)dfsa(p-adjv);p=p-next;深度优先搜索的递归算法（邻接链表存储结构）深度优先搜索的递归算法（邻接链表存储结构）第92页，本讲稿共100页 2广度优先搜索广度优先搜索广广度度优优先先搜搜索索(breadth-firstsearch)类类似似于于树树的的按按层层次遍历的过程。次遍历的过程。假假设设从从图图中中某某顶顶点点V0出出发发，在在访访问问了了V0之之后后依依次次访访问问V0的的各各个个未未曾曾被被访访问问过过的的邻邻接接点点，然然后后分分别别从从这这

47、些些邻邻接接点点出出发发广广度度优优先先搜搜索索遍遍历历图图，直直至至图图中中所所有有已已被被访访问问的的顶顶点点的的邻邻接接点点都都被被访访问问到到。若若此此时时图图中中尚尚有有顶顶点点未未被被访访问问，则则另另选选图图中中一一个个未未曾曾被被访访问问的的顶顶点点作作起起始始点点，重重复复上上述述过过程程，直直至至图图中中所所有有顶顶点点都都被被访访问问到到为止。为止。第93页，本讲稿共100页具体遍历步骤如下：具体遍历步骤如下：(1)访问访问V0。(2)从从V0出出发发，依依次次访访问问V0的的未未被被访访问问过过的的邻邻接接点点W1，W2，Wt。然然后后依依次次从从W1，W2，Wt出出发

48、发，访问各自未被访问过的邻接点。访问各自未被访问过的邻接点。(3)重重复复步步骤骤(2)，直直到到所所有有顶顶点点的的邻邻接接点点均均被被访访问问过过为止。为止。第94页，本讲稿共100页例例对连通图对连通图G6，从顶点，从顶点V1出发，写出顶点的广度优先遍历序列。出发，写出顶点的广度优先遍历序列。解解：按按广广度度优优先先搜搜索索法法从从V1开开始始遍遍历历，访访问问V1，然然后后访访问问V1的的邻邻接接点点V2，V3，再再依依次次访访问问V2和和V3的的未未曾曾被被访访问问的的邻邻接接点点V4，V5及及V6，V7，最后访问，最后访问V4的邻接点的邻接点V8。遍历序列如下：。遍历序列如下：V

49、1V2V3V4V5V6V7V8第95页，本讲稿共100页intgN+1N+1;charverN+1;intvisitedN+1;voidbfsm(i)inti;intj;intqN+1,front,rear;setnull(q,front,rear);printf(“%c”,veri);visitedi=1;enqueue(q,i,front,rear);while(!empty(q,front,rear)i=dequeue(q,front,rear)for(j=1;jadjv)print(“%c”,gp-adjv.ver);visitedp-adjv=1;enqueue(q,p-adjv,f

50、ront,rear);p=p-next;广度优先搜索的递归算法（邻接链表存储结构）广度优先搜索的递归算法（邻接链表存储结构）第97页，本讲稿共100页3.3.5图的应用图的应用 公路网公路网活动网活动网3.3.6小结小结邻接矩阵；邻接链表；深度优先搜索；广度优先搜索邻接矩阵；邻接链表；深度优先搜索；广度优先搜索第98页，本讲稿共100页给出一张某公园的导游图，给出一张某公园的导游图，游客通过终端询问可知：游客通过终端询问可知：a)从某一景点到另一个景点的最从某一景点到另一个景点的最短路径。短路径。b)游客从公园大门进入，选游客从公园大门进入，选一条最佳路线，使游客可以一条最佳路线，使游客可以不