数据结构预算法第九章查找(41页PPT).pptx

《数据结构预算法第九章查找(41页PPT).pptx》由会员分享，可在线阅读，更多相关《数据结构预算法第九章查找(41页PPT).pptx（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、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.动态查找：

2、动态查找：在查找过程中对查找表进行插入或删除元素操作，称为动态查找。v5.5.关键字：关键字：数据元素（或记录）中某个数据项的值，用它可以标识数据元素（或记录）。v6.6.主关键字：主关键字：可以唯一地标识一个记录的关键字称为主关键字。v7.7.次关键字：次关键字：可以标识若干个记录的关键字称为次关键字。v8.8.查找：查找：在查找表中确定是否存在一个数据元素的关键字等于给定值的操作，称为查找（或检索)。若表中存在这样一个数据元素（或记录），则查找成功；否则，查找失败。v9.9.内查找和外查找：内查找和外查找：若整个查找过程全部在内存进行，则称为内查找；若在查找过程中还需要访问外存，则称为外查

3、找。v10.10.平均查找长度：平均查找长度：查找算法的效率，主要是看要查找的值与关键字的比较次数，通常用平均查找长度来衡量。对一个含n个数据元素的表，查找成功时：v v 其中,n是查找表中记录的个数。pi是查找第i个记录的概率,一般地,均认为每个记录的查找概率相等,即pi=1/n(1in),ci是找到第i个记录所需进行的比较次数第三页，编辑于星期二：四点五分。9.2 9.2 静态查找表静态查找表具有具有顺序查找法顺序查找法、折半查找法折半查找法和和分块查找法分块查找法三种三种9.2.1 顺序查找顺序查找顺序查找法的特点是：用顺序查找法的特点是：用所给关键字与线性表中各元素的关键字逐个所给关键

4、字与线性表中各元素的关键字逐个比较，直到成功或失败。比较，直到成功或失败。监视哨的作用：监视哨的作用：（1）省去判定循环中下标越界的条件，从而节约比较时间。）省去判定循环中下标越界的条件，从而节约比较时间。（2）保存查找值的副本，查找时若遇到它，则表示查找成功。这样在）保存查找值的副本，查找时若遇到它，则表示查找成功。这样在从后向前查找失败时，不必判断查找是否检测完，从而达到算法统一。从后向前查找失败时，不必判断查找是否检测完，从而达到算法统一。第四页，编辑于星期二：四点五分。用平均查找长度分析顺序查找算法的性能：用平均查找长度分析顺序查找算法的性能：假设假设列表长度为列表长度为n，那么查找第

5、，那么查找第i个数据元素时需进行个数据元素时需进行n-i+1次比较，即次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，。又假设查找每个数据元素的概率相等，即即Pi=1/n，则顺序查找算法的平均查找长度为：，则顺序查找算法的平均查找长度为：ASL=i=1nPiCin1i=1nCin1i=1n(n-i+1)=21(n+1)顺序查找的缺点：顺序查找的缺点：当当n很大时，平均查找长度较大，效很大时，平均查找长度较大，效率低；率低；优点：优点：对表中数据元素的存储没有要求。另外，对于对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。线性链表，只能进行顺序查找。第五页，编辑

6、于星期二：四点五分。9.2.2 折半查找法折半查找法（二分法查找法）（二分法查找法）条件：条件：要求要求待查找的列表必须是待查找的列表必须是按关键字大小有序排列的顺序按关键字大小有序排列的顺序表表。基本过程：基本过程：将表中间位置记录的关键字与查找关键字比较，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一找关键字，则进一步查找前一子表，否则进一步查找后

7、一子表。重复以上过程，直到找到满足条件的记录，使查找子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。成功，或直到子表不存在为止，此时查找不成功。第六页，编辑于星期二：四点五分。例如用折半查找法查找例如用折半查找法查找10、50的具体过程，的具体过程，其中其中mid=(low+high)/2，当，当highlow时，表示不存在这样的子表时，表示不存在这样的子表空间，查找失败。空间，查找失败。605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=1mid=6high=116058463528252218151

8、26 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=

9、1mid=6high=11605846352825221815126 1 2 3 4 5 6 7 8 9 10 11low=7 mid=9high=11第九页，编辑于星期二：四点五分。605846352825221815126 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第十页，编辑于星期二：四点五分。用平均查找长度分析折半查找算法的性能：用平均查找长度分析折半查找算法的性能：折半查找成功时的平均查找长度为：折半查找成功时的平均查找长度为：A

10、SLbsi=1nPiCin1j=1nj2j-1nn+1log2(n+1)-1优点：优点：比较次数少，查找速度快，平均性能好。比较次数少，查找速度快，平均性能好。缺点：缺点：要求待查的表为有序表，且插入、删除困难。要求待查的表为有序表，且插入、删除困难。第十一页，编辑于星期二：四点五分。9.2.3 分块查找法分块查找法分块查找法要求将列表组织成以下索引顺序结构：分块查找法要求将列表组织成以下索引顺序结构：首先将列表分成若干个块（子表）。首先将列表分成若干个块（子表）。一般情况下，块的长度均一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无匀，最后一块可以不满。每块中元素任意

11、排列，即块内无序，但块与块之间有序。序，但块与块之间有序。构造一个索引表。其中每个索引项对应一个块并记录每块的构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，和每块中的最大关键字（或最小关键字）。索引表起始位置，和每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。按关键字有序排列。第十二页，编辑于星期二：四点五分。下图为一个索引顺序表下图为一个索引顺序表25 58 888871605836453228825121418索引表索引表各块内的最大关键字各块内的最大关键字各块的起始地址各块的起始地址列表列表 0 1 2 3 4 5 6 7 8 9 10 11 12此表包括三个

12、块，第一个块的起始地址为此表包括三个块，第一个块的起始地址为0，块内最大，块内最大关键字为关键字为25;第二个块的起始地址为第二个块的起始地址为5，块内最大关键字，块内最大关键字为为58;第三个块的起始地址为第三个块的起始地址为10，块内最大关键字为，块内最大关键字为88。第十三页，编辑于星期二：四点五分。分块查找的基本过程为：分块查找的基本过程为：（1）首先，将待查关键字首先，将待查关键字K与索引表中的关键字进行比较，以与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。（2 2）进一步用顺序查

13、找法，在相应块内查找关键字为）进一步用顺序查找法，在相应块内查找关键字为K的元的元素。素。第十四页，编辑于星期二：四点五分。分块查找的平均查找长度分块查找的平均查找长度由两部分组成：即查找索引表时的平均由两部分组成：即查找索引表时的平均查找长度为查找长度为LB，以及在相应块内进行顺序查找的平均查找长度，以及在相应块内进行顺序查找的平均查找长度LW。ASLbs=LB+LW 假定假定将长度为将长度为n的表分成的表分成b块，且每块含块，且每块含s个元素，则个元素，则b=n/s。又假定表中每个元素的查找概率相等，则每个索引项的查找概又假定表中每个元素的查找概率相等，则每个索引项的查找概率为率为1/b，

14、块中每个元素的查找概率为，块中每个元素的查找概率为1/s。若用顺序查找法确。若用顺序查找法确定待查元素所在的块，则有：定待查元素所在的块，则有：第十五页，编辑于星期二：四点五分。LBb1jj=1bb12Lws1ji=1ss12ASLbs=LB+LW 2b+s+1将将b=n/s代入，得代入，得ASLbs21+1sn+s)(第十六页，编辑于星期二：四点五分。三种查找方法比较三种查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找ASL大大小小 中中表结构要求表结构要求无无有序表有序表 分段有序分段有序（块之间有序）（块之间有序）第十七页，编辑于星期二：四点五分。v9.3 9.3 动态查找动

15、态查找v9.3.1 9.3.1 二叉排序树二叉排序树1.1.二叉排序树的定义二叉排序树的定义二叉排序树或者是一棵空树,或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值。（2）若右子树不空，则右子树上所有结点的值均大于根结点的值。（3）左、右子树也都是二叉排序树。2.2.二叉排序树的构造二叉排序树的构造根据二叉排序树的性质，每次都按结点大小从根结点查找到对应的插入位置插入。第十八页，编辑于星期二：四点五分。例：有一组结点的关键字大小分别为：45、12、53、3、37、24、100、61、90、78求由这些结点构造成的二叉排序树的过程如图所示。第十九页，编辑于

16、星期二：四点五分。第二十页，编辑于星期二：四点五分。二叉排序树的删除v二叉排序的删除v删除查找树中键值为key的结点的操作可按以下步骤进行：首先确定被删除结点的位置，如被删结点不在树，则函数返回；否则按以下多种情况作结点删除。（1）如被删除结点是根结点：被删除结点无左子树；则以被删除结点的右子树作为删除后的树。被删除结点有左子树，则以被删除结点的左子结点作为根结点，并把被删除结点的右子树作为被删结点的左子树按中序遍历得最后一结点的右子树。第二十一页，编辑于星期二：四点五分。二叉排序的删除（续）（2）如被删结点不是根结点，且被删结点无左子结点。如被删结点是它的双亲结点的左子结子，则把被删结点右子

17、树作为被删结点的双亲结点的左子树；如被删结点是它的双亲结点的右子结点，则被删结点的右子树作为被删结点的双亲结点的右子树。（3）如被删结点不是根结点，且被删结点有左子结点，把被删结点的右子树作为被删结点的左子树按中序遍历得最后一结点的右子树，同时进行以下操作：如被删结点是它的双亲结点的左子结点，则把被删结点的左子树作为被删结点的双亲结点的左子树。如被删结点是它双亲结点的右子结点，则把被删结点的左子树作为被删结点的双亲结点的右子树。第二十二页，编辑于星期二：四点五分。二叉排序树的删除操作v1、若p没有左子树，直接用p的右孩子取代它；v2、若p有左子树，用p的左孩子取代它；找到其左子树的最右边的叶子

18、结点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 第二十四页，编辑于星期二：四点五分。二、平衡

19、化旋转二、平衡化旋转 1、向AVL树插入结点可能造成不平衡，此时要调整树的结构，使之重新达到平衡 2、平衡化旋转方法 从插入位置沿通向根的路径检查各结点的平衡 因子 若发现不平衡结点，则从该结点起沿刚才回溯路径取直接下两层结点 若三个结点在一条直线上(RR、LL型)，则采用单旋转进行平衡化，此时处于中间位置的结点为旋转中心 若三结点不在一条直线上(LR、RL型)，则采用双旋转进行平衡化，此时处于下方位置的结点为旋转中心第二十五页，编辑于星期二：四点五分。3、平衡化旋转示例 RR型（逆时针单旋转）hhhABCDE01(a)AVL树hhh+1ABCDE12(b)E子树中插入结点hhh+1ABCDE

20、00(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型（先逆时针，后顺时针双旋转）二、平衡化旋转二、平衡化旋转第二十八页，编辑于星期二

21、：四点五分。hhh-1hABCDEFG插入(a)G子树插入结点高度变为h21-1hhh-1hABCDEFG(b)绕D，C顺时针转之后hhh-1hABCDEFG(c)绕D，A逆时针转之后03、RL型（先顺时针，后逆时针双旋转）二、平衡化旋转二、平衡化旋转第二十九页，编辑于星期二：四点五分。三、三、AVL树的建立树的建立 对于一组关键码的输入序列，从空开始不断插入结点，最后构成AVL树 每插入一个结点后就应判断从该结点到根的路径上有无结点发生不平衡 如有不平衡问题，利用旋转方法进行树的调整，使之平衡化 建AVL树过程是不断插入结点和必要时进行平衡化的过程 建AVL树过程举例：第三十页，编辑于星期二

22、：四点五分。9.4 9.4 哈希表及其查找哈希表及其查找9.4.1 9.4.1 哈希表哈希表 v哈希表又称散列表，是一种非常实用的查找技术。查找为结点的存储位置和它的关键码之间建立一个确定的关系，从而就可使查找码直接利用这个关系确定结点的位置。v在散列表中，结点存储时，以结点的关键码为自变量，按某种公式计算其存储位置，并以该位置存储。查找时，以查找码为自变量计算同一公式，就能得到对应结点的存储位置，去取出结点，所以散列表能进行快速查找。称查找码计算结点存储位置的公式为散列函数，记为H（）。第三十一页，编辑于星期二：四点五分。9.3.1 9.3.1 哈希表哈希表 v一般情况下，能存入散列表中的结

23、点所有可能的不同关键码个数比散列表能存储的结点个数要大得多。因此两个不同关键码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直接定址法是取关键字的某个线性函数值为哈希地址

24、,即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使用线性探查法解决冲突，会出现堆积现象。可能会发生这样的情况，有某结点的关键码计算出它的散列地址，希望按该地址存储该结点，但该位置已被不是它的同义词的结点所占用。因冲

25、突沿着线性探查序列进行查找，而这些位置也可能已存入非同义词的其他结点，结果使得不是同义词的许多结点处在同一个探查序列中。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用拉链法处理冲突，要求散列表的每个结点增加一个指针字段，用于链接同义词的子表，链表中的结点都是同义词。查找方法如下：（）按散列

26、函数计算出桶号i；（）判断对应的同义词链表指针是否为空，若为空则查找失败结束。（）遍用同义词链表，查到则成功结束，若直到表尾仍未找到，则查找失败。第三十五页，编辑于星期二：四点五分。v建立一个公共溢出区：建立一个公共溢出区：v（1 1）一个基本表：每个单元只能存放一个元素；）一个基本表：每个单元只能存放一个元素；v（2 2）一个溢出表：只要关键字对应的哈希地址在基础）一个溢出表：只要关键字对应的哈希地址在基础表上产生冲突，则所有这样的元素一律存入该表中。表上产生冲突，则所有这样的元素一律存入该表中。第三十六页，编辑于星期二：四点五分。典型例题v1.设顺序表的长度为n，则其每个元素的平均查找长度

27、是(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分析分析根据施加的运算不同，查找表被分为静态查找表和动态查找表。前者仅包含检索操作，后者除检索操作根据施加的运算不同，查找表

28、被分为静态查找表和动态查找表。前者仅包含检索操作，后者除检索操作外，还允许施加修改操作。外，还允许施加修改操作。v答案C)第三十七页，编辑于星期二：四点五分。v3._查找法的平均查找长度与元素个数n无关。v分析散列表查找法是将元素的键值代入散列函数中，通过计算得到散列地址，因此它的平均查找长度与元素个数n无关。v答案散列表典型例题第三十八页，编辑于星期二：四点五分。v4.在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为_，比较二次查找成功的结点数为_，比较三次查找成功的结点数为_，比较四次查找成功的结点数为_，比较五次查找成功的结点数为_。总的比较查找长度为_。v分析二分查

29、找过程可以与一棵有序二叉树相对应，那么第一层上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答案顺序存取

30、，直接存取，按关键字存取。典型例题第四十页，编辑于星期二：四点五分。1、每一个成功者都有一个开始。勇于开始，才能找到成功的路。11月-2211月-22Wednesday,November 9,20222、成功源于不懈的努力，人生最大的敌人是自己怯懦。06:03:3006:03:3006:0311/9/2022 6:03:30 AM3、每天只看目标，别老想障碍。11月-2206:03:3006:03Nov-2209-Nov-224、宁愿辛苦一阵子，不要辛苦一辈子。06:03:3006:03:3006:03Wednesday,November 9,20225、积极向上的心态，是成功者的最基本要素。

31、11月-2211月-2206:03:3006:03:30November 9,20226、生活总会给你另一个机会，这个机会叫明天。09十一月20226:03:30上午06:03:3011月-227、人生就像骑单车，想保持平衡就得往前走。十一月226:03上午11月-2206:03November 9,20228、业余生活要有意义，不要越轨。2022/11/96:03:3006:03:3009 November 20229、我们必须在失败中寻找胜利，在绝望中寻求希望。6:03:30上午6:03上午06:03:3011月-2210、一个人的梦想也许不值钱，但一个人的努力很值钱。11/9/2022 6:03:30 AM06:03:3009-11月-2211、在真实的生命里，每桩伟业都由信心开始，并由信心跨出第一步。11/9/2022 6:03 AM11/9/2022 6:03 AM11月-2211月-22谢谢大家谢谢大家第四十一页，编辑于星期二：四点 五分。