《小白学数据结构》课件——第七章 查找.pptxVIP

主讲教师：

顺序查找

查找基本概念

查找基本概念日常生活中的例子查找表通过考号查询四\六级成绩歌名检索歌曲

查找基本概念查询检索查找同一个概念

查找基本概念定义：给定一个值K，在含有N个节点的表中找出关键字等于给定值K的节点。主关键字：如果这个关键字能唯一的标识一个数据元素，如学号。次关键字：可以对应多个数据元素，如姓名。

顺序查找

顺序查找如果相等就返回下标的值不等则继续向后进行比较，直至最后一个如果都没有相等的则查找失败

空间复杂度：常数的O(1)时间复杂度：最好情况：O(1)最坏情况：O(n)其它情况：O(n)顺序查找的性能

顺序查找通常我们把查找过程中的平均查找长度（ASL）作为衡量一个查找算法优劣的标准。顺序查找的平均查找长度Pi——查找第i个记录的概率Ci——找到第i个记录数据需要比较的次数

等概率的情况下

顺序查找的优缺点算法简单，且对表的结构无任何要求。优点查找效率低，因此，当n较大时不宜采用。缺点

总结查找基本概念顺序查找

总结古之成大事者，不唯有超世之才，亦必有坚韧不拔之志。

主讲教师：

折半查找

折半查找也称二分查找

折半查找有序表：有序表就是顺序表，按关键字递增或递减的顺序排序。也就是说第i个位置记录的关键字是比第i+1个记录关键字大或者小。123456——有序表246913——无序表

折半查找折半查找：将待查关键字与有序表中间位置的记录进行比较，若相等，查找成功，若小于，则只可能在有序表的前半部分，若大于则只可能在有序表的后半部分，因此，经过一次比较，就将查找范围缩小一半。这样一直进行下去直到找到所需记录或记录不在查找表中。

折半查找折半查找的基本思想假设R[1,…,n]是当前的查找区间，首先确定区间的中点位置mid=(1+n)/2；然后将要查找的值K与R[mid]的关键字进行比较。若K==R[mid].Key，则查找成功返回此位置的下标值，否则需要确定新的查找区间。若KR[mid].Key，则由表的有序性可得，R(mid,…,n)内的关键字均大于查找值K，因此若表中存在关键字等于K的节点，则该节点必定在mid位置的左边即[1,…,mid-1]中，所以新的查找区间变为[1,…,mid-1]。同理若KR[mid].Key，则要查找的K值必定在mid位置的右边即[mid+1,…,n]中，所以新的查找区间变为[mid+1,…,n]。接下来就是针对新的查找区间，重复上面的步骤直到找到关键字为K的节点，若当前的查找区间为空则查找失败。

折半查找30，37，51，59，61，68，79，91，10005131921375664758088921234567891011Highlowmid大low小Highmid相等

折半查找的性能平均查找长度：通常我们把查找过程中的平均查找长度（ASL）作为衡量一个查找算法优劣的标准。Pi——查找第i个记录的概率Ci——找到第i个记录数据需要比较的次数

log2(n+1)-1成功的平均查找长度为：

折半查找的劣势折半查找要求查找表必须为有序表。适用于一经建立就很少改动而又经常需要查找的线性表。

主讲教师：

二叉排序树

定义：二叉排序树，BinarySortTree，简称BST。

它可以是空树，对于任何一棵非空的二叉排序树，具有以下的性质：1.所有结点的关键字不同，在任何结点当中，不能出现相同的关键字。2.根的左子树上全部节点的关键之值，都要小于根节点的值。3.与之对称的，根的右子树上所有结点的值都要大于根节点的值。4.与此同时，左右子树也都是BST，也都是二叉排序树。二叉排序树的概念

二叉排序树的概念

1，2，3，4，5，6重要性质：按中序遍历该二叉树所得到的序列是一个递增有序序列。

二叉排序树的概念中序序列为有序序列，即1，2，3，4，5，6。

二叉排序树的概念30，37，51，59，61，68，79，91，1006879911005951373061二叉排序树：左子树全都小于该结点右子树全都大于该结点

二叉排序树的基本操作、查找

若查找成功，则是从根节点出发走了一条从根到待查节点的路径；若查找不成功，则是从根节点出发走了一条从根到某个叶子的路径。查找给定的关键字

查找方法与二分查找类似和关键字比较的次数不超过树的深度

二叉排序树的概念左边的二叉排序树ASL=(1+2*2+3*3)/6=7/3≈2.3，右边的二叉排序树ASL=(1+2*1+3*