数据结构查找.ppt

《数据结构查找.ppt》由会员分享，可在线阅读，更多相关《数据结构查找.ppt（71页珍藏版）》请在优知文库上搜索。

1、第第8 8章章 查找查找1.1.关键字关键字 在实际应用问题中，每个记录一般包含有多在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称关键字（的，这个作为查找依据的域称关键字（keykey）。）。主关键字主关键字 可唯一标识一个记录的关键字。例：学号可唯一标识一个记录的关键字。例：学号次关键字次关键字 可识别若干记录的关键字。例：性别可识别若干记录的关键字。例：性别8.1 8.1 基本概念与术语基本概念与术语2.2.查找表查找表 是由同一类型的数据元素是由同一类型的数据元素( (或记录或记录) )

2、构成的集构成的集合，由于合，由于“集合集合”中的数据元素之间存在着松散中的数据元素之间存在着松散的关系，因此的关系，因此查找表查找表是一种应用灵便的数据结构是一种应用灵便的数据结构。 对查找表经常进行的操作有对查找表经常进行的操作有：查询、检索、：查询、检索、插入、删除。插入、删除。 分类分类：静态查找表：静态查找表 动态查找表动态查找表3 3. .查找查找 根据给定的某个值，在查找表中确定一个其根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，若表中在这样的一个记录，则称查找是成功的，

3、若表中不存在关键字等于给定值的记录，则称查找不成不存在关键字等于给定值的记录，则称查找不成功。功。静态查找静态查找 只查找，不改变数据元素集内的数据元素。只查找，不改变数据元素集内的数据元素。动态查找动态查找 既查找，又改变既查找，又改变( (增减增减) )集合内的数据元素。集合内的数据元素。4.4.平均查找长度平均查找长度(Average Search Length)(Average Search Length) 为确定记录在查找表中的位置，需和给定值为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长

4、度（在查找成功时的平均查找长度（ASLASL）。）。 对于含有对于含有 n n 个记录的表，查找成功时的平个记录的表，查找成功时的平均查找长度为：均查找长度为： ASLASL = = = =niiipc1查找表中第查找表中第i i 个个记录的概率，且记录的概率，且= =nii=1=1p1找表中关键字与给定值相等找表中关键字与给定值相等的第的第i i 个记录时，和给定值个记录时，和给定值已进行过比较的关键字个数已进行过比较的关键字个数8.2 8.2 静态查表法静态查表法8.2.1 8.2.1 顺序表的查找顺序表的查找 也称线性查找。也称线性查找。1.1.查找过程：查找过程： 对给定的一关键字对给

5、定的一关键字 K K，从线性表的一端开，从线性表的一端开始，逐个进行记录的关键字和始，逐个进行记录的关键字和 K K 的比较，直的比较，直到找到关键字等于到找到关键字等于 K K 的记录或到达表的另一的记录或到达表的另一端。端。2.2.实现顺序查找的数据结构实现顺序查找的数据结构 typedef structtypedef struct int key; int key; /关键字域关键字域 /其他域其他域 SSTable;SSTable;3.3.顺序查找的算法顺序查找的算法int seqsearch(SSTable ST , int n, int key) int seqsearch(SST

6、able ST , int n, int key) int i=n; int i=n; while(STi.key!=key) while(STi.key!=key)&(i=1)&(i=1) i- -; i- -; return i; return i; （return i=4return i=4）Key = 80Key = 80408030601020250 1 2 3 4 5 6 74.4.算法分析算法分析查找成功时的平均查找次数为：查找成功时的平均查找次数为： ASL=(1+2+3+4+ASL=(1+2+3+4+n)/n = (n+1)/2 +n)/n = (n+1)/2 查找不成功时的

7、比较次数为：查找不成功时的比较次数为： ASL=(n(n+1)/n = n+1ASL=(n(n+1)/n = n+1 则顺序查找的平均查找长度为：则顺序查找的平均查找长度为： ASL=(ASL=( + + )/2 = 3(n+1)/4)/2 = 3(n+1)/4优点优点：算法简单，无需排序，采用顺序和链式存储均可。算法简单，无需排序，采用顺序和链式存储均可。缺点：缺点：平均查找长度较大。平均查找长度较大。 可用折半查找（二分法查找）来实现。可用折半查找（二分法查找）来实现。1.1.查找思想查找思想 先确定待查找记录所在的范围，然后逐步缩先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确

8、认找不到该记录为止。小范围，直到找到或确认找不到该记录为止。 前提条件：前提条件： 必须在具有顺序存储结构的有序表中进行。必须在具有顺序存储结构的有序表中进行。8.2.2 8.2.2 二分查找二分查找查找查找23和和79的过程如下图：的过程如下图：mid=(low+high)/2( 08, 14, 23, 37, 46, 55, 68, 79, 91 )( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhigh=mid-1mid( 08, 14, 23, 37, 46

9、, 55, 68, 79, 91 )low=mid+1highmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid2.2.折半查找的算法折半查找的算法int Search_Bin( SSTable ST , int n, int key)int Search_Bin( SSTable ST , int n, int key) int low, high,

10、mid; int low, high, mid; low=1; high=n; low=1; high=n; while(low=high) while(low=high) mid=(low+high)/2; mid=(low+high)/2; if(STmid.key= = key) return mid; if(STmid.key= = key) return mid; else if( key STmid.key) high=mid-1; else if( key STmid.key) high=mid-1; else low=mid+1; else low=mid+1; return

11、0; return 0; 3.3.算法性能分析算法性能分析 为了分析二分查找的性能，可以用二叉树来描述二分为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中点作为根结点，左子区间查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为子区间再按类似的方法，由此得到的二叉树称为二分查找二分查找的判定树的判定树。 例：关键字序列例：关键字序列8,17,25,34,48,57,688,17,25,34,48,57,68的判定树的判定树3434

12、171757578 8484825256868 由于第由于第 k k 层结点的查找次数各为层结点的查找次数各为 k k 次（根结点为次（根结点为第第1 1层），而第层），而第 k k 层结点数最多为层结点数最多为 2 2k-1 k-1 个。假设该二叉个。假设该二叉树深度为树深度为 h h，则等概率下，二分查找的成功的，则等概率下，二分查找的成功的 ASL ASL 为：为：最坏情形下：最坏情形下： 取等号；取等号； 最大的结点数最大的结点数n = 2n = 2h h -1-1；则则h=logh=log2 2(n+1)(n+1)，因此，因此 ，ASL=(n+1)/n logASL=(n+1)/n

13、log2 2(n+1)-1(n+1)-1当当 n n 很大时，很大时，ASL ASL log log2 2(n+1)-1 (n+1)-1 则其时间复杂度为则其时间复杂度为O(logO(log2 2n)n)。 = =niiicp1ASL=1/n= =niic11/n（1+2 21+h 2h-1） 可用分块查找来实现。可用分块查找来实现。1.1.查找思想查找思想 是顺序查找的一种改进方法，就是把被查找是顺序查找的一种改进方法，就是把被查找的表分成若干的表分成若干块块，每块中记录的存放顺序是无序，每块中记录的存放顺序是无序的，但块与块之间必须按关键字有序。即第一块的，但块与块之间必须按关键字有序。即

14、第一块中任一记录的关键字都小于第二块中任一记录的中任一记录的关键字都小于第二块中任一记录的关键字，而第二块中任一记录的关键字都小于第关键字，而第二块中任一记录的关键字都小于第三块中任一记录的关键字，依此类推。三块中任一记录的关键字，依此类推。8.2.3 8.2.3 分块查找分块查找18 12 8520 51 36 22 29 53 89 60 72 66 76第第1 1块块第第2 2块块第第3 3块块索引表索引表2053891611块内最大关键字块内最大关键字各块起始地址各块起始地址 该方法要为被查找的表建立一个该方法要为被查找的表建立一个索引表索引表，索索引表中的一项对应于表中的一块，索引表

15、中含有引表中的一项对应于表中的一块，索引表中含有这一块中的这一块中的最大关键字最大关键字和和指向块内第一个记录位指向块内第一个记录位置的指针置的指针，索引表中各项索引表中各项关键字有序关键字有序。特点：块间有序，块内无序特点：块间有序，块内无序2.2.分块查找步骤分块查找步骤1 1）折半查找索引表，确定要找的记录所在块；）折半查找索引表，确定要找的记录所在块；2 2）在相应的块中顺序查找。）在相应的块中顺序查找。例：要找关键字为例：要找关键字为2222的记录。的记录。18 12 8520 51 36 22 29 53 89 60 72 66 76第第1 1块块第第2 2块块第第3 3块块索引表

16、索引表2053891611查找：块间折半，块内线性查找：块间折半，块内线性8.3 8.3 动态查找表动态查找表特点特点 表结构在查找过程中动态生成。表结构在查找过程中动态生成。要求要求 对于给定值对于给定值 key, key, 若表中存在其关键字等于若表中存在其关键字等于 keykey的记的记录，则查找成功返回；否则插入关键字等于录，则查找成功返回；否则插入关键字等于 keykey的记录。的记录。 动态查找表主要有二叉树结构和树结构两种类型。二动态查找表主要有二叉树结构和树结构两种类型。二叉树结构有二叉排序树、平衡二叉树等。树结构有叉树结构有二叉排序树、平衡二叉树等。树结构有B-B-树、树、B B+ +树等。树等。8.3.1 8.3.1 二叉排序树二叉排序树1.1.二叉排序树二叉排序树1 1）什么是二叉排序树）什么是二叉排序树 或是一棵空树；或是具有下列性质的二叉树：或是一棵空树；或是具有下列性质的二叉树： （1 1）若它的左子树不空，则左子树上所有结点）若它的左子树不空，则左子树上所有结点 的值均小于它的根结点的值；的值均小于它的根结点的值； （2 2）若它的右子树不空，则右子树上所