数据结构预算法第九章查找

第九章查找9.1查找的基本概念9.2静态查找9.3动态查找9.4哈希表9.1查找的基本概念1.查找表：由同一类型的数据元素（或记录）构成的集合称为查找表。2.对查找表进行的操作：（1）查找某个特定的数据元素是否存在。（2）检索某个特定数据元素的属性。（3）在查找表中插入一个数据元素。（4）在查找表中删除一个数据元素。3.静态查找：在查找过程中仅查找某个特定元素存在或查找其属性，称为静态查找。4.动态查找：在查找过程中对查找表进行插入或删除元素操作，称为动态查找。5.关键字：数据元素（或记录）中某个数据项的值，用它可以标识数据元素（或记录）。6.主关键字：可以唯一地标识一个记录的关键字称为主关键字。7.次关键字：可以标识若干个记录的关键字称为次关键字。8.查找：在查找表中确定是否存在一个数据元素的关键字等于给定值的操作，称为查找（或检索)。若表中存在这样一个数据元素（或记录），则查找成功；否则，查找失败。9.内查找和外查找：若整个查找过程全部在内存进行，则称为内查找；若在查找过程中还需要访问外存，则称为外查找。10.平均查找长度：查找算法的效率，主要是看要查找的值与关键字的比较次数，通常用平均查找长度来衡量。对一个含n个数据元素的表，查找成功时：其中,n是查找表中记录的个数。pi是查找第i个记录的概率,一般地,均认为每个记录的查找概率相等,即pi=1/n(1≤i≤n),ci是找到第i个记录所需进行的比较次数n1iiicpASL9.2静态查找表具有顺序查找法、折半查找法和分块查找法三种9.2.1顺序查找顺序查找法的特点是：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。监视哨的作用：（1）省去判定循环中下标越界的条件，从而节约比较时间。（2）保存查找值的副本，查找时若遇到它，则表示查找成功。这样在从后向前查找失败时，不必判断查找是否检测完，从而达到算法统一。用平均查找长度分析顺序查找算法的性能：假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为：ASL=i=1nPiCi＝n1i=1nCi＝n1i=1n(n-i+1)=21(n+1)顺序查找的缺点：当n很大时，平均查找长度较大，效率低；优点：对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。9.2.2折半查找法（二分法查找法）条件：要求待查找的列表必须是按关键字大小有序排列的顺序表。基本过程：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。例如用折半查找法查找10、50的具体过程，其中mid=(low+high)/2，当highlow时，表示不存在这样的子表空间，查找失败。6058463528252218151261234567891011low=1mid=6high=116058463528252218151261234567891011low=1mid=3high=5用折半查找法查找12的过程为：6058463528252218151261234567891011low=1mid=1high=26058463528252218151261234567891011low=2mid=2high=2用折半查找法查找50的过程：6058463528252218151261234567891011low=1mid=6high=116058463528252218151261234567891011low=7mid=9high=116058463528252218151261234567891011low=10mid=10high=116058463528252218151261234567891011low=10high=9用平均查找长度分析折半查找算法的性能：折半查找成功时的平均查找长度为：ASLbs＝i=1nPiCi＝n1j=1nj×2j-1＝nn+1log2(n+1)-1优点：比较次数少，查找速度快，平均性能好。缺点：要求待查的表为有序表，且插入、删除困难。9.2.3分块查找法分块查找法要求将列表组织成以下索引顺序结构：★首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。★构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，和每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。下图为一个索引顺序表2558888871605836453228825121418索引表各块内的最大关键字各块的起始地址列表0123456789101112此表包括三个块，第一个块的起始地址为0，块内最大关键字为25;第二个块的起始地址为5，块内最大关键字为58;第三个块的起始地址为10，块内最大关键字为88。分块查找的基本过程为：（1）首先，将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。（2）进一步用顺序查找法，在相应块内查找关键字为K的元素。分块查找的平均查找长度由两部分组成：即查找索引表时的平均查找长度为LB，以及在相应块内进行顺序查找的平均查找长度LW。ASLbs=LB+LW假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b，块中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在的块，则有：LB＝b1∑j＝j=1bb＋12Lw＝s1∑j＝i=1ss＋12ASLbs=LB+LW＝2b+s+1将b=n/s代入，得ASLbs＝21+1sn+s)(三种查找方法比较顺序查找折半查找分块查找ASL大小中表结构要求无有序表分段有序（块之间有序）9.3动态查找9.3.1二叉排序树1.二叉排序树的定义二叉排序树或者是一棵空树,或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值。（2）若右子树不空，则右子树上所有结点的值均大于根结点的值。（3）左、右子树也都是二叉排序树。2.二叉排序树的构造根据二叉排序树的性质，每次都按结点大小从根结点查找到对应的插入位置插入。例：有一组结点的关键字大小分别为：45、12、53、3、37、24、100、61、90、78求由这些结点构造成的二叉排序树的过程如图所示。二叉排序树的删除二叉排序的删除删除查找树中键值为key的结点的操作可按以下步骤进行：首先确定被删除结点的位置，如被删结点不在树，则函数返回；否则按以下多种情况作结点删除。（1）如被删除结点是根结点：①被删除结点无左子树；则以被删除结点的右子树作为删除后的树。②被删除结点有左子树，则以被删除结点的左子结点作为根结点，并把被删除结点的右子树作为被删结点的左子树按中序遍历得最后一结点的右子树。二叉排序的删除（续）（2）如被删结点不是根结点，且被删结点无左子结点。①如被删结点是它的双亲结点的左子结子，则把被删结点右子树作为被删结点的双亲结点的左子树；②如被删结点是它的双亲结点的右子结点，则被删结点的右子树作为被删结点的双亲结点的右子树。（3）如被删结点不是根结点，且被删结点有左子结点，把被删结点的右子树作为被删结点的左子树按中序遍历得最后一结点的右子树，同时进行以下操作：①如被删结点是它的双亲结点的左子结点，则把被删结点的左子树作为被删结点的双亲结点的左子树。②如被删结点是它双亲结点的右子结点，则把被删结点的左子树作为被删结点的双亲结点的右子树。二叉排序树的删除操作1、若p没有左子树，直接用p的右孩子取代它；2、若p有左子树，用p的左孩子取代它；找到其左子树的最右边的叶子结点r，把p的右子树作为r的右子树。9.3.2平衡二叉树(AVL树)一、AVL树（高度平衡的BST）概念1、定义——AVL或是空树，或是具有下列性质的BST：它的左、右子树都是AVL树，且左右子树的高度之差的绝对值不超过1。2、举例是二叉搜索树树和所有子树的右左子树高度之差绝对值不超过1属AVL树111514263971816-1000000013、平衡因子（balancefactor）结点左子树高度减去右子树高度所得高度差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.1哈希表哈希表又称散列表，是一种非常实用的查找技术。查找为结点的存储位置和它的关键码之间建立一个确定的关系，从而就可使查找码直接利用这个关系确定结点的位置。在散列表中，结点存储时，以结点的关键码为自变量，按某种公式计算其存储位置，并以该位置存储。查找时，以查找码为自变量计算同一公式，就能得到对应结点的存储位置，去取出结点，所以散列表能进行快速查找。称查找码计算结点存储位置的公式为散列函数，记为H（）。9.3.1哈希表一般情况下，能存入散列表中的结点所有可能的不同关键码个数比散列表能存储的结点个数要大得多。因此两个不同关键码k1和k2的散列函数值可能相等：H（k1）=H(k2)且k1≠k2。这种现象称为冲突，并称k1和k2为同义词。为了有效地使用散列技术，需要解决两个问题：找一个好的散列函数，使出现冲突机会尽可能少；设计有效解决冲突的方法。9.3.2常见的散列函数1.除留余数法令P是是一个整数,若哈希表长为m,则要求p=m，且接近m或等于m。设查找码为key，计算的散列函数为Hash(key)=key%p2.直接定址法直接定址法是取关键字的某个线性函数值为哈希地址,即Hash(key)=a*key+b3.平方取中法让查找码自乘，取其中间若干位的值，并乘上某个比例因子，使值在0至m-1之间。9.3.3解决冲突的方法1.线性探查法如按查找码key求得的第H（key）桶以满时，就得到另一个桶去找空位，将结点存入。线性探查法使用下列探查序列