6.2 查找的基本概念★1◎2
6.2 查找的基本概念★1◎2
查找的基本概念以学生信息表为例进行说明,学生信息表如表6-2所示。
表6-2 学生信息表
学 号 |
姓 名 |
性 别 |
出生年月 |
分 数 |
||
年 |
月 |
日 |
||||
200809001 | 金鑫 | 男 | 1992 | 11 | 10 | 432 |
200809002 | 王凯 | 女 | 1993 | 08 | 08 | 512 |
… | … | … | … | … | … | … |
1.数据项(也称项或字段)
项是具有独立含义的标识单位,是数据不可分割的最小单位,如表6-2中的“学号”、“姓名”、“年”等。项有名和值之分,项名是一个项的标识,用变量定义,而项值是它的一个可能取值,如“200809001”是项“学号”的一个取值。项具有一定的类型,依项的取值类型而定。
2.组合项
由若干项组合构成,如表6-2中的“出生年日”是组合项,可以由“年”、“月”、“日”三项组成。
3.数据元素(记录)
数据元素是由若干项、组合项构成的数据单位,是在某一问题中作为整体进行考虑和处理的基本单位。数据元素有型和值之分,如表6-2中的项名的集合,即表头部分就是数据元素的类型;而一个学生对应的一行数据就是一个数据元素的值,表中全体学生即为数据元素的集合。
4.关键码
关键码是数据元素(记录)中某个项或组合项的值,用它可以标识一个数据元素(记录)。能唯一确定一个数据元素(记录)的关键码,称为主关键码;而不能唯一确定一个数据元素(记录)的关键码,称为次关键码。表中“学号”即可看成主关键码,“姓名”则应视为次关键码,因为可能有同名同姓的学生。
5.查找表
查找表是由具有同一类型(属性)的数据元素(记录)组成的集合,分为静态查找表和动态查找表两类。
静态查找表:仅对查找表进行查找操作,而不能改变的表。
动态查找表:除对查找表进行查找操作外,可能还要向表中插入数据元素或删除数据元素的表。
6.查找
查找(Search)是在数据结构中确定是否存在关键码,等于给定关键码的记录的过程。在表里进行查找的结果有两种:查找成功和查找不成功。
查找成功:是指在表中找到了要查找的记录,一般查找成功时要给出指定元素的位置。
查找不成功:是指在表中没有找到要查找的记录,查找不成功时要给出查找失败的信息,如空记录或空指针等。
7.平均查找长度ASL
衡量查找算法的最主要的指标是平均查找长度(Average Search Length,ASL)。平均查找长度是指在查找过程中进行的关键码比较次数的平均值,其数学定义为:
其中,是要查找记录的出现概率,是查找相应记录需进行关键码比较的次数。
6.2 查找的基本概念★1◎2转载请注明:6.2 查找的基本概念★1◎2