数据结构 类Pascal版 严蔚敏 chapt9-兰州大学信息院

一、二叉排序树（Binary Sort Tree)（又称为二叉查找树）
1、BST定义： BST或者是一棵空树；或者是具有如下性质的BT:
•
• •
若左子树非空，则左子树上所有结点的值均小于根结点的值；
若右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树也为BST
9.2
例如：
动态查找表
45 53 12 100
3) 所有索引项组成索引表
9.1
例. 查找表为:
静态查找表
22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53
索引表为:
关键字项 指针项
22 1
48 7
86 13
9.1
查找分为两步:
静态查找表
1. 确定待查记录所在块; (可以用顺序或折半查找) 2. 在块内顺序查找. (只能用顺序查找) 例如: k=38 第1步: k=38 的记录只可能在块2中; 第2步: 从r[7]开始, 直到k=r[i].key 或i>12为止.
9.1
静态查找表
3. r[0]起监视哨作用 FUNC seqsrch(r:sqlisttp; k:keytype):integer; r[0].key:=k; i:=n; WHILE r[i].key <>k DO i:=i-1; RETURN(i) ENDF; {seqsrch}
i:=n; WHILE i>=1 CAND r[i].key<>k DO i:=i-1; RETURN(i);
9.2
算法描述为：
动态查找表
FUNC bstsrch (t:bitreptr ; k:keytype):bitreptr; {查找不成功时返回NIL } IF (t=NIL) COR (t↑.key=k) THEN RETURN(t) ELSE IF t↑.key<k THEN RETURN(bstsrch(t↑.rchild, k)) ELSE RETURN(bstsrch(t↑. lchild, k))
查找成功 (table 中存在给定值的记录) 查找不成功 (table 中不存在给定值的记录)
查找表分为:
• 静态查找表 (对查找表中的数据元素不进行插入和删 除操作)
• 动态查找表 (对查找表中的数据元素可进行插入和删 除操作)
9.1
查找表的类型描述:
静态查找表
TYPE rectype=RECORD key: keytype; …… END;
RETURN(i)
ENDF; {seqsrch}
9.1
平均查找长度(ASL):
静态查找表
查找过程中, 给定值需与关键字比较的次数的期望值.
n
ASL=∑PiCi
i =1
其中:
Pi 为查找第i 个记录的概率; Ci 为找到第i 个记录时, 已比较的次数.
顺序查找的平均查找长度ASLss=np1+(n-1)p2+……+pn
sqlisttp=ARRAY[0..n] OF rectype;
9.1
静态查找表
一. 顺序表的查找(顺序查找)
FUNC seqsrch(r:sqlisttp; k:keytype):integer;
r[0].key:=k; i:=n;
WHILE r[i].key <>k DO i:=i-1; RETURN(i) ENDF; {seqsrch}
条件控制式 i = 0 计数控制式
9.1
常规解决办法:
静态查找表
(1) 条件循环为主 WHILE r[i].key <> k DO IF i = 1 THEN RETURN ( 0 ) ELSE i: = i - 1 ; (2) 复合条件 WHILE r[i].key <> k AND i>=1 DO i: = i - 1 ; (3) 计数循环为主 FOR i:=n DOWNDO 1 DO IF r[i].key=k THEN RETURN(i) ；
关键字项 指针项
22 1
48 7
86 13
22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53
9.1
一个示意算法:
静态查找表
PROC bsb(T,r,n,b,s,k)；{T为升序排列的块最大关键字表（索引表），b 为块数，r为查找表，n为r的元素个数，s为每块元素个数，k为关 键字｝ T[b+1]:=k；i:=1； WHILE T[i]＜k DO i:=i+1； IF i≤b THEN 【 j:=(i-1)s+1；i:=is； WHILE j≤i CAND r[j].key≠k DO j:=j+1； IF j≤i THEN WRITE(‘SUCC’) ELSE WRITE(‘UNSUCC’) 】 ELSE WRITE(‘UNSUCC’) ENDP；｛bsb｝
ELSE RETURN(0) ENDF; {seqsrch3}
9.1
静态查找表
有序表的顺序查找(设置监视哨) FUNC seqsrch4(r:sqlisttp; k:keytype):integer; r[0].key:=k; i:=n; WHILE k<r[i].key DO i:=i-1; IF k=r[i].key THEN RETURN(i) ELSE RETURN(0) ENDF; {seqsrch4}
≈log2(n+1)-1
9.1
静态查找表
三. 索引顺序表的查找(分块查找)
索引表 :
1) 按表中记录的关键字分块, R1,R2,…,RL
要求: 第Rk 块中的所有关键字< Rk+1块中的所有关键字 k=1,2,…,L-1, 称为“分块有序” 2) 对每块建立一个索引项, 包含有两项内容:
① 关键字项 : 为该块中最大关键字值; ② 指针项 : 为该块第一个记录在表中位置.
的值, 用它可以标识(识别)一个数据元素(或记 录)。
主关键字(primary key): 可以唯一地标识一个数据
元素(或记录)的关键字。
次关键字(secondary key): 用以标识若干数据元素
(或记录)的关键字。
9.1
静态查找表
查找 : 根据给定的值，在查找表中确定关键字与给定
值相等的DE的过程。 查找结果: • •
ENDF; {bstsrch}
9.2
3. BST的插入
动态查找表
ห้องสมุดไป่ตู้
插入原则：记下查找不成功时比较的最后一个结点的位 置，将插入结点作为该结点的左或右孩子。 PROC insbst (VAR bst :bitreptr; k:keytype); f:=NIL ; found:=false;
f:= srch_bstree (f, bst, k, found)
ASL成功=(n+1)/2+1 ASL不成功=(n+1+1)/2+1=n/2+1+1
9.1
静态查找表
二. 有序表的查找(折半查找)
有序表 : 查找表中记录按关键字有序排列的表.
即: r[i].key<=r[i+1].key i=1,2,…,n-1
折半查找 :
• 要求: 查找表为有序表;
•
查找过程: 先确定待查记录范围;
9.2
一个改进的非递归算法:
动态查找表
FUNC srch_bstree1 (VAR f:bitreptr; bst:bitreptr; k:keytype; VAR found:boolean):bitreptr; IF bst=NIL THEN [ found:=false; RETURN(f)] ELSE [ p:=f:=bst; { 查找不成功时, f记载插入点的双亲 } WHILE p<>NIL DO IF p↑.key=k THEN [ found:=true; RETURN(p)] ELSE IF p↑.key<k THEN [ f:=p; p:=p↑.rchild ] ELSE [ f:=p; p:=p↑.lchild ];
n
当pi=1/n时, ASLss=∑PiCi =(n+1)/2
i =1
9.1
有序表的顺序查找
静态查找表
FUNC seqsrch3(r:sqlisttp; k:keytype):integer; i:=1; WHILE i<=n CAND k>r[i].key DO i:=i+1;
IF i<=n CAND k=r[i].key THEN RETURN(i)
第九章
查找
• 静态查找表 • 动态查找表 • 哈希查找表
9.1
静态查找表
查找表(table):由同类型的DE(或记录)构成的集合. 查找表上的基本运算:
• • 建立查找表create(ST, n) 查找search(ST, k)
•
遍历查找表traverse(ST)
9.1
静态查找表
关键字(key): 是数据元素(或记录)中某个数据项
9.1
静态查找表
1. 查找过程: 从n开始,依次与k进行比较, 若相等则查找
成功; 否则, 继续进行,直到与r[0].key比较为止. 2. 算法分析: (1) 算法结构由一个循环构成;
9.1
静态查找表
(2) 循环结束有两种可能： • 查找成功 r[i].key = k • 查找不成功 这两种可能形成两种不同类型的循环控制： • 条件循环 WHILE 条件 DO 循环体 REPEAT 循环体 UNTIL 条件 • 计数循环 FOR i: = n DOWNTO 0