数据结构 宗大华 宗杰 黄芳 数据结构 大本课件-8

《数据结构 宗大华 宗杰 黄芳 数据结构 大本课件-8》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章查找8.18.28.3本章讲述内容：8.6查找的基本概念静态查找算法二叉查找树散列及散列表的动态查找8.4平衡二叉树8.5B树与B+树8.1查找的基本概念.查找是最为常见的、使用频率最高的、程序中耗费时间最多的一种数据操作，是实施数据读取、插入、修改、删除等重要操作的基础。.所谓“查找”，是要确定具有某个值的元素是否是某个集合中的一个成员的过程。设集合T里有n条记录：(k1,I1)、(k2,I2)、(k3,I3)、…、(kn,In)。其中，k1、k2、…、kn是互不相同的n个关键字值，Ii是与ki相关联的记录信息(1≤i≤n)

2、。给定某个值K。“查找”就是要在集合T中寻找出一个记录(kj,Ij)，使得有kj=K。查找成功的含义就是在T里找到一个关键字为kj的记录，使得kj=K；查找失败就是在T里找不到记录，使得kj=K。.能唯一确定一个记录的数据项，称为是记录的“主关键字”，简称“关键字”；不能唯一确定一个记录的数据项，称为记录的“次关键字”。..有n条记录的集合T是实施查找的基础。讨论查找时，常把T称为“查找表”。若查找只为得知是否成功及获取相应的记录信息，不去改变查找表的内容，那么这种查找称为“静态查找”，这时的查找表称为“静态查找表”；若查找会伴随对

3、数据元素的变更，那么这种查找称为“动态查找”，这时的查找表称为“动态查找表”。.查找时，用给定值K与各记录的关键字ki(1≤i≤n)进行比较。若Ci是查找第i个记录需要的比较次数，Pi是查找第i个记录的概率，则查找成功的“平均查找长度(ASL)”为：ASL=∑pi×cii=1n8.2静态查找算法对一般的无序线性表（顺序存储结构或链式存储结构），进行静态查找时采用的是顺序查找算法；若已经根据某种规则对静态查找表中的记录进行了某种排序，那么就可以设计出别的算法来对表元素进行较高效率的静态查找。.8.2.1顺序查找顺序查找也称线性查找，它

4、基于顺序表Sq，将给定值K依次与表中元素的关键字做比较。若某元素的关键字等于给定值K，则查找成功，返回该元素所在位置下标；若没有找到关键字值为K的元素，则查找失败，返回某个约定的标识，比如返回“-1”。.voidSeqsch_Sq(Sq,n,K){for(i=1;i<=n;i++)if(Sq[i].key==K)break;if(i<=n)returni;elsereturn-1;}顺序表Sq共有n个记录，存储在一维数组里，结点的存储结构如图所示。给定值K，要求对Sq进行顺序查找，返回位置下标或-1。算法描述(1)算法分析(2).k

5、eydata存储结构：关键字其他数据项.顺序查找的优点是适应性强，无需过问查找表中的元素是否有序，也无需过问查找表采用的是顺序存储还是链式存储。但缺点是效率低，查找成功的平均查找长度是(n+1)/2次，即是整个表长的一半；查找失败时需要比较n+1次。所以，顺序查找的时间复杂度是O(n)。查找表有16个记录，关键字序列为：08121520242932353844485660667488。给定K=38，试用折半查找方法找出哪个记录的关键字等于38。8.2.2折半查找所谓“有序表”，是指已经将记录按照关键字的大小顺序进行了排列(由小到大或

6、由大到小)的一种查找表。基于有序表的折半查找算法，具有很高的查找效率。.折半查找的基本思想是以有序表的中间记录为准，将表分为左、右两个子表。用给定值K与中间记录的关键字比较，若结果相等，则查找成功；若给定值K小于中间记录的关键字，则取左子表继续这种查找；若给定值K大于中间记录的关键字，则取右子表继续这种查找。不断重复，直到查找成功，或无该记录存在而查找失败。.例8-2：0812152024293235384448566066748812345678910111213141516序号：初始状态：右子表左子表38444856606674

7、88910111213141516右子表左子表38444891011389序号：第1次比较后：序号：第2次比较后：序号：第3次比较后：解：(a)(b)(c)(d)折半查找的基本思想1.“K==Ar[mid].key”时，表示要查找的记录就是查找区间的中间记录。于是查找成功，返回记录的序号mid，循环结束。“K>Ar[mid].key”时，表示要查找的记录应在当前查找区间的右子表里，因此保持原有high里的值，将low修改成mid+1；“K

8、值，将high修改成mid−1；有序表的折半查找算法算法8-2算法描述(1)算法分析(2)实施折半查找时，应把查找表顺序存储在一个一维数组里，数组元素的存储结构如图所示。.keydata记录关键字记录的其他数据项Bin_Ar(Ar,n