数据结构与算法分析之查找技术(ppt 75页).ppt

1、第9章 查找技术,9.1 顺序查找 9.2 有序表的对分查找 9.3 分块查找 9.4 二叉排序树查找 9.5 hashing技术,9.1 顺序查找,9.1.1 线性表在顺序存储下的顺序查找 9.1.2 线性链表的顺序查找,9.1 顺序查找,9.1.1 线性表在顺序存储下的顺序查找 (1)如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 (2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,9.1 顺序查找,线性表在顺序存储结构下的顺序查找 输入：线性表长度n以及线性表的存储空间V； 被查找的元素x。 输出：被查找元素x在线性

2、表中的序号k。 如果在线性表中不存在元素x，则输出k1。 PROCEDURE SERCH(V，n，x，k) k1 WHILE (kn)and(V(k)x) DO kk1 IF (kn1) THEN k1 RETURN,9.1 顺序查找,/*函数返回被查找元素x在线性表中的序号， 如果在线性表中不存在元素值x，则返回1 */ int serch(v，n，x) int n； ET v，x； /*ET为线性表数据类型*/ int k； k0； while (kn)&(vkx) kk1； if (kn) k1； return(k)； ,9.1 顺序查找,9.1.2 线性链表的顺序查找,9.1 顺序查找

3、,线性表在链式存储结构下的顺序查找 输入：线性链表头指针HEAD以及存储空间V、NEXT； 被查找的元素x。 输出：被查找元素x的结点在线性链表中的存储序号k。 如果在线性链表中不存在元素值为x的结点， 则输出k1。 PROCEDURE LSERCH(V，NEXT，HEAD，x，k) kHEAD WHILE (k0)and(V(k)x) DO kNEXT(k) IF (k0) THEN k1 RETURN,9.1 顺序查找,struct node ET d； struct node *next； ； /*函数返回被查找元素x所在结点的存储地址， 如果在线性链表中不存在元素值为x的结点，则返回N

4、ULL*/ struct node *lserch(head，x) struct node *head； ET x； /*ET为线性链表中值域的数据类型*/ struct node k； khead； while (kNULL)&(kdx) kknext； return(k)； ,9.2 有序表的对分查找,设有序线性表的长度为n，被查元素为x。 将x与线性表的中间项进行比较： 若中间项的值等于x，则说明查到，查找结束； 若x小于中间项的值，则在线性表的前半部分（即中间项 以前的部分）以相同的方法进行查找； 若x大于中间项的值，则在线性表的后半部分（即中间项 以后的部分）以相同的方法进行查找。

5、这个过程一直进行到查找成功或子表长度为0(说明线性 表中没有这个元素)为止。 在最坏情况下，对分查找只需要比较log2n次， 而顺序查找需要比较n次。,9.2 有序表的对分查找,有序线性表在顺序存储结构下的对分查找 输入：有序线性表长度n以及线性表的存储空间V；被查找的元素x。 输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存 在元素x，则输出k1。 PROCEDURE BSERCH(V，n，x，k) i1； jn WHILE (ij) DO k(ij)/2 IF (V(k)x) THEN RETURN IF (V(k)x) THEN jk1； ELSE ik1； IF (ij)

6、THEN k1 RETURN,9.2 有序表的对分查找,int bserch(v，n，x) /*函数返回被查找元素x在线性表中的序号 如果在线性表中不存在元素值x，则返回1 */ int n； ET x，v； int i，j，k； i1； jn； while (ij) k(ij)/2； if (vk1x) return(k1)； if (vk1x) jk1； else ik1； return(1)； ,9.3 分块查找,分块有序表 将长度为n线性表分成m个子表，各子表的长度可以相 等，也可以互相不等，但要求后一个子表中的每一个 元素均大于前一个子表中的所有元素。 分块有序表的结构可以分为两部分

7、： (1)线性表本身采用顺序存储结构。 (2)再建立一个索引表。在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。,9.3 分块查找,struct indnode ET key；/*数据域，存放子表中的最大值， 其类型与线性表中元素的数据类 型相同*/ int k； /*指针域，指示子表中第一个元素 在线性表中的序号*/ ；,9.3 分块查找,9.3 分块查找,(1)首先查找索引表，以便确定被查元素所在的子表。由于索引表数据域中的数据是有序的，因此可以采用对分查找。 (2

8、)然后在相应的子表中用顺序查找法进行具体的查找。 分块查找 输入：长度为n的线性表L的存储空间V(1：n)；索引表中 的数据域存储空间KEY(1：m)与指针域存储空间 K(1：m)；被查元素x。 输出：被查元素x在线性表L中的序号j（即使L(j) x的j）。如果x不在线性表L中，则置j1。,9.3 分块查找,PROCEDURE INSERCH(V，n，KEY，K，m，x，j) i1； jm WHILE (ji1) DO 对分查找索引表 t(ij)/2 IF (xKEY(t) THEN jt ELSE it IF (ij)and(xKEY(i) THEN ij jK(i)； tn IF (im)

9、 THEN tK(i1)1 确定顺序查找的终点 WHILE (jt)and(V(j)x) DO jj1 顺序查找子表 IF (jt) THEN j1 RETURN,9.3 分块查找,在分块查找中，为了找到被查元素x所在的子表，需要对分查找索引 表，在最坏情况下需要查找log2(m1)次。 在相应子表中用顺序查找法查找元素x，在最坏情况下需要查找n/m （假设各子表长度相等）次；而在平均情况下需要查找n/(2m)次。 因此，分块查找的工作量为： 在最坏情况下需要查找log2(m1)n/m次， 平均情况下大约需要查找log2(m1)n/(2m)次。 当mn时，线性表L即为有序表，分块查找即为对分查

10、找 当m1时，线性表L为一般的无序表，分块查找即为顺序查找。 分块查找的效率介于对分查找和顺序查找之间。,9.3 分块查找,struct indnode ET key；/*数据域，存放子表中的最大值， 其类型与线性表中元素的数据类型相同*/ int k； /*指针域，指示子表中第一个元素在线性表中的序号*/ ； /*函数返回被查找元素x在线性表中的序号， 如果在线性表中不存在元素值x，则返回1 */ int inserch(v，n，s，m，x) int n，m； ET x，v； struct indnode s ；,9.3 分块查找, int i，j，t； i1； jm； while (ji1

11、) /*对分查找索引表*/ t(ij)/2； if (xst.key) jt； else it； if (i!j)&(xsi.key) ij； jsi.k； tn； if (i!m) tsi1.k1；/*确定顺序查找的终点*/ while(jt)&(Vj!x) jj1；/*顺序查找子表*/ if (jt) j1； return(j)； ,9.4 二叉排序树查找,9.4.1 二叉排序树及其构造 9.4.2 二叉排序树查找,9.4 二叉排序树查找,9.4.1 二叉排序树及其构造 (1)左子树上的所有结点值均小于根结点值； (2)右子树上的所有结点值均不小于根结点值； (3)左、右子树也满足上述两个

12、条件。,9.4 二叉排序树查找,9.4 二叉排序树查找,9.4 二叉排序树查找,依次读入给定序列中的每一个元素： (1)若当前的二叉排序树为空，则读入的元素为根结点； (2)若读入的元素值小于根结点值，则将元素插入到左子树中； (3)若读入的元素值不小于根结点值，则将元素插入到右子树中。 无论是插入到左子树还是右子树，同样按照上述方法处理。,9.4 二叉排序树查找,9.4 二叉排序树查找,9.4 二叉排序树查找,插入元素68,9.4 二叉排序树查找,插入元素71,9.4 二叉排序树查找,插入元素77,9.4 二叉排序树查找,插入元素88,9.4 二叉排序树查找,二叉排序树的另一种形态,9.4

13、二叉排序树查找,由无序序列构造二叉排序树 输入：长度为n的无序序列A(1：n)。 输出：二叉排序树的头指针BT。 PROCEDURE INBSORT(A，n，BT) BT0 FOR k1 TO n DO NEW(p) 取得一个新结点 V(p)A(k)； L(p)0； R(p)0 jBT IF (j0) THEN BTp 若二叉排序树为空 ELSE 二叉排序树不空,9.4 二叉排序树查找, WHILE (L(j)p)and(R(j)p) DO 未到叶子结点 IF (A(k)V(j) THEN 插入到左子树 IF (L(j)0) THEN jL(j) ELSE L(j)p ELSE 插入到右子树

14、IF (R(j)0) THEN jR(j) ELSE R(j)p RETURN,9.4 二叉排序树查找,#include stdlib.h /* malloc 函数需要包含头文件stdlib.h*/ struct btnode /*定义结点类型*/ ET d； /*数据域*/ struct btnode *lchild； /*左指针域*/ struct btnode *rchild； /*右指针域*/ ； struct btnode *inbsort(a，n) /*函数返回二叉排序树头指针*/ int n； ET a； struct btnode *p， *q， *bt； int k； btN

15、ULL；,9.4 二叉排序树查找,for (k0； kn； k) p(struct btnode *)malloc(sizeof(struct btnode)； pdak； plchildNULL； prchildNULL； /*置新结点的数据域与左、右指针域*/ qbt； if (qNULL) btp； /*二叉排序树为空*/ else /*二叉排序树不空*/ while (qlchild!p)&(qrchild!p) if (akqd) /*插入到左子树*/ if (qlchild!NULL) qqlchild； else qlchildp； ,9.4 二叉排序树查找,else /*插入到

16、右子树*/ if (qrchild!NULL) qqrchild； else qrchildp； return(bt)； /*返回二叉排序树头指针*/ ,9.4 二叉排序树查找,9.4.2 二叉排序树查找 从二叉排序树的根结点开始与被查值进行比较： (1)若被查值等于根结点值，查找成功，查找过程结束。 (2)若被查值小于根结点值，则到左子树中去查找。 (3)若被查值大于根结点值，则到右子树中去查找。 在左、右子树中查找时也采用上述方法。 查找过程直到查找成功或所考虑的子树已空为止。,9.4 二叉排序树查找,二叉排序树查找 输入：二叉排序树头指针BT以及存储空间；被查元素x。 输出：被查元素x在

17、二叉排序树空间中的存储结点序号p PROCEDURE BSTSERCH(BT，x，p) PBT WHILE (p0)and(V(p)x) DO IF (xV(p) THEN pL(p) 沿左子树查找 ELSE pR(p) 沿右子树查找 RETURN,9.4 二叉排序树查找,struct btnode /*定义结点类型*/ ET d； /*数据域*/ struct btnode *lchild； /*左指针域*/ struct btnode *rchild； /*右指针域*/ ；,9.4 二叉排序树查找,/*函数返回被查值x所在结点的存储地址*/ struct btnode *bstserch(

18、bt，x) struct btnode *bt； ET x； struct btnode *p； pbt； while (p!NULL)&(pd!x) if (xpd) pplchild；/*沿左子树查找*/ else pprchild； /*沿右子树查找*/ return(p)； ,9.5 Hash表技术,9.5.1 Hash表的基本概念 9.5.2 几种常用的Hash表,9.5.1 Hash表的基本概念,9.51.1 直接查找技术 9.51.2 Hash表 9.51.3 Hash码的构造,9.51 Hash表的基本概念,9.51.1 直接查找技术 设表的长度为n。如果存在一个函数ii(k)

19、，对于表中 的任意一个元素的关键字k，满足以下条件： (1)1in； (2)对于任意的元素关键字k1k2，恒存在i(k1)i(k2)。 则称此表为直接查找表。其中函数ii(k)称为关键字k 的映象函数。,9.51 Hash表的基本概念,1.直接查找表的填入 要将关键字为k的元素填入到直接查找表，只需做以下两 步： (1)计算关键字k的映象函数ii(k)； (2)将关键字k及有关元素信息填入到表的第i项。,9.51 Hash表的基本概念,2.直接查找表的取出 要在直接查找表中取出关键字k的元素，也只需做以下两 步： (1)计算关键字k的映象函数ii(k)； (2)检查表中第i项： 若第i项为空，

20、则说明表中没有关键字为k的元素； 否则取出第i项中的元素即可。,9.51 Hash表的基本概念,9.51.2 Hash表,9.51 Hash表的基本概念,例 将关键字序列(09，31，26，19，01，13，02，11，27 ，16，05，21)依次填入长度为n12的表中。设映象函 数为iINT(k/3)1。,9.51 Hash表的基本概念,设表的长度为n。如果存在一个函数ii(k)，对于表中 的任意一个元素的关键字k，满足1in，则称此表 为Hash表。其中函数ii(k)称为关键字k的Hash码。 (1)构造合适的Hash码，以便尽量减少表中元素冲突的次 数。即Hash码的均匀性要比较好。

21、(2)当表中元素发生冲突时，要进行适当的处理。,9.51 Hash表的基本概念,9.51.3 Hash码的构造 (1)使各关键字尽可能均匀地分布在Hash表中，即Hash码 的均匀性要好，以便减少冲突发生的机会。 (2)Hash码的计算要尽量简单。,9.51 Hash表的基本概念,1.截段法 2.分段叠加法 3.除法 imod(k，n) 4.乘法 imod(k*，n) 一般取0.618033988747，或0.6125423371， 或0.6161616161。,9.52 几种常用的Hash表,9.52.1 线性Hash表 9.52.2 随机Hash表 9.52.3 溢出Hash表 9.52.

22、4 拉链Hash表 9.52.5 指标Hash表,9.52 几种常用的Hash表,9.52.1 线性Hash表 开放法,9.52 几种常用的Hash表,1.线性Hash表的填入 将关键字k及有关信息填入线性Hash表的步骤如下： (1)计算关键字k的Hash码ii(k)。 (2)检查表中第i项的内容： 若第i项为空，则将关键字k及有关信息填入该项； 若第i项不空，则令imod(i1，n)，转(2)继续 检查。 只要Hash表尚未填满，最终总可以找到一个空项，将关 键字k及有关信息填入到Hash表中。,9.52 几种常用的Hash表,2. 线性Hash表的取出 要在线性Hash表中取出关键字k的

23、元素，其步骤如下： (1)计算关键字k的Hash码ii(k)。 (2)检查表中第i项的内容： 若第i项登记着关键字k，则取出该项元素即可； 若第i项为空，则表示在Hash表中没有该关键字的 信息； 若第i项不空，且登记的不是关键字k，则令 imod(i1，n)，转(2)继续检查。,9.52 几种常用的Hash表,例 将关键字序列(09，31，26，19，01，13，02，11，27， 16，05，21)依次填入长度为n12的线性Hash表中。设 Hash码为iINT(k/3)1。,9.52 几种常用的Hash表,缺点： (1)在线性Hash表填入的过程中，当发生冲突时，首先考 虑的是下一项，因

24、此，当Hash码的冲突较多时，在线 性Hash表中会存在“堆聚”现象，即许多关键字被连续 登记在一起，从而会降低查找效率。 (2)在线性Hash表的填入过程中，处理冲突时会带来新的 冲突。,9.52 几种常用的Hash表,9.52 几种常用的Hash表,9.52.2 随机Hash表,9.52 几种常用的Hash表,1.随机Hash表的填入 将关键字k及有关信息填入随机Hash表的步骤如下： (1)计算关键字k的Hash码i0i(k)。且令ii0。 (2)伪随机数序列初始化，令j1（即将取随机数指针指 向伪随机数序列中的第1个随机数）。 (3)检查表中第i项的内容： 若第i项为空，则将关键字k及

25、有关信息填入该项； 若第i项不空，则令imod(i0RN(j)，n)，并令 jj1（即将取随机数指针指向下一个随机数）， 转(3)继续检查。其中RN(j)表示伪随机数序列RN中的 第j个随机数。,9.52 几种常用的Hash表,伪随机数序列RN按下列方法产生： R1 FOR j1 TO n DO Rmod(5*R，4n) RN(j)INT(R/4) ,9.52 几种常用的Hash表,例 将关键字序列(09，31，26，19，01，13，02，11，27 ，16，05，21)依次填入长度为n2416的随机Hash表 中。设Hash码为iINT(k/3)1。 伪随机数序列为：1，6，15，12，1

26、3，2，11，8，9， 14，7，4，5，10，3，0。,9.52 几种常用的Hash表,2. 随机Hash表的取出 要在随机Hash表中取出关键字k的元素，其步骤如下： (1)计算关键字k的Hash码i0i(k)。且令ii0。 (2)伪随机数序列初始化，令j1（即将取随机数指针指 向伪随机数序列中的第1个随机数）。 (3)检查表中第i项的内容： 若第i项登记着关键字k，则取出该项元素即可； 若第i项空，则表示在Hash表中没有该关键字信息； 若第i项不空，且登记的不是关键字k，则令 imod(i0RN(j)，n)，并令jj1（即将取随机数 指针指向下一个随机数），转(3)继续检查。其中 RN

27、(j)表示伪随机数序列RN中的第j个随机数。,9.52 几种常用的Hash表,9.52 几种常用的Hash表,9.52.3 溢出Hash表 溢出Hash表包括Hash表和溢出表两部分。 在Hash表的填入过程中，将冲突的元素顺序填入溢出表 ，而当查找过程中发现冲突时，就在溢出表中进行顺序 查找。 溢出表是一个顺序查找表。,9.52 几种常用的Hash表,1.溢出Hash表的填入 将关键字k及有关信息填入溢出Hash表的步骤如下： (1)计算关键字k的Hash码ii(k)。 (2)检查表中第i项的内容： 若第i项为空，则将关键字k及有关信息填入该项； 若第i项不空，则将关键字k及有关信息依次填入溢出 表中的自由项。,9.52 几种常用的Hash表,2. 溢出Hash表的取出 要在溢出Hash表中取出关键字k的元素，其步骤如下： (1)计算关键字k的Hash码ii(k)。 (2)检查表中第i项的内容： 若第i项登记着关键字k，则取出该项元素即可； 若第i项为空，则表示在Hash表中没有该关键字 信息； 若第i项不空，且登记的不是关键字k，