第8章查找 8.1查找的基本概念 被查找的对象是由一组记录组成的表或文件,而每个记录则 白若千个数据项组成,并假设每个记录都有一个能唯一标识该 记录的关键字。 在这种条件下查找的定义是:给定一个值k,在含有n个记 录的表中找出关键字等于k的记录。若找到查找成功,返回该 记录的信息或该记录在表中的位置;否则查找失败,返回相关 的指示信息
8.1 查找的基本概念 被查找的对象是由一组记录组成的表或文件，而每个记录则 由若干个数据项组成，并假设每个记录都有一个能唯一标识该 记录的关键字。 在这种条件下,查找的定义是：给定一个值k，在含有n个记 录的表中找出关键字等于k的记录。若找到查找成功，返回该 记录的信息或该记录在表中的位置；否则查找失败，返回相关 的指示信息。 第8章 查 找
查找有内查找和外查找之分。若整个查找过程都在内 存进行,则称之为内查找; 反之,若查找过程中需要访问外存,则称之为外查找
查找有内查找和外查找之分。若整个查找过程都在内 存进行，则称之为内查找； 反之，若查找过程中需要访问外存，则称之为外查找
采用何种查找方法? (1)使用哪种数据结构来表示“表”,即表中记录是按 何种方式组织的。 (2)表中关键字的次序。是对无序集合查找还是对有 序集台查找? 若在查找的同时对表做修改运算(如插入和删除), 则相应的表称之为动态查找表,否则称之为静态查找表
采用何种查找方法? （1）使用哪种数据结构来表示“表” ,即表中记录是按 何种方式组织的。 （2）表中关键字的次序。是对无序集合查找还是对有 序集合查找? 若在查找的同时对表做修改运算（如插入和删除）， 则相应的表称之为动态查找表，否则称之为静态查找表
由于查找运算的主要运算是关键字的比较所以通常把查找 过程中对关键字需要执行的平均比较次数(也称为平均查找长 度)作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL( Average search length)定义为: ASL=∑PC 其中,n是查找表中记录的个数。P是查找第个记录的概率, 般地,均认为每个记录的查找概率相等,即=lMm(1n) c是找到第论个记录所需进行的比较次数 平均查找长度分为成功情况下的平均查找长度和不成功 情况下的平均查找长度
由于查找运算的主要运算是关键字的比较,所以通常把查找 过程中对关键字需要执行的平均比较次数（也称为平均查找长 度）作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL（Average Search Length）定义为： = = n i i i ASL p c 1 其中，n是查找表中记录的个数。pi是查找第i个记录的概率， 一般地，均认为每个记录的查找概率相等，即pi=1/n（1≤i≤n）， ci是找到第i个记录所需进行的比较次数。 平均查找长度分为成功情况下的平均查找长度和不成功 情况下的平均查找长度
8.2性表的查找 在表的组织方式中线性表是最简单的一种。三种在线性表 上进行查找的方法: (1)顺序查找 (2)二分查找 (3)分块查找 因为不考虑在查找的同时对表做修改故上述三种查找操作 都是在静态查找表上实现的
8.2 线性表的查找 在表的组织方式中,线性表是最简单的一种。三种在线性表 上进行查找的方法： （1）顺序查找 （2） 二分查找 （3）分块查找 因为不考虑在查找的同时对表做修改,故上述三种查找操作 都是在静态查找表上实现的