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+10时,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