考前串讲(精品).ppt

《考前串讲(精品).ppt》由会员分享，可在线阅读，更多相关《考前串讲(精品).ppt（141页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、考前串讲考前串讲数据结构数据结构 辅导辅导1线性表的概念线性表的概念顺序表顺序表 链表链表第二章第二章 线性表线性表2线性表线性表 (Linear List)(Linear List)n线性表的定义和特点线性表的定义和特点r定义定义 n（0）个数据元素的有限序列，记作个数据元素的有限序列，记作 （a1,a2,an）ai 是表中数据元素，是表中数据元素，n 是表长度。是表长度。r特点特点 线性排列（这是非线性结构不具备的）线性排列（这是非线性结构不具备的）除第一个元素外，其他每一个元素有一个除第一个元素外，其他每一个元素有一个且仅有一个且仅有一个直接前驱直接前驱。除最后一个元素外，其他每一个元素

2、有一除最后一个元素外，其他每一个元素有一个且仅有一个个且仅有一个直接后继直接后继。3n理解线性表与非线性表的区别理解线性表与非线性表的区别a)线性表每个元素最多一个直接前驱和一个线性表每个元素最多一个直接前驱和一个直接后继。直接后继。b)非线性表每个元素没有这个限制：非线性表每个元素没有这个限制：多维数组每个元素最多有多个直接前驱多维数组每个元素最多有多个直接前驱和多个直接后继。和多个直接后继。树结构每个元素最多一个直接前驱，但树结构每个元素最多一个直接前驱，但可能有多个直接后继。可能有多个直接后继。图结构每个元素最多有多个直接前驱和图结构每个元素最多有多个直接前驱和多个直接后继。多个直接后继

3、。4顺序表顺序表 (Sequential List)(Sequential List)n顺序表的定义和特点顺序表的定义和特点a)定义定义 将线性表中的元素相继存放在一个连续将线性表中的元素相继存放在一个连续的存储空间中，即构成顺序表。的存储空间中，即构成顺序表。b)存储存储 它是线性表的顺序存储表示，可利用一它是线性表的顺序存储表示，可利用一维数组描述存储结构。维数组描述存储结构。a)静态数组：不可扩充静态数组：不可扩充b)动态数组：可扩充动态数组：可扩充c)特点特点 元素的元素的逻辑顺序与物理顺序一致逻辑顺序与物理顺序一致。d)访问方式访问方式 可顺序存取，可按下标直接存取。可顺序存取，可按

4、下标直接存取。5顺序表的静态结构定义顺序表的静态结构定义#define ListSize 100 /最大允许长度最大允许长度typedef int ElemType;/元素的数据类型元素的数据类型typedef struct ElemType elemListSize;/存储数组存储数组 int length;/当前表元素个数当前表元素个数 SeqList;n顺序表静态定义，假定顺序表静态定义，假定 L 是一个类型是一个类型 SeqList 的的顺序表，一般用顺序表，一般用 L.elemi 来访问它。来访问它。n表一旦装满，不能扩充。表一旦装满，不能扩充。6顺序表的动态结构定义顺序表的动态结构

5、定义#define ListSize 100 /最大允许长度最大允许长度typedef int ElemType;/元素的数据类型元素的数据类型typedef struct ElemType*elem;/存储数组存储数组 int length;/当前表元素个数当前表元素个数 int maxSize;/表的最大长度表的最大长度 SeqList;n顺序表动态定义，它可以扩充，新的大小计入顺序表动态定义，它可以扩充，新的大小计入数据成员数据成员maxSize中。中。7n例题：在整数型顺序表例题：在整数型顺序表 A 中查找是否存在两个整中查找是否存在两个整数，它们相加之和等于数，它们相加之和等于 x。

6、是则函数返回。是则函数返回true,否否则函数返回则函数返回false。如果表中有多个相加等于。如果表中有多个相加等于x的的整数，找到一组即可。整数，找到一组即可。bool Find(SeqList&A,int x)for(int i=0;i A.length;i+)for(int j=i+1;j link;char Sn;int top=-1;while(p!=NULL)top+;Stop=p-data;/链表字符进栈链表字符进栈 p=p-link;p=L-link;while(top!=-1)if(Stop!=p-data)return false;top-;/退栈退栈14 p=p-lin

7、k;/字符相等比较下一个字符相等比较下一个return true;/全部相等全部相等15栈栈队列队列第三章第三章 栈和队列栈和队列16n只允许在一端插入和删除的线性表。允许插入和只允许在一端插入和删除的线性表。允许插入和删除的一端称为栈顶删除的一端称为栈顶(top)，另一端称为栈底另一端称为栈底(bottom)n特点：后进先出特点：后进先出(LIFO)n栈的主要操作栈的主要操作r进栈进栈 Push(S,x)r退栈退栈 Pop(S,&x)r看栈顶看栈顶 getTop(S,&x)r置空栈置空栈 initStack(S)r判栈空，判栈满判栈空，判栈满栈栈(Stack)退栈进栈a0an-1an-2to

8、pbottom17栈的数组表示栈的数组表示 顺序栈顺序栈0 1 2 3 4 5 6 7 8 9 StackSize-1top(栈空栈空栈空栈空)elem#define InitSize 100#define StackIncreament 10typedef char ElemType;typedef struct /顺序栈定义 ElemType*elem;/栈数组 int top,StackSize;/栈顶指针及栈大小 SeqStack;18void OverFlow(SeqStack&S)/栈满处理 int newSize=2*S.StackSize;ElemType*newS=new E

9、lemTypenewSize;if(newS=NULL)printf(“数组创建失败!n”);exit(1);ElemType*src=S.elem,*obj=newS;for(int i=0;i S.StackSize;i+)*obj+=*src+;/向新数组传送数据 delete S.elem;/释放老数组 S.elem=newS;/新数组作为栈数组 S.StackSize=newSize;/新数组大小 /栈顶指针不变19top栈的链接表示栈的链接表示 链式栈链式栈n链式栈用不带表头结点的单链表作为其存储结构。链式栈用不带表头结点的单链表作为其存储结构。n链式栈的栈顶在链头，插入与删除仅在

10、栈顶处执链式栈的栈顶在链头，插入与删除仅在栈顶处执行。行。n链式栈栈空即链表空，链式栈栈空即链表空，top=NULL。20a0 a1 a2 an-1frontrear队列队列(Queue)n定义定义n队列是只允许在一端删除，在另一端插入的线队列是只允许在一端删除，在另一端插入的线性表性表n允许删除的一端叫做队头允许删除的一端叫做队头(front)，允许插入的，允许插入的一端叫做队尾一端叫做队尾(rear)。n特性特性n先进先出先进先出(FIFO,First In First Out)21队列的数组存储表示队列的数组存储表示 顺序队列顺序队列#define QueueSize 50;typede

11、f int ElemType;/每个元素的数据类型typedef struct/顺序队列的结构定义 ElemType*elem;/队列存储数组 int rear,front;/队尾与队头指针 SeqQueue;n队列与栈的共性在于它们都是队列与栈的共性在于它们都是限制了存取位置的限制了存取位置的线性表线性表；区别在于存取位置有所不同。；区别在于存取位置有所不同。22队列的进队和出队的原则队列的进队和出队的原则n有两种进有两种进/出队列的方案，考虑一种：出队列的方案，考虑一种：先加元素先加元素再动指针再动指针r进队时先将新元素按进队时先将新元素按 rear 指示位置加入，再指示位置加入，再让队尾

12、指针进一让队尾指针进一 rear=rear+1。r队尾指针指示实际队尾的后一位置。队尾指针指示实际队尾的后一位置。r出队时先将下标为出队时先将下标为 front 的元素取出，再将队的元素取出，再将队头指针进一头指针进一 front=front+1。r队头指针指示实际队头的位置。队头指针指示实际队头的位置。r清华、北大教材均为此方案。清华、北大教材均为此方案。23循环队列循环队列(Circular Queue)n队列存放数组被当作首尾相接的环形表处理。队列存放数组被当作首尾相接的环形表处理。n队头、队尾指针加队头、队尾指针加 1 时从时从 QueueSize-1 直接进到直接进到0，可用语言的取

13、模（，可用语言的取模（%）运算实现。）运算实现。r队头指针进队头指针进1:front=(front+1)%QueueSize;r队尾指针进队尾指针进1:rear=(rear+1)%QueueSize;r队列初始化：队列初始化：front=rear=0;r队空条件：队空条件：front=rear;r队满条件：队满条件：(rear+1)%QueueSize=front。n注意，进队和出队时指针都是顺时针前进。注意，进队和出队时指针都是顺时针前进。2401234567front01234567front01234567frontrearAABCrearrear空队列空队列A 进进队队B,C 进进队队

14、0123456701234567A 退退队队B 退退队队01234567D,E,F,G,H,I 进进队队frontBCrearAfrontBCrearfrontCrearDEFG HI25循环队列操作的实现循环队列操作的实现bool QueueEmpty(SeqQueue&Q)return Q.rear=Q.front;bool EnQueue(SeqQueue&Q,ElemType x)if(QueueFull(Q)return 0;Q.elemQ.rear=x;Q.rear=(Q.rear+1)%QueueSize;return 1;26bool DeQueue(SeqQueue&Q,El

15、emType&x)if(QueueEmpty(Q)return 0;x=Q.elemQ.front;Q.front=(Q.front+1)%QueueSize;return 1;bool getFront(SeqQueue&Q,ElemType&x)if(QueueEmpty(Q)return 0;x=Q.elemQ.front;return 1;27队列的链接表示队列的链接表示 链式队列链式队列frontrearn链式队列采用不带表头的单链表存储队列元素，链式队列采用不带表头的单链表存储队列元素，队头在链头，队尾在链尾。队头在链头，队尾在链尾。n链式队列在进队时无队满问题，但有队空问题。链式

16、队列在进队时无队满问题，但有队空问题。n队空条件为队空条件为 front=NULL，不必判断是否，不必判断是否 rear=front。n链式队列特别适合多个队列同时操作的情形。在链式队列特别适合多个队列同时操作的情形。在并行处理、排序等方面有用。并行处理、排序等方面有用。28字符串定义字符串定义字符串的顺序表示字符串的顺序表示字符串的链表表示字符串的链表表示第四章第四章 字符串字符串29字符串字符串 (String)(String)n字符串的定义：字符串的定义：字符串是字符串是 n(0)个字符的有限序列，记作个字符的有限序列，记作 S:“c1c2c3cn”n其中，其中，S 是串名字，是串名字，

17、“c1c2c3cn”是串值，是串值，ci 是串是串中字符，中字符，n 是串的长度。例如是串的长度。例如,S=“Tsinghua University”n子串的定义：子串的定义：若串若串S是由串是由串S中连续抽取若干字符组成，则称中连续抽取若干字符组成，则称串串S是串是串S的子串。的子串。n例如，例如，“ity”是是“University”的子串。的子串。30n真子串：串是自己的子串。设一个串的长度为真子串：串是自己的子串。设一个串的长度为n，则长度小于则长度小于n的子串即为它的真子串。的子串即为它的真子串。n一个串的子串数目有一个串的子串数目有1+2+(n-1)+n=n(n+1)/2 真子串数

18、目真子串数目31判断字符串是否中心对称判断字符串是否中心对称n例如，例如，“abcddcba”或或“abcdcba”都是中心对称。都是中心对称。n一种解法是两头设指针，向中间并进，检查对应一种解法是两头设指针，向中间并进，检查对应字符是否相等，直到中间会合。字符是否相等，直到中间会合。bool center-sym(HString&S)int i=0,j=S.curLen-1;while(i j if(S.chi!=S.chj)return false;else i+;j-;return true;32第五章第五章 数组和广义表数组和广义表三对角矩阵的压缩存储三对角矩阵的压缩存储广义表广义表3

19、3三对角矩阵的压缩存储三对角矩阵的压缩存储B a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 1034n三对角矩阵中除主对角线及在主对角线上三对角矩阵中除主对角线及在主对角线上 下最临下最临近的两条对角线上的元素外，所有其它元素均为近的两条对角线上的元素外，所有其它元素均为0。总共有。总共有3n-2个非零元素。个非零元素。n将三对角矩阵将三对角矩阵A中三条对角线上的元素按行存放中三条对角线上的元素按行存放在一维数组在一维数组 B 中，且中，且a00存放于存放于B0。n在三条对角线上的元素在三条对角线上的元素

20、aij 满足满足 0 i n-1,i-1 j i+1n在一维数组在一维数组 B 中中 Aij 在第在第 i 行，它前面有行，它前面有 3*i-1 个非零元素个非零元素,在本行中第在本行中第 j 列前面有列前面有 j-i+1 个，所个，所以元素以元素 Aij 在在 B 中位置为中位置为 k=2*i+j。35n若已知三对角矩阵中某元素若已知三对角矩阵中某元素 Aij 在数组在数组 B 存存放于第放于第 k 个位置，则有个位置，则有 i=(k+1)/3 j=k-2*in例如，当例如，当 k=8 时，时，i=(8+1)/3 =3,j=8-2*3=2 当当 k=10 时，时，i=(10+1)/3 =3,

21、j=10-2*3=436广义表广义表 (General Lists)(General Lists)n广义表是广义表是 n(0)个表元素组成的有限序列，个表元素组成的有限序列，记作记作 LS(a1,a2,a3,an)nLS 是表名，是表名，ai 是表元素，可以是表（是表元素，可以是表（称为子表）称为子表），可以是数据元素（称为原子）。，可以是数据元素（称为原子）。nn为表的长度。为表的长度。n=0 的广义表为空表。的广义表为空表。nn 0时，时，表的第一个表元素称为广义表表的第一个表元素称为广义表 的表头的表头（head），除此之外，其它表元素组成的表称），除此之外，其它表元素组成的表称为广义表

22、的表尾（为广义表的表尾（tail）。）。37广义表的特性广义表的特性n有次序性有次序性n有长度有长度n有深度有深度n可共享可共享n可递归可递归A()A长度为长度为0，深度为，深度为1B(6,2)B长度为长度为2，深度为，深度为1C(a,(5,3,x)C长度为长度为2，深度为，深度为2D(B,C,A)D长度为长度为3，深度为，深度为3E(B,D)E长度为？长度为？深度为？深度为？F(4,F)F长度为？长度为？深度为？深度为？38广义表的表头与表尾广义表的表头与表尾n广义表的第一个表元素即为该表的表头，除表广义表的第一个表元素即为该表的表头，除表头元素外其他表元素组成的表即为该表的表尾。头元素外其

23、他表元素组成的表即为该表的表尾。A()head(A)和和 tail(A)不存在不存在B(6,2)head(B)=6,tail(B)=(2)C(a,(5,3,x)head(C)=aD(B,C,A)tail(C)=(5,3,x)E(B,D)head(5,3,x)=(5,3,x)F(4,F)tail(5,3,x)=()39A AB BC Cu vax y zD Du vax y zB BC CA Au vax y zB BC CA AE ED D空表空表空表空表线性表线性表线性表线性表再入表再入表再入表再入表纯表纯表纯表纯表F F递归表递归表递归表递归表d40树的定义与基本概念树的定义与基本概念二叉

24、树二叉树 二叉树遍历二叉树遍历第六章第六章 树与二叉树树与二叉树41二叉树的五种不同形态二叉树的五种不同形态LLRR二叉树(Binary Tree)n二叉树的定义二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。子树和右子树的、互不相交的二叉树组成。n这个定义是递归的。这个定义是递归的。42n注意，结点的深度和结点的高度是不同的。结点注意，结点的深度和结点的高度是不同的。结点的深度即结点所处层次，是从根向下逐层计算的；的深度即结

25、点所处层次，是从根向下逐层计算的；结点的高度是从下向上逐层计算的：结点的高度是从下向上逐层计算的：叶结点的高叶结点的高度为度为1,其他结点的高度是取它的所有子女结点最其他结点的高度是取它的所有子女结点最大高度加一。大高度加一。n例如，例如，E的高度为的高度为4，深，深度为度为3.n树的深度与高度相等。树的深度与高度相等。树的深度按离根最远的树的深度按离根最远的叶结点算，树的高度按叶结点算，树的高度按根结点算，都是根结点算，都是6。ABCDEGHILJ高度=4深度=343二叉树的性质性质性质1 若二叉树的层次从若二叉树的层次从 1 开始开始,则在二叉树的第则在二叉树的第 i 层层最多有最多有 2

26、i-1 个结点。个结点。(i1)性质性质2高度为高度为 h 的二叉树最多有的二叉树最多有 2h-1个结点。个结点。(h1)性质性质3对任何一棵二叉树对任何一棵二叉树,如果其叶结点有如果其叶结点有 n0 个个,度为度为2的非叶结点有的非叶结点有 n2 个个,则有则有 n0n2144n例题：如果已知二叉树只有度为例题：如果已知二叉树只有度为 2 和度为和度为 0 的结的结点。且度为点。且度为 0 的结点有的结点有 17 个，度为个，度为 2 的结点应有的结点应有16 个。该二叉树最大高度为个。该二叉树最大高度为17，最小高度？，最小高度？n已知二叉树各个结点的度为已知二叉树各个结点的度为 di,i

27、=1,2,n，则所有结，则所有结点的度之和应等于树的分支点的度之和应等于树的分支数数n-1。n已知二叉树有已知二叉树有 n 个结点，则其最大高个结点，则其最大高度（深度）为度（深度）为 n，最小高度？，最小高度？ABCDEGILJ45定义定义1 满二叉树满二叉树(Full Binary Tree)定义定义2 完全二叉树完全二叉树(Complete Binary Tree)r若设二叉树的高度为若设二叉树的高度为 h，则共有，则共有 h 层。除第层。除第 h 层外，其它各层层外，其它各层(1h-1)的结点数都达到最大的结点数都达到最大个数，第个数，第 h 层从右向左连续缺若干结点，这就层从右向左连

28、续缺若干结点，这就是完全二叉树。是完全二叉树。46性质性质4具有具有 n(n0)个结点的完全二叉树的高度为个结点的完全二叉树的高度为 log2(n+1)证明：证明：设完全二叉树的高度为设完全二叉树的高度为 h，则有，则有 2h-1-1n 2h-1 上面上面h-1层层结点数结点数 包括包括第第h层层的最大结点数的最大结点数变形变形 2h-1n+12h 取对数取对数 h-1log2(n+1)h 有有 h=log2(n+1)23-124-147注意：注意：n如果仅知道完全二叉树的叶结点个数如果仅知道完全二叉树的叶结点个数 n0，也能够，也能够求高度：求高度：h=log2n0 +1n若设完全二叉树中叶

29、结点有若设完全二叉树中叶结点有 n0 个个,则该二叉树总则该二叉树总的结点数为的结点数为 n=2n0,或或 n=2n0 1。n若完全二叉树的结点数若完全二叉树的结点数为奇数，没有度为为奇数，没有度为 1 的的结点；为偶数，有一个结点；为偶数，有一个度为度为 1 的结点。的结点。48leftChild data rightChilddataleftChildrightChild左子女指针 右子女指针二叉树的二叉链表表示n使用二叉链表，找子女的时间复杂度为使用二叉链表，找子女的时间复杂度为O(1)，找，找双亲的时间复杂度为双亲的时间复杂度为O(log2i)O(i)，其中，其中，i 是是该结点编号。

30、该结点编号。49二叉树的定义typedef char ElemType;/树结点数据类型typedef struct node /树结点定义 ElemType data;/结点数据域 struct node*leftChild,*rightChild;/子女指针域 BinTreeNode;typedef BinTreeNode*BinTree;/树定义，代表树的根指针 50n按按层次层次次序遍历树的结果次序遍历树的结果 -+/a*e f b c dn层次次序遍历算法的实现层次次序遍历算法的实现要求使用一个队列，在处要求使用一个队列，在处理上一层时把下一层结点理上一层时把下一层结点预先进队，当上

31、一层的结预先进队，当上一层的结点都出队并处理完后，下点都出队并处理完后，下一层结点已经到了队头，一层结点已经到了队头，可以继续处理。可以继续处理。层次次序遍历层次次序遍历d51void levelOrder(BinaryTree&T)if(T.root=NULL)return;Queue Q;initQueue(Q);BinTreeNode*p=T.root;cout data leftChild!=NULL)cout leftChild-data leftChild);层次次序遍历算法层次次序遍历算法52 if(p-rightChild!=NULL)cout rightChild)-data

32、 rightChild);n例题：利用这个算法，可以计算二叉树各层的例题：利用这个算法，可以计算二叉树各层的结点个数，只要对每一层加一个控制变量。为结点个数，只要对每一层加一个控制变量。为了提高遍历效率，可把队列嵌入程序。了提高遍历效率，可把队列嵌入程序。void Num-Level(BinaryTree T,int n)BinTreeNode*p;53BinTreeNode*Qn;int front=0,rear=0;rear+;Qrear=T;int level=1,last=1,count=0;while(front!=rear)front=(front+1)%n;p=Qfront;co

33、unt+;if(p-leftChild!=NULL)rear=(rear+1)%n;Qrear=p-leftChild;54 if(p-rightChild!=NULL)rear=(rear+1)%n;Qrear=p-righttChild;if(front=last)cout level count endl;level+;last=rear;count=0;55图的基本概念图的基本概念最小生成树最小生成树最短路径最短路径 活动网络活动网络第八章第八章 图图56图的基本概念图的基本概念n图定义图定义r图是由顶点集合图是由顶点集合(vertex)及顶点间的关系集合及顶点间的关系集合组成的一种数

34、据结构：组成的一种数据结构：Graph(V,E)r其中，其中，V=x|x 某个数据对象某个数据对象 是顶点的是顶点的有穷非空集合；有穷非空集合；E=(x,y)|x,y V 或或 E=|x,y V&Path(x,y)是顶点之间是顶点之间关系的有穷集合，也叫做边关系的有穷集合，也叫做边(edge)集合。集合。Path(x,y)表示从表示从 x 到到 y 的一条单向通路的一条单向通路,它是有方它是有方向的。向的。57n有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对 是是有序的。在无向图中，顶点对有序的。在无向图中，顶点对(x,y)是无序的。是无序的。n完全图完全图 若有若有 n

35、个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边条边,则此图为完全无向图。有则此图为完全无向图。有 n 个顶点的有向图有个顶点的有向图有n(n-1)条边条边,则此图为完全有向图。则此图为完全有向图。完全无向图完全无向图 无向图（自由树）无向图（自由树）有向图有向图 完全有向图完全有向图0000111122226543358 n邻接顶点邻接顶点 如果如果(u,v)是是 E(G)中的一条边，则称中的一条边，则称 u 与与 v 互为邻接顶点。互为邻接顶点。n子图子图 设有两个图设有两个图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子

36、图。n权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为权。这称之为权。这种带权图叫做网络。种带权图叫做网络。0123子图013012302359n顶点的度顶点的度 一个顶点一个顶点 v 的度是与它相关联的边的条的度是与它相关联的边的条数。记作数。记作TD(v)。在有向图中在有向图中,顶点的度等于该顶顶点的度等于该顶点的入度与出度之和。点的入度与出度之和。n顶点顶点 v 的入度的入度是以是以 v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v);顶点顶点 v 的出度的出度是以是以 v 为始点的有向边的条为始点的有向边的条数数,记作记作 OD(v)。n路径路径 在图

37、在图 G(V,E)中中,若从顶点若从顶点 vi 出发出发,沿一些沿一些边经过一些顶点边经过一些顶点 vp1,vp2,vpm，到达顶点到达顶点vj。则则称顶点序列称顶点序列(vi vp1 vp2.vpm vj)为从顶点为从顶点vi 到顶点到顶点 vj 的路径。它经过的边的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于应是属于E的边。的边。60n连通图与连通分量连通图与连通分量 在无向图中在无向图中,若从顶点若从顶点v1到顶点到顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通的。如果图中任意是连通的。如果图中任意一对顶点都是连通的一对顶点都是连通的,则称

38、此图是连通图。则称此图是连通图。n非连通图的极大连通子图叫做连通分量。非连通图的极大连通子图叫做连通分量。n强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中,若对于每一若对于每一对顶点对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是强连通图。则称此图是强连通图。n非强连通图的极大强连通子图叫做强连通分量。非强连通图的极大强连通子图叫做强连通分量。n生成树生成树 一个连通图的生成树是其极小连通子图，一个连通图的生成树是其极小连通子图，在在 n 个顶点的情形下，有个顶点的情形下，有n-1条边。条边。61最小生成树最小生成树(mini

39、mum cost spanning tree)n使用不同的遍历方法，可得到不同的生成树；从使用不同的遍历方法，可得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。不同的顶点出发，也可能得到不同的生成树。n按照生成树的定义，按照生成树的定义，n 个顶点的连通带权图的生个顶点的连通带权图的生成树有成树有 n 个顶点、个顶点、n-1 条边。条边。n构造最小生成树的准则构造最小生成树的准则r必须使用且仅使用该带权图中的必须使用且仅使用该带权图中的n-1 条边来联条边来联结网络中的结网络中的 n 个顶点；个顶点；r不能使用产生回路的边；不能使用产生回路的边；r各边上的权值的总和达到最小。各边上

40、的权值的总和达到最小。62n注意：当各边有相同权值时，由于选择的随意性，注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。当各边的权值不相同产生的生成树可能不唯一。当各边的权值不相同时，产生的生成树是唯一的。时，产生的生成树是唯一的。63最短路径最短路径(Shortest Path)n最短路径问题：如果从图中某一最短路径问题：如果从图中某一顶点顶点(称为源点称为源点)到达另一顶点到达另一顶点(称为终点称为终点)的路径可能不止一条，的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值如何找到一条路径使得沿此路径上各边上的权值总和达到最小。总和达到最小。n问题解法问题解

41、法r 边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题 Dijkstra算法算法r 所有顶点之间的最短路径所有顶点之间的最短路径 Floyd算法算法64边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题n问题的提法：给定一个带权有向图问题的提法：给定一个带权有向图 D 与与源点源点 v，求从求从 v 到到 D 中其它顶点的最短路径。限定各边上中其它顶点的最短路径。限定各边上的权值大于或等于的权值大于或等于0。n为求得这些最短路径，为求得这些最短路径，Dijkstra 提出按路径长度提出按路径长度的递增次序的递增次序,逐步产生最短路径的算法。首先求逐步产生最

42、短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。到其它各顶点的最短路径全部求出为止。n举例说明举例说明65Dijkstra算法的算法的逐步逐步求解的过程求解的过程10432101003050206010最短路径最短路径 路径长度路径长度源源 终终12341234v0v1(v0,v1)10v2(v0,v1,v2)(v0,v3,v2)60 50v3(v0,v3)30v4(v0,v4)(v0,v3,v4)(v0,v3,v2,v4

43、)10090 6066活动网络活动网络(Activity Network)n计划、施工过程、生产流程、程序流程等都是计划、施工过程、生产流程、程序流程等都是“工程工程”。除了很小的工程外，一般都把工程分为。除了很小的工程外，一般都把工程分为若干个叫做若干个叫做“活动活动”的子工程。完成了这些活动，的子工程。完成了这些活动，这个工程就可以完成了。这个工程就可以完成了。n例如，计算机专业学生的学习就是一个工程，每例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有些课程要求先修课程

44、，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地有的课程之间有领先关系，有的课程可以并行地学习。学习。拓扑排序拓扑排序67课程代号课程代号课程名称课程名称先修课程先修课程C1高等数学高等数学C2程序设计基础程序设计基础C3离散数学离散数学C1,C2C4数据结构数据结构C3,C2C5高级语言程序设计高级语言程序设计C2C6编译方法编译方法C5,C4C7操作系统操作系统C4,C9C8普通物理普通物理C1C9计算机原理计算机原理C868学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C269n可以用可以用有向图有向图表示一个工程。在这种有向图中，表示一个工程。在这

45、种有向图中，用顶点表示活动用顶点表示活动，用有向边用有向边表示表示活动活动Vi 必必须先于活动须先于活动Vj 进行。这种有向图叫做顶点表示活进行。这种有向图叫做顶点表示活动的动的AOV网络网络(Activity On Vertices)。n在在AOV网络中不能出现有向回路网络中不能出现有向回路,即有向环。如即有向环。如果出现了有向环，则意味着某项活动应以自己作果出现了有向环，则意味着某项活动应以自己作为先决条件。为先决条件。n因此，对给定的因此，对给定的AOV网络，必须先判断它是否存网络，必须先判断它是否存在有向环。在有向环。70n检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造

46、它的拓网络构造它的拓扑有序序列。即将各个顶点扑有序序列。即将各个顶点(代表各个活动代表各个活动)排列排列成一个线性有序的序列，使得成一个线性有序的序列，使得AOV网络中所有应网络中所有应存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。n这种这种构造构造AOV网络全部顶点的拓扑有序序列的运网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。算就叫做拓扑排序。n在在AOV网络的拓扑有序序列中，不是任意两个顶网络的拓扑有序序列中，不是任意两个顶点点vi和和vj都存在从都存在从vi到到vj的路径，如果顶点的路径，如果顶点vi在拓在拓扑有序序列中排在顶点扑有序序列中排在顶点vj的后面，就

47、不存在从的后面，就不存在从vi到到vj的路径。的路径。71n例如例如,对学生选课工程图进行拓扑排序对学生选课工程图进行拓扑排序,得到的拓得到的拓扑有序序列为扑有序序列为 C1,C2,C3,C4,C5,C6,C8,C9,C7或或 C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C272关键路径关键路径n如果在无有向环的带权有向图中，如果在无有向环的带权有向图中，用有向边表示用有向边表示一个工程中的活动一个工程中的活动(Activity),用边上权值表示活用边上权值表示活动持续时间动持续时间(Duration),用顶点表示事件用顶点表示事件(Event),则这样

48、的有向图叫做用边表示活动的网络，简称则这样的有向图叫做用边表示活动的网络，简称 AOE(Activity On Edges)网络。网络。nAOE网络在某些工程估算方面非常有用。例如，网络在某些工程估算方面非常有用。例如，可以使人们了解：可以使人们了解：r完成整个工程至少需要多少时间（假设网络完成整个工程至少需要多少时间（假设网络中没有环）中没有环）?r为缩短完成工程所需的时间，应当加快哪些为缩短完成工程所需的时间，应当加快哪些活动活动?73n从开始点到各个顶点，以至从开始点到结束点的从开始点到各个顶点，以至从开始点到结束点的有向路径可能不止一条。这些路径的长度也可能有向路径可能不止一条。这些路

49、径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程但只有各条路径上所有活动都完成了，整个工程才算完成。才算完成。n因此，因此，完成整个工程所需的时间取决于从源点到完成整个工程所需的时间取决于从源点到汇点的最长路径长度汇点的最长路径长度，即在这条路径上所有活动，即在这条路径上所有活动的持续时间之和。的持续时间之和。这条路径长度最长的路径就叫这条路径长度最长的路径就叫做关键路径做关键路径(Critical Path)。n要找出关键路径，必须找出要找出关键路径，必须找出关键活动关键活动，即不按期，即不按期完

50、成就会影响整个工程完成的活动。完成就会影响整个工程完成的活动。74注意注意n所有顶点按拓扑有序的次序编号所有顶点按拓扑有序的次序编号n仅计算仅计算 Vei 和和 Vli 是不够的，还须计算是不够的，还须计算 ek 和和 lk。n不是任一关键活动加速一定能使整个工程提前。不是任一关键活动加速一定能使整个工程提前。n想使整个工程提前，要考虑各个关键路径上所有想使整个工程提前，要考虑各个关键路径上所有关键活动关键活动，或，或缩短所有关键路径上共有的活动缩短所有关键路径上共有的活动。75第九章 查找二叉排序树二叉排序树平衡二叉树平衡二叉树B+树树散列散列76二叉排序树(Binary Search Tr