IT[low]. next; STele[o]. key=key; If(low!=BLOCK NUM)p=IT[low+1]. next else p=sTlength+1 while(sTelem i%p]. key!=key)1++ return( 1%op) 性能分析: ASL(bls)=Lb+Lw=(b+1/)2+(s+1)/2 =(b+s+2)/2=(n/s+s)/2+1 分块的个数b=n/2 每块中的记录个数 记录的总个数 Lb 确定所在的块 Lw 块内查找
i=IT[low].next; ST.ele[0].key = key; If(low!=BLOCK_NUM) p=IT[low+1].next; else p=ST.length+1; while(ST.elem[i%p].key != key ) i++ ; return( i%p ) ; } 性能分析： ASL（bls）=Lb+Lw=(b+1/)2 +(s+1)/2 =(b+s+2)/2 =(n/s+s)/2+1 b —— 分块的个数 b=n/2 s —— 每块中的记录个数 n —— 记录的总个数 Lb —— 确定所在的块 Lw —— 块内查找
第i(1≤i<h)层结点有2-1个,查找第i层结点要 比较次,…。假定每个结点的查找概率相等,即 P=1mn,则查找成功的平均查找长度为 ASL sucC ∑ ∑C1=(1*1+2*21+ +3*2 +(h-1)×2″2+h×2) 可以用归纳法证明 1×1+2×2+3×22+…+(h-1)×2 h-2 +h×2 (h-1)×2”+1 这样ASL0=(h-1)×2+1)=-(n+1)log2(n+1)-n) n+1 log, (n+1)-1slog,(n+1)
( 1) 2 1 1 1 2 2 3 2 ( 1) 2 2 1 2 2 1 h h h h h h log ( 1) 1 log ( 1) 1 1 (( 1)log ( 1) ) 1 (( 1) 2 1) 1 2 2 2 n n n n n n n n h n ASL h succ 3 2 ( 1) 2 2 ) (1 1 2 2 1 1 2 2 1 1 1 1 h h n i i n i succ i i h h n C n ASL P C
92动态查找表 表结构本身是在查找过程中动态生成的。 基本操作: InitDSTablet(&DT);∥构造一个空的动态查找表DT Destroy DSTable(&DT),∥销毁表 SearchdsTable① DT, key);∥查找关键字为key的数据元素 InsertDSTable(&Dt e DeleteDSTable(&DT, key) TraverseTABle(DT, visito;遍历查找表
表结构本身是在查找过程中动态生成的。 基本操作： InitDSTable(&DT); //构造一个空的动态查找表DT DestroyDSTable(&DT); //销毁表 SearchDSTable(DT,key); //查找关键字为key的数据元素 InsertDSTable(&DT,e); DeleteDSTable(&DT,key); TraverseDSTable(DT,visit()); //遍历查找表
921二又排序树( Binary Sort Tree 定义 叉排序树(二叉查找树)或者是一棵空树, 或者是具有下列性质的二叉树: 每个结点都有一个作为查找依据的关键字 key),所有结点的关键字互不相同。 左子树(若非空)上所有结点的关键字都小于 根结点的关键字。 右子树(若非空)上所有结点的关键字都大于 根结点的关键字。 左子树和右子树也是二叉排序树
定义
(2 (a) (b) 几个二叉排序树的例子 如果对一棵二叉排序树进行中序遍历,可以按 从小到大的顺序,将各结点关键字排列起来
几个二叉排序树的例子