《数据结构之查找课件》由会员分享，可在线阅读，更多相关《数据结构之查找课件（76页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第八章 查找,第八章 查找,知 识 点查找的基本概念三种基本查找方法：顺序查找、二分查找和分块查找树型查找的基本概念和查找算法散列法、散列函数冲突的基本概念和解决冲突方法难 点二叉排序树查找平衡树及平衡树的调整,要 求 熟练掌握以下内容：三种基本查找方法的基本思想和算法二叉排序树查找的基本思想和算法散列法基本思想、散列函数的常用构造方法及解决冲突方法 了解以下内容：平衡树及平衡树的调整B-树查找,第八章目录,8.1 查找的基本概念8.2 基本查找方法8.3 树型查找8.4 散列法8.5 应用举例及分析小 结习题与练习,8.1 查找的基本概念,查找又称为查询或检索，是在一批记录中依照某
2、个域的指定域值，找出相应的记录的操作。在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。,对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数的平均
3、值，作为衡量查找算法好坏的依据。,返回,8.2 线性表的查找,1。顺序查找(Sequential search)基本思想：查找从线性表的一端开始，顺序将各单元的关键字与给定值k进行比较，直至找到与k相等的关键字，则查找成功，返回该单元的位置序号；如果进行到表的另一端，仍未找到与k相等的关键字，则查找不成功，返回0作为查找失败的信息。,顺序查找的线性表定义如下：Typedef struct rectype keytype key; itemtype item1 rectype;,顺序查找算法,int sequsearch (r, n, k) /*R1N中存放N个元素*/ r0.key=k; i=
4、n; while (ri.key!=k) i-; return(i);,顺序查找算法分析,监视哨的作用最坏的情况查找成功需比较n次，最好的情况是比较1次，如果对每个关键字进行查找的概率相等，则查找成功所需的平均比较次数为(n+1)/2，而查找失败则需比较(n+1)次，时间复杂度为O（n）。顺序查找的优点是算法简单、适应面广，且不要求表中数据有序。缺点是平均查找长度较大，特别是当n较大时，查找效率较低，不宜采用。,2.折半查找,折半查找又称二分查找(Birary search)。假设记录在查找表R1n中按关键字排列有序。首先用k与查找表中间元素的关键字比较，。,比较结果有三种可能： 如果rm.k
5、eyk，说明如果存在欲查找的元素，该元素一定在数组的前半部分，查找范围缩小了一半，修改查找范围的的上界high=m-1，继续对数组的前半部分进行二分查找； 如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的后半部分，查找范围缩小了一半，修改查找范围的的下界low=m+1，继续对数组的后半部分进行二分查找； 如果rm.key=k，查找成功，m所指的记录就是查找到的数据。,重复上述过程，查找范围每次缩小1/2，当范围不断缩小，出现查找范围的下界大于上界时，则查找失败，确定关键字为key的记录不存在。,例：从下列序列中查找K=21的记录,5 13 19 21 37 56 64 75 8
6、0 88 92,int binsearch(r, n, k) /*记录存储在r1n中 int low=1，hig=n， mid; while (low=hig) mid=(low+high)/2; if (rmid.key=k) return(mid); else if (rmid.keyk) low=mid+1; else hig=mid-1; return(0); ,折半查找的分析折半查找的判定树平均查找长度 ASL= log2(n+1)-1查找成功时的最大查找长度为折半查找判定树的深度log2n +1，查找不成功时的最大查找长度也为折半查找判定树的深度log2n +1。,3.有序表的其它
7、查找方法,斐波那契查找方法插值查找法,8.2.3 分块查找,分块查找又称为索引顺序查找，是顺序查找方法的另一种改进，其性能介于顺序查找和二分查找之间。分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但块与块之间必须按关键字大小有序排列，即前一块中的最大关键字值小于后一块中的最小关键字值。还需要建立一个索引表，索引表中的一项对应于线性表中的一块，索引项由键域和链域组成，键域存放相应块的最大关键字，链域存放指向本块第一个结点和最末一个结点的指针。索引表按关键字值的递增顺序排列。,分块查找的算法分两步进行，首先确所查找的结点属于哪一块，即在索引表中查找其所在的块，然后在块内查找待查的数据
8、。由于索引表是递增有序的，可采用二分查找，而块内元素是无序的，只能采用顺序查找。如果块内元素个数较少，则不会对执行速度有太大的影响。例如线性表中关键字为:9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82其索引如图8.1所示。,图8.1 线性表与索引表,索引表的定义,struct indexterm keytype key; int low, high;typedef struct indexterm indexMAXITEM; 这里的keytype可以是任何相应的数据类型，如int、float、或char等，在算法中，我们规定keytype缺省是in
9、t类型。,int blksearch (sqlist r, index idx, int k, bn) /*bn为块的个数*/ int i, j, mid, low=1, high=bn, find=0; while (low=high & !find) /*二分查找索引表*/ mid=(low+high)/2; if (kidxmid.key) low=mid+1; else find=1; ,分块查找算法续,if(find=1) i=idxmid.low; j=idxmid.high; else if (lowbn) /*k小于索引表内最大值*/,分块查找算法续, i=idxlow.low
10、; j=idxlow.high; while (ij) i=0; return(i);,返回,分块查找的分析,设有n个的记录，均匀地分成b块，每块含有s个记录，即b=n/s，又设每个记录的查找概率相等，则每块的查找概率为1/b，块中每个记录的查找概率为1/s，若用顺序查找确定记录所在的块，则分块查找的平均查找长度为 ASLsucc=（b+1）/2+（s+1）/2 =（n/s+s）/2 + 1若用折半查找确定记录所在的块，则分块查找的平均查找长度为 ASLsucc log2（n/s+1）+ s/2,顺序查找、折半查找、分块查找的比较,顺序查找对查找表无任何要求，既适用无序表，又适用有序表，查找成
11、功的平均查找长度为(n+1)/2，时间复杂度为O(n)；折半查找要求表中元素必须按关键字有序，其平均查找长度为近似(log2(n+1)-1)，时间复杂度为O(log2n)；分块查找每块内的元素可以无序，但要求块与块之间必须有序，并建立索引表。,8.3 二叉排序树(BST) 二叉排序树或是一棵空树,或是具有下列性质的树:若左子树非空, 则左子树上的所有结点都小于其根结点的值;若右子树非空, 则右子树上的所有结点都大于其根结点的值;左,右子树也都是一棵二叉排序树. 例,结点定义如下：Typedef struct node keytype key; itemtype others; struct n
12、ode *lchild, *rchild; BSTree,8.3.1 二叉排序树查找,基本思想：查找过程从根结点开始，首先将它的关键字与给定值k进行比较，如果相等，则查找成功，输出有关的信息；如果不等，若根结点关键字大于给定值k，向左子树继续查找，否则向右子树继续查找。,树型查找是一种递归的查找过程。在二叉排序树上查找关键字为k的结点，成功时返回该结点位置，否则返回NULL，递归函数如下：,递归函数如下btree search (BSTree *b, int k) if (b=NULL) return (NULL); else if(b-data=k) return (b); if(kdata
13、) return (search (b-left, k); else return (search (b-right,k); ,非递归算法,btree treesearch (BSTree *b, int k) BSTree *p; p=b; while(p!=NULL); if (p-data=k) return (p); else if (kdata) p=p-left; else p=p-right; return (NULL); ,二叉排序树查找分析,树型查找最坏情况时，需要的查找时间取决于树的高度，当二叉排序树接近满二叉树时，其高度为log2n，最坏情况下查找时间为O(log n)，与二分查找是同样数量级的；当二叉排序树为只有一个端结点的所谓“退化树”时，其高度等于n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。为了保证树型查找有较高的查找速度，我们希望该二叉树接近满二叉树，也就是希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树。,
