【考研计算机专业课】武汉大学数据结构PPT课件 第9章 查找

子表2
若k＜x.key，只需在子表1中查找；
若k>x.key，只需在子表2中查找；
例 如 ， 在 关 键 字 有 序 序 列 {2,4,7,9,10,14,18,26,32,40}中采用二分查找 法查找关键字为7的元素。
二分查找过程如下：
开始: 40
0
2
1
2
4
3
7
4
9
5
10
6
7
14
8
18
high=9
i=6
查找成功，返回序号6
顺序查找的算法如下（在顺序表R[0..n-1]中查找关键 字为 k 的记录 , 成功时返回找到的记录位臵 , 失败时返回 1）：
int SeqSearch(SeqList R,int n,KeyType k)
{ int i=0; while (i<n && R[i].key!=k) i++; //从表头往后找 if (i>=n) return -1; else return i; }
i=1
第3次比较: 3 9 1 5 8 10 6 7 2 4
i=2
第4次比较: 3 9 1 5 8 10 6 7 2 4
i=3
第5次比较: 3 9 1 5 8 10 6 7 2 4
i=4
第6次比较: 3 9 1 5 8 10 6 7 2 4
i=5
第7次比较: 3 9 1 5 8 10 6 7 2 4
查找算法
采用何种查找方法?
数据组织方式 数据是否有序
（ 1 ）使用哪种数据结构来表示“表”，即 表中记录是按何种方式组织的。
（ 2 ）表中关键字的次序。是对无序集合查 找还是对有序集合查找?
若在查找的同时对表做修改运算（如插入 和删除），则相应的表称之为动态查找表；否 则称之为静态查找表。
由于查找运算的主要运算是关键字的比较,所以通常把查找 过程中对关键字需要执行的平均比较次数(也称为平均查找长度) 作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL
思考题 采用二分查找的数据适合采用什么存储结构。
其算法如下（在有序表R[0..n-1]中进行二分查找,成功时返回记录 的位臵，失败时返回-1）：
int BinSearch(SeqList R,int n,KeyType k) { int low=0,high=n-1,mid; while (low<=high) { mid=(low+high)/2; if (R[mid].key==k) //查找成功返回 return mid; if (R[mid].key>k) //继续在R[low..mid-1]查找 high=mid-1; else low=mid+1; //继续在R[mid+1..high]中查找 } return -1; }
第9章 查找
9.1 查找的基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表查找
9.1 查找的基本概念
被查找的对象是由一组记录组成的表或文件 ,而每
个记录则由若干个数据项组成 , 并假设每个记录都有
一个能唯一标识该记录的关键字。
在这种条件下 , 查找的定义是：给定一个值 k, 在含有 n 个记 录的表中找出关键字等于 k 的记录。若找到 ,则查找成功 , 返回 该记录的信息或该记录在表中的位臵；否则查找失败 , 返回相 关的指示信息。
从顺序查找过程可以看到（不考虑越界比较i<n），ci取 决于所查记录在表中的位臵。如查找表中第1个记录R[0]时, 仅需比较一次；而查找表中最后一个记录R[n-1]时，需比较 n次,即ci=i。因此，成功时的顺序查找的平均查找长度为：
1 n 1 n(n 1) n 1 ASL p c i sq i 1 i i n i 1 n 2 2
9
26
32
low=0 第1次比较: 2
0
mid=(0+9)/2=4 4
1
7
2
9
3
10
4
14
40
9
low=0 mid=(0+3)/2=1 high=3
第2次比较: 2
0
4
1
7
2
9
3
10
4
14
5
18
6
26
7
32
8
40
9
low=2 mid=(2+3)/2=2 high=3 查找成功，返回序号2
（1）顺序查找 （2）二分查找 （3）分块查找 因为不考虑在查找的同时对表做修改，故上述三种查找操作 都是在静态查找表上实现的。
查找与数据的存储结构有关,线性表有顺序和链式两种存储
结构。本节只介绍以顺序表作为存储结构时实现的顺序查找算 法。定义被查找的顺序表类型定义如下：
#define MAXL <表中最多记录个数>
typedef struct { KeyType key; //KeyType为关键字的数据类型
InfoType data;
} NodeType;
//其他数据
typedef NodeType SeqList[MAXL]; //顺序表类型
9.2.1 顺序查找
顺序查找是一种最简单的查找方法。
思路：从表的一端开始，顺序扫描线性表，依次将扫描到的 关键字和给定值k相比较，若当前扫描到的关键字与k相等，则 查找成功；若扫描结束后，仍未找到关键字等于 k 的记录，则
n
查找成功时的平均比较次数约为表长的一半 。 思考题：不成功时的平均查找长度是多少？
9.2.2 二分查找
二分查找也称为折半查找，要求线性表中的结点 必须己按关键字值的递增或递减顺序排列。
思路：首先用要查找的关键字 k 与中间位臵的结点的关键 字相比较，这个中间结点把线性表分成了两个子表，若比较结 果相等则查找完成；若不相等,再根据k与该中间结点关键字的 比较大小确定下一步查找哪个子表，这样递归进行下去，直到 找到满足条件的结点或者该线性表中没有这样的结点。 子表1 若k=x.key，找到了； x
（Average Search Length）定义为：
ASL p i c i
i 1
n
其中,n是查找表中记录的个数。pi是查找第i个记录的概率。一 般地，均认为每个记录的查找概率相等，即pi=1/n（1≤i≤n），ci是 找到第i个记录所需进行的比较次数。
9.2 线性表的查找
在表的组织方式中 , 线性表是最简单的一种。三种 在线性表上进行查找的方法：
查找失败。
例 如 ， 在 关 键 字 序 列 为 {3,9,1,5,8,10,6,7,2,4}的线性表查找关键
字为6的元素。
顺序查找过程如下：
从前向后查找 开始: 3 9 1 5 8 10 6 7 2 4
第1次比较: 3 9 1 5 8 10 6 7 2 4
i=0
第2次比较: 3 9 1 5 8 10 6 7 2 4