6.2 查找的基本概念★1◎2

6.2 查找的基本概念★1◎2

　　查找的基本概念以学生信息表为例进行说明，学生信息表如表6-2所示。

表6-2 学生信息表

　　1．数据项（也称项或字段）
　　项是具有独立含义的标识单位，是数据不可分割的最小单位，如表6-2中的“学号”、“姓名”、“年”等。项有名和值之分，项名是一个项的标识，用变量定义，而项值是它的一个可能取值，如“200809001”是项“学号”的一个取值。项具有一定的类型，依项的取值类型而定。
　　2．组合项
　　由若干项组合构成，如表6-2中的“出生年日”是组合项，可以由“年”、“月”、“日”三项组成。
　　3．数据元素（记录）
　　数据元素是由若干项、组合项构成的数据单位，是在某一问题中作为整体进行考虑和处理的基本单位。数据元素有型和值之分，如表6-2中的项名的集合，即表头部分就是数据元素的类型；而一个学生对应的一行数据就是一个数据元素的值，表中全体学生即为数据元素的集合。
　　4．关键码
　　关键码是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素（记录）。能唯一确定一个数据元素（记录）的关键码，称为主关键码；而不能唯一确定一个数据元素（记录）的关键码，称为次关键码。表中“学号”即可看成主关键码，“姓名”则应视为次关键码，因为可能有同名同姓的学生。
　　5．查找表
　　查找表是由具有同一类型（属性）的数据元素（记录）组成的集合，分为静态查找表和动态查找表两类。
　　静态查找表：仅对查找表进行查找操作，而不能改变的表。
　　动态查找表：除对查找表进行查找操作外，可能还要向表中插入数据元素或删除数据元素的表。
　　6．查找
　　查找（Search）是在数据结构中确定是否存在关键码，等于给定关键码的记录的过程。在表里进行查找的结果有两种：查找成功和查找不成功。
　　查找成功：是指在表中找到了要查找的记录，一般查找成功时要给出指定元素的位置。
　　查找不成功：是指在表中没有找到要查找的记录，查找不成功时要给出查找失败的信息，如空记录或空指针等。
　　7．平均查找长度ASL
　　衡量查找算法的最主要的指标是平均查找长度（Average Search Length，ASL）。平均查找长度是指在查找过程中进行的关键码比较次数的平均值，其数学定义为：

　　其中，是要查找记录的出现概率，是查找相应记录需进行关键码比较的次数。