期末复习-树、图、查找、排序.ppt

《期末复习-树、图、查找、排序.ppt》由会员分享，可在线阅读，更多相关《期末复习-树、图、查找、排序.ppt（212页珍藏版）》请在三一办公上搜索。

1、期末复习树、图、查找、排序,树:是 n(n0)个结点的有限集合。如果该集合为空，称为空树。在任意一棵非空树中:,树的定义,有且仅有一个特定的称为根结点(root)的结点;2)其他结点可分为若干个互不相交的子集,而且每一个子集本身又是一棵树,称为根的子树。,递归定义,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,结点分支的个数,即子树的数目如：A的度-3；B的度-2；K的度-0；,树中所有结点的度的最大值 如：树的度为3；,度为零的结点，也称终端结点如例：K，L，F，G，M，I，J为终端结点,度大于零的结点如例：A,B,C,D,E,基本术语,森林：是 m（m

2、0）棵互不相交的树的集合,A,root,F,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),7.2 二叉树,二叉树或为空树；或是由一个根结点加上两棵分别称为左和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,E,F,特点：1）每个结点最多只有两棵子树；2）两颗子树有左右之分，顺序不能换。,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,特殊的二叉树：满二叉树,满二叉树：指的是

3、深度为k且含有2k-1个结点的二叉树。,深度为3，节点数=23-1=7,深度为4，节点数=24-1=15,特点：1）每一层上的结点数都是最大结点数；2）叶子结点都在最后一层。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,特点：1）除了最下一层外其余各层都是满的；2）最下一层的结点都集中在该层的左侧。,特殊的二叉树：完全二叉树,性质 1：满二叉树的第 i 层上有2i-1 个结点(i1),用归纳法证明：归纳基：归纳假设：归纳证明：,i=1 时，只有一个根结点，2i-1=20=1；,假设第j层有2j-1结点，命题成立;,第j层的每个结点都有2个结点，则第(j+

4、1)层上的结点数=2*2j-1=2j=2(j+1)-1。,二叉树的性质,性质 1的推论：在二叉树的第 i 层上至多有2i-1 个结点(i1)。,性质 2：深度为 k 的满二叉树共有 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的满二叉树上的结点数为：20+21+2k-1=2k-1,性质 2的推论：深度为 k 的二叉树上最多有 2k-1 个结点（k1）,性质 3：设二叉树叶子结点数为n0，度为 2 的结点数为n2，则必存在关系式：n0=n2+1。,性质4：具有 n 个结点的完全二叉树的深度为 log2n+1,性质 5：对于具有n个结点的完全二叉树，如果按照从上到下和从左至右的

5、顺序对二叉树中的所有结点从 1 至 n进行编号，则对于任意的序号为 i 的结点，有：若 i1，则序号为i的结点的双亲结点的序号为i/2；如果i=1，则该结点是根，无双亲;若 2in 则该结点无左孩子；若 2i+1n，则序号为i的结点无右孩子结点。,二叉树的存储结构,二、二叉树的链式存储表示,一、二叉树的顺序存储表示,用一组连续的存储单元存储二叉树的数据元素,以结点存储的相对位置表示结点之间的关系。为了正确地反映结点之间的关系,任何二叉树都必须按照完全二叉树的形式来存储.这种存储方式对某些二叉树的存储会造成存储空间的浪费。,顺序存储结构,在高级语言中,可以用一维数组来描述这种顺序存储结构。例如：

6、,完全二叉树的顺序存储,一般二叉树的存储,NOTES:代表空元素,#define MAX_TREE_SIZE 100/二叉树的最大结点数TElemType SqBiTreeMAX_TREE_SIZE;/1号单元存储根结点,例如:,练习：,1已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（）A7B8 C9D102若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（）A10B11 C12D不确定的已知一棵二叉树的顺序存储序列为：aebfcd，则：1）e的左孩子是哪个结点？右孩子是哪个结点？2）d的双亲是哪个结点？,答案：B答案：A答案：1）没有左孩子；右孩子是f；2）b；

7、,练习：,3假设一棵二叉树的顺序存储结构如图所示，请回答下列问题：（1）哪个结点是根结点？（2）哪些结点是叶子结点？（3）哪些结点是H的祖先？（4）哪些结点是B的兄弟？（5）树的深度是多少？,AD,HA,C,EC4,二、二叉树的链式存储表示,1.二叉链表,2三叉链表,二叉链结构 每个结点包含三个域:数据域和左右指针域,如下表所示,root,二叉链表,struct BTNode datatype data;struct BTNode*lchild,*rchild;Typedef BTNode*BTree;将二叉树类型BTree定义为指向二叉链表结点结构的指针类型。,结点结构:,C 语言的类型描述

8、如下:,三叉链表 三叉链表结构：每个结点除包含数据域和左右指针域外,还包含一个指向其双亲结点的指针域。,root,struct TriTNode/结点结构 datatype data;struct TriTNode*lchild,*rchild;/左右孩子指针 struct TriTNode*parent;/双亲指针 typedef TriTNode*TriTree;,结点结构:,C 语言的类型描述如下:,在这两种结构中,只需要给出指向根结点的指针,即可访问树中任意一个结点.,尽管在二叉表中无法由结点直接找到其双亲，但由于二叉链表的结构灵活，操作方便，对于一般情况下的二叉树，甚至比顺序存储结构

9、还节省空间。因此二叉链表是最常用的二叉树存储方式。今后，我们所涉及到的二叉树，如不加特别说明均采用二叉链表存储。,说明,二叉树的遍历,遍历二叉树是指按照一定的规律对二叉树中的每个结点，访问且仅访问一次的处理过程。,“访问”的含义可以很广，如：求结点的度、层次、输出结点的信息等等。,“遍历”是任何类型均有的操作，1）对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。2）而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。,对“二叉树”而言，可以把二叉树看成由三个基本单元组成:根结点(D)、左子树(L)、右子树(R),并且规定

10、左子树上的所有结点应该在右子树上的所有结点之前被访问,由此可以得到三种遍历顺序:先序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD),先序的遍历算法,中序的遍历算法,后序的遍历算法,遍历算法,若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。,先序的遍历算法：,先序遍历：,A B D E G C F,若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。,中序的遍历算法：,中序遍历：,D B G E A C F,若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。

11、,后序的遍历算法：,后序遍历：,D G E B F C A,先序遍历：,中序遍历：,后序遍历：,A B D G C E H F,B G D A H E C F,G D B H E F C A,例题,中序遍历：,先序遍历：,后序遍历：,a+b*c d e/f,-+a*b c d/e f,a b c d-*+e f/-,例题,(),根据遍历序列画二叉树,由一棵二叉树的先序序列和中序序列或中序和后序能够唯一确定一棵二叉树。,先序序列：A B C D E F G H I 中序序列：B C A E D G H F I,练习,已知一棵二叉树的先序序列和中序序列，请画出该二叉树。,先序序列：A B C D

12、E F G H I J 中序序列：C B E D F A H G J I,树和森林,树的存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟）存储表示法,树的双亲表示法,以一组连续空间(数组)存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在数组中的位置.,typedef struct datatype data;int parent;Node;typedef Node Tree MAX_NODE_NUM,#define MAX_NODE_NUM 100,C语言的类型描述:,孩子表示法,存储每个结点及其孩子信息。每个结点的所有孩子结点形成该结点的孩子链表。,孩子

13、链表,孩子-兄弟表示法,struct TreeNode datatype data;struct TreeNode*children;struct TreeNode*next;typedef struct Tree;,C语言的类型描述:,结点结构:,每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。,孩子-兄弟表示法,树、森林与二叉树之间的转换,将树转换成二叉树的方法加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,将二叉树转换成树加线：若p结点

14、是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构,树的先序遍历和后序遍历可以借用二叉树的先序遍历和中序遍历的算法来实现。,先序序列：ABEFGCDHI后序序列：EFGBCHIDA,先序序列：ABEFGCDHI中序序列：EFGBCHIDA后序序列：GFEIHDCBA,树,二叉树,森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，

15、及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树,由此，树和森林的各种操作均可与二叉树的各种操作相对应。,应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟,把下面的树转化成二叉树。,A,B,C,D,E,F,G,H,I,练习,K,L,J,哈夫曼树与哈夫曼编码,相关概念,树的路径长度定义为：树中每个结点的路径长度之和。,结点的路径长度定义为：从根结点到该结点的路径上分支的数目。,树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和 WPL(T)=wklk(对所有叶子结点),结点的带权路径长度定义为：从根结点到该结点的路

16、径长度与结点上权的乘积。,设：a,b,c,d 的权值为：a=7,b=5,c=2,d=4;下面三棵不同的树的带权路径长度为：(7+5+4+2）*2=36(7+5)*3+4*2+2=46 7+5*2+(2+4)*3=35 第3棵树的带权路径长度最小。,最优二叉树:设有n个权值w1,w2,w3,.,wn,构造有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树(赫夫曼树).赫夫曼树的应用：判定问题。例：将学生的百分制变成五级分制：设学生的成绩分布在五个等级上是不均匀的。,二、如何构造最优树,赫夫曼算法:(1)根据给定的n个权值w1,w2,w3,.,wn构

17、成n棵二叉树的集合F=T1,T2,T3,.,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均为空.(2)在集合F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,新二叉树的根结点的权值为其左右子树上根结点的权值之和.(3)在集合F中删除这两棵树,同时将新得到的二叉树加入F中.(4)重复步骤(2)、(3),直到F中只含一棵树为止,这棵树就是一棵赫夫曼树.,9,例如:已知权值 W=5,6,2,9,7,5,6,2,7,5,2,7,6,9,7,6,7,13,9,9,16,29,0,0,0,0,1,1,1,1,00,01,11,100,101,(1)根据给定的n个权值w1,w

18、2,w3,.,wn构成n棵二叉树的集合F=T1,T2,T3,.,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均为空.,(2)在集合F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,新二叉树的根结点的权值为其左右子树上根结点的权值之和.,(3)在集合F中删除这两棵树,同时将新得到的二叉树加入F中.(4)重复步骤(2)、(3),直到F中只含一棵树为止,这棵树就是一棵赫夫曼树.,哈夫曼编码 通信中的信息传递问题：在传递信息时，如何在能够识别的前提下，使传递的字符数最少。例：电报中的报文“ABACCDA”四个字符的编码问题。两位编码：00 01 10 11 如果用不同长

19、度的编码：例用 0 1 00 01前缀编码:对于不等长编码,若任一个字符的编码都不是另一个字符的编码的前缀,则这种编码称为前缀编码.前缀编码使得字符编码的平均长度最短.赫夫曼编码是一种前缀编码.赫夫曼编码的方法:(1)把字符出现的频率作为权值,根据这些权值构造一棵赫夫曼树.(2)约定在赫夫曼树中,左分支表示字符0,右分支表示字符1,则从根结点到叶子结点的路径上的分支字符组成的字符串即为该叶子结点字符的编码.,已知某系统在通信联系中只可能出现8种字符：abcdefgh，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23,0.03，0.11，试据此构造哈夫曼树，要求：1)画出构

20、造哈夫曼树的过程；2)求每个字符的哈夫曼编码。,例题,哈夫曼编码：a:0110b:10c:1110d:1111,e:110f:00g:0111h:010,设权值序列为8，5，3，4，7，据此构造一棵哈夫曼树。画出构造哈夫曼树过程。,练习,习 题 一,1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。A15 B16 C17 D472.深度为5的二叉树至多有_个结点。A.16 B.32 C.31 D.103.对一个满二叉树，m个树叶，n个结点，深度为h，则_。A.n=h+m B.h+m=2n C.m=h-1 D.n=2 h-1,答案：B C D,二叉树的前序遍历

21、序列中，任意一个结点均处在其子女结点的前面，这种说法_。A.正确 B.错误5.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca6.在一非空二叉树的中序遍历序列中，根结点的右边_。A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点,答案：A D A,7.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二

22、叉树叫做这棵数对应的二叉树。结论_是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对,答案：A,8.有一棵树如图所示，回答下面的问题：这棵树的根结点是_；这棵树的叶子结点是_；结点k3的度是_；这棵树的度是_；这棵树的深度是_；结点k3的子女是_；结点k3的父结点是_；,k1,k7,k5,k2,k4,k6,k3,1.k1 k2,k5,k7,k4 2 3 4 k5,k6 k1,9.一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图所示，则该二叉树的

23、链接表示形式为_ _。,10.深度为k的完全二叉树至少有_个结点。至多有_个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_。,2 k-1、2 k-1、2 k-1,11.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。,以数据集4，5，6，7，10，12，18为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度为。假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07

24、,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这八个字母设计哈夫曼编码。,习题二,1.三个结点的二叉树的基本形态有 种，三个结点的树的基本形态有 种。2一棵具有64个结点的完全二叉树的高度为。3.设一棵二叉树的先序遍历序列为ABCDFEGH，中序遍历序列为BAFDCGEH，请完成下列要求：1）画出该二叉树；2）写出该二叉树的后序遍历序列；3）将该二叉树转换成森林；,习题,4.已知一棵二叉树的顺序存储结构如下图所示，图中“0”表示不存在的结点，1）画出该二叉树；2）求该二叉树的先序遍历序列和中序遍历序列；3）将该二叉树转换成一棵树。5.设字符集为A，B，C，D，E，

25、其对应的权值为7，5，2，4，9，据此构造哈夫曼树，要求：1）画出构造哈夫曼树过程；2）求每个字符的哈夫曼编码；,本章复习要点,1、树的基本概念；结点、结点的度、树的度、叶子结点、分支结点、路径、孩子、双亲、结点的层次、树的深度、兄弟、堂兄弟2、二叉树的基本概念：二叉树、满二叉树、完全二叉树；3、二叉树的5个性质；4、具有3个结点的二叉树的5种形态；3个结点的树的2种的形态；5、理解二叉树的顺序存储结构；根据二叉树的顺序存储结构画二叉树；6、二叉树的先序、中序和后序遍历；根据先序和中序遍历的序列画二叉树；7、构造哈夫曼树，写出哈夫曼编码；8、树、森林、二叉树的互相转换；,1.B 2.B 3.C

26、 4.C,1.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_。A.正确 B.错误2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。A15 B16 C17 D473.按照二叉树的定义，具有3个结点的不同形状的二叉树有_种。A.3 B.4 C.5 D.64.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_种。A.5 B.6 C.30 D.32,5.C 7.D 8.A,5.深度为5的二叉树至多有_个结点。A.16 B.32 C.31 D.107.对一个满二叉树，m个树叶，n个结点，深度为h，则_。A.n=h+m B.h+m=2n C

27、.m=h-1 D.n=2 h-18.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对,9.C 10.A 11.D,9.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_。A.uwvts B.vwuts C.wuvts D.wutsv10.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_。A.正确 B.错误11.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。A.bdgcefha B.gd

28、becfha C.bdgaechf D.gdbehfca,1.A 15.B,12.在一非空二叉树的中序遍历序列中，根结点的右边_。A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的部分结点 D.只有左子树上的所有结点15设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孙,16.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A.acbed B.decab C.deabc D.cedba,18.如图6.3所示的4棵二叉树，_不是完全二叉树。(A)(B)(C)(D)

29、图6.3,第八章 图,图的基本概念,图的定义：一个图G是由两个集合V和E组成，V是有限的非空顶点集，E是V上的顶点对所构成的边集，分别用V（G）和E（G）来表示图中的顶点集和边集。用二元组G=（V，E）来表示图G。有向图与无向图 若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向的，则称G为无向图。,完全图 对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1)，则称其为有向完全图。邻接顶点 若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接，并称边（vi,vj）关联于顶点v

30、i和vj，或称（vi,vj）与顶点vi和vj相关联。若（vi,vj）是一条弧，则称顶点vi邻接至顶点vj,顶点vj邻接至顶点vi,。弧（vi,vj）与顶点vi、vj关联。,顶点的度 一个顶点v的度是与它相关联（依附）的边的条数。,顶点 v 的入度 是以 v 为终点的有向边的条数。顶点 v 的出度是以 v 为始点的有向边的条数。有向图的顶点的度等于它的入度与出度之和。,子图 设有两个图 G(V,E)和 G(V,E)。若 V V 且 EE,则称 图G 是 图G 的子图。,路径 在图 G(V,E)中,若存在一个顶点序列 vp1,vp2,vpm，使得(vi,vp1)、(vp1,vp2)、.、(vpm,

31、vj)均属于E，则称顶点vi到vj存在一 条路径。若一条路径上除了vi 和vj 可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为简单回路或简单环。,图的连通 在无向图G中，若两个顶点vi和vj之间有 路径存在，则称vi 和vj 是连通的。若G中任意两 个顶点都是连通的，则称G为连通图。非连通图的 极大连通子图叫做连通分量。,强连通图与强连通分量 在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,权 某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。,权图（网

32、络）,生成树 一个连通图的生成树是它的极小 连通子图，在n个顶点的情形下，有n-1条 边。,生成林 若G是一个不连通的无向图，G的每个连通分量都有一棵生成树，这些生成树构成G的生成森林，简称生成林。,习 题,1.在一个图中，所有顶点的度数之和等于所有边数的_倍。A.1/2 B.1 C.2 D.4 2.任何一个无向连通图的最小生成树。A.只有一棵B.有一棵或多棵 C.一定有多棵D.可能不存在3.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。A.1/2 B.1 C.2 D.4,答案：C B B,4.一个有n个顶点的无向图最多有_条边。A.n B.n(n-1)C.n(n-1)/2

33、D.2n5.具有4个顶点的无向完全图有_条边。A.6 B.12 C.16 D.206.具有6个顶点的无向图至少应有_条边才能确保是一个连通图。A.5 B.6 C.7 D.87.在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。A.n B.n+1 C.n-1 D.n/2,C,A,A,C,图的存储表示,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,图的数组(邻接矩阵)存储表示,邻接矩阵表示顶点间相联关系的矩阵定义：设G=(V,E)是有 n 个顶点的图，G的邻接矩阵A是如下的n阶方阵。,2）有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n3）无向图中顶点Vi的度TD(

34、Vi)是邻接矩阵A中第i行元素之和4）有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和,图的邻接矩阵的性质,1）无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2,网的邻接矩阵,0 0 1 0 0 30 100 0 0 5 0 0 0 0 0 0 50 0 0 A=0 0 0 0 0 10 0 0 0 20 0 60 0 0 0 0 0 0,无向图,有向图,AdjMatrix,AdjMatrix,练习,邻接表是图的一种链式存储结构。方法是对图中的每一个顶点建立一个依附于该顶点的边的表。而表头结点用一顺序结构(向量）的形式存储。,图的邻

35、接表存储表示,例题：画出下图的邻接表,有向图的邻接表和逆邻接表在有向图的邻接表中，第 i 个边链表链接的边都是顶点 i 发出的边。也叫做出边表。在有向图的邻接表中不易找到指向该顶点的弧在有向图的逆邻接表中，第 i 个边链表链接的边都是进入顶点 i 的边。也叫做入边表。在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧,邻接表,逆邻接表,有向图的邻接表,有向图的逆邻接表,例题画出该有向图的邻接表和逆邻接表,网络(带权图)的邻接表,图的遍历,图的遍历:从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,深度优先搜索,广度优先搜索,深度优先搜索遍历图,从图中的

36、某一个顶点 v0 出发，访问此顶点，然后 依次从 v0 的没被访问的邻接点出发深度优先遍历图，直至图中所有和 v0 有路径相通的顶点都被访问到；若此时图中仍有顶点没有被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程。,深度遍历,根据图的形态做图的深度优先遍历,根据图的形态可以得出图的多个深度优先遍历序列。,0a-,2c-,6g-,5f-,1b-,4e-,7h-,3d,根据图的邻接表做深度优先遍历,从顶点a出发的深度优先遍历：,0,2,6,0,1,4,7,根据图的邻接表得到的深度优先遍历序列是唯一的。,方法：从图中的某一个顶点 v0 出发，访问v0之后，依次访问v0 的没被访问的邻接点

37、，然后，分别从这些邻接点出发，广度优先遍历图，直至所有顶点都被访问；若此时图中仍有结点没有被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程。,遍历结果：V1-V2-V3-V4-V5-V6-V7-V8,广度优先搜索遍历图,遍历结果：V1-V3-V2-V6-V7-V4-V5-V8,先访问的顶点其邻接顶点也先被访问,从a出发根据邻接表广度优先遍历：,1,a-,c-,b-,g-,f-,e-,h,2,3,4,5,6,d-,7,8,根据图的邻接表得到的广度优先遍历序列是唯一的。,8.4 生成树生成树定义：所有顶点均由边连接在一起，但不存在回路的图叫生成树深度优先生成树与广度优先生成树说明一个图可

38、以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,最小生成树(minimum cost spanning tree),假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？,问题：,构造网的一棵最小生成树，

39、即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法一：（普里姆算法）,普里姆(Prim)算法,基本思想：从连通网络 N=V,E 中的某一顶点 u0 出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合 U 中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。,a,e,d,c,b,g,f,14,8,5,3,16,21,所得生成树权值和,=14+8+3+5

40、+16+21=67,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,克鲁斯卡尔(Kruskal)算法,基本思想：设有一个有 n 个顶点的连通网络 N=V,E,最初先构造一个只有 n个顶点,没有边的非连通图 T=V,图中每个顶点自成一个连通分量。当在E 中选一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边入到 T 中;否则将此边舍去，重新选择一条权值最小的边。如此重复下去,直到所有顶点在同一个连通分量上为止。

41、,0,1,0,2,6,3,4,5,12,14,16,18,10,22,24,25,习 题,由V1，V2，V3，V4，V5，V6六个顶点构成的无向图的邻接矩阵如下表所示。1）画出该无向图；2）画出该无向图的邻接表存储结构。3）根据所画邻接表，给出从定点V1出发的深度和广度优先遍历序列。,深度遍历序列：V1 V2 V4 V5 V6 V3 广度遍历结果：V1 V2 V3 V4 V6 V5,习 题,一个有向图有5个顶点，6条弧。5个顶点编号为0，1，2，3，4；其弧用顶点对表示为，。要求：（1）画出该有向图；(2）建立该有向图邻接表存储结构；（3）写出从0号顶点出发的深度优先搜索与广度优先搜索的序列。

42、,深度：0 1 4 2 3；广度：0 1 2 4 3；,本章复习要点,1、基本概念；2、图的邻接矩阵、邻接表；3、图的深度优先遍历、广度优先遍历；4、图的最小生成树：普里姆算法、克鲁斯卡尔算法；,第九章 查找,关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。,若此关键字能识别若干记录，则称之为“次关键字”。,基本概念,基本概念,查找（Searching）的定义是：给定一个关键字值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败

43、，返回相关的指示信息。,基本概念,查找表是由同一类型的数据元素(或记录)构成的集合。对查找表经常进行的操作:1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。,查找表的数据结构表示,若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表（Dynamic Search Table）。否则称之为静态查找表(Static Search Table)。例如：词典、电话薄 若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。,顺序查找,二分查找

44、,分块查找,线性表的查找,顺序查找(Sequential Search)基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。既适用于顺序表，也适用于链表。,顺序查找,以顺序表或线性链表表示静态查找表 回顾顺序表的查找过程：,顺序查找表,ST.elem,假设给定值 kval=64要求 ST.elemi=kval,问:i=?,66,循环的判断条件：ST.elemi.key!=kval&iST.Length,ST.elem,ST.elem,60,kval=64,kva

45、l=60,64,顺序表中设置“哨兵”进行查找,循环的判断条件：ST.elemi.key!=kval,int Search_Seq(SqList ST,KeyType kval)/在顺序表ST中顺序查找其关键字等于/key的数据元素。若找到，则函数值为/该元素在表中的位置，否则为0。ST.elem0.key=kval;/设置“哨兵”/从后往前找for(int i=ST.length;ST.elemi.key!=kval;-i);return i;/找不到时，i为0/Search_Seq,顺序查找的优点 算法简单，且对表的结构无任何要求，无论是用数组还是用链表来存放结点，也无论结点之间是否按关键字

46、有序，它都同样适用。顺序查找的缺点 查找效率低。,二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求：1）线性表是有序表，即表中结点按关键字有序；2）要用数组作为表的存储结构（顺序表）；不妨设有序表是递增有序的。,二分查找,二分查找的基本思想是：1）首先确定该区间的中点位置：mid=2）然后将待查的K值与searchildhListmid.key比较：(1)若相等，则查找成功并返回此位置(2)若searchildhListmid.key k，则在low到mid-1中继续查找；(3)若searchildhListmid.key k，则在mid+1到high中继续查找。,二分查找,ST

47、.elem,ST.length,例如:key=64 的查找过程如下,low,high,mid,low,mid,high,mid,low 指示查找区间的下界;high 指示查找区间的上界;mid=(low+high)/2。,ST.elem,ST.length,例如:key=20 的查找过程如下,low,high,mid,low 指示查找区间的下界;high 指示查找区间的上界;mid=(low+high)/2。,high,mid,low,mid,high,highlow 没找到,int bin_searchildh(DataNode searchildhList,int n,KeyType k)

48、int low=1;high=n;/置区间初值 while(low k)high=mid-1;/继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找 return 0;/顺序表中不存在待查元素,二分查找的优点和缺点,虽然二分查找的效率高，但是要将表按关键字排序。二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。,练习,给出一个折半查找算法如下：设记录R1，R2，.，Rn的关键字K1Ki，转第五步；如果K=Ki，则查找成功 第四步【调整U】置Ui，返回第二步；第五步【调整L】置Li；返回第二步；,分块查找是顺序查找和二分查找的折衷

49、，也称索引顺序查找。将一个主表分成n个块，即n个子表，要求子表之间元素是按关键字有序排列的，而子表中元素可以无序，用每个子表最大关键字和指示块中第一个记录在表中位置建立索引表。,查找过程：1）由索引确定记录所在块；由于索引表按关键字有序，故可用顺序查找或折半查找2）在顺序表的某个块内进行查找。由于块内无序，只能用顺序查找,分块查找,树表的查找,二叉排序树（二叉查找树）,1定义,2查找算法,3插入算法,4删除算法,5查找性能的分析,1定义：,二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有

50、结点的值均大于根结点的值；（3）它的左、右子树也都分别是二叉排序树。,是二叉排序树,不是二叉排序树,二叉排序树的查找算法,1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。,若二叉排序树为空，则查找不成功，否则：,例如:,二叉排序树,查找关键字,=50,50,50,35,50,30,40,35,50,90,50,80,90,95,从上述查找过程可见，,在查找过程中，生成了一条查找路径:,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发，沿着左分支