查找

nullnull 第十章 查找null● 查找表：是由同一类型的数据元素构成的集合。 ● 关键字：是数据元素中某个关键字域的值，可 以标识一个数据元素。 ● 主关键字：可以唯一标识一个数据元素的关键 字叫主关键字。 null10.1 线性表查找 10.1.1 顺序查找 ● 顺序查找算法SS 算法SS（R，n，K．i） /* 给定R1，R2，…，Rn的表，其中Ri 的关键词为Ki（1≤i≤n），本算法查找关键词等于K的记录*/ SS1 [初始化] i←1 ．Kn+1←K ． SS2 [比较关键词] WHILE K≠Ki DO i←i+1. ▌ null算法SS（R，n，K．i） SS1 [初始化] i←1 ．Kn+1←K ． SS2 [比较关键词] WHILE K≠Ki DO i←i+1. ▌ null● 查找成功的平均查找长度： E(n) ●查找失败的查找长度：n+1 ● 顺序查找的时间复杂度：O(n)null 把经常出现的元素（它的发生概率较大）自动向表的前端移动，把不经常出现的元素自动向表的后端移动，并称以该方式组织的表为自组织表 . MOVE-AHEAD-ONE MOVE-TO-FRONT ● 顺序查找优缺点: 优点:算法简单，且适用面广，对表的结构无任何要求. 缺点:平均查找长度较大，特别n很大时查找效率低。 10.1.2 有序表的查找 算法SO（R，n，K．i） /*表R1，R2，…，Rn按照关键字递增有序*/ SO1 [初始化] i←1 ．Kn+1←+∞ . SO2 [顺序与表中各元素比较] WHILE K＞Ki DO i←i+1. SO3 [若未找到，设i←n+1 ] IF K≠Ki THEN i←n+1. ▌ 有序表查找演示 10.1.2 有序表的查找 算法SO（R，n，K．i） /*表R1，R2，…，Rn按照关键字递增有序*/ SO1 [初始化] i←1 ．Kn+1←+∞ . SO2 [顺序与表中各元素比较] WHILE K＞Ki DO i←i+1. SO3 [若未找到，设i←n+1 ] IF K≠Ki THEN i←n+1. ▌ 有序表查找演示null算法SO的三种改进方法： 1. 对半（折半，二分）查找 2. 斐波那契查找 3. 插值查找 用线性插值决定K的期望地址null1. 对半（折半，二分）查找 [例] 假定有序表A中10个元素的关键字序列为： 12，23，26，37，54，60，68，75，82，96 当给定值分别为96和58时进行二分查找。 null查找k=96时二分查找过程(4次比较成功） null 算法B(R，n，K. found) /*对半查找算法，表中元素R1，R2，…，Rn相应的关键词满足K1≤K2≤…≤Kn*/ B1 [初始化] s←1 ．e←n ．found←false ． B2 [查找] WHILE s≤e DO （i←(s+e)/2 ． // 找中间元素 IF K＜Ki THEN e←i-1 ． IF K＝Ki THEN （found←true．RETURN）． IF K＞Ki THEN s←i+1 ）▌ null查找k=58时二分查找过程(3次比较失败）null[例] T（1，10）的二叉判定树每个圆圈结点表示关键词比较 K : Kinull ● 二叉判定树 二叉判定树，T（s，e）的递归定义如下： (1) 当e-s+10时，T（s，e）为空树； (2) 当e-s+1>0时，二叉判定树的根结点是有序 表中序号为(e+s)/2的记录，根结点的左子树是与有序表Rs，Rs+1，…，R(e+s)/2 -1相 对应的二叉判定树，根结点的右子树是与有序表R(e+s)/2+1，R(e+s)/2+2，…，Re相对应的二叉判定树。null ● 外部结点：树中所有结点的空指针都指向一个 方形结点，则称这些方形结点为查 找树的外部结点。 ● 内部结点：树中原来那些圆形结点就叫做查找 树的内部结点。 ● 增长的二叉树：当原二叉树中的结点没有左子树形和右子树形时，就增加特殊的结点（称外部结点，树中原来的那些结点称内结点），由此生成的二叉树称为增长的二叉树。 构造二叉判定树null搜索K=96成功的情况：null搜索K=58失败的情况：null [例]T(1,10)查找成功的平均查找长度.ASLSUCC ＝(1*1+2*2+3*4+4*3)/10 ＝29/10 ＝2.9null 查找失败的平均查找长度： ASLUNSUCC ＝ En/(n+1) ＝ (3*5+4*6)/11＝ 39/11null ● 完全平衡二叉树： 一棵增长树，如果存在k，并使所有的外结点都在k层上或者都在k层和k+1层上，则称该增长树为完全平衡二叉树。 ● 对半查找无论成功还是失败，其时间复杂度都为 O(log2n).null引理10.1 设算法B对n个记录的成功查找是等概率的，且对不成功的查找也是等概率的，则成功查找的关键词比较的平均次数Sn=1+In/n，不成功查找的关键词比较的平均次数Un=En/(n+1)，其中In，En为T（1，n）的内、外通路长度. 引理10.2 对半查找二叉判定树T（s，e）的高度是log2(e-s+2) . 引理10.3 设 T（1，n）是n个结点的二叉查找判定树，则T（1，n）是n个内结点的完全平衡二叉树. 定理10.1 算法B在最坏情况下的关键词比较次数为  log2(n＋1) ，且期望复杂性等于O(log2n) . null● 二分查找优缺点: 优点:查找效率为O(log2n) //比顺序查找高 缺点:只适用于有序表，且限于顺序存储结构，对线性链表无法进行二分查找。null算法SO的三种改进方法： 1. 对半（折半，二分）查找 2. 斐波那契查找 3. 插值查找 用线性插值决定K的期望地址null斐波那契（Fibonacci）查找 对半查找的替代，以Fibonacci序列的分划代替了对半查找的均匀分划。 Fibonacci序列的定义： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…… null 假定表中元素的个数是某个Fibonacci数减1，即n=FK-1 .不妨设m= FK-1 ,KK=Km Fibonacci查找是把关键词K与KK作首次比较，从而产生如下的结果： null（a）K KK，这时查找从FK-1+1到 FK-1的子表，且表的元素个数是 (FK-1) - (FK-1+1)+1=FK-2-1 即一个 Fibonacci数FK-2减1 .（b）K= KK ，则查找成功；null费波那契查找演示 算法Fibonacci (K, m . found) /* Fibonacci查找算法．假定表中元素数 n= Fm+1-1(m≥2)，且表中记录已排序 */ Fib1 [初始化] i←Fm ．p←Fm-1 . q←Fm-2 . found←false . nullFib2 [查找] WHILE i≠0 DO （ IF K1时，二叉判定树的根结点是有序表中序号为Fm的记录，根结点的左子树是与有序表R1，R2，… ， RFm-1相对应的二叉判定树，根结点的右子树是与有序表RFm+1，RFm+2，… ，RFm+1 -1相对应的二叉判定树. nullFibonacci树形T6 null引理10.4 设m≥3，Tm是m阶Fibonacci树形，则Tm的左子树形的高度等于右子树形的高度加1，且Tm 的高度为m-1 . 引理10.5 设n= Fm+1-1，则m阶Fibonacci树形的高度约等于1. 44log2（n＋1） . 定理10.2 令n=Fm+1-1，则算法Fibonacci在最坏情况下的时间复杂性为O(log2n)，且期望复杂性亦为O(log2n) .null3. 插值查找 在所期望的地址附近开始的查找，我们称为插值查找. 假定表中记录的关键词是数字类型，且K1KEY（P）：P←RLINK（P）. K=KEY（P）：found←true）▌null 设表中元素的关键词K1