二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(22)

例：某工程的AOE网如下，求1) 整个工程完工需要多长时间，2) 关键路径。说明：图中的虚线仅表示事件的先后关系，不代表具体活动。

分析：按照拓扑有序排列顶点，然后“从前往后”计算事件的最早发生时间得到总时间，再“从后往前”计算事件的最晚发生时间，最后计算活动的最早和最晚开始时间得到关键活动和关键路径。

表 错误！文档中没有指定样式的文字。.12 关键路径

所以，1) 工程完工需要时间15，2) 关键路径是1?2?5?6?8?9。 最短路径

迪杰斯特拉算法

求一个顶点到其他各顶点的最短路径。

算法：(a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞； (b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径； (c) 修改最短路径：计算u的邻接点的最短路径，若(v,?,u)+(u,w)<(v,?,w)，则以(v,?,u,w)代替。

(d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。 特点：总是按照从小到大的顺序求得最短路径。

例：用迪杰斯特拉算法求下图中A到其余顶点的最短路径。

(比原来)有更短路径即可，这弗洛伊德算法

求每对顶点之间的最短路径。

(0)(1)(n)(0)(k)(k)(k-1)

依次计算A，A，?，A。A为邻接矩阵，计算A时，A(i,j)=min{A(i,j), (k-1)(k-1)

A(i,k)+A(k,j)}。

(k)

技巧：计算A的技巧。第k行、第k列、对角线的元素保持不变，对其余元素，考查A(i,j)

20

与A(i,k)+A(k,j) （“行+列”），如果后者更小则替换A(i,j)，同时修改路径。

例：用弗洛伊德算法计算图中各顶点之间的最短路径。

20

第k列i“行”元素加上第k行j“列”元素。

A

AAA

3第4列也不变，这样，只剩下A(4,2)和A(4,3)需要计算。

查找

基础知识和算法 有关概念

查找表，静态查找表（只进行“查找”），动态查找表（可“查找”，“插入”，“删除”）。 关键字，平均查找长度

ASL??pici

i?1n

pi第i个关键字出现的概率，ci比较的关键字的个数。

静态查找表，顺序查找表，折半查找表，静态树表，次优查找树，索引顺序表。 动态查找表，二叉排序树，平衡二叉树（L树），B-树，B+树，键树，哈希表。 顺序查找

思路

按顺序逐个比较，直到找到或找不到。

算法

程序，要灵活应用。

例如：在数组a的前n个元素中查找x int Search ( int a[], int n, int x ) {

for ( i=n-1; i>=0; i-- )if ( a[i]==x ) return i; return -1; // -1表示找不到 }

编程技巧：所有执行路径都要有正确的返回值，不要忘记最后那个return语句。 应试技巧：题目要求不明确时，按照方便的方法做，用适当的注释说明。

分析

顺序查找特点：思路简单(逐个比较)，适用面广(对查找表没有特殊要求)。

平均查找长度

一般在等概率情况下，查找成功时，平均查找长度 ASL?1?2?...?nn?1 ?n2

思路：假设对每个元素进行1次查找，共进行n次查找，计算出进行比较的关键字的个数，然后除以查找次数n，就求得平均查找长度。

例：10个元素的表等概率情况下查找成功时的平均查找长度 ASL?1?2?...?10?5.5 10

判定树

判定树是一种描述查找中比较过程的直观形式，

个关键字所在层次就是其查找长度，有利于分析

找过程。顺序查找的判定树是一棵深度为n的单

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-22.html