2001 -- 12 --29
华中科技大学计算机学院 (10)数据结构
9.0 与查找有关的术语：
● 查找表 ----由同一类型的数据元素（记录）组成的集合。
记作,ST={a1,a2,...,an}
学 号 姓 名 性别 数学 外语
200041 刘大海 男 80 75
200042 王 伟 男 90 83
200046 吴晓英 女 82 88
200048 王 伟 女 80 90
......,....,..,...,.,
序号
1
2
3
4
n
● 关键字 -------可以标识一个记录的数据项
● 主关键字 -----可以唯一地标识一个记录的数据项
● 次关键字 -----可以识别若干记录的数据项学生成绩表数据项 1
(主关键字 )
数据项 2 数据项 5
● 查找表的操作
● 生成 查找表
● 查找元素 (记录 )x在是否在表 ST中
● 查找元素 (记录 )x的属性
● 插入新 元素 (记录 )x
● 删除 元素 (记录 )x
......
● 查找 ----根据给定的某个关键字值，在查找表中确定一个其关键字等于给定值的记录或数据元素。
设 k为 给定的一个关键字值,R[1..n]为 n个记录的表,若存在 R[i].key=k,1≤i≤n,称 查找成功 ；否则称 查找失败 。
● 静态查找 ----查询某个特定的元素,检查某个特定的数据元素的属性,不插入新 元素 或删除 元素 (记录 ) 。
● 动态查找 ----在查找过程中,同时插入查找表中不存在的数据元素 (记录 )。
● 查找表的类型及其查找方法
(1) 静态查找 表
● 顺序表，用顺序 查找法
● 线性链表，用顺序 查找法
● 有序的顺序表，用：
折半 查找法 ； **斐班那契 查找法 ；插值 查找法 ；
● 索引顺序表 /分块表，用分块 查找法 。
(2) 动态查找 表
● 二叉排序树,平衡二叉树 (AVL树）
**● B树,B+树,键 树
(3) 哈希 (Hash)表
● 平均查找长度 ----查找一个记录时比较关键字次数的平均值。
n
ASL=∑ P iCi
i=1 Pi --- 查找 r[i]的概率
Ci --- 查找 r[i]所需比较关键字的次数
9.1 静态查找 表
9.1.1 顺序表 与顺序 查找法
1.顺序表的描述例 元素 (记录 )类型
#define n 100 //表长 100
struct arecord
{ keytype key ； //关键字类型
char name[6]； //姓名
.....,//其它
} r[n+1]； //n+1个记录其中,r[0]为 监视哨；
记录按输入次序存入 r[1..n]中。
2041 刘大海,..
2042 王 伟,..
2046 吴晓英,..
...,..,..
...,..,..
...,..,..
0
1
2
3
n
key name,..
监视哨
2.顺序查找法 (sequential search)
12 10 30 20 25 15
0 1 2 3 4 5 6
监视哨 r[1..6]
3.算法设计算法 1,假定不使用监视哨 r[0]
基本思想：将关键字 k依次与记录的关键字
r[n].key,r[n-1].key,...,r[1].key 比较,
如果找到一个记录 r[i],有 r[i].key＝ k (1≤i≤n),则查找成功，停止比较,返回记录的下标 i；否则,查找失败,返回 0。
int sequsearch(struct arecord r[],int n,keytype k)
{ int i=n； //从第 n个记录开始查找
while (i>=1 && k!=r[i].key)
i--； //继续扫描
if (i) printf(”success\n”)； //查找成功
else printf(”fail\n”)； //查找失败
return i； //返回记录的下标 i
}
算法 2,假定使用监视哨 r[0]
基本思想：先将关键字 k存入 r[0].key,再将 k依次与
r[n].key,r[n-1].key,...,r[1].key,r[0].key进行比较,
如果找到一个记录,有 k=r[i].key,(0≤i≤n),则停止比较。
如果 i>0,则查找成功；否则,查找失败。
int sequsearch(struct arecord r[],int n,keytype k)
{ int i=n； //从第 n个记录开始查找
r[0].key=k； //k填入 r[0].key
while( k!=r[i].key )
i-- ； //继续扫描
if (i!=0) printf(”success\n”)； //查找成功
else printf(”fail\n”)； //查找失败
return i； //返回记录的下标 i
}
4 查找算法性能分析：
对 n个记录的表,所需比较关键字的 次数
● 若查找成功,最少为 1,最多为 n
假定每个记录的查找概率相等，即 P1 = P2 =,.,= Pn =1/n
n 1 n 1
ASL=∑ P iCi =-- ∑ C i =--(n+(n-1)+...+1)=(n+1)/2
i=1 n i=1 n
● 若查找失败,使用监视哨 r[0],为 n+1
不使用监视哨 r[0],为 n
假定查找成功和失败的机会相同，对每个记录的查找概率相等,Pi=1/(2*n),则
1 n n+1 n+1 n+1
ASL=-- ∑ C i + --- =--- + --- =3(n+1)/4
2n i=1 2 4 2
9.1.2 有序的顺序表 的查找与 折半 查找 法
1.有序表
r[1].key≤r [2].key≤...≤r [n].key
2.折半 查找 (binary search,对半 查找,二分 查找 )
假定 k=10
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
↑ ↑ ↑
low mid hig
low=1,hig=8
mid=(low+hig)/2=4
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
↑ ↑ ↑
low mid hig
low=1,hig=3
mid=(low+hig)/2=2
假定 k=40
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
↑ ↑ ↑
low mid hig
low=1,hig=8
mid=(low+hig)/2=4
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
↑ ↑ ↑
low mid hig
low=5,hig=8
mid=(low+hig)/2=6
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
↑ ↑
low mid hig
low=7,hig=8
mid=(low+hig)/2=7
↑
假定 k=40
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
low mid hig
low=8,hig=8
mid=(low+hig)/2=8
↑ ↑ ↑
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
↑ ↑ ↑
low mid hig
low=1,hig=8
mid=(low+hig)/2=4
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
↑ ↑ ↑
low mid hig
low=5,hig=8
mid=(low+hig)/2=6
假定 k=22
假定 k=22
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
low mid hig
low=5,hig=5
mid=(low+hig)/2=5
↑ ↑ ↑
5 10 12 18 20 25 30 40
1 2 3 4 5 6 7 8
mid hig low
mid=5
low=6,hig=5
↑ ↑ ↑
3 折半查找算法 1
int binsrch(struct arecord r[],int n,keytype k)
{ int low,mid,hig；
low=1；
hig=n；
while (low<=hig)
{ mid=(low+hig)/2； //计算中间记录的地址
if (k<r[mid].key) hig=mid-1； //查左子表
else if (k==r[mid].key) break； //查找成功,退出循环
else low=mid+1； //查右子表
｝
if (r[mid].key==k)
{ printf("success\n”)； //查找成功
return mid；
}
else{
printf("fail\n”)； //查找失败
return 0；
}
}
折半查找算法 2
int binsrch(struct arecord r[],int n,keytype k)
{ int low,mid,hig；
low=1； hig=n；
while (low<=high)
{ mid=(low+high)/2；
if (k<r[mid].key)hig=mid-1； //查左子表
else if (k==r[mid].key)
{ printf("success\n”)； //查找成功
return mid； //返回 mid
}
else low=mid+1； //查右子表
｝
printf("fail\n”)； //查找失败
return 0 ； //返回 0
}
判定树 （描述折半查找过程的二叉树）
● 若 n = 2k -1,则判定树为满二叉树,其深度为 k=log2(n+1)
假定 Pi=1/n(i=1,2,...,n),比较关键字的次数：
● 最少 Cmin=1
● 最多 Cmax=log2(n+1)
n+1● ASL=----log
2(n+1)-1n
15+1 16设 n=15 ASL =------log
2(15+1)-1=----*4-1≈ 3.315 15
6
3 9
1 4 7 11
2 10 125 8
n=12,非满二叉树
7
8
4
62
531 15
12
1410
13119
n=15,满二叉树
n=11,加外部结点的判定树
6
3 9
1 4 7 10
2 115 8
5-64-5
3-4
2-31-2 7-8 8-9 10-11
6-7 9-10-1
11-
对任意的 n
n+1
ASL≈ ---- log2(n+1)-1 = O(log2 n)
n
1+2+2+3+3+3+3+4+4+4+4+4 37设 n=12,ASL= ----------------------- = -- ≈ 3.1
12 12
6
3 9
1 4 7 11
2 10 125 8
n=12,判定树
9.1.3 索引顺序表 (分块表 )与分块 查找 法
20,..
15,..
30,..
10,..
35,..
33,..
40,..
45,..
50,..
60,..
58,..
52,..
...,..
key 其它数据项
1 30
5 45
9 60
13,..
首地址 最大 key
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
3
4
分块表索引表
k=40
k=55
k38
第一块第二块第三块第四块
● 条件
(1)分块表 "按块有序 ",索引表 "按 key有序 "
(2)设 n个记录分为 b个块，每块的记录数 s=n/b
● 查找 方法与 ASL
(1)顺序查找 (或折半查找 )索引表确定 k值所在的块号或块的首地址
b+1ASL(1)=Lb= ---
2
(2)在某一块中顺序查找 s+1
ASL(2)=Lw= ---2
b+1 s+1 1 1 n● ASL=Lb+Lw= --- + --- =-- (b+s)+1= --( -- + s)+1
2 2 2 2 s
● 最佳分块
s=√n b=√n
ASLmin=√n + 1 =O(√n )
9.2 动态查找表
1.二叉排序树 (二叉查找树）
(1) 二叉排序树的定义如果二叉树的任一结点大于其非空左子树的所有结点,而小于其非空右子树的所有结点,则这棵二叉树称为 二叉排序树 。
对一棵二叉排序树进行中序遍历,所得的结点序列一定是递增有序的 。
8
5 14
10 35
8
5 40
10 80
35
3
LDR,5,8,10,14,35
LDR,3,5,8,10,35,40,80
下列二叉树是否为二叉排序树？
30
11
18
15 196
4
10
55
60
26 80
30
10
28
15
22
T1 T2
30
T3
（ 2）二叉排序树的生成设输入序列为,30,11,18,4,55,19,15,70,58
30 30
11
18
30
11
184
19
30
11
30
11
184
19
30
11
184
55
19
30
11
184
55
15
70
19
30
11
184
55
15
70
58
30
11
184
55
55
15
插入 30 插入 11 插入 18 插入 4
插入 55
插入 19 插入 15 插入 70 插入 58
课堂练习：
设输入关键字序列为,58,60,15,80,19,55,4,18,70,11,30,
生成二叉排序树,试画出二叉排序树；假定查找每个结点 (关键字 )的概率相同，计算查找成功时的平均查找长度 ASL。
课堂练习：
设输入关键字序列为,58,60,15,80,19,55,4,18,70,11,30,
生成二叉排序树,试画出二叉排序树；假定查找每个结点 (关键字 )的概率相同，计算查找成功时的平均查找长度 ASL。
55
58
15
194
60
18
80
7011
30
1+2+2+3+3+3+4+4+4+4+5 35
ASL=--------------------- = -- ≈ 3.18
11 11
(3)二叉排序树的存储结构
lchild data rchild
key,....
左子树 右子树结点类型定义：
struct nodeb
{ struct
{ int key ； //关键字
....,//其它数据项
} data ；
struct nodeb *lchild,*rchild ； //左 右 子树的指针
} *root,*t；
结点
(4) 插入 1个元素到二叉排序树的 算法
struct bnode *intree(struct bnode *t,ElemType x)
{ if (t==NULL) //t是指向二叉树根指针的指针
{ t=(struct bnode *)malloc(sizeof(struct bnode))；
t->data=x； //生成并插入结点 x
t->lchild=t->rchild=NULL； //为叶子结点
}
else if(x<t->data.key)
t->lchild=intree(t->lchild,x)； //插入左子树
else
t->rchild=intree(t->rchild,x)； //插入右子树
return t;
}
main() //主函数
{ root=NULL；,....
root=intree(root,x)； //插入 1个元素 x
}
(5)二叉排序树的 查找算法 (返回值 失败,NULL 成功：非 NULL）
(1) 递归算法
struct nodeb *search_tr(struct nodeb *t keytype k)
{ if (t==NULL) return NULL； //查找失败
else if (k==t->data.key) return t； //查找成功
else
if (k<t->data.key)
return search_tr(t->lchild,k)； //查 左子树
else
return search_tr(t->rchild,k)； //查右 子树
}
(2) 非递归算法
struct nodeb *search_tree(struct nodeb *t)
{ while (t!=NULL){
if (k==t->data.key) return t； //查找成功
else if (k<t->data.key) t=t->lchild； //查 左子树
else t=t->rchild； } //查右 子树
return t； //查找失败
}
(6)算法分析最好情况 (为满二叉树）
n+1
ASL=---log2(n+1)-1 = O(log2 n)
n
最坏情况 (为单枝树 ),ASL=1+2+...+n=n(n+1)/2
平均值,ASL≈O(log 2 n)
58
28
49
3045
58
15
1910
18114 88
69
7964
756560
满二叉树 单枝树
ASL=(15+1)/15*log2(15+1)-1≈3.3 ASL=(1+2+3+4)/4=2.5
2.平衡 二叉树 (高度 平衡 二叉树）
● AVL树 ----由 G.M.Adelson-Velskii和 E.M.Landis提出。
● 结点的 平衡因子 ---结点的 左 右 子树的深度之差 。
● 平衡 二叉树 ---任意结点的平衡因子的绝对值小于等于 1
的 二叉树。
T1 T2 T3 T4 T5
0 1
0
2
-1
0
0
0
-1
1 2
1
0
0
-2
平衡二叉树、二叉排序树、平衡二叉排序树的区别：
48
50
35
10
20
41
45 60
平衡二叉排序树
68
70
65
10
20
41
45 80
平衡二叉树
68
80
75
10
41
45 85
二叉排序树
-2-1-1
0
1
-1-1
1 -1
1
0 0
0
0
0
0
0
0
0
0
00
0
家庭作业
1.画出折半 查找 20个记录时的判定树，计算 ASL。
2.设输入的元素 (关键字 )序列为：
40,30,20,25,14,80,32,66,50,58,15,55
(1)试生成二叉排序树；
(2)计算 ASL；
(3)写出中序遍历结果。
3.判断下列二叉树那是平衡二叉树、二叉排序树、平衡二叉排序树
58
50
35
10
20
41
45 60
62
70
50
10
6
21
35 80 68
90
75
10
41
45 85
41
6
92
92
88
T1 T2 T3