第八章 查找.

Presentation on theme: "第八章 查找."— Presentation transcript:

1 第八章 查找

2 学习要点： 数据查找的概念与查找类型。 基于线性表的查找基本情形，一般线性表查找与“有序”线性表查找。
基于二叉树的查找概念和实现算法，二叉查找树与平衡二叉树。 基于散列表的查找概念，常用散列函数构造方法和散列冲突处理。

3 §8.1 数据查找 1、数据查找基本特征 查找表T具有两个基本特点：
给定一个数据集合T和一个数据元素e，确定e是否在T中的过程称为关于数据e的查找，简称为数据查找（search）。 1、数据查找基本特征 查找过程中给定的数据集合T称为查找表 T中数据元素称为记录 查找表T具有两个基本特点： ● T中元素之间的联系比较松散，查找表T只是一种集合，人们可以使用各种查找结构灵活处理查找表。 ● T中元素e本身要求限制较少，所有元素只需具有同一数据类型，人们可以基于数据元素的关键码对其进行操作。

4 (k1, I1)，(k2, I2)，(k3, I3)，…，(kn, In)
§8.1 数据查找2 2、查找结构 常见查找结构：线性表、树表、散列表 设给定查找表T中存在n条如下形式的记录： (k1, I1)，(k2, I2)，(k3, I3)，…，(kn, In) 其中，k1、k2、…、kn是n个关键码值，Ii是与ki相关联的记录信息（1≤i≤n）。 给定某个值K，“查找”就是要在集合T中寻找出记录（kj, Ij），使得kj =K。 评价指标：平均查找长度ASL（Average Search Length） ASL= CiPi （Ci：第i个元素的比较次数 Pi：第i个元素的查找概率）

5 查找的分类： 基于线性表查找 基于二叉树查找 （静态查找） 基于比较的查找 基于计算的查找（散列表查找） （动态查找） （静态查找）

6 §8.2 基于线性表查找 8.2.1 顺序查找 从查找表一端到另一端，给定值逐一与关键字比较。
00 int SeqSearch1(int r[ ], int n, int k) 01 { i=1; while (i<n && r[i]!=k) i++; if（i>n）,return(0), return（i）; 07 }；

7 8.2.1 顺序查找2 可设置“监视哨” ，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。
设置监视哨的查找程序如下： 00 int SeqSearch2(int r[ ], int n, int k) 01 { r[0]=k; i=n; 03 while (r[i]!=k) i --; return（i）; 06 }；

8 8.2.1 顺序查找3 评价：适应面广，关键字无要求，存储方式无要求，当关键字多时效率低。

9 练习： 某查找表有10个元素，采用顺序查找方法，前三个元素的查找概率分别为0.35，0.20与0.1，其他的元素均为0.05，问该算法的MSL和ASL。 解：MSL= 10 ASL= 1×0.35＋2×0.20＋3×0.1 ＋（4＋5＋…＋10）×0.05 = 3.5

10 8.2.2 分块查找 分块查找（block search）也称为索引顺序查找，其中无序查找表每块中记录关键码无序，但“前驱”块中记录的最大关键码小于“后继”块中最大关键码。 基本思想： 依照分块有序表的块的顺序，以每块中记录最大关键码值建立起一个索引顺序表。 在查找过程中，首先使用给定关键码k在索引顺序表里采用顺序查找确定可能所在的块，然后在该块里使用顺序查找算法最终获得查找结果。

11 8.2.2 分块查找2 索引顺序表结点结构： 分块查找索引顺序表：

12 8.2.2 分块查找3 算法8-1 基于分块有序表的分块查找算法
00 int Blk_Ar(DataType Ar[],IndexType Ib[],KeyType K, int b) 01 { int i; i = 0; while ((i<=b) && (K>Ib[i].key)) /* 顺序查找索引顺序表Ib */ i++; if (i>b) /* 在索引顺序表里找不到适当的关键码 */ return (−1); else /* 在索引顺序表里找到适当的关键码 */ { j = Ib[i].addn; /* j被置为本块的起始位置 */ 11 while((j<=Ib[i].addn+Ib[i].len−1)&&(K!=Ar[j].key)) j++; if (j>Ib[i].len+Ib[i].addn−1) /* 超出块范围，没有找到 */ return (−1); else return (j); /* 找到，返回记录位置 */ } 18 }

13 8.2.3 二分查找 1、二分查找（折半查找）算法 给定查找表T，其中元素关键码之间存在一种顺序关系时，可采用二分查找。
n个元素的查找表T采用二分查找时，效率为O（log2n）。

14 1、二分查找（折半查找）算法2 算法8-2 非递归有序表二分查找算法
00 int Bin_Ar(DataType Ar[], int n, KeyType K) 01 { int mid; low = 0; /* 查找范围内起始记录序号置为0 */ high = n-1; /* 查找范围终端记录序号置为n-1 */ while (low<=high) { mid = (low+high)/2; /* 将整除得到查找范围中间记录序号存入mid */ if (K<Ar[mid].key) /* 将给定值K与中间记录关键码比较 */ high = mid – 1; /* 所查记录在左子表，修改查找范围终端记录序号 */ 10 else if (K>Ar[mid].key) low = mid + 1;/* 所查记录在右子表，修改查找范围起始记录序号*/ else /* 成功！返回记录序号 */ return (mid); } return (-1); /* 失败！返回-1 */ 16 }

15 1、二分查找（折半查找）算法3 ASL＝O(log2n) 优势：速度快 局限性：关键字必须有序，必须采用顺序存储结构，适应面窄

16 1、二分查找（折半查找）算法4 算法8-3 基于递归的有序表二分查找算法
00 int Bin_Ar1(DataType Ar[],KeyType K, int low, int high) 01 { int mid; if (low>high) /* 查找失败，返回−1 */ 04 return (−1); else { mid = (low+high)/2; /* 二分 */ if (Ar[mid].key == K) /* 查找成功，返回记录序号 */ return (mid); if (Ar[mid].key > K) return Bin_Ar1(Ar, K, low, mid−1); /* 在左子表继续递归地查找 */ else return Bin_Ar1(Ar, K, mid+1, high); /* 在右子表继续递归地查找 */ } 15 }

17 8.2.3 二分查找2 2、二分查找判定树 二分查找判定树 在二分查找过程中，将当前查找表的“中点”作为根结点，左、右子查找表分别作为根结点的左右子树，而左右子树再按照相同方式构建其左右子树。由此得到的一棵二叉树就成为二分查找判定树（binary decision tree）或简称为判定树。

18 2、二分查找判定树2 （1）基于判定树的二分查找过程描述 （2）基于判定树的二分查找性能分析
通过判定树对二分查找过程描述可知，具有n个结点的二分查找判定树的深度为 [log2n] （不超过log2n的最大整数） 查找成功时，查找表中查找任一记录的过程就是二分查找判定树中从根结点到该数据结点的路径，和给定值的比较次数等于该数据结点在树中的层数。 查找失败时，查找过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。

19 §8.3 基于二叉树查找 8.3.1 二叉查找树概念 （中序有序）
二叉查找树（binary search tree，BST）也称为二叉排序树（binary sort tree），它采用递归方式进行定义，即一个BST或者是一棵空树，或者是一棵满足如下性质（BST性质）的二叉树： ① 当BST左子树非空时，其左子树上所有结点值都小于根结点值； ② 若BST右子树非空时，其右子树上所有结点值都大于根结点值； ③ BST左子树和右子树自身又是一棵二叉排序树。

20 8.3.1 二叉查找树概念2 练习1：判断以下是否二叉查找树？

21 8.3.1 二叉查找树概念3 二叉查找树通常使用二叉链表存储结构： 00 typedef struct node 01 {
01 { KeyType key; InfoType data; Struct node *lchild,*rchild; 05 } BSTNode;

22 8.3.2 二叉查找树查找 基本思想：将给定关键码值k与二叉查找树根结点中关键码值进行比较，相等就得到查找成果，否则，k小于根结点关键码，所查找数据只可能在根结点的左子树中，需要沿左子树继续进行搜索；k大于根结点关键码时，所查具记录只可能在根结点的右子树中，需要沿右子树继续进行搜索。

23 8.3.2 二叉查找树查找2 算法8-4 基于二叉查找树的查找算法
算法8-4 基于二叉查找树的查找算法 00 int Bss_Bs(BSTNode *Bs, KeyType K) 01 { BSTNode *ptr; ptr = Bs; while ( (ptr != NULL) &&(ptr->key != K) ) { if ( K<ptr->key ) ptr = ptr->Lchild; else ptr = ptr->Rchild; } if (ptr != NULL) return (ptr); else return (−1); 15 }

24 8.3.3 二叉查找树插入与生成 功能：找到在树非空情况下待插入数据记录正确的插入位置。 1、二叉查找树插入算法
算法8-4 基于二叉查找树的查找算法（第1部分） while (ptr != NULL) /* 寻找插入位置 */ { if (K == ptr->key) /* 已有关键码值为K的记录 */ return ; 08 qtr = ptr; /* 指针qtr存放结点欲插入的位置 */ if (K<ptr->key) ptr = ptr->Lchild; else ptr = ptr->Rchild; 13 } 功能：找到在树非空情况下待插入数据记录正确的插入位置。

25 8.3.3 二叉查找树插入与生成 功能：为插入结点申请一个存储区并赋值 1、二叉查找树插入算法2
算法8-4 基于二叉查找树的查找算法（第2部分） rtr = (BSTNode *)malloc(sizeof(BSTNode)); rtr->key = K; rtr->Lchild = NULL; rtr->Rchild = NULL; 功能：为插入结点申请一个存储区并赋值

26 8.3.3 二叉查找树插入与生成 功能：根据K值的情况完成插入。 1、二叉查找树插入算法3 算法8-4 基于二叉查找树的查找算法（第3部分）
算法8-4 基于二叉查找树的查找算法（第3部分） if (Bs == NULL) /* 原先树为空 */ Bs = rtr; else /* 树不空，按照qtr所指位置进行插入 */ if (K<qtr->key) qtr->Lchild = rtr; 23 else qtr->Rchild = rtr; 功能：根据K值的情况完成插入。

27 8.3.3 二叉查找树插入与生成2 2、二叉查找树创建算法 算法8-6 二叉查找树的创建算法 00 BSTNode *Crt_Bs()
算法8-6 二叉查找树的创建算法 00 BSTNode *Crt_Bs() 01 { BSTNode *ptr; KeyType key; ptr = NULL; scanf ("%d", &key); /* 输入一个关键码值 */ while (key != −1) /* 调用插入算法，进行结点插入 */ { Ins_Bs(ptr, key); scanf ("%d", %key); } return (ptr); /* 返回创建的二叉查找树根结点指针 */ 12 }

28 2.二叉查找树创建算法2 例：有关键码序列：38，30，41，24，35，56，32。构造二叉查找树。 空集 插入30 插入38 插入41
插入24 插入35

29 2.二叉查找树创建算法2 例：有关键码序列：38，30，41，24，35，32，56。构造二叉查找树（续）。 插入32 插入56

30 练习： 1、有数列38，26，60，94，75，50，35，47，试构造二叉查找树。

31 8.3.4 二叉查找树删除 设P为需要删除结点，Pp为P的父结点，Pc为P的左或右子结点。 1、P为叶结点 直接将Pp指向P的域置空即可。

32 8.3.4 二叉查找树删除2 2、P只有一棵非空子树 直接将Pp指向P的域指向P的非空子树。

33 8.3.4 二叉查找树删除3 3、P具有两棵非空子树 （1）中序序列法 基于中序前驱删除：

34 8.3.4 二叉查找树删除3 3、P具有两棵非空子树 （1）中序序列法2 基于中序后继删除：

35 8.3.4 二叉查找树删除3 3、P具有两棵非空子树2 （2）子树根结点取代法
若用P的左子树的根结点PL去取代需删结点P，那么需删结点P的右子树成为新根结点PL的右子树。此时PL的左子树（如果有的话）保持不变，而PL右子树应被调整为P中序后继Pm1的左子树。

36 8.3.5 平衡二叉树 二叉查找树的ASL与形态有关，最好能平衡，则 ASL=O（log2n）。
平衡二叉树 二叉查找树的ASL与形态有关，最好能平衡，则 ASL=O（log2n）。 平衡因子： 左、右子树深度之差（hl-hr） AVL：二叉查找树上所有结点平衡因子 |hl-hr|≤1

37 平衡二叉树2 平衡二叉树的调整： 在生成二叉查找树的过程中，需修改祖先结点的平衡因子，如遇第一个平衡被破坏的祖先即开始调整，使第一个被破坏的祖先|hl-hr|≤1，即可保持平衡，称为局部调整。 调整的四种类型（P为新结点，A为被破坏平衡的祖先）： 1、LL型：P插入在A的左子结点B的左子树BL上。 2、LR型：P插入在A的左子结点B的右子树BR上。 3、RR型：P插入在A的右子结点B的右子树BR上。 4、RL型：P插入在A的右子结点B的左子树BL上。

38 8.3.5 平衡二叉树3 1、LL型调整：（一次顺时针旋转）
平衡二叉树3 1、LL型调整：（一次顺时针旋转） 将B“提升”为根结点，将A“下降”为B的右子结点，将B的右子树BR转换为A的左子树，即顺时针旋转。

39 8.3.5 平衡二叉树4 2、 LR型调整：（一次逆时针旋转）
平衡二叉树4 2、 LR型调整：（一次逆时针旋转） 先处理B这棵子树，将C“提升”为根结点，B“下降”为C的左子结点，C原来的左子结点成为B的右子结点，即局部逆时针旋转；再处理整棵树，将C“提升”为根结点，将A“下降”为C的右子结点，C原来的右子结点成为A的左子结点，即整体顺时针旋转。

40 8.3.5 平衡二叉树5 3、 RR型调整：（一次逆时针旋转）
平衡二叉树5 3、 RR型调整：（一次逆时针旋转） 将B“提升”为根结点，将A“下降”为B的左子结点，将B左子树BL转换为A的右子树，即逆时针旋转。

41 8.3.5 平衡二叉树6 4、 RL型调整：（先局部顺时针，再整体逆时针旋转）
平衡二叉树6 4、 RL型调整：（先局部顺时针，再整体逆时针旋转） 先处理B这棵子树，将C“提升”为根结点，B“下降”为C的右子结点，C原来的右子结点成为B的左子结点，即局部顺时针旋转；再处理整棵树，将C“提升”为根结点，将A“下降”为C的左子结点，C原来的左子结点成为A的右子结点，即整体逆时针旋转。

42 平衡二叉树7 相应算法可以描述如下： ① 查找P插入位置过程中记录距插入位置最近同时平衡度不等于0的结点A，这是可能的最小不平衡树的根结点。 ② 修改A到插入位置路径上所有点的平衡度，而其他结点平衡度不予改变。 ③ 判断插入P后，A平衡度绝对值是否增加1。在肯定情况下调用最小不平衡树调整算法；否则插入P的过程就此结束。 基于AVL查找的时间复杂度为O（log2n）。

43 练习： 集合{50，20，10，100，120，30，110，60，70，90，80，40}，画出为其构造二叉平衡树的过程。

44 §8.4 基于散列表查找 散列查找：设需要存储的线性表中数据对象个数为n，开辟一个长度为m（m≥n）的连续内存单元。以数据元素关键码k为自变量，建立一个Hash函数H（k），该Hash函数将关键码映射为内存单元地址（也称为下标）同时将对应数据元素存储在该内存单元当中。 散列表：查找表，表中关键字的位置是由散列函数求得的。 散列函数：以关键字为自变量的函数，函数值为该关键字在表中的地址。 冲突：不同关键字得到的散列函数值一样，即地址一样，产生冲突。 同义词：产生冲突的关键字

45 §8.4 基于散列表查找2 散列查找特点： 基于计算找到关键字地址 平均查找长度（ASL）与散列表长度或关键字个数无关。

46 8.4.1 常用散列函数的构造 1、直接定址法 散列函数H（k）定义为 H（k）=k+c。 2、数字分析法
对关键字进行分析，取其中分布均匀的几位构造散列函数。 3、除余法 对关键字进行取模运算，散列函数H (k)为：H (k) = key% p 。 关键：模的选取。如散列表长度为n，取小于n的质数，减少地址冲突。

47 8.4.1 常用散列函数的构造2 4、平方取中法 平方取中法是先将关键码进行平方，然后根据散列表大小选取平方数中间若干位作为相应数据记录的散列地址。 5、折叠法 将关键码分割成位数相等的几部分（最后一部分的位数可以不同），对这几部分叠加求和。 移位折叠法 边界折叠法 （以上各种方法应根据实际情况选取，可结合使用）

48 8.4.1 常用散列函数的构造3 构造散列函数应考虑的因素： 1、计算散列函数的时间（不能太复杂） 2、关键字的长度（是否等长，多大等）
3、散列表的大小（地址范围，即值域） 4、关键字的值的情况（各位值的分布等） 5、查找概率（概率大的先散列）

49 8.4.2 散列冲突处理 冲突难以避免，影响因素有： 首先，定义装填因子α=n/m，其中n为散列表中的数据元素个数，m为Hash地址空间大小。α越小，就表明散列表中空闲单元比例越大，待插入记录与已插入记录发生冲的可能性也越小；α越大时，就表明发生冲突的可能性越高。当然，α越小时存储空间利用率也就越低。为了达到适当平衡，通常需要控制α在0.6至0.9的范围之内。 其次，散列函数的选择，应尽量使得Hash地址得到均匀分布，进而减少冲突的发生。 另外，散列冲突函数选择适当与否也或减少或增加冲突发生可能性。

50 目的：找到一个空地址，以存放产生冲突的关键字。 hi (key) = (h (k) + i ) % m， (i=1, 2, …, p)
8.4.2 散列冲突处理2 目的：找到一个空地址，以存放产生冲突的关键字。 1、开放地址法 当冲突产生时，按一个已知序列逐个查询空地址 （1）线性探测法 hi (key) = (h (k) + i ) % m， (i=1, 2, …, p) p是探测的最大次数

51 例子： 散列表长为10，以关键码末尾数字作为散列地址，依次插入35、22、23、85、19、32、39、72共8个记录，采用线性探测法处理可能发生的冲突。

52 hi (key) = (h (k) i2) % m， (i=1, 2, …, p)
8.4.2 散列冲突处理2 1、开放地址法2 （2）二次方探测 hi (key) = (h (k) i2) % m， (i=1, 2, …, p)

53 例子： 设散列表长m=10，h (k)定义为以关键码末尾数码作为散列地址，依次插入35、22、23、85、19、32、39、72共8个记录，采用二次探测法处理可能发生的冲突。

54 发生冲突进行探测时，使用的地址增量是一个随机数序列。
8.4.2 散列冲突处理2 1、开放地址法3 （3）伪随机探测 发生冲突进行探测时，使用的地址增量是一个随机数序列。 即事先设好的伪随机d(i)

55 8.4.2 散列冲突处理3 2、拉链法 拉链法也称为“链地址法”，其基本点是把具有相同散列地址的关键码记录（它们都是同义词）用一个单链表链接在一起，组成同义词链表。 如右图：

56 8.4.2 散列冲突处理4 注意：冲突是无法根除的，如最后关键字都不能填入表中，则视为溢出处理。
查找算法：取决于散列函数与解决冲突的方法，算法效率则还与装填因子有关。

57 练 习: 键值集合{ ICK，BAR，FLY，KER，FRE，LOW，BEN，FON，ERV，KNO }，试构造装填因子=10/13的散列表，取键值的首字母的（字典序-1）作为散列函数值，用线性探测法解决冲突，画出其散列表，并计算等概率下查找成功的平均查找长度。 解：hash(key)=ord(key)-ord(‘A’) A B C D E F G H I J K L

58 { ICK，BAR，FLY，KER，FRE， LOW，BEN，FON，ERV，KNO } A B C D E F G H I J K L 0 1 2 3 4 5 6 7 8 9 10 11
BAR BEN ERV FLY FRE FON ICK KER LOW KNO 1 2 3 比较次数： ASL=（ ）/10=1.6

59 上 机: 自己定义一个散列函数，例如f(x)=x mod 11， 从键盘输入一数列，依次插入到散列表中去， 采用线性探测方法解决碰撞问题。
上 机: 自己定义一个散列函数，例如f(x)=x mod 11， 从键盘输入一数列，依次插入到散列表中去， 采用线性探测方法解决碰撞问题。 输入一个数字，根据你所选择的散列函数进行相应的查找，输出查找结果。

60 建立散列表： 1、定义一个长度为15的数组； 2、循环10次，循环体内容为： 1）键盘输入一个数字 2）利用f(x)函数计算地址
3）看地址是否是空地址， 是:则填写入该地址; 否:则探测其后3个单元内（注意应是合法地址）是否有空地址，有则填写，否则认为溢出，输出不能插入的提示。 3、输出数组。

61 查找： 1、输入一个数字x； 2、利用f(x)函数计算地址 y=x % 11; 3、查看地址是否为该数， 是：则表示找到，输出该地址；
否：则探测其后3个单元内是否有该数，有则表示找到，输出该地址填写，否则认为找不到，输出提示信息。

62 本章小结 本章基本内容