数据结构ch08 查找.pptxVIP

第8章 查找8.1 查找的基本概念提纲8.2 线性表的查找CONTENTS8.3 树表的查找8.4 哈希表查找8.1 查找的基本概念一般情况下，被查找的对象称为查找表，查找表包含一组元素（或记录），每个元素由若干个数据项组成，并假设有能唯一标识元素的数据项，称为主关键字（默认按主关键字查找）。查找定义为：给定一个值k，在含有n个元素的查找表中找出关键字等于k的元素。若找到这样的元素，表示查找成功，返回该元素的信息或该元素在表中的位置；否则查找不成功或者查找失败，返回相应的指示信息。查找表按照操作方式分为静态查找表和动态查找表两类。静态查找表是只作查找操作的查找表，主要操作有查询某个“特定的”数据元素是否在查找表中，检索某个“特定的”数据元素及其属性。动态查找表是在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。查找有内查找和外查找之分。若整个查找过程都在内存进行，则称之为内查找。反之，若查找过程中需要访问外存，则称之为外查找。查找性能评价查找算法中的主要操作是关键字之间的比较，所以通常把查找过程中关键字平均比较次数也就是平均查找长度作为衡量一个查找算法效率优劣的依据。平均查找长度ASL（Average Search Length）定义为其中，n是查找表中元素的个数，pi是查找第i个元素的概率，一般地，除特别指出外，均认为每个元素的查找概率相等，即pi=1/n（1≤i≤n），ci是查找到第i个元素所需的关键字比较次数。 由于查找的结果有查找成功和不成功两种情况，所以平均查找长度也分为成功情况下的平均查找长度和不成功情况下的平均查找长度。成功情况下的平均查找长度指在查找表中找到指定关键字k的元素平均所需关键字比较的次数。不成功情况下的平均查找长度指在查找表中确定找不到关键字k的元素平均所需关键字比较的次数。　　查找表T：含有n个记录。　成功情况下（概率相等）的平均查找长度ASL成功是指找到T中任一记录平均需要的关键字比较次数。　　例如：关键字514879243找到时的比较次数1234567891+2+3+4+5+6+7+8+9= 5ASL成功=9　查找表T：含有n个记录。 不成功情况下的平均查找长度ASL不成功是指查找失败（在T中未查找到）平均需要的关键字比较次数。?x ? T通过关键字比较后确定不在T中平均关键字比较次数8.2 线性表的查找线性表采用顺序表存储，由于顺序表不适合数据修改操作（插入和删除元素几乎需要移动一半的元素）? 顺序表是一种静态查找表。三种线性表查找方法，即顺序查找、折半查找和分块查找算法。顺序表组织：待查找的顺序表直接采用Python列表R[0..n-1]表示。如10个整数关键字序列表示为：R=[1,6,2,5,3,7,9,8,10,4]（不存在相同的关键字）。若待排序表中每个元素除整数关键字外还有其他数据项，可以采用嵌套列表表示。如3个学生元素，每个元素由学号（每个学生的学号是唯一的）和姓名组成，R表示为：R=[[1,Mary],[3,John],[2,Smith]]，其中R[i][0]存放关键字。8.2.1 顺序查找1. 顺序查找算法基本思路从顺序表的一端开始依次遍历，将遍历的元素关键字和给定值k相比较，若两者相等，则查找成功，返回该元素的序号。若遍历结束后，仍未找到关键字等于k的元素，则查找失败，返回-1。默认从顺序表的前端开始遍历。关键字比较def SeqSearch1(R,k):#顺序查找算法1 n=len(R) i=0 while in and R[i]!=k: i+=1#从表头往后找 if i=n: return -1; #未找到返回-1 else: return i#找到后返回其序号i简单比较方法关键字比较设置一个哨兵def SeqSearch2(R,k):#顺序查找算法2 n=len(R) R.append(k) #末尾添加一个哨兵 i=0 while R[i]!=k: i+=1 #从表头往后找 if i==n: return -1 #未找到返回-1 else: return i#找到后返回其序号i由于查找算法主要考虑关键字之间的比较，两个算法的效率差不多说明2. 顺序查找算法分析1）仅考虑查找成功的情况第1个元素即R[0]=k，1次关键字比较。第2个元素即R[1]=k，2次关键字比较。以此类推，第n个元素即R[n-1]=k，n次关键字比较ci=i+1共有n种查找成功的情况，在等概率时，pi=1/n。2）仅考虑查找不成功的情况 若k值不在表中，则总是需要n次比较之后才能确定查找失败，所以仅仅考虑查找不成功时对应的平均查找长度为：ASL不成功 = n3）既考虑查找成功又考虑查找不成功的情况一个顺序表中顺序查找的全部情况（查找成功和失败）可以用一棵