第1章数据结构1.3ppt课件

1、 数 据 库 原 理 与 应 用第第1章章 数据构造数据构造1.1 数据构造的根本概念数据构造的根本概念1.2 线性构造线性构造1.3 非线性构造非线性构造1.4 查找与排序查找与排序 计 算 机 软 件 技 术 基 础1.3.1 1.3.1 树树1.3.2 1.3.2 图图1.3 1.3 非线性构造非线性构造逻逻辑辑构构造造 计 算 机 软 件 技 术 基 础1.3.1 1.3.1 树与二叉树树与二叉树1.3.1.1 树的根本概念树的根本概念1.3.1.2 二叉树及其根本性质二叉树及其根本性质1.3.1.3 二叉树的存储构造二叉树的存储构造1.3.1.4 二叉树的遍历二叉树的遍历1.3.1.

2、5 二叉排序树二叉排序树1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换1.3.1.7 二叉树运用举例二叉树运用举例 计 算 机 软 件 技 术 基 础父结点：每一个结点只需一个前件，称为父父结点：每一个结点只需一个前件，称为父结点。结点。子结点：每一个结点可以有多个后件，都称子结点：每一个结点可以有多个后件，都称为该结点的子结点。为该结点的子结点。根结点：没有前件的结点只需一个，称为树根结点：没有前件的结点只需一个，称为树的根结点。的根结点。叶子结点：没有后件的结点称为叶子结点。叶子结点：没有后件的结点称为叶子结点。1.3.1.1 1.3.1.1 树的根本概念树的根本概念 计 算

3、 机 软 件 技 术 基 础 结点的度：一个结点所拥有的后件结点的度：一个结点所拥有的后件 个数称为该结点的度。个数称为该结点的度。度度 树的度：一切结点中的最大度称为树的度：一切结点中的最大度称为树的度。树的度。树的深度：树的最大层次称为树的深度。树的深度：树的最大层次称为树的深度。子树子树: :在树中，以某结点的一个子结点为在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。根构成的树称为该结点的一棵子树。1.3.1.1 1.3.1.1 树的根本概念树的根本概念 计 算 机 软 件 技 术 基 础 父父结结点、根点、根结结点、子点、子结结点、叶子点、叶子结结点、点、结结点的度、点

4、的度、树树的度、的度、树树的深度的深度1.3.1.1 1.3.1.1 树的根本概念树的根本概念 计 算 机 软 件 技 术 基 础1.3.1.1 1.3.1.1 树的根本概念树的根本概念 计 算 机 软 件 技 术 基 础1.3.1.1 1.3.1.1 树的根本概念树的根本概念 计 算 机 软 件 技 术 基 础树链表中的结点构造树链表中的结点构造1.3.1.1 1.3.1.1 树的根本概念树的根本概念 计 算 机 软 件 技 术 基 础1.3.1 1.3.1 树与二叉树树与二叉树1.3.1.1 树的根本概念树的根本概念1.3.1.2 二叉树及其根本性质二叉树及其根本性质1.3.1.3 二叉树

5、的存储构造二叉树的存储构造1.3.1.4 二叉树的遍历二叉树的遍历1.3.1.5 二叉排序树二叉排序树1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换1.3.1.7 二叉树运用举例二叉树运用举例 计 算 机 软 件 技 术 基 础1.1.什么是二叉树什么是二叉树 (1) (1)非空二叉树只需一个根结点；非空二叉树只需一个根结点； (2) (2)每一个结点最多有两棵子树，且分别称为每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。该结点的左子树与右子树。1.3.1.2 1.3.1.2 二叉树及其根本性质二叉树及其根本性质 计 算 机 软 件 技 术 基 础例例 画出具有画出

6、具有3 3个结点的树和二叉树的一切不同形状。个结点的树和二叉树的一切不同形状。解：解：(1) (1) 具有具有3 3个结点的树有个结点的树有2 2种不同的形状，种不同的形状，(a)(b)1.3.1.2 1.3.1.2 二叉树及其根本性质二叉树及其根本性质 计 算 机 软 件 技 术 基 础例例 画出具有画出具有3 3个结点的树和二叉树的一切不同形状。个结点的树和二叉树的一切不同形状。解：解：(2) (2) 具有具有3 3个结点的二叉树有个结点的二叉树有5 5种不同的形状，种不同的形状，(a)(b)(c)(d)(e) 树和二叉树的区别主要是二叉树的结点的子树和二叉树的区别主要是二叉树的结点的子树

7、要区分左子树和右子树。即使在结点只需一个树要区分左子树和右子树。即使在结点只需一个子树的情况下，也要明确指出该子树是左子树还子树的情况下，也要明确指出该子树是左子树还是右子树。是右子树。1.3.1.2 1.3.1.2 二叉树及其根本性质二叉树及其根本性质 计 算 机 软 件 技 术 基 础2.2.二叉树的根本性质二叉树的根本性质性质性质1 1 在二叉树的第在二叉树的第k k层上，最多有层上，最多有2k2k1(k1)1(k1)个个 结点。结点。性质性质2 2 深度为深度为m m的二叉树最多有的二叉树最多有2m2m1 1个结点。个结点。性质性质3 3 在恣意一棵二叉树中，度为在恣意一棵二叉树中，度

8、为0 0的结点的结点 即叶子结点总是比度为即叶子结点总是比度为2 2的结点多一个。的结点多一个。性质性质4 4 具有具有n n个结点的二叉树，其深度至少为个结点的二叉树，其深度至少为 log2n log2n1 1 其中其中log2nlog2n表示取表示取log2nlog2n的整数部分。的整数部分。1.3.1.2 1.3.1.2 二叉树及其根本性质二叉树及其根本性质 计 算 机 软 件 技 术 基 础3.3.满二叉树与完全二叉树满二叉树与完全二叉树满二叉树满二叉树除了最后一层外，每一层上的一切结点都有两个除了最后一层外，每一层上的一切结点都有两个子结点。子结点。1.3.1.2 1.3.1.2 二

9、叉树及其根本性质二叉树及其根本性质 计 算 机 软 件 技 术 基 础(2)(2)完全二叉树完全二叉树除了最后一层外，每一层上的结点数均到达最除了最后一层外，每一层上的结点数均到达最大值；在最后一层上只短少右边的假设干结点大值；在最后一层上只短少右边的假设干结点。1.3.1.2 1.3.1.2 二叉树及其根本性质二叉树及其根本性质 计 算 机 软 件 技 术 基 础1.3.1.2 1.3.1.2 二叉树及其根本性质二叉树及其根本性质 计 算 机 软 件 技 术 基 础性质性质5 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n1。性质性质6 设完全二叉树共有设完全二叉树

10、共有n个结点。假设从根结点开场，按个结点。假设从根结点开场，按层序每一层从左到右用自然数层序每一层从左到右用自然数1，2，n给结给结点进展编号，那么对于编号为点进展编号，那么对于编号为k(k1，2，n)的的结点有以下结论：结点有以下结论： (1)假设假设k1，那么该结点为根结点，它没有父结点；，那么该结点为根结点，它没有父结点； 假设假设k1，那么该结点的父结点编号为，那么该结点的父结点编号为INT(k/2)。1.3.1.2 1.3.1.2 二叉树及其根本性质二叉树及其根本性质1 12 23 34 45 56 67 78 89 9101012121111 计 算 机 软 件 技 术 基 础 (

11、2)假设假设2kn，那么编号为，那么编号为k的结点的左子结点编号为的结点的左子结点编号为2k； 否那么该结点无左子结点显然也没有右子结点。否那么该结点无左子结点显然也没有右子结点。(3)假设假设2k1n，那么编号为，那么编号为k的结点的右子结点编号的结点的右子结点编号 为为2k1；否那么该结点无右子结点。；否那么该结点无右子结点。1 12 23 34 45 56 67 78 89 91010111112121.3.1.2 1.3.1.2 二叉树及其根本性质二叉树及其根本性质 计 算 机 软 件 技 术 基 础1.3.1 1.3.1 树与二叉树树与二叉树1.3.1.1 树的根本概念树的根本概念1

12、.3.1.2 二叉树及其根本性质二叉树及其根本性质1.3.1.3 二叉树的存储构造二叉树的存储构造1.3.1.4 二叉树的遍历二叉树的遍历1.3.1.5 二叉排序树二叉排序树1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换1.3.1.7 二叉树运用举例二叉树运用举例 计 算 机 软 件 技 术 基 础1.1.二叉链表二叉链表 #include stdlib.h #include stdlib.h struct btnode / struct btnode /* *定义结点类定义结点类型型* */ / ET d ET d； / /* *数据域数据域* */ / struct btno

13、de struct btnode * *lchildlchild； / /* *左指针域左指针域* */ / struct btnode struct btnode * *rchildrchild； / /* *右指针域右指针域* */ / ；1.3.1.3 1.3.1.3 二叉树的存储构造二叉树的存储构造 计 算 机 软 件 技 术 基 础1.3.1.3 1.3.1.3 二叉树的存储构造二叉树的存储构造 计 算 机 软 件 技 术 基 础1.3.1.3 1.3.1.3 二叉树的存储构造二叉树的存储构造 计 算 机 软 件 技 术 基 础2.2.二叉链表的生成二叉链表的生成(1)(1)输入根结

14、点值；输入根结点值；(2)(2)假设左子树不空，那么输入左子树，否那么输假设左子树不空，那么输入左子树，否那么输入一个终了符；入一个终了符；(3)(3)假设右子树不空，那么输入右子树，否那么输假设右子树不空，那么输入右子树，否那么输入一个终了符。入一个终了符。 1.3.1.3 1.3.1.3 二叉树的存储构造二叉树的存储构造 计 算 机 软 件 技 术 基 础例如，例如，F F A AD DB BE EGHGHP P其中其中表示终了符表示终了符C C1.3.1.3 1.3.1.3 二叉树的存储构造二叉树的存储构造 计 算 机 软 件 技 术 基 础二叉二叉链链表的生成表的生成#include

15、stdio.h#include stdio.h#include stdlib.h#include stdlib.hstruct btnodestruct btnode int d int d； struct btnode struct btnode * *lchildlchild； struct btnode struct btnode * *rchildrchild； ；struct btnode struct btnode * *creatbt(btcreatbt(bt，k)k)struct btnode struct btnode * *btbt；int kint k； int b in

16、t b； struct btnode struct btnode * *p p， * *t t； printf(input b printf(input b ：)； scanf(%d scanf(%d，&b)&b)；1.3.1.3 1.3.1.3 二叉树的存储构造二叉树的存储构造 计 算 机 软 件 技 术 基 础 if (b! if (b!0) /0) /* *输入的不是终了符输入的不是终了符* */ / p p(struct btnode (struct btnode * *)malloc(sizeof()malloc(sizeof(struct btnode)struct

17、 btnode)； p pddb b； p plchildlchildNULLNULL； p p rchildrchildNULLNULL； if (k if (k0) t0) tp p；/ /* *假设是第假设是第1 1个值个值，那么置二叉链表头指针，那么置二叉链表头指针* */ / if (k if (k1) bt1) btlchildlchildp p； / /* *链链接到左子树接到左子树* */ / if (k if (k2) bt2) btrchildrchildp p； / /* *链链接到右子树接到右子树* */ / creatbt(p creatbt(p，1)1)； / /*

18、 *输入左子结点输入左子结点值值* */ / creatbt(p creatbt(p，2)2)； / /* *输入右子结点输入右子结点值值* */ / return(t)/ return(t)/* *前往二叉链表头指针前往二叉链表头指针* */ / 1.3.1.3 1.3.1.3 二叉树的存储构造二叉树的存储构造 计 算 机 软 件 技 术 基 础1.3.1 1.3.1 树与二叉树树与二叉树1.3.1.1 树的根本概念树的根本概念1.3.1.2 二叉树及其根本性质二叉树及其根本性质1.3.1.3 二叉树的存储构造二叉树的存储构造1.3.1.4 二叉树的遍历二叉树的遍历1.3.1.5 二叉排序树

19、二叉排序树1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换1.3.1.7 二叉树运用举例二叉树运用举例 计 算 机 软 件 技 术 基 础 二叉树的遍历是要确定访问各结点二叉树的遍历是要确定访问各结点的顺序的顺序, ,以便不重不漏地访问到二叉树的以便不重不漏地访问到二叉树的一切结点。实践就是将二叉树这种非线一切结点。实践就是将二叉树这种非线性构造按某种需求转化为线性序列，以性构造按某种需求转化为线性序列，以便以后在对二叉树进展某种处置时直接便以后在对二叉树进展某种处置时直接运用。运用。1.3.1.4 1.3.1.4 二叉树的遍历二叉树的遍历 计 算 机 软 件 技 术 基 础FCA

20、DBEGHP1.3.1.4 1.3.1.4 二叉树的遍历二叉树的遍历1.1.前序遍历前序遍历(DLR)(DLR)假设二叉树为空，那么终了前假设二叉树为空，那么终了前往。往。否那么：否那么：(1)(1)访问根结点；访问根结点；(2)(2)前序遍历左子树；前序遍历左子树；(3)(3)前序遍历右子树。前序遍历右子树。 计 算 机 软 件 技 术 基 础1.3.1.4 1.3.1.4 二叉树的遍历二叉树的遍历 计 算 机 软 件 技 术 基 础#include stdio.h#include stdio.hstruct btnodestruct btnode int d int d；struct bt

21、node struct btnode * *lchildlchild；struct btnode struct btnode * *rchildrchild； ；pretrav(bt)pretrav(bt)struc btnode struc btnode * *btbt； if (bt ! if (bt !NULL) NULL) printf(%dn printf(%dn，btbtd)d)； pretrav(bt pretrav(btlchild)lchild)； pretrav(bt pretrav(btrchild)rchild)； return return； 1.3.1.4 1.3.

22、1.4 二叉树的遍历二叉树的遍历 计 算 机 软 件 技 术 基 础ACBDFE HGP2.2.中序遍历中序遍历(LDR)(LDR)假设二叉树为空，那么终了前假设二叉树为空，那么终了前往。往。否那么：否那么：(1)(1)中序遍历左子树；中序遍历左子树；(2)(2)访问根结点；访问根结点；(3)(3)中序遍历右子树。中序遍历右子树。1.3.1.4 1.3.1.4 二叉树的遍历二叉树的遍历 计 算 机 软 件 技 术 基 础1.3.1.4 1.3.1.4 二叉树的遍历二叉树的遍历 计 算 机 软 件 技 术 基 础#include stdio.h#include stdio.hstruct btn

23、odestruct btnode int d int d；struct btnode struct btnode * *lchildlchild；struct btnode struct btnode * *rchildrchild； ；intrav(bt)intrav(bt)struc btnode struc btnode * *btbt； if (bt ! if (bt !NULL) NULL) intrav(bt intrav(btlchild)lchild)； printf(%dn printf(%dn，btbtd)d)； intrav(bt intrav(btrchild)rchi

24、ld)； return return； 1.3.1.4 1.3.1.4 二叉树的遍历二叉树的遍历 计 算 机 软 件 技 术 基 础ACBDFEH GP3.3.后序遍历后序遍历(LRD)(LRD)假设二叉树为空，那么终了前假设二叉树为空，那么终了前往。往。否那么：否那么：(1)(1)后序遍历左子树；后序遍历左子树；(2)(2)后序遍历左子树；后序遍历左子树；(3)(3)访问根结点。访问根结点。1.3.1.4 1.3.1.4 二叉树的遍历二叉树的遍历 计 算 机 软 件 技 术 基 础1.3.1.4 1.3.1.4 二叉树的遍历二叉树的遍历 计 算 机 软 件 技 术 基 础#include s

25、tdio.h#include stdio.hstruct btnodestruct btnode int d int d；struct btnode struct btnode * *lchildlchild；struct btnode struct btnode * *rchildrchild； ；postrav(bt)postrav(bt)struc btnode struc btnode * *btbt； if (bt ! if (bt !NULL) NULL) postrav(bt postrav(btlchild)lchild)； postrav(bt postrav(btrchil

26、d)rchild)； printf(%dn printf(%dn，btbtd)d)； return return； 1.3.1.4 1.3.1.4 二叉树的遍历二叉树的遍历 计 算 机 软 件 技 术 基 础1.3.1 1.3.1 树与二叉树树与二叉树1.3.1.1 树的根本概念树的根本概念1.3.1.2 二叉树及其根本性质二叉树及其根本性质1.3.1.3 二叉树的存储构造二叉树的存储构造1.3.1.4 二叉树的遍历二叉树的遍历1.3.1.5 二叉排序树二叉排序树1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换1.3.1.7 二叉树运用举例二叉树运用举例 计 算 机 软 件 技 术

27、 基 础二叉排序树及其构造二叉排序树及其构造(1)左子树上的一切结点值均小于根结点左子树上的一切结点值均小于根结点值；值；(2)右子树上的一切结点值均不小于根结右子树上的一切结点值均不小于根结点值；点值；(3)左、右子树也满足上述两个条件。左、右子树也满足上述两个条件。1.3.1.5 1.3.1.5 二叉排序树二叉排序树 计 算 机 软 件 技 术 基 础1.3.1.5 1.3.1.5 二叉排序树二叉排序树 计 算 机 软 件 技 术 基 础1.3.1.5 1.3.1.5 二叉排序树二叉排序树 计 算 机 软 件 技 术 基 础依次读入给定序列中的每一个元素：依次读入给定序列中的每一个元素：(

28、1)假设当前的二叉排序树为空，那么读入的元假设当前的二叉排序树为空，那么读入的元素为根结点；素为根结点；(2)假设读入的元素值小于根结点值，那么将元假设读入的元素值小于根结点值，那么将元素插入到左子树中；素插入到左子树中；(3)假设读入的元素值不小于根结点值，那么将假设读入的元素值不小于根结点值，那么将元素插入到右子树中。元素插入到右子树中。 无论是插入到左子树还是右子树，同样无论是插入到左子树还是右子树，同样按照上述方法处置。按照上述方法处置。1.3.1.5 1.3.1.5 二叉排序树二叉排序树 计 算 机 软 件 技 术 基 础1.3.1.5 1.3.1.5 二叉排序树二叉排序树 计 算

29、机 软 件 技 术 基 础1.3.1.5 1.3.1.5 二叉排序树二叉排序树 计 算 机 软 件 技 术 基 础1.3.1.5 1.3.1.5 二叉排序树二叉排序树 计 算 机 软 件 技 术 基 础1.3.1.5 1.3.1.5 二叉排序树二叉排序树 计 算 机 软 件 技 术 基 础二叉排序树的查找：二叉排序树的查找：从根结点开场与被查值进展比较：从根结点开场与被查值进展比较：(1)假设被查值等于根结点值，查找胜利。假设被查值等于根结点值，查找胜利。(2)假设被查值小于根结点值，那么查找左子树。假设被查值小于根结点值，那么查找左子树。(3)假设被查值大于根结点值，那么查找右子树。假设被查

30、值大于根结点值，那么查找右子树。 在左、右子树中查找时也采用上述方法。在左、右子树中查找时也采用上述方法。 查找过程直到查找胜利或所思索的子树已空查找过程直到查找胜利或所思索的子树已空为止。为止。1.3.1.5 1.3.1.5 二叉排序树二叉排序树 计 算 机 软 件 技 术 基 础1.3.1 1.3.1 树与二叉树树与二叉树1.3.1.1 树的根本概念树的根本概念1.3.1.2 二叉树及其根本性质二叉树及其根本性质1.3.1.3 二叉树的存储构造二叉树的存储构造1.3.1.4 二叉树的遍历二叉树的遍历1.3.1.5 二叉排序树二叉排序树1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的

31、转换1.3.1.7 二叉树运用举例二叉树运用举例 计 算 机 软 件 技 术 基 础1.3.1.6 1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换树与二叉树的对应关系树与二叉树的对应关系树与二叉树均可用二叉链表作为存树与二叉树均可用二叉链表作为存储构造，因此给定一棵树，用二叉链表储构造，因此给定一棵树，用二叉链表存储，可独一对应一棵二叉树，反之亦存储，可独一对应一棵二叉树，反之亦然。然。 计 算 机 软 件 技 术 基 础树变为二叉树的方法：树变为二叉树的方法：衔接亲兄弟不包括堂兄弟衔接亲兄弟不包括堂兄弟保管长子断绝父亲与其他孩子关保管长子断绝父亲与其他孩子关系系顺时针旋转顺时针

32、旋转4545度度 特点：根无右子树特点：根无右子树1.3.1.6 1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换 计 算 机 软 件 技 术 基 础如图：如图： F=T1 ，T2， T3DBCABT1FEBT2BCFEJHADIGT1T3T2BT3HJIG1.3.1.6 1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换 计 算 机 软 件 技 术 基 础森林转换为二叉树的方法森林转换为二叉树的方法 将森林将森林 F=T1 F=T1，T2 . TmT2 . Tm的各棵树的各棵树分别转成二叉树分别转成二叉树BT1BT1，BT2 . BTm BT2 . BTm 将将BTi+

33、1BTi+1作为作为BTiBTi根结点的右子树根结点的右子树i=1,2,.,m-1i=1,2,.,m-1, ,得到一棵得到一棵BTBT。1.3.1.6 1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换 计 算 机 软 件 技 术 基 础如图：如图： F=T1 ，T2， T3DBCABT1FEBT2BT3HJIGJIFEBDAHGC1.3.1.6 1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换 计 算 机 软 件 技 术 基 础二叉树转换森林的方法二叉树转换森林的方法 将当前根结点和其左子树作为森林的一棵将当前根结点和其左子树作为森林的一棵树树,并将其右子树作为森林的其

34、他子树；并将其右子树作为森林的其他子树； 反复上面直到某结点的右子树为空。反复上面直到某结点的右子树为空。JIHGFEBCDAT1BCDAFET2T3JIHG1.3.1.6 1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换 计 算 机 软 件 技 术 基 础1.3.1 1.3.1 树与二叉树树与二叉树1.3.1.1 树的根本概念树的根本概念1.3.1.2 二叉树及其根本性质二叉树及其根本性质1.3.1.3 二叉树的存储构造二叉树的存储构造1.3.1.4 二叉树的遍历二叉树的遍历1.3.1.5 二叉排序树二叉排序树1.3.1.6 树、森林与二叉树的转换树、森林与二叉树的转换1.3.1

35、.7 二叉树运用举例二叉树运用举例 计 算 机 软 件 技 术 基 础1.3.1 1.3.1 树树1.3.2 1.3.2 图图1.3 1.3 非线性构造非线性构造逻逻辑辑构构造造 计 算 机 软 件 技 术 基 础1.3.2.1 1.3.2.1 图的根本概念图的根本概念1.3.2.2 1.3.2.2 图的存储构造图的存储构造1.3.2.3 1.3.2.3 图的遍历图的遍历1.3.2 1.3.2 图图 计 算 机 软 件 技 术 基 础1.图的概念：假设数据元素集合图的概念：假设数据元素集合D中的各元素间中的各元素间存在恣意前后件关系，那么此数据构造称为图存在恣意前后件关系，那么此数据构造称为图

36、。2.在具有在具有n个结点的无向图中，边的最大数目为个结点的无向图中，边的最大数目为n (n-1)/2。3.结点的后件个数称为该结点的出度结点的后件个数称为该结点的出度,前件个数前件个数称为该结点的入度。入度与出度之和称为该结称为该结点的入度。入度与出度之和称为该结点的度。点的度。4.实践运用中实践运用中,假设图中恣意两结点假设图中恣意两结点a与与b间规定间规定了一个值了一个值f(a,b)，那么称该图为有值图。，那么称该图为有值图。1.3.2.1 1.3.2.1 图的根本概念图的根本概念 计 算 机 软 件 技 术 基 础1.3.2.1 1.3.2.1 图的根本概念图的根本概念 计 算 机 软

37、 件 技 术 基 础1.3.2.1 1.3.2.1 图的根本概念图的根本概念 计 算 机 软 件 技 术 基 础1.3.2.2 1.3.2.2 图的存储构造图的存储构造1.1.关联矩阵关联矩阵 长度为长度为n n的一维数组的一维数组D(1D(1：n)n)存放存放图中各数据结点的信息。图中各数据结点的信息。 n n阶的二维数组阶的二维数组R(1R(1：n n，1 1：n)n)存存放图中各结点的关联信息。放图中各结点的关联信息。 其中二维数组其中二维数组R R称为图的关联矩阵称为图的关联矩阵。在关联矩阵。在关联矩阵R R中，每一个元素中，每一个元素R(iR(i，j) j) (1in(1in，1jn

38、)1jn)的定义为的定义为1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础1.3.2.2 1.3.2.2 图的存储构造图的存储构造1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础2.2.求值矩阵求值矩阵1.3.2.2 1.3.2.2 图

39、的存储构造图的存储构造 计 算 机 软 件 技 术 基 础1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础3.3.邻接表邻接表“顺序索引链接存储构造顺序索引链接存储构造1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础struct node /struct node /* *单链表中结点构造单链表中结点构造* */ / int num int num；/ /* *图中结点编号图中结点编号* */ / ET1 val E

40、T1 val；/ /* *求值函数求值函数* */ / struct node struct node * *nextnext；/ /* *指针域指针域* */ / ；struct gpnode /struct gpnode /* *顺序存储空间中结点构造顺序存储空间中结点构造* */ / ET data ET data； / /* *结点值结点值* */ / struct node struct node * *linklink；/ /* *指针域指针域* */ / ；1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础1.3.2.2 1.3.2.2

41、图的存储构造图的存储构造图邻接表的构造图邻接表的构造输入：图的结点数输入：图的结点数n n；依次存放图中结点值的数组；依次存放图中结点值的数组D D(1(1：n)n)。输出：邻接表顺序存储空间的首地址。输出：邻接表顺序存储空间的首地址。PROCEDURE CREATGP(DPROCEDURE CREATGP(D，n)n)定义定义DATA(1DATA(1：n)n)，LINK(1LINK(1：n) n) 建立顺序存储空建立顺序存储空间间 FOR kFOR k0 TO n DO 0 TO n DO DATA(k) DATA(k)DkDk； LINK(k) LINK(k)0 0 INPUT m INP

42、UT m，v /v /* *输入图中第输入图中第k k个结点的后件个结点的后件信息信息* */ / WHILE (m WHILE (m0) DO /0) DO /* *输入后件信息未终输入后件信息未终了了* */ / NEW(p) / NEW(p) /* *分配单链表结点分配单链表结点* */ / NUM(p) NUM(p)m m； VAL(p) VAL(p)v v；NEXT(p)NEXT(p)LINLINK(k)K(k)；LINK(k)LINK(k)p p INPUT m INPUT m，v /v /* *继续输入后件信息继续输入后件信息* */ / RETURNRETURN1.3.2.2

43、1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础#include stdio.h #include stdlib.h#include stdio.h #include stdlib.hstruct node /struct node /* *单链表中结点构造单链表中结点构造* */ / int num int num； / /* *图中结点编号图中结点编号* */ / int val int val； / /* *求值函数求值函数* */ / struct node struct node * *nextnext； / /* *指针域指针域* */ / ；struc

44、t gpnode /struct gpnode /* *顺序存储空间中结点构造顺序存储空间中结点构造* */ / char data char data； / /* *结点值结点值* */ / struct node struct node * *linklink； / /* *指针域指针域* */ / ；1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础struct gpnode struct gpnode * *creatgp(dcreatgp(d，n)/n)/* *该函数前往顺序存储空间的首地址该函数前往顺序存储空间的首地址* */ /int n

45、int n；char dchar d； struct gpnode struct gpnode * *headhead； struct node struct node * *p p； int k int k，m m，v v； head head(struct gpnode (struct gpnode * *)malloc(n)malloc(n* *sizeof(struct gpnode)sizeof(struct gpnode)； for (k for (k0 0；k kn n；k k) ) / /* *依次对图中的每一个结点建立链接一切后件的单链表依次对图中的每一个结点建立链接一切后件

46、的单链表* */ / (head (headk)k)datadatadkdk； / /* *置顺序存储空间的结点值置顺序存储空间的结点值* */ / (head (headk)k)linklinkNULLNULL；/ /* *置顺序存储空间结点指针域为空置顺序存储空间结点指针域为空* */ / printf(input linked list of %c :n printf(input linked list of %c :n，dk)dk)； scanf(“%d%d scanf(“%d%d，&m&m，&v)&v)； / /* *输入图中第输入图中第k k个结点的

47、后件信息个结点的后件信息* */ /1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础 while (m while (m0) /0) /* *输入后件信息未终了输入后件信息未终了* */ / p p(struct node (struct node * *)malloc(sizeof(struct node)malloc(sizeof(struct node)； p pnumnumm m； p pvalvalv v；/ /* *后件结点号与求值函数值后件结点号与求值函数值* */ / p pnextnext(head(headk)k)linklink

48、；/ /* *新结点指针指向头结点新结点指针指向头结点* */ / (head (headk)k)linklinkp p； / /* *将新结点链接到单链表链头将新结点链接到单链表链头* */ / scanf(%d%d scanf(%d%d，&m&m，&v)&v)；/ /* *继续输入后件信息继续输入后件信息* */ / return(head) return(head)；/ /* *前往顺序存储空间的首地址前往顺序存储空间的首地址* */ / 1.3.2.2 1.3.2.2 图的存储构造图的存储构造 计 算 机 软 件 技 术 基 础1.1.深度深度( (纵向

49、纵向) )优先搜索法优先搜索法 从图中某一结点作为当前结点，然后进展从图中某一结点作为当前结点，然后进展以下过程：以下过程： (1) (1)处置或输出当前结点，记录当前结点处置或输出当前结点，记录当前结点的查访标志。的查访标志。 (2) (2)假设当前结点有后件结点，那么取第假设当前结点有后件结点，那么取第一个后件结点。假设该后件结点未被查访过一个后件结点。假设该后件结点未被查访过，那么以该后件结点为当前结点用纵向优先，那么以该后件结点为当前结点用纵向优先搜索法进展查访。搜索法进展查访。1.3.2.3 1.3.2.3 图的遍历图的遍历 计 算 机 软 件 技 术 基 础深度优先搜索法遍历图的递

50、归算法深度优先搜索法遍历图的递归算法输入：图中结点数输入：图中结点数n n；邻接表顺序存储空间；邻接表顺序存储空间DATA(1DATA(1：n)n) 与与LINK(1LINK(1：n)n)；单链表的存储空间；单链表的存储空间NUMNUM与与NEXTNEXT。输出：遍历序列。输出：遍历序列。PROCEDURE DFSGP(DATAPROCEDURE DFSGP(DATA，LINKLINK，n n，NUMNUM，NEXT)NEXT)定义标志数组定义标志数组MARK(1MARK(1：n)n)FOR kFOR k1 TO n DO MARK(k)1 TO n DO MARK(k)0 0 标志数组初始化

51、标志数组初始化 k k1 1FOR kFOR k1 TO n DO1 TO n DODFS(DATADFS(DATA，LINKLINK，k k，MARK) MARK) IF MARK(k)IF MARK(k)0 THEN DFS(DATA0 THEN DFS(DATA，LINKLINK，k k，MARK)MARK)RETURNRETURN1.3.2.3 1.3.2.3 图的遍历图的遍历 计 算 机 软 件 技 术 基 础PROCEDURE DFS(DATAPROCEDURE DFS(DATA，LINKLINK，k k，MARKMARK，NUMNUM，NEXT) NEXT) OUTPUT DAT

52、A(k) OUTPUT DATA(k) 处置或输出当前结点值处置或输出当前结点值 MARK(k)MARK(k)1 1 记录当前结点的查访标志记录当前结点的查访标志 p pLINK(k) LINK(k) 当前结点的第一个后件结点当前结点的第一个后件结点 WHILE (p0) DO WHILE (p0) DO 存在后件结点存在后件结点 k kNUM(p) NUM(p) 后件结点的结点编号后件结点的结点编号 IF MARK(k) IF MARK(k)0 THEN 0 THEN 该后件结点未被查访过该后件结点未被查访过 DFS(DATA DFS(DATA，LINKLINK，k k，MARKMARK，N

53、UMNUM，NEXT) NEXT) p pNEXT(p) NEXT(p) 下一个后件结点下一个后件结点 RETURNRETURN1.3.2.3 1.3.2.3 图的遍历图的遍历 计 算 机 软 件 技 术 基 础#include stdlib.h#include stdlib.h#include “stdio.h#include “stdio.hstruct node /struct node /* *单链表中结点构造单链表中结点构造* */ / int num int num； / /* *图中结点编号图中结点编号* */ / int val int val； / /* *求值函数求值函数*

54、 */ / struct node struct node * *nextnext；/ /* *指针域指针域* */ / ；struct gpnode /struct gpnode /* *顺序存储空间中结点构造顺序存储空间中结点构造* */ / char data char data； / /* *结点值结点值* */ / struct node struct node * *linklink； / /* *指针域指针域* */ / ；1.3.2.3 1.3.2.3 图的遍历图的遍历 计 算 机 软 件 技 术 基 础dfsgp(headdfsgp(head，n)n)struct gpnod

55、e struct gpnode * *headhead；int nint n； int k int k，* *markmark； mark markmalloc(nmalloc(n* *sizeof(int)sizeof(int)；/ /* *定义标志数组空间定义标志数组空间* */ / for (k for (k0 0； k kn n； k k) markk) markk0 0；/ /* *标志数组初始化标志数组初始化* */ / k k1 1； / /* * for (k for (k1 1； k kn n； k k) ) * */ / dfs(head dfs(head，k k，mark

56、)mark)； / /* * if (markk if (markk110) dfs(head0) dfs(head，k k，mark)mark)；* */ / printf(n) printf(n)； free(mark) free(mark)； / /* *释放标志数组空空间释放标志数组空空间* */ / return return； 1.3.2.3 1.3.2.3 图的遍历图的遍历 计 算 机 软 件 技 术 基 础static dfs(headstatic dfs(head，k k，mark) /mark) /* *递归函数递归函数* */ /struct gpnode struct

57、gpnode * *headhead；int kint k，* *markmark； struct node struct node * *p p； printf(%c printf(%c，(head(headk k1)1)data)data)；/ /* *输出当前结点值输出当前结点值* */ / markk markk111 1；/ /* *记录当前结点的查访标志记录当前结点的查访标志* */ / p p(head(headk k1)1)linklink； / /* *当前结点的第一个后件结点当前结点的第一个后件结点* */ / while (p! while (p!NULL) /NULL)

58、 /* *还存在后件结点还存在后件结点* */ / if (mark(p if (mark(pnum)num)110) /0) /* *该后件结点未被查访过该后件结点未被查访过* */ / dfs(head dfs(head，p pnumnum，mark)mark)；/ /* *递归调用递归调用* */ / p pp pnextnext；/ /* *下一个后件结点下一个后件结点* */ / return return； 1.3.2.3 1.3.2.3 图的遍历图的遍历 计 算 机 软 件 技 术 基 础深度优先搜索法遍历图的非递归算法深度优先搜索法遍历图的非递归算法输入：图中的结点数输入：图中

59、的结点数n n；邻接表的顺序存储空间；邻接表的顺序存储空间DATADATA(1(1：n)n) 与与LINK(1LINK(1：n)n)；单链表的存储空间；单链表的存储空间NUMNUM与与NEXTNEXT。输出：遍历序列。输出：遍历序列。PROCEDURE DFSGP(DATAPROCEDURE DFSGP(DATA，LINKLINK，n n，NUMNUM，NEXT)NEXT)定义标志数组定义标志数组MARK(1MARK(1：n)n)定义栈顺序存储空间定义栈顺序存储空间S(1S(1：L) LL) L足够大足够大 FOR kFOR k1 TO n DO MARK(k)1 TO n DO MARK(k

60、)0 0 标志数组初标志数组初始化始化 toptop0 0 栈初始化栈初始化 FOR mFOR m1 TO n DO1 TO n DO1.3.2.3 1.3.2.3 图的遍历图的遍历 计 算 机 软 件 技 术 基 础 k km m IF MARK(k) IF MARK(k)0 THEN 0 THEN OUTPUT DATA(k) OUTPUT DATA(k) 处置或输出当前结点值处置或输出当前结点值 MARK(k) MARK(k)1 1 记录当前结点的查访标志记录当前结点的查访标志 PUSH(S PUSH(S，L L，toptop，k)k) p pLINK(k) LINK(k) 当前结点的第一个后件结点当前结点的第一个后件结点 WHILE (p0)or(top0