7.1 查找的基本概念

1. 查找。在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找结果分为两种：一是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败。

2. 查找表。用于查找的数据集合称为查找表，由同一类型的数据元素组成，可以是数组、链表等数据类型。对查找表经常进行的操作一般有4种：①查询某个特定的数据元素是否在查找表中；②检索满足条件的某个特定的数据元素的各种属性；③在查找表中插入一个数据元素；④从查找表中删除某个数据元素。

3. 静态查找表。若一个查找表的操作只涉及上述操作①和②，则无须动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、哈希查找等；适合动态查找表的查找方法有二叉排序树的查找、哈希查找等。

4. 关键字。数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如“学号”这一数据项唯一地标识一名学生。

5. 平均查找长度。在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为：$$ASL = \sum_{i=1}^nP_iC_i$$式中，$n$是查找表的长度；$P_i$是查找第$i$个数据元素的概率，一般认为每个数据元素的查找概率相等，即$P_i=l/n$；$C_i$是找到第$i$个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

6.4 图的应用

6.4.1 最小生成树（最小代价树）

概念： 一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边，即生成树是一个包含图的全部顶点的一个极小连通子图。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。

​ 对于一个带权连通无向图G=(V，E)，图G的生成树可能不唯一，对于不同的生成树，每棵树的权(即树中所有边上的权值之和)也可能不同。设R是由G的所有生成树构成的集合，若T为R中边的权值之和最小的那棵生成树，则称T为G的最小生成树(Minimum-Spanning-Tree，MST)。