数据结构课程讲义9.pptVIP

§1 线性查找 这也是线性表的基本运算之一。通常称为检索、查询等。 §1 线性查找 1．1 顺序检索 基本思想： 从线性表的一端开始，逐个地将待查找元素的关键字与每个元素的关键字进行比较，若找到，则返回1，否则返回0。 该算法的时间复杂度为O(n). §1 线性查找 顺序查找采用从头至尾逐个比较 最快O(1) 最慢O(n) 查找成功的等概率平均时间复杂性 O((n+1)/2) 1/n(1+2+3+······+n)=(n+1)/2 查找失败O(n+1) 查找的等概率平均时间复杂性 O(3(n+1)/4) 查找成功失败各半 1/2n((1+2+······+n)+n(n+1))=3(n+1)/4 §1 线性查找 1．2 二分查找 亦称折半查找，是基于提高查找速度的一种方法。检索时要求元素是排序的。 基本思想： 每次将待查找元素的关键字与已排序元素序列的中间点元素进行比较，如相等，则返回1，否则修改高点或低点，重新进行查找比较。 该算法的时间复杂度为O(n). 这是有序表的查找查找 对已排序的查找结构先确定中点，比较待查关 键字与中点关键字的大小，反复直到成功。 求n个数据折半查找的等概率成功查找的平均时 间复杂性 1 2 3 4 5 6 7 8 9 10 n个元素的折半查找 2k-1≤n2k+1-1 查找成功平均概率时间复杂性 介于 log2(2k)-1 和 log2(2k+1)-1 之间 即 k-1 和 k 之间 k=[log2(n+1)] n个元素的折半查找成功平均概率时间复杂性 log2(n+1)-1/2 §1 线性查找 1．3 分块查找 亦称索引顺序查找。也是基于提高查找速度的一种方法。检索时要求元素构成的块间是排序的，而块内是未排好序的。 基本思想： 将所有元素按关键字值划分成若干块，块之间是排序的，而块内暂时是无序的。查找时候，首先折半查找确定元素所在的块，然后再在块内进行顺序查找即可比较。 3、索引顺序查找 分块有序 后一子表中的关键字都大于前一子表中的关键字 索引顺序表的查找 查找 关键字key=38 1. 先检索索引表 确定子表位置 2. 再在子表中查找 分块查找成功的平均概率时间复杂性 索引表查找时间+子表查找时间 设索引表长为s，查找表长为n,被平均分成s块， 每块长n/s, 索引表平均查找时间 (s+1)/2 子表平均查找时间 (n/s+1)/2 ?(s+1)+ ?(n/s+1)= ?(s+n/s)+1 当 s=√n 时 有最小值 √n +1 当索引顺序表已经排序时，子块查找可以用折半查找。 平均查找时间： (s+1)/2 +log2(1+n/s)-1/2 = log2(1+n/s)+s/2 索引也用折半查找，平均查找时间 log2(s+1)-1/2 +log2(1+n/s)-1/2 = log2(s+1)(1+n/s)-1 当s= √n 时 2 log2(√n +1)-1 §2 树形结构的查找 2．1 二叉排序树及其查找过程 二叉树BT是二叉排序树，只要BT是满足如下的条件： （1）若BT的左子树非空，则其左子树上所有结点的值均小于其根结点的值；（2）若其右子树上所有结点的值均大于其根结点的值；（3）其左右子树均为二叉排序树。 对二叉排序树的中序遍历的结果就是一个升序序列。 二叉排序树又称为二叉查找树。 于是，只要将元素序列组织成二叉排序树，在进行查找时，让待查找元素与根结点值进行比较，若相等，则查找成功，否则，如果比根结点小，则只需要在左子树中查找即可；如果比根结点大，则只需要在右子树中