阅读:0       作者:解学武

查找表是什么

在数据结构中,数据之间的逻辑关系归纳为 4 种,分别是无关系、“一对一”、“一对多”和“多对多”。

通过前面章节的学习,我们掌握了用线性结构(线性表)存储“一对一”关系的数据,用结构存储“一对多”关系的数据,用结构存储“多对多”关系的数据。那么,该如何存储无逻辑关系的数据呢?


图 1 无逻辑关系的数据

图 1 中的元素 1、2、3 和 4 之间就不存在任何逻辑关系,增加一个新元素或者删除一个元素,其它元素不会受到影响。

日常工作和生活中,无逻辑关系的数据是最常见的。例如,电话簿中的电话号之间不存在任何逻辑关系,字典中的汉字之间也不存在逻辑关系,数据库表中存储的记录之间也不存在逻辑关系。

数据结构中,将存储无逻辑关系数据的结构称为查找表

查找表是什么

查找表是一种存储结构,专门用来存储无逻辑关系的数据。也可以这样理解,查找表就是一个包含众多元素的集合,表中的各个元素独立存在,之间没有任何关系。

对于无逻辑关系的数据,做的最多的操作就是从中查找某个特定的元素。和有逻辑关系的数据相比,在无逻辑关系的数据中查找特定元素的难度更大。例如,同样是查找一个电话号,在杂乱无章的电话簿中查找既费时又费力,在有序的电话簿中很快就能找到。

原本没有逻辑关系的数据,为了提高查找效率,会人为地给数据赋予一种逻辑关系,继而选用线性表、树或者图结构来存储数据。比如说,为电话簿中的电话号赋予“一对一”的关系,就可以用线性表(顺序表或者单链表)存储电话号。

从名称上看,查找表是一种新的存储结构,但实际上它指的就是用线性表、树或者图结构来存储数据,只不过数据间的逻辑关系是人为赋予的。

数据结构中,将存储无逻辑关系数据的线性表、树或者图结构统称为查找表。

查找表的分类

在查找表中查找特定的元素,常见的操作有以下几种:
  1. 查找特定元素是否在查找表中;
  2. 获取(读取)查找表中某个元素的值;
  3. 查找失败时,将目标元素插入到查找表中;
  4. 查找成功时,将目标元素从查找表中删除。

如果只对查找表做前两种操作,不改变查找表的存储结构,这样的查找表称为静态查找表;反之,如果对查找表做插入或者删除操作,查找表的结构发生了改变,这样的查找表称为动态查找表

动态查找表可以在查找过程中动态建立,而静态查找表只能先建立然后再执行查找操作。

查找算法的性能分析

用不同的存储结构表示查找表,查找特定元素使用的算法会有所区别。哪怕在同一个查找表中,也可以选用不同的查找算法。

一个算法的好坏,可以从时间复杂度空间复杂度两个维度衡量。对于查找算法来说,查找过程中只需要极少量的辅助存储空间,所以各个查找算法的空间复杂度区别不大。多数情况下,我们通过时间复杂度衡量查找算法的好坏。

除了时间复杂度之外,还有一种衡量查找算法好坏的方法。

几乎所有的查找算法执行过程中只做一件事,就是将表中元素逐一和目标元素做比较,因此比较次数的平均值(又称平均查找长度,简称 ASL)可以作为衡量查找算法好坏的依据。

一个查找算法的平均查找长度,可以借助下面的数学公式计算出来:

对公式的说明:
  • n:查找表中的元素数量;
  • Pi:找到第 i 个元素的概率,默认情况下表中各个元素被查找到的概率是相同的,为1/n。在某些特殊场景下,可能会指定表中各个元素被查找到的概率。
  • Ci:和第 i 个元素比较后,算法比较过的总次数。比如第 1 个元素首次和目标元素做比较,那么 C1=1。 

ASL 值越大,表明查找算法的性能越差,执行效率越低。

接下来,我会系统讲解多种查找算法,包括顺序查找算法、折半查找算法、分块查找算法等。待讲到具体的查找算法时,会详细介绍这个公式的用法。