ch10查找.pptVIP

数据结构讲义 第10章　查找 教学要求： 1、理解和掌握：查找的基本思想及相关概念；线性表的顺序、折半和分块查找算法；哈希表的定义、哈希函数的构造、冲突处理方法、查找及分析。 2、了解：二叉查找树、二叉平衡树和B-树查找算法。 内容提要 查找的基本概念 静态查找表 动态查找表 哈希表及其查找 基本概念 查找：查找，也称为检索。我们规定查找是按关键字进行的。 关键字：数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。 主关键字：唯一标识一个数据元素的关键字称为主关键字 次关键字：其它关键字称为辅助关键字或从关键字，次关键字通常不能唯一标志不同元素。 查找表：查找操作针对的对象。查找表是由同一类型的数据元素构成的集合。查找表是一种非常灵活的数据结构。在实际中，我们通常强加给查找表的元素之间一些关系，将它表示某种数据结构（如线性表、二叉树等）。查找算法依赖查找表采用的数据结构。 查找表的四种操作： 查询某个特定的数据元素是否在表中； 查询某个特定元素的各个属性； 在查找表中插入一个数据元素； 从查找表中删除一个数据元素。 静态查找表：只有上面的前两种操作 动态查找表：包括上面四种操作 查找结果：查找成功、查找失败 查找效率 最大查找长度(MSL)：为确定关键字等于给定值的记录在查找表中的位置，需和给定值进行比较次数的最大值称为查找算法查找成功时的最大查找长度。 平均查找长度(ASL)：为确定关键字等于给定值的记录在查找表中的位置，需和给定值进行比较次数的期望值称为查找算法查找成功时的平均查找长度。 静态查找表 静态查找表可以有不同的表示方法，包括顺序表、有序表、索引顺序表等。在不同的表示方法中，实现查找的算法也有所不同。 一、顺序表的查找 顺序查找的基本思想 从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，返回成功位置；若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败，返回－1。 顺序查找既适用于顺序表，也适用于链表。 顺序表查找的实现 首先定义查找表中数据元素类型 #define ElemType int struct Node { …; ElemType key; //key为关键字 }; 算法一：//在表中查找关键字值k, int SeqSearch (Node r[ ],int n,ElemType k) { int i = 0; while ((in) (r[i].key!=k)) i++; if(in) return i; else retur(-1); } 算法二：带监视哨的顺序查找算法 int SeqSearch1 (node r[ ],int n,ElemType k) { int i = 0; r[n].key = k; //监视哨 while ( r[i].key!=k) i++; if(in) return i; else return -1; } 算法分析： 最大查找长度：n 平均查找长度：(n+1)/2 顺序查找的优点是算法简单，对表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序，它都同样适用。顺序查找的缺点是查找效率低，当 n 较大时，不宜采用顺序查找，而必须寻求更好的查找方法。 二、有序表的查找－二分查找法 二分查找法的算法思想 二分查找，也称折半查找，是一种高效率的查找方法。但要求表中元素必须按关键字有序(升序或降序)。不妨假设表中元素为升序排列。 二分查找的基本思想是： 首先将待查值K与有序表r[0]到r[n-1]的中点mid上的关键字r[mid].key进行比较，若相等，则查找成功；否则，若r[mid].keyk ， 则在r[0]到r[mid-1]中继续查找，若有r[mid].keyk ， 则在r[mid+1]到r[n-1]中继续查找。 每通过一次关键字的比较，查找区间的长度就缩小一半。如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)。 示例：假设给定有序表中关键字为05、13、19、21、37、56、64、74、80、88、92，下面讨论查找K=21和K=85的情况。 二分查找法算法的实现 int BiSearch (Node r[ ],int n,ElemType k) { i