数据结构liuli查找演示

《数据结构liuli查找演示》由会员分享，可在线阅读，更多相关《数据结构liuli查找演示（51页珍藏版）》请在金锄头文库上搜索。

1、结束第 1 页结束第 2 页第第九九章章查查找找 第九章第九章 查找查找 9.1 概述 9.2 静态表查找表 9.3 动态表查找表 9.4 哈希表结束第 3 页第九章第九章 查查 找找学习要点1 掌握顺序表和有序表的查找方法；了解二分查找过程的描述方法判定树；2 掌握二叉排序树的查找方法；3 掌握哈希表的构造方法和查找方法，理解哈希表与其他结构的表的实质性的差异，了解哈希表解决冲突的方法：开放地址法，链地址法结束第 4 页9.1 9.1 概概 述述本章讨论数据结构：查找表本章讨论数据结构：查找表何何谓查找表找表？查找表是由同一找表是由同一类型的数据元素型的数据元素(或或记录)构成的构成的集合。

2、集合。由于由于“集合中的数据元素之集合中的数据元素之间存在着松散的关存在着松散的关系，因此系，因此查找表是一种找表是一种应用灵便的用灵便的结构。构。结束第 5 页对查找表找表经常常进行的行的操作操作:l1查询某某个个“特特定定的的数数据据元元素素是是否否在在查找表中；找表中；l2检索索某某个个“特特定定的的数数据据元元素素的的各各种种属属性；性；l3在在查找表中插入一个数据元素；找表中插入一个数据元素；l4从从查找表中找表中删去某个数据元素。去某个数据元素。结束第 6 页9.1 9.1 概概 述述二 查找的有关概念1 静态查找表、动态查找表仅作查询和检索操作的查找表。静静态查找表找表有时在查询

3、之后，还需要将“查询结果为“不在查找表中的数据元素插入到查找表中；或者，从查找表中删除其“查询结果为“在查找表中的数据元素。动态查找表找表查找表可分为两类查找表可分为两类:结束第 7 页9.1 9.1 概概 述述2 记录、关键字记录：由假设干数据项构成的数据元素称为记录是数据元素或记录中某个数据项的值，用以标识识别一个数据元素或记录。关键字关键字: 假设此关键字可以识别唯一的一个记录，那么称之谓“主关键字。 假设此关键字能识别假设干记录，那么称之谓“次关键字。结束第 8 页9.1 9.1 概概 述述例：学生管理系统，假设想按姓名查找，可将姓名作为关键字，假设想按学号查找，可将学号作为关键字，学

4、号学号 姓名姓名 专业专业 年龄年龄 0101王洪王洪 计算机计算机 17 17 0202 孙文孙文 计算机计算机 18 18 03 03 谢军谢军 计算机计算机 18 18 0404李辉李辉 计算机计算机 20 20 05 05 沈祥福沈祥福 计算机计算机 25 25 06 06 余斌余斌 计算机计算机 19 19 0707巩力巩力 计算机计算机 17 17 0808王辉王辉 计算机计算机 18 18说明：说明： 记录的任何数据项都可用为关键字；记录的任何数据项都可用为关键字； 假设此关键字的值能唯一标识记录，那么称该关键字为主关键字，假设此关键字的值能唯一标识记录，那么称该关键字为主关键字

5、，否那么次关键字；否那么次关键字；例：学号是主关键字，姓名是次关键字例：学号是主关键字，姓名是次关键字结束第 9 页9.1 9.1 概概 述述3 3 查找查找 应用中有各种各样的查找，本章讨论的查找操作定义如下：应用中有各种各样的查找，本章讨论的查找操作定义如下：查找：给定某个值，在查找表中查找关键字值等于给定值的记录，假设查找：给定某个值，在查找表中查找关键字值等于给定值的记录，假设表中存在这样的记录，那么称查找成功，查找结果为该记录在表中表中存在这样的记录，那么称查找成功，查找结果为该记录在表中的位置，否那么称为查找不成功，查找结果为的位置，否那么称为查找不成功，查找结果为“空记录或空记录

6、或“空指空指针针nu11nu11。 查找有内查找和外查找之分。假设整个查找过程全部在内查找有内查找和外查找之分。假设整个查找过程全部在内存进行，那么称这样的查找为内查找；反之，假设在查找过程中还需存进行，那么称这样的查找为内查找；反之，假设在查找过程中还需要访问外存，那么称之为外查找。我们仅介绍内查找。要访问外存，那么称之为外查找。我们仅介绍内查找。 结束第 10 页 要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL= ，其中i为查找第i个

7、元素的概率，且 =1。一般情形下我们认为查找每个元素的概率相等，i为查找第i个元素所用到的比较次数。查找算法的效率用平均查找长度度量设查找不成功的可能性很小，可忽略不计4 4 平均查找长度平均查找长度平均查找长度平均查找长度ASL = ASL = 在查找过程中与给定值比较的关键字个数的在查找过程中与给定值比较的关键字个数的数学期望值数学期望值 PiCi PiCiCiCi为在查找表中查找第为在查找表中查找第i i个记录所需的比较次数，个记录所需的比较次数，PiPi为在查找表中查找第为在查找表中查找第i i个记录的概率个记录的概率 i=1,2n i=1,2n结束第 11 页9.1 9.1 概概 述

8、述三 查找表的组织与查找如何在查找表中查找？取决于如何组织查找表例1： 查找索引号为的图书1 假设图书馆中的图书无序地摆放，那么只能顺序查找；2 假设图书按索引号顺序摆放，那么可先找到TP类图书，再找到TP3 例2 在词典中查找单词 are1 先找到a打头的单词，再在a打头的单词中找2 假设词典中无序排列，那么只能顺序查找；本章介绍： 静态查找表的组织方法与查找 动态查找表的组织方法与查找 哈希表的组织方法与查找 本章介绍： 静态查找表的组织方法与查找 动态查找表的组织方法与查找结束第 12 页9.1 9.1 概概 述述约定：假设1) 本章查找是关于主关键字查找；2假设本章涉及的关键字为整型类

9、型；3为使查找的图示简洁，对于查找表中的每一记录，只写出其关键字；关键字类型定义为 typedef int KeyType; 记录类型定义为： stypedef struct KeyType key; /关键字域 /其它域 ElemType;结束第 13 页9.1 9.1 概概 述述 R=R= 01,02,03,04,05,06,07,08 01,02,03,04,05,06,07,08 4) 本章所讨论的查找方法，只要稍加修改即可用于其他类型的查找例例学号 姓名 专业 年龄 01 王洪 计算机 17 02 孙文 计算机 18 03 谢军 计算机 18 04 李辉 计算机 20 05 沈祥福

10、计算机 25 06 余斌 计算机 19 07 巩力 计算机 17 08 王辉 计算机 18结束第 14 页9.2 9.2 静态查找表静态查找表9.2 9.2 静态查找表静态查找表只提供如下两种查找的查找表，称为静态查找表只提供如下两种查找的查找表，称为静态查找表 1 1查询某个查询某个“特定元素是否在表中；特定元素是否在表中； 2 2检索某个检索某个“特定元素的各种属性；特定元素的各种属性；对静态查找表介绍两种组织与查找方法对静态查找表介绍两种组织与查找方法 顺序表及查找顺序表及查找 有序表及查找有序表及查找抽象数据类型静态查找表的定义为：抽象数据类型静态查找表的定义为：结束第 15 页数据数

11、据对象象D：数据关系数据关系R：D是具有相同特性的数据元素的集合。每个数每个数据元素含有据元素含有类型相同的型相同的关关键字字，可唯一标识数据元素。 数据元素同属一个集合。ADTStaticSearchTable结束第 16 页 Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();根本操作根本操作P：nextADTStaticSearchTable结束第 17 页构造一个含n个数据元素的静态查找表ST。 Create(&ST, n);操作结果：结束第 18 页销毁表ST。Destroy(&ST);初始条件：操作结果：

12、静态查找表ST存在；结束第 19 页假设 ST 中存在其关键字等于 key 的数据元素，那么函数值为该元素的值或在表中的位置，否那么为“空。 Search(ST, key);初始条件：操作结果：静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；结束第 20 页按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，那么操作失败。Traverse(ST, Visit();初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；结束第 21 页9.2.1 9.2.1 顺序表的查找顺序表的查找一 顺序表及查找线性表及查找 查找表组织

13、：查找表用线性表表示。即将查找表的记录排成一个记录序列。L1=(45,53,12,3,37,24,100,61,90,78) 顺序查找法 1根本思想：从表的最后一个记录或第一个记录开始，依次将记录的关键字与给定值比较，假设相等：查找成功，否那么，继续查找。设查找表用顺序表存储，其类型定义如下：Tyypedef struct ElemType *elem; int length; SSTable结束第 22 页intSearch_Seq(SSTableST,KeyTypekey)/在在顺顺序表序表ST中中顺顺序序查查找其关找其关键键字等于字等于/key的数据元素。假的数据元素。假设设找到，那么函

14、数找到，那么函数值为值为/该该元素在表中的位置，否那么元素在表中的位置，否那么为为0。ST.elem0.key=key;/“哨兵哨兵for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找从后往前找returni;/找不到找不到时时，i为为0/Search_Seq结束第 23 页 在上面的程序中，我们首先将关键字的值送到0号存储单元，其目的在于免去查找过程中每一步都要检测整个表是否查找完毕。在此，0号存储单元起到了监视哨监视哨的作用。3)说明：1算法简单；2顺序查找法对于查找表的存储结构没有特别的要求，既可用顺序表也可用线性链表存储；假设用顺序表，查找可从前往后

15、扫描，也可从后往前扫描，但假设采用单链表，那么只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。3) 平均查找长度ASLSS=n+1/2结束第 24 页ST.elemiST.elemi60ikey=64key=60i64结束第 25 页定定义：查找算法的平均找算法的平均查找找长度度(AverageSearchLength)为确定确定记录在在查找表中的位置，需和找表中的位置，需和给定定值进行比行比较的关的关键字个数的期望字个数的期望值其中其中:n为表表长，Pi为查找表中第找表中第i个个记录的概率，的概率，且且Ci为找到找到该记录时，曾和，曾和给定定值比比较过的关的关键字的个数字的个数分析顺

16、序查找的时间性能。结束第 26 页在等概率查找的情况下， 顺序表查找的平均查找长度为：对顺序表序表而言，Ci = n-i+1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn结束第 27 页 假设查找概率无法事先测定，那么查找过程采取的改进方法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。在不等概率查找的情况下，ASLss 在 PnPn-1P2P1时取极小值结束第 28 页 如果再考虑查找成功与不成功的可能性相同，对每个记录的查找概率也相等，那么 Pi=1/2n,平均查找长度为： 顺序查找缺点是当顺序查找缺点是当n n很大时，平均查找长度较大，效率低；很大时，平均查找长

17、度较大，效率低；优点是对表中数据元素的存储没有要求。另外，对于线性链表，优点是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。只能进行顺序查找。结束第 29 页有序表的查找有序表的查找二有序表及查找三 有序表：假设线性表中的记录按关键字有序，那么称为有序表四 查找表组织：查找表用有序表表示。即将查找表的记录排成 按关键字有序的序列。五 二分查找法也称为折半查找法六1根本思想：将查找范围中间位置的记录关键字与给定值比较： ：继续在前半个表中用二分查找法查找 = ：查找成功，返回记录位置 ：继续在后半个表中中用二分查找法查找结束第 30 页有序表的查找有序表的查找 例1 L2=

18、( 3,12,24,37,45,53,61,78,90,100 )L2=( 3,12,24,37,45,53,61,78,90,100 )，查找查找 Key=24Key=24的记录的记录 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 1003 12 24 37 45 53 61 78 90 100lowmid high 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 24 373 12 24 37 45 53 61 78 90 100 45 53 61 78

19、90 100lowmid high 24 45 继续在前半个表中用二分查找法查找 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 3 12 24 3724 37 45 53 61 78 90 100 45 53 61 78 90 100Low mid high 24 12 继续在后半个表中用二分查找法查找查找成功结束第 31 页结束第 32 页intSearch_Bin(SSTableST,KeyTypekey)/在有序表在有序表ST中折半中折半查查找其关找其关键键字等于字等于key的数据元素。的数据元素。假假设设找到，那么函数找到，那么函数值为值

20、为/该该元素在表中的位置，否那么元素在表中的位置，否那么为为0。;/置区置区间间初初值值while(low50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。结束第 37 页有序表的查找有序表的查找说明：折半查找法效率比顺序查找高;平均查找长度ASLbs=log2n+1-1要求表中的记录按关键字有序；3) 表中的记录要用顺序结构存储；例 在有1000个记录的查找表查找，顺序查找法平均要比较500次，折半查找法平均要比较9次，可见折半查找法效率比顺序查找高。结束第 38 页9.2.2、有序表的查找、有序表的查找Fibonacci查找查找

21、1、Fibonacci数数定义：定义：F0=0F1=1Fn=Fn-1+Fn-2如：如：0,1,2,3,5,8,13,21,34,55,89,144,2332、实现、实现设结点的总数为设结点的总数为n=Fu-1，查找键值为，查找键值为key的结点的结点首先比较首先比较keySTFu1.key如果如果keySTFu1.key，那么比较，那么比较key=STFu1+Fu3.key3、注意：、注意：参照以下图，设根结点或子树的根结点同它的左、右儿子的下标之差为参照以下图，设根结点或子树的根结点同它的左、右儿子的下标之差为Fu3那么，根结点或子树的根结点的左儿子的同它的儿子的下标之差为那么，根结点或子树

22、的根结点的左儿子的同它的儿子的下标之差为Fu4根结点或子树的根结点的右儿子的同它的儿子的下标之差为根结点或子树的根结点的右儿子的同它的儿子的下标之差为Fu5可以设计类似于二分查找的算法。但先要把可以设计类似于二分查找的算法。但先要把Fu3、Fu4、Fu5计算出来，计算出来，它们也构成它们也构成Fibonacci数数?？结束第 39 页9.2、静态查找表、静态查找表Fibonacci查找查找4、e.g:n=F6-1=13-1=12个结点的查找过程个结点的查找过程Fu1=8Fu3=3Fu4=2Fu5=1311127105826419STFu1.key差为差为Fu3=3差为差为Fu5=1差为差为Fu

23、2=2共共Fu11817个个结点结点共共Fu21514个个结点结点5、优点：只用、优点：只用、法，不用除法。平均查找速度更快。、法，不用除法。平均查找速度更快。Olog2n级。级。缺点：最坏情况下比二分查找法差。必须先给出缺点：最坏情况下比二分查找法差。必须先给出Fibonacci数。数。结束第 40 页插值查找插值查找1、除中点下标的选择和二分查找不同外，、除中点下标的选择和二分查找不同外，其余类似。用于其余类似。用于关键字值均匀的情况，平均特性更好。关键字值均匀的情况，平均特性更好。2、实现、实现设设mid为中点的下标。为中点的下标。low为具有最小关键字值结点的下标，为具有最小关键字值结

24、点的下标，high为具有最大关键字值结点的下标。为具有最大关键字值结点的下标。mid=(high-low+1)(key-ST.elemlow.key)/(ST.elemhigh.key-ST.elemlow.key结束第 41 页关键字: A B C D E Pi: Ci: 231239.2.3静态查找树表静态查找树表 在不等概率不等概率查找找的情况下，折半折半查找找不不是是有序表最好的查找方法例如例如:此时 ASL=20.2+30.3+10.05+20.3+30.15=假设改变Ci的值 2 1 3 2 3那么 ASL=20.2+10.3+30.05+20.3+30.15=结束第 42 页 使

25、 达最小的判定树称为最优二叉树，其中: 定定义:结束第 43 页为计算方便，令 wi = pi选择二叉树的根结点，使 达最小 介绍一种次优二叉树的构造方法:为便于计算，引入累计权值和 并设 wl-1 = 0 和 swl-1 = 0，那么推导可得结束第 44 页0238111518 23例如例如:lh21 18 124310 18h9608EC21Ah53lhG3013结束第 45 页ECGABDF所得次所得次优二叉二叉树如下所示如下所示:查找比找比较“总次数次数=3 2+4 1+2 5+3 3+1 4+3 3+2 5=52查找比找比较“总次数次数=3 2+2 1+3 5+1 3+3 4+2 3

26、+3 5=59和折半和折半查找相比找相比较DBACFEG结束第 46 页但从上面的查找结果可以看出，该二叉树并不是最优二叉树，棵可以得到比该二叉树更优的二叉树。但研究结果说明，次优查找树和最优查找树的查找性能之差仅为1%2%，很少超过3%，而且构造次优查找树的算法时间复杂度为Onlogn，因此该算法比较有效。其相应的程序可通过page223页的递归算法实现略。结束第 47 页分块查找分块查找1.分分块查找找的思想的思想 分块查找是顺序查找的一种改进方法，又称索引顺序查找，具体实现如下：将一个主表分成n个子表，要求子表之间元素是按关键字有序排列的，而子表中元素可以无序的，用每个子表最大关键字和指

27、示块中第一个记录在表中位置建立索引表。 typedef struct int key; ; NODE; typedef struct int key, pos; INDEX;结束第 48 页例如，给定关键字序列如下：22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,假设n=3，即将该序列分成3个子表，每个子表有6个元素，那么得到的主表和索引表如图所 示。22121389203342443824486058744986532248860612 分块查找的过程是先确定待查记录所在的块，然后在块中顺序查找。假设给定k=38, 那么先在索引表中按顺序比较，因为22k48，那么可确定38应该在第二块中，从第二块的第一个记录 array6 顺序查起. 分块查找的时间复杂度是Om+n) m是块长度，n是索引表长度。结束第 49 页分块查找方法评价结束第 50 页ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找结束第 51 页