非线性数据结构

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

2、 amn 如下所示，就是一个m行n列的二维数组(也称为矩阵)，记作Am, n。第3页，共100页，2022年，5月20日，3点39分，星期四 矩阵A可以看成是由m个行向量组成的向量，也可以看成是由n个列向量组成的向量。 在矩阵A中，每个元素aij都属于两个线性表。一个是第i行的行表(ai1，ai2，.，aij，.，ain)，另一个是第j列的列表(a1j，a2j，.，aij，.，amj)。这种行表(行向量)和列表(列向量)都相当于线性表。 所以说，数组可看作是线性表的推广，将线性表推广到二维或高维，就是我们所说的数组。第4页，共100页，2022年，5月20日，3点39分，星期四 3.1.3 数

3、组的存储结构 数组的顺序分配就是用向量作为数组的存储结构。但是二维以上的多维数组，不像一维数组那样，所有的元素已经排成一个序列，所以要把多维数组顺序地存储到一维顺序的存储器中，则必须对多维数组里的元素存放顺序做出一些规定。 通常数组采用两种顺序存储方式。第5页，共100页，2022年，5月20日，3点39分，星期四 1) 行优先顺序存储 行优先顺序存储就是数组元素按行表次序进行存储，即第i+1个行表紧跟在第i个行表后面进行存储。在C、BASIC、PASCAL、COBOL等高级语言中均采用这种方法。 以二维数组Amn为例，按行优先顺序存储的数组元素次序为： a11，a12，a1n，a21，a22

4、，a2n，am1，am2，amn 第6页，共100页，2022年，5月20日，3点39分，星期四 2) 列优先顺序存储 列优先顺序存储就是数组元素按列表次序进行存储，即第j+1个列表紧跟在第j个列表后面进行存储。在FORTRAN语言中，数组是按列优先顺序组织存储。 以二维数组Amn为例，按列优先顺序存储的数组元素次序为： a11，a21，am1，a12，a22，am2，a1n，a2n，amn 第7页，共100页，2022年，5月20日，3点39分，星期四二维数组的两种存储方式第8页，共100页，2022年，5月20日，3点39分，星期四 同样，对n维数组也有上述两种不同的顺序分配的存储结构。当

5、把n维数组的元素这样顺序地存放在存储器里，则每个元素的存储地址可以用公式计算出来。这些计算公式称为“地址公式”。 假设每个数据元素占k个存储单元，则可得 （1）一维数组的地址公式为：Loc(ai)= Loc(a1)+(i-1)* k （2）若存储分配采用行优先顺序分配，则二维数组Amn的地址公式为：Loc(aij)= Loc(a11)+ (i-1)* n +(j-1) *k第9页，共100页，2022年，5月20日，3点39分，星期四 同理，可写出三维数组、n维数组的数组元素存储地址的计算公式。 （3）若存储分配采用列优先顺序分配，则二维数组Amn的地址公式为： Loc(aij)= Loc(a

6、11)+ (j-1)* m +(i-1) * L 同理，可写出三维数组、n维数组的数组元素存储地址的计算公式。第10页，共100页，2022年，5月20日，3点39分，星期四 3.1.4 特殊矩阵的压缩存储 假若值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵。像三角矩阵，对称矩阵、三对角矩阵等都属于特殊矩阵。 通常在实际计算中经常出现一些阶数很高的矩阵，同时矩阵中有许多值相同的元素或者零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元素不分配空间。 第11页，共100页，2022年，5月20日，3点39

7、分，星期四 1）三角矩阵 例：下三角矩阵Ann，当i1，则其双亲是结点。 (2) 如果2in，则结点i无左孩子；否则其左孩子是2i。 (3) 如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1。 证明从略。第33页，共100页，2022年，5月20日，3点39分，星期四3、满二叉树和完全二叉树的关系满二叉树 =完全二叉树满二叉树 完全二叉树4、平衡二叉树 二叉树上任一结点的左子树深度减去右子树深度的差值，称为此结点的平衡因子。 若一棵二叉树中，每个结点的平衡因子之绝对值都不大于1，则称这棵二叉树为平衡二叉树。是平衡二叉树 不是平衡二叉树第34页，共100页，2022年，5月20日，3

8、点39分，星期四 3.2.3.3 二叉树的存储结构 对于二叉树，我们既可采用顺序存储，又可采用链式存储。 1顺序存储结构 顺序存储就是将一棵二叉树的所有结点按照一定的次序顺序存放到一组连续的存储单元中，为此，必须把二叉树中所有结点构成一个适当的线性序列，以使各个结点在这个序列中的相互位置能反映出结点之间的逻辑关系。第35页，共100页，2022年，5月20日，3点39分，星期四 对于完全二叉树，按图的编号顺序，就能得到一个足以反映整个二叉树结构的线性序列。因此，可将完全二叉树中所有结点按编号顺序依次存储到一组连续的存储单元(即向量)中，这样既不浪费内存，又可以利用地址公式确定其结点的位置。12

9、34567ABDEFCJ第36页，共100页，2022年，5月20日，3点39分，星期四 但对于一般的二叉树，顺序分配常会造成内存的浪费，因为一般的二叉树也必须按完全二叉树的形式来存储。1234567891011ABDEFCJGH第37页，共100页，2022年，5月20日，3点39分，星期四 2链式存储结构 因为树型结构是非线性的结构，所以在存储器里表示树型结构的最自然的方法是链式存储。根据二叉树的特性，任何一个结点最多有左、右两棵子树，所以每个结点至少设有三个域：数据域和左、右指针域。其结点结构为：lchilddatarchild第38页，共100页，2022年，5月20日，3点39分，星

10、期四第39页，共100页，2022年，5月20日，3点39分，星期四二叉链表结点的类型定义typedef struct node datatype data; struct node * lchild, *rchild; bstree;第40页，共100页，2022年，5月20日，3点39分，星期四3.2.3.4 二叉树的遍历 遍历二叉树就是按一定的次序，系统地访问树中的所有结点，使每个结点恰好被访问一次。所谓访问结点，其含义是很广的，可以理解为对结点的增、删、修改等各种运算的抽象。在本节讨论中，假定访问结点即为输出结点数据域值。二叉树的遍历是最重要和最基本的运算，二叉树的许多操作都是以遍历为

11、基础的。 按照对二叉树中根结点、左子树和右子树访问的先后顺序，共有三种遍历二叉树的方法：根、左、右；左、根、右；左、右、根根据这三种方法中根结点被访问的先后，分别称之为二叉树的先序(根)遍历，中序(根)遍历和后序(根)遍历。 第41页，共100页，2022年，5月20日，3点39分，星期四(1) 先序遍历： 若二叉树为空，则空操作；否则 访问根结点； 先序遍历左子树； 先序遍历右子树。遍历序列：A B D E G H C F第42页，共100页，2022年，5月20日，3点39分，星期四先序遍历的算法void preorder(bstree *p) if(p!=NULcL) printf(“%

12、5”, p-data); preorder(p-lchild); preorder(p-rchild); 第43页，共100页，2022年，5月20日，3点39分，星期四(2) 中序遍历：若二叉树为空，则空操作；否则 中序遍历左子树； 访问根结点； 中序遍历右子树。遍历序列： D B G E H A C F第44页，共100页，2022年，5月20日，3点39分，星期四中序遍历算法void preorder(bstree *p) if(p!=NULcL) inorder(p-lchild); printf(“%5”, p-data); inorder(p-rchild); 第45页，共100页

13、，2022年，5月20日，3点39分，星期四(3) 后序遍历：若二叉树为空，则空操作；否则 后序遍历左子树； 后序遍历右子树。 访问根结点；遍历序列：D G H E B F C A第46页，共100页，2022年，5月20日，3点39分，星期四后序遍历算法void posorder(bstree *p) if(p!=NULcL) posorder(p-lchild); posorder(p-rchild); printf(“%5”, p-data); 第47页，共100页，2022年，5月20日，3点39分，星期四3.2.4 树的存储结构 树在计算机内存储，可以用顺序存储方式、也可以用链式存储

14、方式，这主要取决于要对树结构进行什么运算。这里主要介绍链式分配的存储结构。孩子-兄弟表示法的链式存储结构表示如下：firstdatanext链表中结点的两个指针域分别指向该结点的第一个孩子和下一个兄弟结点。第48页，共100页，2022年，5月20日，3点39分，星期四RADEFCBGKHRADECHFGBK第49页，共100页，2022年，5月20日，3点39分，星期四 3.2.5 树的遍历 树的遍历有两种次序：一种是先序遍历树；另一种是后序遍历树。 (1) 先序遍历树：先访问树的根结点，然后从左到右依次先序遍历根的每棵子树。如先序遍历右图所示的树，得到的结点序列为： R A D E B C

15、 F G H K 。 (2) 后序遍历树：先从左到右依次后根遍历每棵子树，然后访问根结点。如后序遍历右图所示的树，得到的结点序列为：D E A B G H K F C R 。 RADEFCBGKH第50页，共100页，2022年，5月20日，3点39分，星期四3.2.6 树、森林与二叉树的转换 由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到惟一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。图3-15给出了树与二叉树之间的对应关系。第51页，共100页，2022年，5月20日，3点

16、39分，星期四图3-15 树与二叉树的对应关系第52页，共100页，2022年，5月20日，3点39分，星期四 下面给出树与二叉树之间的转换规则。 1一般树转换为二叉树 步骤： (1) 加线：亲兄弟之间加一虚连线。 (2) 抹线：抹掉(除最左一个孩子外)该结点到其余孩子之间的连线。 (3) 旋转：新加上去的虚线改实线且均向右斜(rchild)，原有的连线均向左斜(lchild)。第53页，共100页，2022年，5月20日，3点39分，星期四图3-16 一般树转换为二叉树的操作过程(a) 一般树；(b) 加线后；(c) 抹线后；(d) 旋转后第54页，共100页，2022年，5月20日，3点3

17、9分，星期四 2森林转换为二叉树 森林是树的有限集合，利用树的转换思想，可以实现森林到二叉树的转换。 步骤： (1) 将各棵树分别转换为二叉树。 (2) 按给出森林中树的次序，依次将后一棵二叉树作为前一棵二叉树根结点的右子树，则第一棵树的根结点是转换后二叉树的根。第55页，共100页，2022年，5月20日，3点39分，星期四图3-17 森林转换成对应的二叉树的过程(a) 森林；(b) 各棵树对应的二叉树；(c) 转换成的二叉树第56页，共100页，2022年，5月20日，3点39分，星期四3.2.7 树的应用 树结构被广泛地用于分类、检索、数据库及人工智能等方面。二叉排序树二叉排序树是一种动

18、态树表。 二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树本身又各是一棵二叉排序树。二叉排序树的性质： 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。第57页，共100页，2022年，5月20日，3点39分，星期四（1）二叉排序树生成： 从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。 插入一个结点的操作按下述方法完成： 若原二叉排序树为空，则将待插结点作为此数的根结点。 若原二叉排序树不为空，

19、 则比较待插结点和根结点的关键字值；若待插元素的关键字值小于根结点的的关键字值，则将其插入到左子数中；否则，将其插入到右子树中； 在二叉排序树的左右子树中的插入过程同上。例：对于一组关键字51，34，79，18，45，86，生成对应的二叉排序树第58页，共100页，2022年，5月20日，3点39分，星期四 （2）二叉排序树的删除: 假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论： 若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可. 若结点*p只有左子树PL或者只有右子树PR，则只要使PL或PR 成为其双亲结点的左子树即可。 若结点*p的左、右子

20、树均非空，先找到*p的中序前趋结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法： 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。 以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。第59页，共100页，2022年，5月20日，3点39分，星期四本节结束！第60页，共100页，2022年，5月20日，3点39分，星期四3.3 图3.3.1 引言 图是一种重要的，比树更复杂的非线性数据结构。在树中，每个结点只与上层的父结点有联系，并可以与其下层

21、的多个子结点有联系。但在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。 图的应用极为广泛，特别是近年来发展迅速，已渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其它分支中。第61页，共100页，2022年，5月20日，3点39分，星期四3.3.2 图的定义及逻辑结构 1、图的定义图G由两个集合V(G)和E(G)所组成，记作G=(V,E)。其中，V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。有向图。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括号括起一对顶点表示。无向图。如果图中每条边都是

22、顶点的无序对，则称此图为无向图。无向边用圆括号括起的两个相关顶点来表示。第62页，共100页，2022年，5月20日，3点39分，星期四图G1的顶点集合为： V(G1)=V1,V2,V3,V4边集合为：E(G1)=(V1,V2),(V1,V3),(V1,V4),(V2,V4),(V3,V4)第63页，共100页，2022年，5月20日，3点39分，星期四图G2的顶点集合为： V(G2)=V1,V2,V3边集合为：E(G2)=,第64页，共100页，2022年，5月20日，3点39分，星期四 2、图的有关术语 邻接：在无向图中，若边(x,y)E， 则x、y互为邻接点；在有向图中，若弧E，则y是x

23、的邻接点。度：VxVyx、y互为邻接点VxVyy是x的邻接点第65页，共100页，2022年，5月20日，3点39分，星期四 度：无向图中:顶点的度是连接该顶点的边的条数。例如，G1中V2的度为3，V4的度为1。有向图中 :入度:以某顶点为弧头的弧的数目 G2中顶点1的入度为1。出度:以某顶点为弧尾的弧的数目。顶点1的出度为2。顶点的度=入度+出度。顶点1的度=2+1=3。213 G24oooov1v2v3v4 G1第66页，共100页，2022年，5月20日，3点39分，星期四子图有两个图G=(V, E)和图G=(V, E), 若V V且EE, 则称图G为G的子图。第67页，共100页，20

24、22年，5月20日，3点39分，星期四路径图中从顶点Vx到顶点Vy的顶点序列称为从Vx到Vy的路径,路径可能是不唯一的。例如:G1中V1到V3的路径为:(V1V2V3)或(V1V3);G2中，1到4的路径为。oooov1v2v3v4G1213 G24第68页，共100页，2022年，5月20日，3点39分，星期四路径的长度路径上边或弧的数目。 例如，G1中V1到V3的长度为1或2； G2中1到4的长度为2。oooov1v2v3v4G1213 G24第69页，共100页，2022年，5月20日，3点39分，星期四连通图 在无向图G中，若从顶点V到顶点V有路径，则称V和V是连通的。 无向图中任意两

25、个顶点都连通，则称G是连通图。第70页，共100页，2022年，5月20日，3点39分，星期四强连通图有向图每对顶点之间都存在路径第71页，共100页，2022年，5月20日，3点39分，星期四完全无向图若一个具有n个顶点的无向图共有n(n-1)/2条边，即每一对顶点之间都有边相连，则称其为完全无向图完全有向图若一个具有n个顶点的无向图共有n(n-1)条边，即每一对顶点之间都有两条方向不同的边相连，则称其为完全有向图第72页，共100页，2022年，5月20日，3点39分，星期四网： 边或弧上带有权值的图权值是与边或弧有关的书，可以表示从一个顶点到另一定点的距离或耗费等。第73页，共100页，

26、2022年，5月20日，3点39分，星期四3.3.3 图的存储结构 图的结构比较复杂，存储的方法也很多，需要根据具体的图形和将来所要做的运算选取适当的存储结构。这里只讨论两种最常用的表示方法：邻接矩阵表示法和邻接表表示法。 第74页，共100页，2022年，5月20日，3点39分，星期四 1、顺序存储结构 邻接矩阵：可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集合E)。这个二维数组称之为邻接矩阵。邻接矩阵是表示顶点之间的邻接关系的矩阵。设G =(V，E)是有n(n1)个顶点的图，则G的邻接矩阵A是一个具有下列性质的nn阶矩阵第75页，共100

27、页，2022年，5月20日，3点39分，星期四无向图邻接矩阵定义:设图G=(V,E)是有n(n1)个顶点的图，则G的邻接矩阵是具有下述性质的对称阵： 1 (Vi，Vj） E Aij=Aji = 0 (Vi，Vj） E G1的邻接矩阵为：oooov1v3v4G1A=G.edge = 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 4x4G.nodes = 1234第76页，共100页，2022年，5月20日，3点39分，星期四有向图邻接矩阵定义:设图G=（V，E）是有n（n 1）个顶点的图，则G的邻接矩阵是具有下述性质的nxn的方阵： 1 Vi，Vj E Aij = 0 Vi，V

28、j E 例如，G2的邻接矩阵为：G.nodes= 1234A= G.Arc= 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 04x41324 G2第77页，共100页，2022年，5月20日，3点39分，星期四 借助于邻接矩阵，可以很容易地求出图中顶点的度。从上例可以很容易看出，邻接矩阵有如下结论： (1) 无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。对无向图可考虑只存下三角(或上三角)元素。 (2) 对于无向图，邻接矩阵第i行(或第i列)的元素之和是顶点Vi的度。 (3) 对于有向图，邻接矩阵第i行元素之和为顶点Vi的出度；第i列的元素之和为顶点Vi的入度。第78页

29、，共100页，2022年，5月20日，3点39分，星期四 2、链式存储结构 图的链式存储结构是通过为每一个顶点建立一个相应的单链表来实现的，这种存储结构被称为邻接链表。 邻接链表是一种顺序分配和链式分配相结合的存储结构。它包括两个部分：一部分是链表；另一部分是向量。第79页，共100页，2022年，5月20日，3点39分，星期四在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点Vi的所有邻接顶点。每个结点由三个域组成：adjvex、data和nextarc，如下图所示。第80页，共100页，2022年，5月20日，3点39分，星期四 为便于邻接表操作，在每个单链表上附设一

30、个头结点，在头结点中有两个域：vexdata和firstarc。如下图所示。第81页，共100页，2022年，5月20日，3点39分，星期四第82页，共100页，2022年，5月20日，3点39分，星期四图的邻接链表数据类型定义如下：struct adjnode int adjv; struct adjnode *next; struct vernode char ver; struct adjnode *first; adjlistN+1;第83页，共100页，2022年，5月20日，3点39分，星期四有向图建立邻接链表的算法struct vernode gN+1 void creatadj

31、list() int i, j, k; adjnode *s; for(i=1;i=N;i+) gi.ver=getchar(); gi.first=NULL; for(k=1;kadjv=j; s-next=gi.first; gi.first=s; 第84页，共100页，2022年，5月20日，3点39分，星期四 对一个图来说，邻接链表不是惟一的，它取决于建立邻接链表时，结点在每个单链表中的插入策略。另外，对于有向图，其邻接链表中第i个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第i个单链表的结点个数就是此结点的度。第85页，共100页，2022年，5月20日，3点39分，星期

32、四3.3.4 图 的 遍 历图的遍历(traversing graph)是指从图中某一顶点出发，沿着一定的搜索路径，对图中各个顶点进行访问，使每个顶点都被访问且仅被访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。第86页，共100页，2022年，5月20日，3点39分，星期四 然而，图的遍历要比树的遍历复杂得多，因为图中任一顶点都可能和其余的顶点相邻接，所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，设一个辅助数组visitedn，它的初值为“假”或者零，一旦访问了顶

33、点Vi，便置visitedi为“真”或者为被访问时的次序号。 通常有两种遍历图的方法，深度优先搜索和广度优先搜索。 第87页，共100页，2022年，5月20日，3点39分，星期四 1深度优先搜索 图的深度优先搜索遍历(depth-first search)类似于树的先序遍历，是树的先序遍历的推广。 特点：遍历时尽可能向纵深的方向搜索。步骤（从Vi出发） 1) 访问Vi，并将其对应的访问标志为visitedi置为1；2) 搜索出Vi的一个未访问过的邻接点Vj。3) 从Vj出发，按以上步骤继续进行深度优先搜索，直到所有顶点均访问完毕。第88页，共100页，2022年，5月20日，3点39分，星期

34、四 显然，这个遍历过程是个递归过程。在设计具体算法时，首先要确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。 例 连通图G6的邻接表表示如下图所示，以顶点V1为始点，按深度优先搜索遍历图中所有顶点，写出顶点的遍历序列。第89页，共100页，2022年，5月20日，3点39分，星期四 解：先访问V1，再访问与V1邻接的V2，再访问V2的第一个邻接点，因V1已被访问过，则访问V2的下一个邻接点V4，然后依次访问V8，V5。这时，与V5相邻接的顶点均已被访问，于是反向回到V8去访问与V8相邻接且尚未被访问的V6，接着访问V3，V7，至此，全部顶点均被访问。相应的访问序列为：V1V2V4V8V5V6V3V7。第90页，共100页，2022年，5月20日，3点39分，星期四深度优先搜索的递归算法（邻接矩阵存储结构）#define NULL 0 int gN+1N+1; char verN+1; int visitedN+1; void dfsm(i) int i; int j; printf(“%c”,veri); visitedi=1; for(j=1;jadjv) dfsa(p-adjv); p=p-next; 深度优先搜索的递归算法（邻接链表存储结构）第92页，共100页，2022年，5月20日，3点3