02-与查找算法相关的概念

9.1　与查找算法相关的概念

• 查找表 （search table）：由同一种类型的数据元素构成的集合。查找表中的数据元素是完全松散的，数据元素之间没有直接的联系。
• 查找 （search）：根据关键字在特定的查找表中找到一个与给定关键字相同的数据元素的操作。如果在查找表中找到相应的数据元素，则查找是成功的；否则，查找是失败的。例如，表9.1所示为学生学籍信息。如果要查找入学年份为“2008”并且姓名是“刘*平”的学生，则可以先利用姓名将记录定位（如果有重名的），然后查找入学年份为“2008”的记录。

| 学号 | 姓名 | 性别 | 出生年月 | 所在院系 | 籍贯 | 入学年份 | | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | | 200609001 | 张 | 男 | 1988.09 | 信息管理 | 陕西西安 | 2006 | | 200709002 | 王 | 女 | 1987.12 | 信息管理 | 四川成都 | 2007 | | 200909107 | 陈 | 女 | 1988.01 | 通信工程 | 安徽合肥 | 2009 | | 200809021 | 刘平 | 男 | 1988.11 | 计算机科学 | 江苏常州 | 2008 | | 200709008 | 赵* | 女 | 1987.07 | 法学院 | 山东济宁 | 2007 |

• 关键字 （key）：数据元素中某个数据项的值。如果该关键字可以将所有的数据元素区别开来，也就是说，可以唯一标识一个数据元素，则该关键字称为主关键字；否则，称为次关键字。特别地，如果数据元素只有一个数据项，则数据元素的值就是关键字。
• 静态查找 （static search）：仅仅在数据元素集合中查找是否存在与关键字相等的数据元素。在静态查找过程中使用的存储结构称为静态查找表。
• 动态查找 （dynamic search）：在查找过程中，同时在数据元素集合中插入某个数据元素，或者在数据元素集合中删除某个数据元素。动态查找过程中使用的存储结构称为动态查找表。
• 平均查找长度 （Average Search Length，ASL）：在查找过程中，需要比较关键字的平均次数，它是衡量查找算法效率的标准。平均查找长度的数学定义为
• 。其中，P_i表示查找表中第i个数据元素出现的概率，C_i表示在找到第i个数据元素时，与关键字比较的次数。