七章 查找
7.1 顺序查找 7.2 折半查找 7.3 分块查找 7.4 哈希查找
电子与通信工程系 Department of Electronic and Communication Engineering
软件技术基础
主讲：李中
查找——也叫检索，是根据给定的某个值，在表中 确定一个关键字等于给定值的记录或数据元素 关键字——是数据元素中某个数据项的值，它可以 标识一个数据元素 对含有n个记录的表， ASL p c 查找方法评价
电子与通信工程系 Department of Electronic and Communication Engineering
软件技术基础
主讲：李中
算法评价
判定树：描述查找过程的二叉树 有n个结点的判定树的深度为log2n+1 折半查找法在查找过程中进行的比较次数最多不超过其判 定树的深度
折半查找的ASL
电子与通信工程系 Department of Electronic and Communication Engineering
软件技术基础
主讲：李中
7.3 分块查找
查找过程：将表分成几块，块内无序，块间有序；先确定 待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 用数组存放待查记录,每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向 本块第一个结点的指针
9 80
10 88
11 92
软件技术基础
主讲：李中
1 5
2 13
3 19
4 21
5 37
6 56
7 64
8 75
9 80
10 88
11 92
1 5
2 13
3 19
4 21
5 37
6 56 6
high low 7 8 64 75
9 80
10 88
11 92
判定树： 3 1 2 4
9 7 5 8 10 11
n i 1 i i
• • • •
查找速度 其中：p 为查找表中第 i个元素的概率， p 1 占用存储空间多少 c 为找到表中第 i个元素所需比较次数 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确 定记录在表中的位置，需和给定值进行比较的关 键字的个数的期望值
比较次数=5
电子与通信工程系 Department of Electronic and Communication Engineering
软件技术基础
主讲：李中
顺序查找方法的ASL
对含有n个记录的表， ASL pi ci
i 1 n
设表中每个元素的查找 概率相等pi
n
1 n
1 n 1 n(n 1) n 1 则ASL pi ci i n i 1 n 2 2 i 1
设表长n 2 h 1, h log2 (n 1),即判定树是深度为 h的满二叉树 设表中每个记录的查找 概率相等pi
n
1 n
1 n 1 h n 1 则：ASL pi ci ci j 2 j 1 log2 (n 1) 1 log2 (n 1) 1 n i 1 n j 1 n i 1
low
1 5
low
1 5 2 13 3 19 4 21 5 37 6 56 7 64
low mid high
1 5 2 13 3 19 4 21 5 37 6 56 7 64 8 75 low high mid
电子与通信工程系 Department of Electronic and Communication Engineering
i i 1 i i
n
电子与通信工程系 Department of Electronic and Communication Engineering
软件技术基础
主讲：李中
7.1 顺序查找
查找过程：从表的一端开始逐个进行记录的关键字和给定 值的比较
找64
例 0 1 64 5 2 13 3 19 4 21 5 37 6 56 7 64 i 监视哨 比较次数： 查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1 i 8 75 9 80 i 10 88 i 11 92 i
电子与通信工程系 Department of Electronic and Communication Engineering
软件技术基础
主讲：李中
7.2 折半查找
查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长为n，low、high和mid分别指向待查元素所在区 间的上界、下界和中点,k为给定值 初始时，令low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k==r[mid].key，查找成功 若k<r[mid].key，则high=mid-1 若k>r[mid].key，则low=mid+1 重复上述操作，直至low>high时，查找失败
low 1 2 5 13
mid 3 4 19 21
high 5 6 37 56
7 64
8 75
9 80
10 88
11 92
low mid high
电子与通信工程系 Department of Electronic and Communication Engineering
软件技术基础
主讲：李中
找70 例 1 5 2 13 3 19 4 21 5 37 6 56 mid 2 13 3 19 4 21 5 37 6 56 7 64 8 75 9 80 mid 8 75 9 80 10 88 10 88 7 64 8 75 9 80 10 88 11 92 high 11 92 high 11 92
电子与通信工程系 Department of Electronic and Communication Engineering
软件技术基础
主讲：李中
找21 例 1 5 low 1 5 2 13 3 19 4 21 5 37 2 13 3 19 4 21 5 37 6 56 mid 6 56 7 64 8 75 9 80 10 88 7 64 8 75 9 80 10 88 11 92 high 11 92