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