第2章至第7章中已经介绍了各种线性或非线性的数据结构...

第9章查找

第2章至第7章中已经介绍了各种线性或非线性的数据结构,在这一章将讨论另一种在实际应用中大量使用的数据结构——查找表。

查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。

对查找表经常进行的操作有:

(1)查询某个“特定的”数据元素是否在查找表中;

(2)检索某个“特定的”数据元素的各种属性;

(3)在查找表中插入一个数据元素;

(4)从查找表中删去某个数据元素。

若对查找表只作前两种统称为“查找”的操作,则称此类查找表为静态查找表(Static Search Table)。若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类表为动态查找表(Dynamic Search Table)。

所谓“查找”即为在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)。

关键字(Key)是数据元素(或记录)中某个数据项的值,用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录,则称此关键字为主关键字(Primary Key)(对不同的记录,其主关键字均不同)。反之,称用以识别若干记录的关键字为次关键字(Secondary Key)。当数据元素只有一个数据项时,其关键字即为该数据元素的值。

查找(Searching)根据给定的某个值,在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录,则称查找是成功的,查找的结果为给出整个记录的信息,或指示该记录在查找表中的位置;若表中不存在关键字等于给定值的记录,则称查找不成功,此时查找的结果可给出一个“空”记录或“空”指针。

如何进行查找?

显然,在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位。因此,对表进行查找的方法取决于表中数据元素依何种关系(这个关系是人为地加上的)组织在一起的。

[例如],查电号码时,由于电话号码簿是按用户(集体或个人)的名称(或姓名)分类且依笔划顺序编排,则查找的方法就是先顺序查找待查用户的所属类别,然后在此类中顺序查找,直到找到该用户的电话号码为止。[又如],查阅英文单词时,由于字典是按单词的字母在字母表中的次序编排的,因此查找时不需要从字典中第一个单词比较起,而只要根据待查单词中每个字母在字母表中的位置查到该单词。

同样,在计算机中进行查找的方法也随数据结构不同而不同。正如前所述,本章讨论的查找表是一种非常灵便的数据结构。但也正是由于表中数据元素之间仅存在着“同属一个集合”的松散

相关推荐
相关主题
热门推荐