数据结构课件：第9章 查找1静态查找表.pptx

第9章 查找
查找的基本概念
静态查找表
动态查找表
哈希表
查找的基本概念
§ 查找的基本概念
查找表：是由同一类型的具有相同可辨认特性的 n i;
}
5
37
19
21
13
56
64
92
88
80
75
0
1
2
3
4
5
6
7
8
9
10
11
找60
60
监视哨
监视哨作用：避免每步都去判断是否查找结束
顺序查找的算法分析
§ 静态查找表
对于n个数据元素的表，若给定值key与表中第i个元素的关键字相等，则需要n-i+1次关键字比较，即Ci=n-i+1。
例如，当第n个元素的关键字为key时，需要进行1次比较(n-n+1=1)，又如，当第一个元素为所求时，需要进行n次比较(n-1+1=n)。因此，查找成功时，顺序查找的平均查找长度为
Pi每个元素的查找概率，假设所有元素的查找概率均相等。
顺序查找的算法分析
§ 静态查找表
对于n个数据元素的表，若给定值key与表中第i个元素的关键字相等，则需要n-i+1次关键字比较，即Ci=n-i+1。
例如，当第n个元素的关键字为key时，需要进行1次比较(n-n+1=1)，又如，当第一个元素为所求时，需要进行n次比较(n-1+1=n)。因此，查找成功时，顺序查找的平均查找长度为
顺序查找的算法分析
§ 静态查找表
若查找失败，则算法一直遍历到Elem[0]，总共比较n+1次。
5
37
19
21
13
56
64
92
88
80
75
0
1
2
3
4
5
6
7
8
9
10
11
60
顺序查找的算法分析
§ 静态查找表
查找成功时的平均查找次数为：
ASL=(1+2+3+4+……+n)/n = (n+1)/2 ①
查找不成功时的比较次数为：
ASL=(n(n+1))/n = n+1 ②
则顺序查找的平均查找长度为：
ASL==(① + ②)/2 = 3(n+1)/4
优点：算法简单，无需排序，采用顺序和链式存储均可。
缺点：当n很大时，平均查找长度较大。
有序表的查找
§ 静态查找表
折半查找
又称为二分法查找，每次将待查记录所在区间缩小一半
查找思想
先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止
前提条件
必须在具有顺序存储结构的有序表中进行
有序表的查找
§ 静态查找表
8
14
23
37
46
55
68
79
91
low
high
mid
例:查找23
high = mid-1
key
mid > key
high = n
low = 1
mid = (low+high)/2
mid = (low+high)/2
mid < key
low = mid +1
mid = (low+high)/2
有序表的查找
§ 静态查找表
8
14
23
37
46
55
68
79
91
low
high
mid
例:查找79
low = mid + 1
key
mid < key
high = n
low = 1
mid = (low+high)/2
mid = (low+high)/2
mid < key
low = mid +1
mid = (low+high)/2
有序表的查找
§ 静态查找表
8
14
23
37
46
55
68
79
91
low
high
mid
例:查找80
low = mid + 1
Key=80
mid < key
high = n
low = 1
mid = (low+high)/2
mid = (low+high)/2
mid < key
low = mid +1
mid = (low+high)/2
mid < key
low = mid + 1
mid = (low + high)/2
mid > key
high = mid - 1
折半查找的算法
§ 静态查找表
int Search_Bin( SSTable ST[ ], int n, int ke