《数据结构 教学课件 ppt 作者 宗大华 陈吉人 08查找》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 宗大华 陈吉人 08查找（97页珍藏版）》请在金锄头文库上搜索。
1、第8章 查 找,通过计算机获取信息的手段，就是通常所说的“查找”，或“检索”。它是最为常见、使用频率最高、程序中耗费时间最多的一种对数据的操作，是读取、插入、修改、删除等操作的基础。,本章主要介绍以下几个方面的内容： 有关查找的基本概念； 各种静态查找算法； 基于二叉查找树的动态查找算法； 基于散列表的动态查找算法。,8.1 查找的基本概念,设集合T里有n条记录，形式如下：,(k1, I1)，(k2, I2)，(k3, I3)，(kn, In),其中，k1、k2、kn是互不相同的n个关键字值，Ii是与ki相关联的记录信息（1in）。给定某个值K。“查找”就是要在集合T中寻找出一个记录（kj,
2、Ij），使得有kj =K。,查找成功的含义就是在T里找到一个关键字为kj的记录，使得kj=K；查找失败就是在T里找不到记录，使得kj=K（可能在T里不存在这样的记录）。,记录中的关键字ki，是记录（即数据元素）中的一个数据项。由于互不相同，因此可以用它们来标识记录。能够唯一标识一个记录的数据项，被称为是记录的“主关键字”，简称“关键字（Key）”；不能唯一标识一个记录的数据项，称为记录的“次关键字”。,有n条记录的集合T是实施查找的基础。在讨论查找问题时，常把T称为“查找表”。 如果查找只是为了获取是否成功以及相应的记录信息，并不去改变查找表的内容，那么这种查找称为“静态查找”，这时的查找表称
3、为“静态查找表”；如果查找过程会伴随着对数据元素的变更，那么这种查找称为“动态查找”，这时的查找表称为“动态查找表”。,查找时，人们总是用给定值K与各记录的关键字ki（1in）进行比较的。若用Ci表示查找第i个记录时需要进行比较的次数，用Pi表示要查找第i个记录的概率，那么查找成功的“平均查找长度（ASL）”为：,对于一般的无序线性表（顺序存储结构或链式存储结构），进行静态查找时采用的都是大家熟悉的顺序查找算法。也就是从查找表的第1个记录开始，将K按顺序依次与每个记录的关键字比较，直到找到要查找的记录（找到），或到达查找表的末尾（没有找到）为止。这种查找的效率是比较低的。,8.2 静态查找算法
4、,若已经根据某种规则对静态查找表中的记录进行了某种排序，那么就可以设计出别的算法来对表元素进行较高效率的查找。,所谓“有序表”，是指已经将记录按照关键字的大小顺序进行了排列（由小到大或由大到小）的一种查找表。基于有序表的折半查找算法，具有很高的查找效率。,8.2.1 折半查找,1折半查找的基本思想,折半查找也称为二分查找，基本思想是以有序表的中间记录为准，将表分为左、右两个子表。用给定值K与中间记录的关键字比较，若比较结果相等，则查找成功；若K小于中间记录的关键字，则取左子表继续这种查找过程；若K大于中间记录的关键字，则取右子表继续这种查找过程。重复这种做法，直到查找成功，或无该记录存在而查找
5、失败。,例8-2 设有16个记录的查找表，关键字序列如下： 08 12 15 20 24 29 32 35 38 44 48 56 60 66 74 88 现在给定K=38，试用折半查找方法找出哪一个记录的关键字等于38。,解：,图8-1 折半查找过程的描述,图8-2 结点的存储结构,2折半查找算法,实施折半查找时，应该把查找表顺序存储在一个一维数组里，数组元素的存储结构如图8-2所示。,算法8-1 有序表的折半查找算法。 已知有序表Ar共有n个记录，存储在一个一维数组里。给定值K，要求对Ar进行折半查找，返回查找成功或失败的信息。算法名为Bin_Ar()，参数为Ar、n、K。,Bin_Ar(
6、Ar, n, K) low = 1; /* 查找范围内起始记录序号置为1 */ high = n; /* 查找范围终端记录序号置为n */ while (low=high) mid = (low+high)/2; /* 将整除得到的查找范围中间记录序号存入mid */ if (KArmid.key) /* 将给定值K与中间记录关键字比较 */ high = mid 1; /* 所查记录在左子表里，修改查找范围终端记录序号 */,else if (KArmid.key) low = mid + 1; /* 所查记录在右子表里，修改查找范围起始记录序号 */ else /* 成功！返回记录序号 *
7、/ return (mid); return (-1); /* 失败！返回-1 */ ,算法8-2 有序表的（递归）折半查找算法。 已知有序表Ar，存储在一个一维数组里，起始记录序号为low，终端记录序号为high。给定值K。要求对Ar进行折半查找，返回查找成功或失败的信息。算法名为Bin_Ar1()，参数为Ar、K、low、high。,Bin_Ar1(Ar, K, low, high) if (lowhigh) /* 查找失败，返回1 */ return (1 ); else mid = (low+high)/2; /* 折半 */ if (Armid.key = K) /* 查找成功，返回
8、记录序号 */ return (mid); if (Armid.key K) return Bin_Ar1(Ar, K, low, mid1); /* 在左子表继续递归地查找 */ else return Bin_Ar1(Ar, K, mid+1, high); /* 在右子表继续递归地查找 */ ,例8-3 有如下的有序表： 7 14 18 21 23 29 31 35 38 42 46 49 52 要查找关键字为14和22的记录。利用图示说明折半查找时变量low、high、mid的变化。,图8-3 折半查找时low、high、mid的变化,所谓“分块有序表”，是指这样的一种线性表，若把它顺
9、序分为若干部分，每部分称为一“块”，那么每块里面的记录关键字虽然是无序的，但前面块里记录的最大关键字总是小于后面块里的最大关键字。比如，一线性表记录关键字的排列顺序为：,8.2.2 分块查找,图8-4 一个分块有序表,14 22 8 31 18 ，43 62 49 35 52 ， 88 78 71 83 这种分块有序表是实施分块查找的基础。,分块查找的基本思想是：按分块有序表的块的顺序，以每块中记录的最大关键字值建立一个索引表，称为索引顺序表。查找时，先用给定值K在索引顺序表里采用顺序查找算法确定出它可能在的块，然后再在该块里使用顺序查找算法最终获得查找结果：是成功或是失败。,1分块查找的基本
10、思想,例8-4 基于图8-4的分块有序表，查找关键字为K=56的记录。 解：,图8-5 分块查找时的索引顺序表,2分块查找算法,图8-6 索引顺序表结点的存储结构,算法8-3 基于分块有序表的分块查找算法。 已知分块有序表Ar存储在一个一维数组里，结点的存储结构如图8-2所示。将Ar分成b块，建立的索引顺序表Ib存储在一个一维数组里，结点的存储结构如图8-6所示。给定值K。要求对Ar进行分块查找，返回查找成功或失败的信息。算法名为Blk_Ar()，参数为Ar、Ib、K、b。,Blk_Ar(Ar, Ib, K, b) i = 1; while (iIbi.key) /* 顺序查找索引顺序表Ib
11、*/ i+; if (ib) /* 在索引顺序表里找不到适当的关键字 */ return (1); else /* 在索引顺序表里找到适当的关键字 */ j = Ibi.addn; /* j被置为本块的起始位置 */,while (jIbi.len+Ibi.addn1) /* 超出块范围，没有找到 */ return (1); else return (j); /* 找到，返回记录位置 */ ,折半查找和分块查找，它们属于静态查找的范畴。 本节讨论的二叉查找树查找，不仅具有较高的查找效率，而且还便于在查找表中进行数据的插入和删除等操作。所以，它属于动态查找的范畴。,8.3 二叉查找树的动态查找
12、,二叉查找树，又叫二叉排序树或有序二叉树，可以将它定义如下。 所谓“二叉查找树”，或是一棵空树，或是一棵满足下列条件的二叉树：,8.3.1 二叉查找树及查找算法,1二叉查找树定义,（1）若它的左子树非空，则左子树上所有结点的值都小于根结点的值； （2）若它的右子树非空，则右子树上所有结点的值都大于根结点的值； （3）它的左、右子树本身也是一棵二叉查找树。,例8-5 图8-7（a）所示为一棵二叉树，它是一棵二叉查找树吗？,图8-7 二叉查找树示例,解：图8-7（a）给出的二叉树，符合二叉查找树的条件，是一棵二叉查找树。 二叉查找树具备的条件，使这种树结构反映出了结点关键字值间的次序关系：任一结点
13、的关键字值都大于其左孩子（及其子孙）的关键字值，小于其右孩子（及其子孙）的关键字值。因此，对二叉查找树进行中序遍历，就可以得到各结点关键字由小到大的序列。,应该用二叉链表结构来存储二叉查找树，这时结点的存储结构如图8-8所示。,2二叉查找树的查找算法,图8-8 二叉查找树结点的存储结构,算法8-4 基于二叉查找树的查找算法。 已知一棵二叉查找树Bs，其结点的存储结构如图8-8所示。查找给定值为K的记录。若查找成功，返回记录的结点位置；若不成功，返回1。算法名为Bss_Bs()，参数为Bs、K。,Bss_Bs(Bs, K) ptr = Bs; while ( (ptr != NULL) ,图8-
14、9 两棵具有不同形态的二叉查找树,在二叉查找树上进行查找时的效率，与树的形状是很有关系的。,如果查找每个结点的概率相等，在查找成功的情况下，图8-9（a）给出的二叉查找树的平均查找长度为：,ASLa=(1+22+34+43)/10=3,图8-9（b）给出的二叉查找树的平均查找长度为： ASLb=(1+2+3+4+5+6+7+8+9+10)/10=5.5,由于二叉查找树采用链式存储结构，因此便于在其上进行插入和删除操作，它是一种动态查找表。在对二叉查找树进行插入、修改或删除操作时，必须保证操作后的二叉树仍是一棵二叉查找树，仍满足二叉查找树应满足的条件。,8.3.2 二叉查找树的插入与删除,只有在
15、二叉查找树上查找失败时，才进行插入。 算法8-5 基于二叉查找树的插入算法。 已知一棵二叉查找树Bs，要将关键字为K的记录插入其中。算法名为Ins_Bs()，参数为Bs、K。,1二叉查找树的插入,Ins_Bs(Bs, K) ptr = Bs; while (ptr != NULL) /* 寻找插入位置 */ if (K = ptr-key) /* 已有关键字值为K的记录 */ return ; qtr = ptr; /* 指针qtr存放结点欲插入的位置 */ if (Kkey) ptr = ptr-Lchild; else ptr = ptr-Rchild; ,rtr = malloc(siz
16、e); /* 为插入结点申请一个存储区 */ rtr-key = K; rtr-Lchild = NULL; rtr-Rchild = NULL; if (Bs = NULL) /* 原先树为空 */ Bs = rtr; else /* 树不空，按照qtr所指位置进行插入 */ if (Kkey) qtr-Lchild = rtr; else qtr-Rchild = rtr; ,算法8-6 二叉查找树的创建算法。 算法名为Crt_Bs()，最终返回指向所创建的二叉查找树的指针。,2二叉查找树的建立,Crt_Bs() ptr = NULL; scanf (“%d“, /* 返回创建的二叉查找树根结点指针 */ ,例8-6 设有关键字序列：44、77、55、22、99、33、88，请利用二叉查找树的创建算法，构造相对应的二叉查找树。 解：以所给关键字序列为基础
