数据结构预算法第九章查找.pptx
第九章第九章 查找查找9.19.1 查找的基本概念查找的基本概念9.2 静态查找9.39.3 动态查找动态查找9.49.4 哈希表哈希表v 9.1 9.1 查找的基本概念查找的基本概念v1.1.查找表：查找表：由同一类型的数据元素（或记录）构成的集合称为查找表。v2.2.对查找表进行的操作：对查找表进行的操作：v（1）查找某个特定的数据元素是否存在。v（2）检索某个特定数据元素的属性。v（3）在查找表中插入一个数据元素。v（4）在查找表中删除一个数据元素。v3.3.静态查找：静态查找：在查找过程中仅查找某个特定元素存在或查找其属性，称为静态查找。v4.4.动态查找：动态查找：在查找过程中对查找表进行插入或删除元素操作，称为动态查找。v5.5.关键字：关键字：数据元素（或记录）中某个数据项的值，用它可以标识数据元素（或记录）。v6.6.主关键字：主关键字：可以唯一地标识一个记录的关键字称为主关键字。v7.7.次关键字：次关键字：可以标识若干个记录的关键字称为次关键字。v8.8.查找：查找：在查找表中确定是否存在一个数据元素的关键字等于给定值的操作，称为查找（或检索)。若表中存在这样一个数据元素（或记录），则查找成功；否则，查找失败。v9.9.内查找和外查找：内查找和外查找：若整个查找过程全部在内存进行，则称为内查找；若在查找过程中还需要访问外存，则称为外查找。v10.10.平均查找长度：平均查找长度：查找算法的效率，主要是看要查找的值与关键字的比较次数，通常用平均查找长度来衡量。对一个含n个数据元素的表，查找成功时： v v 其中,n是查找表中记录的个数。pi是查找第i个记录的概率,一般地,均认为每个记录的查找概率相等,即pi=1/n(1in),ci是找到第i个记录所需进行的比较次数 n1iiicpASL9.2 9.2 静态查找表静态查找表具有具有顺序查找法顺序查找法、折半查找法折半查找法和和分块查找法分块查找法三种三种9.2.1 顺序查找顺序查找顺序查找法的特点是：用顺序查找法的特点是：用所给关键字与线性表中各元素所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。的关键字逐个比较，直到成功或失败。 监视哨的作用：监视哨的作用：（1）省去判定循环中下标越界的条件，从而节约比较时间。）省去判定循环中下标越界的条件，从而节约比较时间。（2）保存查找值的副本，查找时若遇到它，则表示查找成）保存查找值的副本，查找时若遇到它，则表示查找成功。这样在从后向前查找失败时，不必判断查找是否检测完，功。这样在从后向前查找失败时，不必判断查找是否检测完，从而达到算法统一。从而达到算法统一。用用平均查找长度分析顺序查找算法的性能：平均查找长度分析顺序查找算法的性能： 假设假设列表长度为列表长度为n，那么查找第那么查找第i个数据元素时需个数据元素时需进行进行n-i+1次比较，即次比较，即Ci=n-i+1。又假设查找每个数据又假设查找每个数据元素的概率相等，即元素的概率相等，即Pi=1/n，则顺序查找算法的平均则顺序查找算法的平均查找长度为：查找长度为： ASL=i=1nPiCin1i=1nCin1i=1n(n-i+1)=21(n+1)顺序查找的缺点：顺序查找的缺点：当当n很大时，平均查找长度较大，很大时，平均查找长度较大，效率低；效率低；优点：优点：对表中数据元素的存储没有要求。对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。另外，对于线性链表，只能进行顺序查找。9.2.2 折半查找法折半查找法（二分法查找法）（二分法查找法）条件：条件：要求要求待查找的列表必须是待查找的列表必须是按关键字大小有序按关键字大小有序排列的顺序表排列的顺序表。 基本过程：基本过程：将表中间位置记录的关键字与查找关键将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。表不存在为止，此时查找不成功。 例如用折半查找法查找例如用折半查找法查找10、50的具体过程，的具体过程，其中其中mid=(low+high)/2，当，当highlow时，表示不存在这样时，表示不存在这样的子表空间，查找失败。的子表空间，查找失败。 605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=1mid=6high=11605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=1 mid=3high=5用用折半查找法查找折半查找法查找12的过程为：的过程为：605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=1mid=1high=2605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=2mid=2high=2用用折半查找法查找折半查找法查找50的过程：的过程：605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=1mid=6high=11605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=7 mid=9high=11605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=10mid=10high=11605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=10high=9用用平均查找长度分析折半查找算法的性能：平均查找长度分析折半查找算法的性能：折半查找成功时的平均查找长度为：折半查找成功时的平均查找长度为：ASLbsi=1nPiCin1j=1nj2j-1nn+1log2(n+1)-1优点：优点：比较次数少，查找速度快，平均性能好。比较次数少，查找速度快，平均性能好。缺点：缺点：要求待查的表为有序表，且插入、删除困难。要求待查的表为有序表，且插入、删除困难。9.2.3 分块查找法分块查找法分块查找法要求将列表组织成以下索引顺序结构：分块查找法要求将列表组织成以下索引顺序结构：首先将列表分成若干个块（子表）。首先将列表分成若干个块（子表）。一般情况下，一般情况下，块的长度均匀，最后一块可以不满。每块中元素任块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。意排列，即块内无序，但块与块之间有序。 构造一个索引表。其中每个索引项对应一个块并构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，和每块中的最大关键字（或记录每块的起始位置，和每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。最小关键字）。索引表按关键字有序排列。 下图为下图为一个索引顺序表一个索引顺序表25 58 888871605836453228825121418索引表索引表各块内的各块内的最大关键字最大关键字各块的各块的起始地址起始地址列表列表 0 1 2 3 4 5 6 7 8 9 10 11 12此表此表包括三个块，第一个块的起始地址为包括三个块，第一个块的起始地址为0，块内最，块内最大关键字为大关键字为25;第二个块的起始地址为第二个块的起始地址为5，块内最大，块内最大关键字为关键字为58;第三个块的起始地址为第三个块的起始地址为10，块内最大关，块内最大关键字为键字为88。分块查找的基本过程为：分块查找的基本过程为：（1）首先，将待查关键字首先，将待查关键字K与索引表中的关键字进与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。序查找法或折半查找法进行。（2 2）进一步用顺序查找法，在相应块内查找关键字）进一步用顺序查找法，在相应块内查找关键字为为K的元素。的元素。 分块查找的平均查找长度分块查找的平均查找长度由两部分组成：即查找索由两部分组成：即查找索引表时的平均查找长度为引表时的平均查找长度为LB，以及在相应块内进行以及在相应块内进行顺序查找的平均查找长度顺序查找的平均查找长度LW。ASLbs=LB+LW 假定假定将长度为将长度为n的表分成的表分成b块，且每块含块，且每块含s个元素，则个元素，则b=n/s。又假定表中每个元素的查找概率相等，则每又假定表中每个元素的查找概率相等，则每个索引项的查找概率为个索引项的查找概率为1/b，块中每个元素的查找概块中每个元素的查找概率为率为1/s。若用顺序查找法确定待查元素所在的块，若用顺序查找法确定待查元素所在的块，则有：则有： LBb1jj=1bb12Lws1ji=1ss12ASLbs=LB+LW 2b+s+1将将b=n/s代入，得代入，得ASLbs21+1sn+s)(三种查找方法比较三种查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找ASL大大小小 中中表结构要求表结构要求无无有序表有序表 分段有序分段有序（块之间有序）（块之间有序）v9.3 9.3 动态查找动态查找v9.3.1 9.3.1 二叉排序树二叉排序树1.1.二叉排序树的定义二叉排序树的定义二叉排序树或者是一棵空树,或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值。（2）若右子树不空，则右子树上所有结点的值均大于根结点的值。（3）左、右子树也都是二叉排序树。2.2.二叉排序树的构造二叉排序树的构造根据二叉排序树的性质，每次都按结点大小从根结点查找到对应的插入位置插入。例：有一组结点的关键字大小分别为：45、12、53、3、37、24、100、61、90、78求由这些结点构造成的二叉排序树的过程如图所示。二叉排序树的删除v二叉排序的删除v删除查找树中键值为key的结点的操作可按以下步骤进行： 首先确定被删除结点的位置，如被删结点不在树，则函数返回；否则按以下多种情况作结点删除。（1）如被删除结点是根结点： 被删除结点无左子树；则以被删除结点的右子树作为删除后的树。 被删除结点有左子树，则以被删除结点的左子结点作为根结点，并把被删除结点的右子树作为被删结点的左子树按中序遍历得最后一结点的右子树。二叉排序的删除（续）（2）如被删结点不是根结点，且被删结点无左子结点。 如被删结点是它的双亲结点的左子结子，则把被删结点右子树作为被删结点的双亲结点的左子树； 如被删结点是它的双亲结点的右子结点，则被删结点的右子树作为被删结点的双亲结点的右子树。（3）如被删结点不是根结点，且被删结点有左子结点，把被删结点的右子树作为被删结点的左子树按中序遍历得最后一结点的右子树，同时进行以下操作： 如被删结点是它的双亲结点的左子结点，则把被删结点的左子树作为被删结点的双亲结点的左子树。 如被删结点是它双亲结点的右子结点，则把被删结点的左子树作为被删结点的双亲结点的右子树。二叉排序树的删除操作v1、若p没有左子树，直接用p的右孩子取代它；v2、若p有左子树，用p的左孩子取代它；找到其左子树的最右边的叶子结点r，把p的右子树作为r的右子树。 9.3.2平衡二叉树平衡二叉树(AVL树树)一、一、AVL树（高度平衡的树（高度平衡的BST）概念概念 1、定义AVL或是空树，或是具有下列性质的BST：它的左、右子树都是AVL树，且左右子树的高度之差的绝对值不超过1。2、举例 是二叉搜索树 树和所有子树的右左子树 高度之差绝对值不超过1 属AVL树111514263971816-1000000013、平衡因子（balance factor） 结点左子树高度减去右子树高度所得高度差 AVL树中所有结点的平衡因子只能取0，1，1 二、平衡化旋转二、平衡化旋转 1、向AVL树插入结点可能造成不平衡，此时要调整树的结构，使之重新达到平衡 2、平衡化旋转方法 从插入位置沿通向根的路径检查各结点的平衡 因子 若发现不平衡结点，则从该结点起沿刚才回溯路径取直接下两层结点 若三个结点在一条直线上(RR、LL型)，则采用单旋转进行平衡化，此时处于中间位置的结点为旋转中心 若三结点不在一条直线上(LR、RL型)，则采用双旋转进行平衡化，此时处于下方位置的结点为旋转中心3、平衡化旋转示例 RR型（逆时针单旋转）hhhABCDE01(a)AVL树hhh+1ABCDE12(b)E子树中插入结点hhh+1ABCDE00(c)左向旋转后的AVL树二、平衡化旋转二、平衡化旋转 LL型（顺时针单旋转）hhhABCDE0- 1(a)AVL树hhh+1ABCDE- 1- 2(b)D子树中插入结点hhh+1ABCDE00(c) 右向旋转后的AVL树3、平衡化旋转示例二、平衡化旋转二、平衡化旋转hhh-1hABCDEFG插入(a)F子树插入结点高度变为h- 21- 1hhh-1hABCDEFG(b)绕E，将B逆时针转后hhh-1hABCDEFG(c)绕E，将A顺时针转后03、 LR型（先逆时针，后顺时针双旋转）二、平衡化旋转二、平衡化旋转hhh-1hABCDEFG插入(a)G子树插入结点高度变为h21- 1hhh-1hABCDEFG(b)绕D，C顺时针转之后hhh-1hABCDEFG(c)绕D，A逆时针转之后03、 RL型（先顺时针，后逆时针双旋转）二、平衡化旋转二、平衡化旋转三、三、AVL树的建立树的建立 对于一组关键码的输入序列，从空开始不断插入结点，最后构成AVL树 每插入一个结点后就应判断从该结点到根的路径上有无结点发生不平衡 如有不平衡问题，利用旋转方法进行树的调整，使之平衡化 建AVL树过程是不断插入结点和必要时进行平衡化的过程 建AVL树过程举例：9.4 9.4 哈希表及其查找哈希表及其查找9.4.1 9.4.1 哈希表哈希表 v哈希表又称散列表， 是一种非常实用的查找技术。查找为结点的存储位置和它的关键码之间建立一个确定的关系，从而就可使查找码直接利用这个关系确定结点的位置。v在散列表中，结点存储时，以结点的关键码为自变量，按某种公式计算其存储位置，并以该位置存储。查找时，以查找码为自变量计算同一公式，就能得到对应结点的存储位置，去取出结点，所以散列表能进行快速查找。称查找码计算结点存储位置的公式为散列函数，记为H（）。9.3.1 9.3.1 哈希表哈希表 v一般情况下，能存入散列表中的结点所有可能的不同关键码个数比散列表能存储的结点个数要大得多。因此两个不同关键码k1和k2的散列函数值可能相等：H（k1）=H(k2)且k1k2。这种现象称为冲突，并称k1和k2为同义词。为了有效地使用散列技术，需要解决两个问题：v找一个好的散列函数，使出现冲突机会尽可能少；v设计有效解决冲突的方法。9.3.2 9.3.2 常见的散列函数常见的散列函数 1.除留余数法v令P是是一个整数,若哈希表长为m,则要求p= m，且接近 m或等于m。设查找码为key，计算的散列函数为Hash(key)= key%p2.直接定址法v直接定址法是取关键字的某个线性函数值为哈希地址,即vHash(key)=a*key+b3.平方取中法v让查找码自乘，取其中间若干位的值，并乘上某个比例因子，使值在0至m-1之间。9.3.3 9.3.3 解决冲突的方法解决冲突的方法 1.线性探查法v如按查找码key求得的第H（key）桶以满时，就得到另一个桶去找空位，将结点存入。线性探查法使用下列探查序列：vH（key）,H（key）+1,H（key）+2,，m-1，0，1H（key）-1v使用线性探查法解决冲突，会出现堆积现象。可能会发生这样的情况，有某结点的关键码计算出它的散列地址，希望按该地址存储该结点，但该位置已被不是它的同义词的结点所占用。因冲突沿着线性探查序列进行查找，而这些位置也可能已存入非同义词的其他结点，结果使得不是同义词的许多结点处在同一个探查序列中。 2.双散列函数法v由于线性探查发容易产生堆积现象，会大大降低查找效率，可用双散列函数法。散列函数H1（）产生0到m-1的桶号d，当冲突发生时，散列函数H2（）产生1到m-1,并与m 互质的数c作为对H1（）的补偿，使探查序列跳跃式地分布在整个散列表中：v （d+c）%m,(d+2c)%m,(d+3c)%m,3. 拉链法v用拉链法处理冲突，要求散列表的每个结点增加一个指针字段，用于链接同义词的子表，链表中的结点都是同义词。查找方法如下：（）按散列函数计算出桶号i；（）判断对应的同义词链表指针是否为空，若为空则查找失败结束。（）遍用同义词链表，查到则成功结束，若直到表尾仍未找到，则查找失败。v建立一个公共溢出区：建立一个公共溢出区：v（1 1）一个基本表：每个单元只能存放一个元素；）一个基本表：每个单元只能存放一个元素；v（2 2）一个溢出表：只要关键字对应的哈希地址在）一个溢出表：只要关键字对应的哈希地址在基础表上产生冲突，则所有这样的元素一律存入该基础表上产生冲突，则所有这样的元素一律存入该表中。表中。典型例题v1.设顺序表的长度为n，则其每个元素的平均查找长度是(D)。vA)nB)(n-1)/2C)n/2D)(n+1)/2v分析分析对长度为对长度为n的顺序表，在查找成功的前提下，最好情况为的顺序表，在查找成功的前提下，最好情况为1(查找第一个元素查找第一个元素)，最，最坏为坏为n(查找最后一个元素查找最后一个元素),故其每个元素的平均查找长度为故其每个元素的平均查找长度为(1+n)/2。v答案答案D)v2.静态查找表与动态查找表两者的根本差别在于()。vA)逻辑结构不同B)存储实现不同C)施加的操作不同D)数据元素的类型不同v分析分析根据施加的运算不同，查找表被分为静态查找表和动态查找表。前者根据施加的运算不同，查找表被分为静态查找表和动态查找表。前者仅包含检索操作，后者除检索操作外，还允许施加修改操作。仅包含检索操作，后者除检索操作外，还允许施加修改操作。v答案C)v3._查找法的平均查找长度与元素个数n无关。v分析散列表查找法是将元素的键值代入散列函数中，通过计算得到散列地址，因此它的平均查找长度与元素个数n无关。v答案散列表典型例题v4.在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为_，比较二次查找成功的结点数为_，比较三次查找成功的结点数为_，比较四次查找成功的结点数为_，比较五次查找成功的结点数为_。总的比较查找长度为_。v分析二分查找过程可以与一棵有序二叉树相对应，那么第一层上1个结点，第二层上2个结点，第三层上4个结点，第四层上8个结点，第5层上9个结点。平均查找长度ASL=(1*1+2*2+3*4+4*8+5*9)/24=3.92v答案1,2,4,8,9,3.92。典型例题v5.在二叉排序树上插入新结点时，不必移动其他结点，仅需使某结点的指针域由_变为_即可。v分析在二叉排序数上插入的新结点一定是个叶子，因此无需移动其他结点，只要将该叶子的双亲结点的指针域由空改为指向该叶子即可。v答案空，非空。v6.文件的基本运算分为检索和修改两类，前者有3中方式，分别是_、_和_。v答案顺序存取，直接存取，按关键字存取。典型例题
