T12-基于线性表的查找算法

基于线性表的查找算法第六章

主讲：周翔回顾请思考如何用邻接表来存储图。请简述图的广度优先遍历和深度优先遍历。预习检查请描述一下折半查找的算法思想。请回答构造哈希函数有哪几种方法。本章目标3树表的查找重点了解掌握2哈希表的查找线性表的查找1查找的基本概念查找的定义是在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素。查找的基本概念列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。主关键字：惟一标识列表中的一个数据元素次关键字：不是主关键字，就为次关键字当数据元素仅有一个数据项时，数据元素的值就是关键字查找的基本概念查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。静态查找：在查找过程中只是对数据元素进行查找动态查找：在实际查找的同时，插入找不到的元素，或从查找表中删除已查到的某个元素查找的基本概念查找的基本方法：比较式查找法计算式查找法－HASH（哈希）查找法基于线性表的查找法基于树的查找法查找的基本概念在查找算法中要用到三类参量：①查找对象K（找什么）②查找范围L（在哪找）③查找的结果（K在L中的位置）①、②为输入参量，在函数中不可缺少③为输出参量，可用函数返回值表示查找的基本概念平均查找长度（ASL）：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。平均查找长度（ASL）的计算方式对于长度为n的列表，查找成功时的平均查找长度为：Pi为查找列表中第i个数据元素的概率Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。ASL=P1C1+P2C2+…+PnCn=

i=1nPiCi基于线性表的查找法顺序表的查找法有序表的查找法索引顺序查找法顺序表的查找法基本思想：从表的一端开始，顺序扫描线性表，依次将扫描到的元素的关键字与给定的关键字k相比较。若当前扫描到的结点关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字与k相等的元素，则查找失败。dagw…kqo顺序表的查找法平均查找长度（ASL）的计算方式假设列表长度为n，查找从最后一个元素开始找起：查找第1个元素，需进行n次比较；查找第2个元素，需进行n-1次比较；…………查找第n个元素，需进行1次比较又假设查找每个数据元素的概率相等，即Pi=1/n则顺序查找算法的平均查找长度为： ASL=1*1/n+2*1/n+…+n*1/n =(1+2+…+n)*1/n=(n+1)/2顺序表的查找法假设列表长度为n，从最后一个元素开始找起：查找第i个元素，需进行()次比较?

若顺序查找法从第一个元素开始找起，则平均查找长度为(

)？

n-i+1(n+1)/2，一样!顺序表的查找法顺序表的查找算法的特点算法简单，对表结构无任何要求（顺序和链式）n很大时查找效率较低改进措施：非等概率查找时，可按照查找概率进行排序。有序表的查找法有序表是元素有序排列的查找表，它也是顺序表中的一种，但相比于无序表来说，有序表中的元素都是有序排列的，因此查找时会有一些效率更高的方法。常用的有序查找算法：折半查找插值查找斐波那契查找有序表的查找法——折半查找法(二分查找法)前提条件：必须采用顺序存储结构必须按关键字大小有序排列！！！基本思想：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。有序表的查找法——折半查找法(二分查找法)假设要查找元素：e=42

121728313336384259middleleft=1right=9middle=512345678967比较次数：1比较次数：288比较次数：3middle

leftright

left42>3342>3842==42有序表的查找法——折半查找法(二分查找法)用折半查找法查找12的过程：有序表的查找法——折半查找法(二分查找法)有序表的查找法——折半查找法(二分查找法)用折半查找法查找50的过程：有序表的查找法——折半查找法(二分查找法)当high<low时，表示不存在这样的子表空间，查找失败!!!!有序表的查找法——折半查找法(二分查找法)折半查找法的平均查找长度（ASL）假设列表长度为n：查找第1个元素，需进行？次比较；查找第2个元素，需进行？次比较；…………查找位于中间位置的元素，需进行？次比较；…………查找第n个元素，需进行？次比较又假设查找每个数据元素的概率相等，即Pi=1/n有序表的查找法——折半查找法(二分查找法)折半查找过程可用一判定树描述判定树：树中每一结点表示表中一记录，结点值记录在表中的位置。从根到被查结点路径关键字比较次数为被查结点层数成功进行最多比较次数不超过树的深度有序表的查找法——折半查找法(二分查找法)用折半查找法查找12的过程：251546182858122235660比较1次，1个比较2次，2个比较3次，4个比较4次，4个有序表的查找法——折半查找法(二分查找法)n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为假定表的长度n=2h-1，则相应判定树必为深度是h的满二叉树h=log2(n+1)折半查找法的平均查找长度为：

ASLbs＝

i=1nPiCi＝n1

j=1nj×2j-1＝nn+1log2(n+1)-1有序表的查找法——折半查找法(二分查找法)优点：比较次数少，查找速度快，平均性能好缺点：要求待查表为有序表，且插入删除困难。有序表的查找法——插值查找法插值查找是对折半查找的一种优化，但是它的适用场景也比折半查找更狭窄，要求查找表不仅是已经排好序的，而且呈均匀分布。在折半查找中，mid=(begin+last)/2，而在插值查找中，如果要查找的关键字为key，则mid=begin+(key-arr[begin])*(last-begin)/(arr[last]-arr[begin])。有序表的查找法——斐波那契查找在C语言中我们学习过斐波那契数列，在斐波那契数列中，有一个特性，对于任一角标k(k>=2)，F[k]=F[k-1]+F[k-2]，即后边每一个数都是前两个数的和。而且随着数列的递增，前后两个数的比值会越来越接近黄金分割数—0.618，利用这个特性，就可以将黄金比例运用到查找技术中。但要注意：如果一个有序表的元素个数为n，并且n正好是某个斐波那契数减1，即满足n=F[k]-1时，才能使用斐波那契查找。如果元素个数n不满足这个关系，那么需要将查找表扩展，直到n满足这个关系。索引顺序查找索引顺序查找又叫分块查找，它是介于顺序查找和折半查找之间的一种查找方法。在此查找方法中，除查找表外还需要为查找表建立一个“索引表”，索引表是分段有序的。将查找表分为若干个子表，为每一个子表建立一个索引项存储在索引表中，索引项包括两项内容：关键字项和指针项。索引顺序查找前提条件：要求将列表组织成以下索引顺序结构首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，和每块中的最大关键字（或最小关键字）。索引表按关键字有序排列索引顺序查找此表包括三个块：第一个块的起始地址为0，块内最大关键字为25；第二个块的起始地址为5，块内最大关键字为58；第三个块的起始地址为10，块内最大关键字为88。索引顺序查找基本思想：（1）首先根据给定的关键字key，在索引表中查找以确定key所在的子表；（2）然后再在子表中查找关键字为key的元素，如果找到，则查找成功；否则查找失败。索引表是有序表，则既可进行顺序查找也可进行折半查找，以确定待查元素所在子表；而子表可能是无序的，因此只能用顺序查找。索引顺序查找查找36：将36与索引表中的关键字比较，因为25<36≤58，所以36在第二块中；在第二块中顺序查找，最后在8单元中找到36。索引顺序查找分块查找法的平均查找长度包括两个部分：查找索引表时的平均查找长度为LB，在相应块内进行顺序查找的平均查找长度LW。ASLbs=LB+LW索引顺序查找假定将长度为n的