发布时间 : 星期六 文章数据结构-朱二周更新完毕开始阅读
7关键路径
7.1 AOE网概念定义：若在带权的有向图中,以顶点表示事件,有向边表示活动,边上的权值表示完成该活动的开销(如该活动所需的时间),则称此带权的有向图为用边表示活动的网络,简称AOE网(Activity On Edge) 说明：
(1) AOV网与AOE网有密切关系又有不同。如果用他们表示工程，AOV网表
示各个子工程之间的优先关系，是定性关系；在AOE网中还要体现完成各个子工程的确切时间，是定量关系。对于AOE网，我们关心的问题是：（A）完成整个工程至少需要多少时间？（B）哪些活动是关键活动：哪些活动的进度是影响整个工程进度的关键？
(2) 在AOE网中，只有在某顶点所代表的事件发生后，从该顶点出发的各有
向边所代表的活动才能开始。只有在进入每顶点的各有向边所代表的活动都已经结束后，该顶点所代表的事件才能发生。
(3) 在一个表示工程的AOE网中，应该不存在回路，网中仅存在一个入度为
零的顶点，乘作开始顶点，它表示了整个工程的开始；网中仅存在一个出度为零的顶点，称为结束顶点，它表示整个工程的结束。
7.2关键路径有关术语
路径长度：AOE网中一条路径的长度是该路径上个活动所需时间的总和。
关键路径：AOE网中,从开始顶点到结束顶点之间路径长度中的最大路径为关键
路径。由于AOE网中某些子工程（活动）可以同时进行，要保证每个子工程都能完成，完成该工程的最少时间就是该工程AOE网的关键路径长度。
事件的最早发生时间：事件vi的最早发生时间ve(i)是从开始顶点v到vi的最长路径长度。
活动的最早开始时间：活动aj的最早开始时间e (j)是该活动的起点所表示的
事件最早发生时间,如果由边(vi,vk)表示活动aj,则有e(j)=ve(i)。
事件的最迟发生时间：事件vk的最迟发生时间vl(k)是在不推迟整个工程完成
(即保证结束顶点vn在ve(n)时刻发生)的前提下,该事件最迟必须发生的时间。vl（k）为ve（n）减去顶点vk到结束顶点vn的最长路径的长度。
活动的最迟开始时间：活动aj的最迟开始时间l(j)是该活动的终点所表示的事
件最迟发生时间与该活动的所需时间之差。如果由边(vi,vk)表示活动aj,则有l(j)=vl（k）-aj所需时间。
时间余量：活动aj的 l(j)-e(j)是该活动完成的时间余量。它是在不增加完成
整个工程所需时间的情况下，活动aj可以拖延的时间。
关键活动：当一活动的时间余量=0，说明该活动必须如期完成，否则就会拖延完
成整个工程的进度。若活动aj的时间余量=0，则称该活动为关键活动。当时间余量〉0，活动aj不是关键活动，只要拖延的时间不超过时间余量，就不会影响整个工程的进度；但如果拖延的时间超过时间余量，则关键活动就可能发生变化。
7.3关键路径的求解过程与算法。 8最短路径问题
8.1单源最短路径—用Dijkstra（迪杰斯特拉）算法
单源点最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。
迪杰斯特拉(Dijkstra)提出了按路径长度递增序产生各顶点的最短路径算法,我们称之为迪杰斯特拉算法。
算法的基本思想是：把图中顶点集合分成两组，第一组为集合S，存放已求出其最短路径的顶点，第二组为尚未确定最短路径的顶点集合是V-S（用U表示），其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个把U中的顶点加到S中，直到S中包含全部顶点，而U为空。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
算法的具体步骤：
（1）初始时，S只包含源点，S={v}，v的距离为0。U包含除v外的其他顶
点，U中顶点的距离为顶点的权或∞ 。
（2）从U中选取一个距离最小的顶点k，把k加入到S中。 （3）以k 作为新考虑的中间点，修改U中各顶点的距离。 （4）重复步骤（2）、（3）直到所有顶点都包含在S中。 8.2所有顶点间的最短路径—用Floyd（弗洛伊德）算法
所有顶点间的最短路径是指：给定一个有向网G=(V，E),求出其中任意两点之间的最短路径。 （二）基本要求
熟悉图的定义和术语，掌握图的邻接矩阵存储结构和邻接矩阵存储结构，理解图的遍历操作，了解图的几个典型问题。 （三）重点、难点
本章是课程的重点内容之一，且内容较多。(1)图的两种遍历策略：深度优先搜索和广度优先搜索；(2)求解最小生成树；(3)求解关键路径；(4)图的两类最短路径问题的解法。 （四）作业及课外学习要求：
(1) 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i不等于j)。 (2) 试基于图的广度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i不等于j)。 (3) 给出图G：（1）画出G的邻接表表示图；（2）根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。
(4) 已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。
本知识点的讲授和学习，可以支撑“毕业要求1工程知识”中的“指标点1.1和1.2能够运用数学与自然科学基础知识，理解软件工程中涉及的相关科学
原理；能够运用软件工程基础知识，解决复杂软件工程中涉及的相关工程问题”，使学生掌握将工程基础知识和本专业的基本理论知识向结合，锻炼学生的工程实践能力，并为后续课程的学习奠定理论基础。
第8章 查找 ( 8学时) （1）基本内容 1静态查找表
静态查找表：若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。 1.1顺序表的查找
基本思想：是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。 1.2有序表的查找
基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功，否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。 1.3索引顺序表的查找
在建立顺序表的同时，建立一个索引。索引顺序表 = 索引 + 顺序表
2动态查找表
有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。
2.1二叉排序树
在二叉排序树中进行查找的过程和二分查找类似，也是一个逐步缩小查找范围的过程。若查找成功，则是走了一条从根结点到待查结点的路径；若查找失败，则是走了一条根结点到某个叶子结点的路径。因此，查找过程中和关键字比较的
次数不超过树的深度。由于含有n个结点的二叉排序树不唯一，形态和深度可能不同。故含有n个结点的二叉排序树的平均查找长度和树的形态有关。
最好的情况是： 二叉排序树和二叉判定树形态相同。
最坏的情况是： 二叉排序树为单支树，这时的平均查找长度和顺序查找时
相同。
就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无须大量移动结点。 2.2平衡二叉树
1）如果建立的二叉查找树的左右子树深度之差的绝对值不超过1，则称为平衡二叉树 2）最佳二叉查找树就是平均查找长度最短的二叉查找树，它的结点构成上的特点是：除了最下一层可以不满外，其他各层都是充满了的。 2.3B－树和B＋树 (1) B－树
B-树是一种平衡的多路查找树：在m阶的B-树上，每个非终端结点可能含有：
n 个关键字 Ki（1≤ i≤n） n int keynum; // 结点中关键字个数，结点大小 struct BTNode *parent; // 指向双亲结点的指针 KeyType key[m+1]; // 关键字（0号单元不用） struct BTNode *ptr[m+1]; // 子树指针向量 Record *recptr[m+1]; // 记录指针向量 } BTNode, *BTree; // B树结点和B树的类型 B-树特点： (1)非叶结点中的多个关键字均自小至大有序排列，即：K1< K2 < ? < Kn;且 Ai-1 所指子树上所有关键字均小于Ki; (2)Ai 所指子树上所有关键字均大于Ki; (3)树中所有叶子结点均不带信息，且在树中的同一层次上; (4)根结点或为叶子结点，或至少含有两棵子树; (5)其余所有非叶结点均至少含有ém/2ù棵子树，至多含有 m 棵子树; 查找过程： 从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个过程。 交叉进行。若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置。若查找不成功，则返回插入位置。 (2) B+树 是B-树的一种变型。B+树的结构特点： 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值；所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 ?m/2?和 m