配套课件 数据结构（C语言版）（第二版）.ppt

7.1 查找的基本概念 查找的基本概念 3.查找表（search table） 由同一数据类型的数据元素构成的数据集合，可以是一个数组或一个链表等数据类型。 (1) 静态查找表(Static Search Table) 如果一个查找表的操作只涉及查询某个特定的数据元素是否在查找表中或者检索满足条件的某个特定的数据元素的各属性值，无须修改查找表，这类查找表称为静态查找表。 静态查找表适用于：查找表一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作。 7.1 查找的基本概念 查找的基本概念 3.查找表（search table） 由同一数据类型的数据元素构成的数据集合，可以是一个数组或一个链表等数据类型。 (2) 动态查找表(Dynamic Search Table) 如果对一个查找表的操作在查找的同时需要动态地插入或删除的查找表则称为动态查找表。 动态查找表适用于：查找与插入或删除操作在同一个阶段进行，例如，在某些问题中，当查找成功时，要删除查找的记录，当查找不成功时，要插入被查找的记录。 7.1 查找的基本概念 查找的基本概念 4.查找算法的时间复杂度 对于不同的数据结构，有不同的查找方法，也有不同的查找效率。而在查找中，要衡量一种查找算法的优劣，主要是看要查找的值与关键字的比较次数。因此，通常把查找过程中对关键字的最多比较次数和平均比较次数作为衡量一个查找算法效率优劣两个基本技术指标。 前者叫做最大查找长度（Maximun Search Length），简记为MSL。 后者叫做平均查找长度（Average Search Length），简记ASL，其计算公式定义为： ASL= 6.5 最短路径 单源点到其余各顶点的最短路径 if(!s[w]dist[w]min) { v=w; min=dist[w]; } } s[v]=1;/*顶点v并入s*/ for(j=0;jG.n;j++) { //更新当前最短路径及距离 if(!s[j](min+ G.arcs[v][j]dist[j])) { dist[j]=min+G.arcs[v][j]; path[j]=v; } }}} 6.6 AOV网与拓扑排序 6.6 AOV网与拓扑排序 AOV网 在一个有向图中，若用顶点表示活动，有向边表示活动间的先后关系，称该有向图为用顶点表示活动的网络(Activity On Vertex network，AOV) 。 若从顶点vi到顶点vj之间存在一条有向路径，称顶点vi是顶点vj的前驱，或者称顶点vj是顶点vi的后继。即若vi，vj是图中的边，则称顶点vi是顶点vj的直接前驱，顶点vj是顶点vi的直接后继。 现代化管理中，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。在整个工程实施过程中，有些活动开始是以它的所有前序活动的结束为先决条件的，必须在其他有关活动完成之后才能开始，有些活动没有先决条件，可以安排在任意时间开始。 AOV网就是一种可以形象地反映出整个工程中各个活动之间前后关系的有向图。 6.6 AOV网与拓扑排序 拓扑排序 拓扑排序(Topological Sort)是图中重要的运算之一，在实际中应用很广泛。 因此，对给定的AOV网应首先判定网中是否存在环。检测的办法是对有向图进行拓扑排序（Topological Sort），拓扑排序指按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑排序序列。 6.6 AOV网与拓扑排序 拓扑排序 1.拓扑排序的定义 给出有向图G=(V，E)，对于V中的顶点的线性序列(v1，v-2，…，vk)，如果满足如下条件：若在G中从顶点vi到vj有一条路径，则在序列中顶点vi必在顶点vj之前，称该序列为G的一个拓扑序列。构造有向图的拓扑序列的过程称为拓扑排序。 6.6 AOV网与拓扑排序 拓扑排序 1.拓扑排序的定义 (1) 拓扑排序的注意事项 关于拓扑排序我们需要注意以下几点： ① 在AOV网中，若不存在回路，则所有活动可排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，那么该序列为拓扑序列。 ② 拓扑序列不是唯一的。 ③ 对AOV网不一定都有拓扑序列。 ④ 将AOV图中顶点排成一个线性序列，若该线性序列中包含AOV网全部的顶点，则AOV网中无环，否则，AOV网中存在有向环，该网所代表的工程是不可行的。