数据结构部分线性表树图

《数据结构部分线性表树图》由会员分享，可在线阅读，更多相关《数据结构部分线性表树图（56页珍藏版）》请在金锄头文库上搜索。

1、 数据结构数据结构第八章第八章第八章第八章 数据结构数据结构数据结构数据结构v数据结构概要数据结构概要1.数据结构数据结构定义定义：指数据元素的集合及元素之间的关系和构造方法，可以用二元组指数据元素的集合及元素之间的关系和构造方法，可以用二元组表示为：表示为：B=（A，R），其中），其中A是数据元素的非空有限集合，是数据元素的非空有限集合，R是是定义在定义在A上的关系的非空有限集合上的关系的非空有限集合。2.要达到的要达到的目标目标：(1)从问题入手，分析和研究数据结构的特性，选择适当的逻辑结构、从问题入手，分析和研究数据结构的特性，选择适当的逻辑结构、存储结构及相应的操作方法。存储结构及相应

2、的操作方法。(2)并掌握时间复杂度和空间复杂度的概念。并掌握时间复杂度和空间复杂度的概念。3. 按逻辑关系按逻辑关系分类分类线性结构线性结构(包括线性表、栈、队列、数组、串等包括线性表、栈、队列、数组、串等)非线性结构非线性结构(树、图树、图) 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构v一、线性表一、线性表最常见的一种线性结构，有两种存储方法：顺序存储和链式存储最常见的一种线性结构，有两种存储方法：顺序存储和链式存储1、定义定义：N个元素的有限序列，个元素的有限序列，n0，通常表示为（，通常表示为（a1,a2,an）2、特点特点：元素集合中存在唯

3、一称作元素集合中存在唯一称作“第一个第一个”和唯一和唯一“最后一个最后一个”元素，除第元素，除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，序一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，序列中的每个元素只有一个直接后继。列中的每个元素只有一个直接后继。3、存储结构存储结构：顺序存储结构顺序存储结构含义：用一组连续的存储单元存放线性表中的数据元素。含义：用一组连续的存储单元存放线性表中的数据元素。特点：逻辑相邻的元素，物理位置也相邻。特点：逻辑相邻的元素，物理位置也相邻。优点和缺点：存取方便，插入删除操作需要移动大量元素。优点和缺点：存取方便，插入删除操作需要移动大量

4、元素。 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构. 链式存储结构链式存储结构含义：含义： 存储数据元素的同时必须存储元素之间的关系。用节点来存储数据元素，存储数据元素的同时必须存储元素之间的关系。用节点来存储数据元素，节点地址可以连续，也可以不连续。节点地址可以连续，也可以不连续。节点结构：节点结构：节点的插入和删除操作节点的插入和删除操作 插入操作插入操作 删除操作删除操作 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构4.其他几种链表结构其他几种链表结构：双向链表：双向链表： 每个节点包含两个指针，分

5、别指出当前节点元素的直接前驱和直接每个节点包含两个指针，分别指出当前节点元素的直接前驱和直接后继。后继。循环链表：循环链表：静态链表：静态链表： 借助数组来描述线性表的链式存储结构借助数组来描述线性表的链式存储结构 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构v二、栈和队列二、栈和队列1. 栈栈定义定义只能通过它的一端来实现数据存储和检索的只能通过它的一端来实现数据存储和检索的线性结构，也称为后进先出（或先进后出）的线性结构，也称为后进先出（或先进后出）的线性表。线性表。基本运算基本运算初始化栈：初始化栈：InitStack(S)判栈空判栈空: St

6、ackEmpty入栈入栈:Push(S,x)出栈出栈:Pop(S)读栈顶元素读栈顶元素:Top(s)存储结构存储结构顺序存储顺序存储：（顺序栈）指用一组地址连续的存储单元依次存储自栈：（顺序栈）指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。指示栈顶元素的位置。 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构链式存储链式存储（链栈）：为了克服（链栈）：为了克服顺序栈可能存在上溢的不足，采顺序栈可能存在上溢的不足，采用钻链表作为存储结构的栈。用钻链表作为存储结构的栈。栈的应用

7、：表达式求值，括号匹配，递归转非递归。栈的应用：表达式求值，括号匹配，递归转非递归。2. 队列队列定义：是一种先进先出（定义：是一种先进先出（FIFO）的线性表，只允许在表的一端插入元素，）的线性表，只允许在表的一端插入元素，表的另一端删除元素。表的另一端删除元素。基本运算：基本运算： (1)初始化队初始化队 InitQueue(Q) (2)判队空判队空 Empty(Q) (3)入队入队 EnQueue(Q,x) (4)出队出队 DeQueue(Q) (5)读队头元素读队头元素 FrontQue(Q) 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构队列

8、的存储结构队列的存储结构顺序存储（顺序队列）顺序存储（顺序队列） 利用一组地址连续的存储单元存放队列中的元素，同时设置队头指针和队尾利用一组地址连续的存储单元存放队列中的元素，同时设置队头指针和队尾指针，分别表示当前的队首元素和队尾元素。指针，分别表示当前的队首元素和队尾元素。 思考思考:(1)为什么要引入为什么要引入循环队列？循环队列？ (2)什么叫假溢出？如何形成的？什么叫假溢出？如何形成的？链式存储（链队列）链式存储（链队列）队列的应用：队列的应用：常用于需要排队的场合：比如操作系统中处理打印任务，离散事件的计算模常用于需要排队的场合：比如操作系统中处理打印任务，离散事件的计算模拟等。拟

9、等。 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构3 串串 即字符串，是一种特殊的线性表，它的数据元素仅由一个字符组成。即字符串，是一种特殊的线性表，它的数据元素仅由一个字符组成。串的串的定义定义是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为：是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为：S=a1a2an，其中，其中S是串名，单引号括起来的字符序列是串值。是串名，单引号括起来的字符序列是串值。几个相关的几个相关的基本概念基本概念空串：长度为零的串，不包含任何字符。空串：长度为零的串，不包含任何字符。空格串：由一个或多个空格组

10、成的串。空格串：由一个或多个空格组成的串。子子串串：由由串串中中任任意意长长度度的的连连续续字字符符构构成成的的序序列列称称为为子子串串。空空串串是是任任意意串串的的子串。子串。串相等：两个串长度相等，且对应位置上的字符也相同。串相等：两个串长度相等，且对应位置上的字符也相同。串比较：比较大小时，以串比较：比较大小时，以ASCII码值作为依据。码值作为依据。基本操作基本操作赋值赋值strAssign(s,t): 将串将串t赋给串赋给串s连接连接Concat(s,t) : 串串t接续在串接续在串s的尾部，形成一个新串。的尾部，形成一个新串。 数据结构数据结构第一部分：线性结构第一部分：线性结构第

11、一部分：线性结构第一部分：线性结构求串长求串长StrLength(s)串比较串比较StrCompare(s,t) 返回值返回值-1、0、1分别表示分别表示st求子串求子串SubString(s,start,len)串的串的存储结构存储结构静态存储静态存储(即串的顺序存储结构即串的顺序存储结构) 用一组地址连续的存储单元来存储串值的字符序列。（在程序设计语言中可用一组地址连续的存储单元来存储串值的字符序列。（在程序设计语言中可借助字符数组定义串的存储空间）。借助字符数组定义串的存储空间）。链式存储链式存储 用链表存储串中的字符，每个节点中可以存储一个字符，也可以存储多个用链表存储串中的字符，每个

12、节点中可以存储一个字符，也可以存储多个字符，注意存储密度问题字符，注意存储密度问题,因为它直接影响到串和处理效率。因为它直接影响到串和处理效率。串的串的模式匹配模式匹配即子串的定位操作，是各种串处理中最重要的运算之一。有以下两种算法：即子串的定位操作，是各种串处理中最重要的运算之一。有以下两种算法：（1）朴素模式匹配算法）朴素模式匹配算法基本思想：基本思想：P432（2）改进的模式匹配算法）改进的模式匹配算法基本思想：基本思想：P433 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构4 数组、矩阵和广义表数组、矩阵和广义表（1）数组）数组定义定义：线性

13、表的元素又是一个线性表，是定长线性表在维数上的一个扩张。：线性表的元素又是一个线性表，是定长线性表在维数上的一个扩张。特点特点： .数据元素数目固定数据元素数目固定 .数据元素具有相同数据类型数据元素具有相同数据类型 .数据元素的下标关系具有上下界的约束且下标有序数据元素的下标关系具有上下界的约束且下标有序两个两个基本运算基本运算 其一：给定一组下标，存取相应的数据元素；其一：给定一组下标，存取相应的数据元素； 其二：给定一组下标，修改相应的数据元素中某个数据项的值。其二：给定一组下标，修改相应的数据元素中某个数据项的值。存储结构存储结构由于数组一般不作插入和删除运算，所以数组中数据元素个数和

14、元素之间的由于数组一般不作插入和删除运算，所以数组中数据元素个数和元素之间的关系固定不变，因此适合采用顺序存储结构。关系固定不变，因此适合采用顺序存储结构。 .二维数组的存储方式有两种：二维数组的存储方式有两种： 行优先：行优先： 列优先：列优先： 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构（2）矩阵）矩阵在数据结构中，我们研究的是如何存储矩阵中的元素。在数据结构中，我们研究的是如何存储矩阵中的元素。特殊矩阵特殊矩阵 指矩阵中的元素分布有一定的规律的矩阵。例如：对称矩阵、三角矩阵、对指矩阵中的元素分布有一定的规律的矩阵。例如：对称矩阵、三角矩阵、对

15、 角矩阵。角矩阵。 存储时，可以将其压缩存储在一维数组中，并建立起每个非零元素在矩阵中的位置与其存储时，可以将其压缩存储在一维数组中，并建立起每个非零元素在矩阵中的位置与其一维护数组中的位置之间的对应关系。一维护数组中的位置之间的对应关系。稀疏矩阵稀疏矩阵非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律。非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律。 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构5 广义表广义表定义定义 是线性表的推广一，由零个或多个单元素或子表所组成的有限序列。一般记为：是线性表的推广一，由零个或多个单元

16、素或子表所组成的有限序列。一般记为：LS=（a1,a2,an）其中）其中ai(1=i=0）个节点的有限集合，当）个节点的有限集合，当n=0时，称为空树，在任一非空树中：时，称为空树，在任一非空树中： （1）有且仅有一个称为根的节点；）有且仅有一个称为根的节点； （2）其余节点可分为）其余节点可分为m (m=0) 个互不相交的有限集个互不相交的有限集T1、T2、 、Tm,其中其中Ti又都是一棵树，又都是一棵树， 并且乐为根节点的子树。并且乐为根节点的子树。 （递归定义）（递归定义）2、树的基本概念、树的基本概念 与树相关的概念有：与树相关的概念有： 双亲、孩子、兄弟双亲、孩子、兄弟节点的度、叶子

17、节点、节点的层次、树的高度、有序（无序）树节点的度、叶子节点、节点的层次、树的高度、有序（无序）树 3、树的遍历、树的遍历 按照某种次序，获取树中全部节点的信息。按照某种次序，获取树中全部节点的信息。 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（二）二叉树的定义及基本运算、（二）二叉树的定义及基本运算、1、二叉树的定义：、二叉树的定义：二叉树或为空树；空树；或是由一个根结点根结点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。2、二叉树的运算、二叉树的运算 二叉树的基本运算是遍历，其它运算都是建立在遍历的基础之上。二

18、叉树的基本运算是遍历，其它运算都是建立在遍历的基础之上。 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（三）二叉树的性质（共五个性质）（三）二叉树的性质（共五个性质）1、在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点。个结点。 (i1)2、深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k-1 个结点（个结点（k1）3、对任何一棵二叉树，若它含有、对任何一棵二叉树，若它含有n0 个叶子结点、个叶子结点、n2 个度为个度为 2 的结点，的结点，则必存在关系式：则必存在关系式：n0 = n2+1 两类两类特殊特殊的二叉树：的二

19、叉树：满二叉树：满二叉树：指的是深度为指的是深度为k且含有且含有2k-1个结点的二叉树个结点的二叉树。 完全二叉树完全二叉树：树中所含的：树中所含的 n 个结点和满二叉树中编号为个结点和满二叉树中编号为 1 至至n 的结点一的结点一 一对应。一对应。 4、具有具有 n 个结点的完全二叉树的个结点的完全二叉树的深度深度为为 log2n +1 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构5、若对含若对含 n 个结点的完全二叉树从上到下且从左至右进行个结点的完全二叉树从上到下且从左至右进行 1 至至 n 的编的编号，则对完全二叉树中任意一个编号为号，则对

20、完全二叉树中任意一个编号为 i 的结点：的结点：(1) 若若 i=1，则该结点是二叉树的根，无双亲，则该结点是二叉树的根，无双亲, 否则，编号为否则，编号为 i/2 的结的结点为其双亲结点点为其双亲结点; (2) 若若 2in，则该结点无左孩子，则该结点无左孩子， 否则，编号为否则，编号为 2i 的结点为其左孩子结点；的结点为其左孩子结点；(3) 若若 2i+1n，则该结点无右孩子结点，则该结点无右孩子结点， 否则，编号为否则，编号为2i+1 的结点为其右孩子结点。的结点为其右孩子结点。 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构(四四) 二叉树

21、的存储结构二叉树的存储结构1、顺序存储结构顺序存储结构 (1) 存储存储要求要求： 用一组地址连续的存储单元存储二叉树中的数据元素，节点必须排用一组地址连续的存储单元存储二叉树中的数据元素，节点必须排成线性序列，并且该序列能反映出节点之间的逻辑关系。成线性序列，并且该序列能反映出节点之间的逻辑关系。 (2) 完全二叉树的存储完全二叉树的存储 完全二叉树的存储完全二叉树的存储 一般二叉树的存储一般二叉树的存储 二者二者比较比较得知：对于一般的二叉树，不宜采用顺序存储结构，对于完全得知：对于一般的二叉树，不宜采用顺序存储结构，对于完全二叉树，采用顺序存储结构既简单，又节省空间二叉树，采用顺序存储结

22、构既简单，又节省空间 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构2、链式存储结构链式存储结构 可以采用二叉链表或三叉链表来存储二叉树。可以采用二叉链表或三叉链表来存储二叉树。 ABDCEF 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构(五五)二叉树的遍历二叉树的遍历1、遍历的、遍历的含义含义： 指按照某种策略访问树中的每个节点，且仅访问一次。遍历过程的实指按照某种策略访问树中的每个节点，且仅访问一次。遍历过程的实质是：将树中的节点排成一个线性序列的过程。质是：将树中的节点排成一个线性序列的过程。2、常

23、见几种遍历常见几种遍历：先序先序遍历算法遍历算法 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）访问根结点；）访问根结点；（2）先序遍历左子树；）先序遍历左子树；（3）先序遍历右子树）先序遍历右子树。void PreOrder(BiTree root) if(root!=null) return ; elseprintf(“%d”,root-data); PreOrder(root-lchild); PreOrder(roolt-rchild); 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构中序中序遍历算法：遍历算法： 若二

24、叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则， （1）中序遍历左子树；）中序遍历左子树； （2）访问根结点；）访问根结点； （3）中序遍历右子树）中序遍历右子树 void InOrder(BiTree root) if(root=null) return ; else InOrder(root-lchild); printf(“%d”,root-data); InOrder(root-rchild); 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构后序后序遍历算法：遍历算法： 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否

25、则，（1）后序遍历左子树；）后序遍历左子树；（2）后序遍历右子树；）后序遍历右子树；（3）访问根结点。）访问根结点。 void PostOrder(BiTree root) if(root=null ) return ;else PostOrder(root-lchild); PostOrder(root-rchild); printf(“%d”,root-data); 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构层次层次遍历算法：遍历算法：从树的根结点出发，首先访问第一层的树的根结点，然后从左到右依次访问从树的根结点出发，首先访问第一层的树的根结

26、点，然后从左到右依次访问第二层上的节点，其次是第三层上的节点第二层上的节点，其次是第三层上的节点依次类推，自上而下，自左至依次类推，自上而下，自左至右，逐层访问树中各层上的节点。右，逐层访问树中各层上的节点。 层次遍历序列层次遍历序列： A B E C F D G H K 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构(六六) 线索二叉树线索二叉树1、定义、定义 二叉树的遍历实质：对非线性结构进行线性化操作，使得每个结点二叉树的遍历实质：对非线性结构进行线性化操作，使得每个结点（除第一个和最后一个结点外）在线性序列中有且仅有一个直接前驱和（除第一个和

27、最后一个结点外）在线性序列中有且仅有一个直接前驱和直接后继。直接后继。 由于二叉链表的存储结构中，只能找到结点的左、右孩子的信息，由于二叉链表的存储结构中，只能找到结点的左、右孩子的信息，得不到前驱和后继信息，因此引入线索二叉树保存遍历过程中得到的得不到前驱和后继信息，因此引入线索二叉树保存遍历过程中得到的前驱和后继信息。前驱和后继信息。2、建立线索二叉树、建立线索二叉树 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构对线索链表中结点的对线索链表中结点的约定：

28、约定： 在二叉链表的结点中在二叉链表的结点中增加两个标志域增加两个标志域，并作如下规定：，并作如下规定： 若该结点的左子树不空，则若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域域的指针指向其左子树，且左标志域的值为的值为“指针指针 Link”； 否则否则,Lchild域的指针指向其域的指针指向其“前驱前驱”，且左标志的值为，且左标志的值为“线索线索Tread” 。若该结点的右子树不空，则若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的指针指向其右子树，且右标志域的值为域的值为 “指针指针 Link”； 否则，否则，rchild域的指针指向其域的指针指

29、向其“后继后继”，且右标志的值为，且右标志的值为“线索线索 Thread”。 如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表” 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构 思考：画出下列二叉树的中序线索二叉树及其中序线索链表。思考：画出下列二叉树的中序线索二叉树及其中序线索链表。 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构(七七) 二叉树的应用：最优二叉树二叉树的应用：最优二叉树1. 哈夫曼树（1）相关概念：结点的路径长度结点的路径长度：从根结点到该结点的路径上分支的

30、数目。树的路径长度树的路径长度： 树中每个结点的路径长度之和。树的带权路径长度树的带权路径长度定义为： 树中所有叶子结点的带权路径长度结点的带权路径长度之和 WPL(T) = WkLkWPL(T)= 72+52+23+43+92 =60 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构(2)如何构造最优二叉树（Huffuman算法） 根据给定的 n 个权值 w1, w2, , wn， 构造 n 棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点,其左、右子树为空树; 在 F 中选取其根结点的权值为最

31、小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之和; WPL(T)= 74+94+53+42+21 =89 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构 从F中删去这两棵树，同时加入刚生成的新树。 重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。(3)举例： 已知权值 W= 5, 6, 2, 9, 7 构造一棵哈夫曼树。步骤如下：（右图为哈夫曼编码） 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（八）树和森林1、树的存储结构

32、（三种表示方法）(1) 双亲表示法：双亲表示法： 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构 (2) 孩子表示法孩子表示法 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（3）孩子兄弟表示法： 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构2、树和林林的遍历（1）树的遍历：先根遍历后根遍历（2）森林的遍历先序遍历中序遍历3、树、森林和二叉树之间的相互转换 （1）树、森林转换为二叉树 利用孩子兄弟法实现转换（P454例） （2）二叉树转换为树和森林（P454例）

33、 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构v三、图三、图（一）图的定义与图相关的概念有：有向图/无向图：无向完全图/有向完全图：度、出度和入度：路径：从一个顶点到另一个顶点的顶点序列子图：连通图与连通分量：强连通图与强连通分量：网：带权值的图有向树：有向图恰有一个顶点的入度为0，其余顶点的入度为1. 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构(二) 图的存储结构1、邻接矩阵表示法： 无向图邻接矩阵 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构 数据结构

34、数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构2、邻接表表示法 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构有向图逆邻接表 在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（三）图的遍历（三）图的遍历1、深度优先（DFS）遍历算法： 从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。 例子： 数据结构数据结构第二部分第二部

35、分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构2、广度优先遍历（BFS）遍历算法： 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构(四) 生成树及最小生成树1、生成树的概念 一个连通图的生成树是一个极小连通子图，它包含图中的全部顶点，但只有构成

36、一棵树的n-1条边。 按深度和广度优先搜索可以分别得到不同的生成树，分别称为深度优先生成树深度优先生成树和广度优先生成树广度优先生成树。上面图的深度优先生成树和广度优先生成树分别如下： 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构 深度优先生成树 广度优先生成树 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构2、最小生成树 由于生成树不唯一，从不同顶点出发可得到不同的生成树，因此如何求解最小生成树有许多实际应用价值。 常见的最小生成树算法有两种：、（1）普里姆算法（Prim） 基本思想基本思想： 取图中任

37、意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构 举例 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（2）克鲁斯卡尔算法(kruskal) 基本思想基本思想： 考虑问题的出发点考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的

38、权值尽可能地小。 具体做法具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。 算法举例 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构举例（2）两种算法比较： 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（五）拓扑排序和关键路径1、拓扑排序拓扑排序 （1）问题的提出: 假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。 检查有向图中是否存在回路的方法之一，是对有向

39、图进行拓扑排序。（2）什么叫拓扑排序 对有向图进行如下操作: 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。 由此所得顶点的线性序列称之为拓扑有序序列拓扑有序序列 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（3）如何进行了拓扑排序？）如何进行了拓扑排序？ 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构结论： 数据结构数据结构第二部分第二部分

40、第二部分第二部分 非线性结构非线性结构非线性结构非线性结构2、关键路径（1）问题的提出 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。 问：哪些子工程项是“关键工程”？ 即：哪些子工程项将影响整个工程的完成期限的。 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（2） 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构v（3）举例 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（六）最短路径1、单源点最短路径 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构 算法思想：P466 举例P4672、每对顶点之间的最短路径 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（续）