数据结构课件 第8章查找.pptVIP

第8章 查找;8.1 查找的基本概念;有了主关键字及关键字后，我们可以给查找下一个完整的定义。所谓查找，就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。;因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先取决于使用哪种数据结构来表示表，即表中结点是按何种方式组织的。 为了提高查找速度，我们经常使用某些特殊的数据结构来组织表。因此在研究各种查找算法时，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。;查找有内查找和外查找之分。若整个查找过程全部在内存中进行，则称这样的查找为内查找；反之，??在查找过程中还需要访问外存，则称之为外查找。 我们仅介绍内查找。;要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准。 对于一个含有n个元素的表，查找成功时的平均查找长度可表示为 其中pi为查找第i个元素的概率，且 。一般情形下我们认为查找每个元素的概率相等，ci为查找第i个元素所用到的比较次数。;8.2 线性表的查找8.2.1 顺序查找1. 顺序查找的基本思想;顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。;2. 顺序查找算法实现;// 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为 // 该元素在表中的位置，否则为0。算法9.1 int Search_Seq(SSTable ST,KeyType key) { int i; ST.elem[0].key=key; // 哨兵 for(i=ST.length;!EQ(ST.elem[i].key,key);--i) ; // 从后往前找 return i; // 找不到时，i为0 };在函数Search_Seq中，若返回的值为0表示查找不成功，否则查找成功。 函数中查找的范围从R[n]到R[1]，R[0]为监视哨，起两个作用： 其一，是为了省去判定循环中下标越界的条件i≥1，从而节省比较时间； 其二，保存要找值的副本，若查找时，遇到它，表示查找不成功。 若算法中不设立监视哨R[0]，程序花费的时间将会增加。;3. 顺序查找性能分析;顺序查找的优点是算法简单，对表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序，它都同样适用。 顺序查找的缺点是查找效率低，当n较大时，不宜采用顺序查找，而必须寻求更好的查找方法。;8.2.2 二分查找1. 二分查找的基本思想;二分查找的基本思想是： ①首先将待查值K与有序表R[1]到R[n]的中点mid上的关键字R[mid].key进行比较，若相等，则查找成功； ②否则，若R[mid].keyk， 则在R[1]到R[mid-1]中继续查找，若有R[mid].keyk ， 则在R[mid+1]到R[n]中继续查找。 ③每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空（表示查找失败）。 从上述查找思想可知，每进行一次关键字比较，区间数目增加一倍，故称为二分（区间一分为二），而区间长度缩小一半，故也称为折半（查找的范围缩小一半）。;例如，假设给定有序表中关键字为8,17,25,44,68,77,98,100,115,125，将查找K=17和K=120的情况描述为如下图的形式。;图 查找K=17的情形（成功）;查找K=120;图 查找K=120的情形（不成功）;2. 二分查找算法实现;3. 二分查找的性能分析;从上图可知，查找根结点68，需一次比较，查找17和100，各需二次比较，查找8、25、77、115各需三次比较，查找44、98、125各需四次比较。;可以得到结论：二叉树第K层结点的比较次数各为k次(根结点为第1层)，而第k层结点数最多为2k-1个。假设该二叉树的深度为h（见P220）， 则二分查找成功的平均查找长度为（假设每个结点的查找概率相等）：;8.2.3 索引顺序查找1. 索引查找的思想;查找步骤分两步进行： ① 对索引表使用折半查找法（因为索引表是有序表）； ② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）。;8.3 树表查找8.3.1 什么是二叉排序树;8.3.2