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