数据结构第9章课件.ppt

《数据结构第9章课件.ppt》由会员分享，可在线阅读，更多相关《数据结构第9章课件.ppt（68页珍藏版）》请在三一办公上搜索。

1、第九章 查找,基本概念 顺序查找 二分查找 分块索引查找 二叉排序树的查找 B树与B+树的查找 Hash(散列)查找,9.1 基本概念,查找表:由具有同一类型的数据元素（或记录）组成的集合称为查找表。关键字:关键字是记录中某个项或组合项的值，用它可以标识一个记录。能唯一确定一个记录的关键字，称为主关键字；而不能唯一确定一个记录的关键字，称为次关键字.查找是指按给定的某个值k，在查找表中查找关键字为给定值k的记录。查找是计算机中经常遇到的操作。特别是当问题所涉及到的数据量相当大时，查找的效率就显得格外重要。,查找运算的主要操作是关键字的比较，所以，通常把查找过程中对关键字需要执行的平均比较次数（

2、也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。*查找结果：成功、失败*查找算法的性能指标 时间复杂性 平均查找长度:平均比较次数,平均查找长度定义为：,其中，n是元素的个数；pi 是查找第i个元素的概率，p1=p2=.=pn=1/n；ci 是找到第i个元素所需要的比较次数,*常用的查找算法,顺序查找 二分查找(折半查找)分块索引查找 二叉排序树的查找 B树与B+树的查找 Hash(散列)查找,9.2 顺序查找,struct Record int key;Record rn;,无监视哨的顺序查找:int SeqSearch(Record r,int n,int k)int i=0;wh

3、ile(in,有监视哨的顺序查找,int SeqSearch2(Record r,int n,int k)int i=0;rn.key=k;while(ri.key!=k)i+;if(in)return i;else return-1;,顺序查找的平均查找长度为：,顺序查找的特点：算法简单，但查找效率低。,9.3 二分查找,二分查找又称为折半查找。二分查找要求顺序表是有序的。二分查找的基本思想是：首先将待查的K值与有 序表R0到Rn-1的中间位置mid上的结点的关键 字进行比较，若相等，则查找完成；否则，若 Rmid.keyK，则说明待查找的结点只可能在左 子表R0到Rmid-1中，只需在左子

4、表中继续查 找；否则在右子表Rmid+1到Rn-1中继续查找。这样，经过一次关键字的比较就缩小了一半的查找区间。如此进行下去，直到找到为止（当然也存在最后找不到的可能）。,例:05 13 19 21 37 56 64 75 80 88 92,05 13 19 21 37 56 64 75 80 88 92,05 13 19 21 37 56 64 75 80 88 92,查找K=21的过程（查找成功）,05 13 19 21 37 56 64 75 80 88 92,05 13 19 21 37 56 64 75 80 88 92,05 13 19 21 37 56 64 75 80 88 9

5、2,查找K=85的过程（查找失败）,05 13 19 21 37 56 64 75 80 88 92,二分查找算法(非递归)int BiSearch(Record r,int n,int k)low=0,high=n-1;while(low=high)mid=(low+high)/2;if(rmid.key=k)return mid;else if(rmid.keyk)low=mid+1;else high=mid-1;return-1;,二分查找算法(递归)int BiSearch2(Record r,int low,int high,int k)if(lowhigh)return-1;el

6、semid=(low+high)/2;if(rmid.key=k)return mid;else if(rmid.keyk)return BiSearch2(r,mid+1,high,k);else return BiSearch2(r,low,mid-1,k);,算法分析,如果把当前查找位置上的结点作为根，左子表和右子表的结点分别作为根的左子树和右子树，由此得到的二叉树称为描述二分查找的判定树。借助于判定树很容易求得二分查找的平均查找长度。查找数据的比较次数最多为该判定树的树高.,二分查找的算法复杂度为：O(log n)即在最坏情况下，二分查找方法查找成功的比较次数不超过判定树的高度。虽然二

7、分查找的效率较高，但它要求被查找序列事先按关键字排好序，而排序本身是一种很费时的运算；另外，二分查找只适用于顺序存储结构，因此，二分查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。,平均长度的计算例如:长度为13的有序表进行折半查找的平均查找长度ASL=(11+22+34+46)/13=41/13。,9.4 分块查找,分块查找又称为索引查找，它是一种性能介于顺 序查找和二分查找之间的查找算法。分块查找要求将被查找表分成块，建立块索引。每一块中的关键字不一定有序，但前一块中的最 大关键字必须小于后一块中的最小关键字，即要“分块有序”。抽取各块中的最大关键字及其起始位置构成一个 索

8、引表。由于被查找表是分块有序的，所以索引表是一个递增有序表。例如：,13,3,9,20,33,42,44,38,60,80,74,49,86,53,22,12,0,6,12,22,48,86,24,48,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,分块查找的基本思想：首先，查找索引表，因为索引表是有序表，故可采用二分查找，也可以采用顺序查找，以确定待查的结点在哪一块；然后在以确定的那一块中顺序查找。,算法分析,由于分块查找实际上是两次查找过程，故整个算法的平均查找长度应该是两次查找的平均查找长度之和。若以二分查找来确定块，则分块查找的平均查找长度约为

9、：,若以顺序查找来确定块，则分块查找的平均查找长度约为：,对于后一种情况，当 时，平均查找长度为极小值。在实用中，可根据表的具体情况进行分块。,分块查找的性能介于顺序查找和二分查找之间的，例如，对长度为10000的线性表，它们的平均查找长度分别是：,顺序查找：约5000分块查找：约100二分查找：约14,9.5 二叉排序树的查找,二叉排序树的概念二叉排序树的建立二叉排序树的插入二叉排序树的删除二叉排序树的查找查找性能分析,1.二叉排序树的概念,也称为二叉查找树.(1)左子树的所有结点的值根结点的值(3)左子树、右子树都是二叉排序树。举例：,性质：中序遍历二叉排序树得到的是有序序列。,class

10、 BiSortTreeBiNode*root;void Insert(BiNode*,2二叉排序树的插入和建立,在一棵二叉排序树中插入值为k的结点，步骤如下：若二叉排序树为空，则生成值为k的新结点s，同时将新结点s作为根结点插入。若k小于根结点的值，则在根的左子树中插入值为k的结点。若k大于根结点的值，则在根的右子树中插入值为k的结点。若k等于根结点的值，表明二叉排序树中已有此关键字，则无须插入。,void BiSortTree:Insert(BiNode*,二叉排序树的建立算法 BiSortTree:BiSortTree(int a,int n)root=NULL;for(int i=0;i

11、 n;i+)Insert(root,ai);,3二叉排序树的查找过程 查找给定值k的过程如下：若二叉排序树为空，则表明查找失败，返回空指针；否则，若给定值k等于根结点的值，则表明查找成功，返回根结点；若给定值k小于根结点的值，则继续在根的左子树中查找；若给定值k大于根结点的值，则继续在根的右子树中查找。这是一个递归查找过程。,BiNode*BiSortTree:Search(BiNode*ptr,int k)/在以ptr为根的二叉排序树中查找关键字为k的结点 if(ptr=NULL)return NULL;else if(ptr-key=k)return ptr;else if(kkey)re

12、turn Search(ptr-lchild,k);elsereturn Search(ptr-rchild,k);bool BiSortTree:Search(int k)/查找 return Search(root,k)!=NULL;,非递归算法:循环实现BiNode*BiSortTree:Search2(BiNode*ptr,int k)/在以ptr为根的二叉排序树中查找值为k的结点 while(ptr)if(k=ptr-key)return ptr;else if(kkey)ptr=ptr-lchild;else ptr=ptr-rchild;return NULL;bool BiSo

13、rtTree:Search2(int k)/查找 return Search2(root,k)!=NULL;,4二叉排序树的删除操作,分三种情况:（1）删除叶子结点,（2）删除单支结点,（3）删除双支结点,递归删除算法的步骤如下：,若二叉排序树为空，则表明不存在删除的结点，不进行删除操作。若给定值k小于根结点的值，则继续在根的左子树中删除。若给定值k大于根结点的值，则继续在根的右子树中删除。若给定值k等于根结点的值，则根结点即为要删除的结点，此时需要根据上述分析的三种结点情况：叶子结点、单支结点或双支结点，执行相应的删除操作。,void BiSortTree:Delete(BiNode*/在右

14、子树进行删除 else/ptr指向的结点就是要删除的结点,if(ptr-lchild!=NULL,else temp=ptr;if(ptr-lchild=NULL)/单支结点，左子树为空 ptr=ptr-rchild;else if(ptr-rchild=NULL)/单支结点，右子树为空 ptr=ptr-lchild;delete temp;/删除 void BiSortTree:Delete(int k)/删除Delete(root,k);,9.6 平衡二叉树,问题的提出什么是平衡二叉树平衡二叉树的建立,平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉

15、树，且左子树和右子树高度之差的绝对值不超过1.,左子树与右子树高度之差称为结点的平衡因子。由平衡二叉树定义可知，平衡二叉树所有结点的平衡因子只能取1，0，1三个值之一。,如何使建立的一棵二叉排序树是平衡的呢？这就要求当新结点插入二叉排序树时，必须保持所有结点的平衡因子满足平衡二叉树的要求，一旦不满足要求，就必须进行调整。,调整有4种情况,（1）LL型,（2）RR型,（3）LR型,（4）RL型,9.7 B树与B+树,什么是B树?B树的查找什么是B+树?B+树的查找,9.8 Hash查找,1.基本概念 Hash,哈希,也称为散列.Hash是一种重要的存储方法，也是一种常见的查找方法。它的基本思想是

16、：以数据元素的关键字K为自变量，通过一个确定的函数关系，计算出对应的函数值f(K)，把这个值作为数据元素的存储地址。查找时也是根据这个函数计算其存储位置。,【例】假设一组记录的关键字分别为18，27，1，20，22，6，10，13，41，15，25。选取关键字与记录位置间的函数为f(key)=key%11。,Hash函数-关键字与记录位置间的函数.Hash地址-据Hash函数计算出的存储位置.Hash表-存储记录的查找表,该表中根据Hash函数计算出的存储位置.基于Hash表的查找称为Hash查找。,在建立Hash表时，若Hash函数是一个一对一的函数，则在查找时，只需根据散列函数对给定值进行

17、某种运 算，即可得到待查数据的存储位置。在一般情况下，Hash表的空间必须比数据的集合大，此时虽然浪费了一定的空间，但换取的是查找效率。设散列表的空间大小为m，填入表中的数据个数为n，则称=n/m为散列表的装填因子。Hash函数的选取原则是：运算尽可能简单；函数的值 域必须在表长的范围内；尽可能使得关键字不同时，其散列函数值亦不相同。若某个Hash函数对于不相等的关键字计算出了相同的 Hash地址，则称该现象为hash冲突，发生冲突的两个关键字该Hash函数的同义词。在实际应用中，不产生冲突的Hash函数极少存在。,2.Hash函数的构造方法,直接定址法除留余数法数字分析法平方取中法折叠法,直

18、接定址法,Hash函数是关键字的线性函数。即：H(key)=akeyb例1：已知一个含有70个数据的线性表，其关键字是两位十进制数字组成，则可将线性表存储在如下说明的散列表中：int HT100;其中，HTi存放关键字为i的结点，即散列函数为：H(key)=key,除留余数法,选择一个适当的正整数P，用P去除关键字，取所得得余数作为散列地址，即：H(key)=key%P,这个方法的关键是选取适当的P。选择P最好不要是偶数，也不要是基数的幂。一般地选P为小于或等于散列表长度m的某个最大质数比较好。例如：m=8，16，32，64，128，256，512，1024 P=7，13，31，61，127，

19、251，503，1019,除余法的地址计算公式简单，而且在很多情况下效果较好，因此是一种常用的构造散列函数的方法。,数字分析法,若事先知道关键字集合，且关键字的位数比散列表的地址位数多，则可选取数字分布比较均匀的若干位作为散列地址。例如，有一组8位数字组成的关键字：,经过分析可知，前三位和第五位分布不均匀，所以，若表长为1000，则可取4、6、7位的数字作为散列地址，若表长为100，则可取4、6与7、8位之和并舍去进位作为散列地址。,平方取中法,通常，要预先估计关键字的数字分布并不容易，要找数字均匀分布的位数更难。此时可采用平方取中法：即先通过求关键字的平方来扩大差别，再取其中的几位或其组合作

20、为散列地址。例如：一组关键字：(0100，0110，1010，1001，0111)平方结果为：(0010000，0012100，1020100，1002001，0012321)若表长为3位，则可取中间三位作为散列地址集：(100，121，201，020，123),折叠法,若关键字位数较多，可将关键字分割成位数相同的几段（最后一段的位数可以不同），段的长度取决于散列表的地址位数，然后将各段的迭加和（舍去进位）作为散列地址。例如，对于key=58242324169,3.处理hash冲突的方法,(1)开放地址法 线性探察法 二次探察法 双散列函数法(2)链地址法,用开放地址法解决冲突的基本思想是：当

21、冲突发生时，使用某种方法在散列表中形成一个探查序列，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到一个开放的地址（单元为空）为止。插入时碰到开放的地址，即可将待插入新结点放到该地址单元中；查找时碰到开放的地址，则说明表中没有待查的关键字。形成探测的方法不同，所得到的解决冲突的方法也不同。,线性探测法,将散列表看成是一个环形表。若地址为d（即H(key)=d）的单元发生冲突，则依次探查下述地址单元：d+1，d+2，.，m-1，0，1，.，d-1直到找到一个空单元或查找到关键字为key的结点为止。当然，若沿着该探查序列查找一遍之后，又回到了地址d，则无论是做插入操作还是做查找操作，都意味着

22、失败。例:有关键字序列为36，7，40，11，16，81，22，8，14，Hash表表长为11，Hash(key)=key%11，用线性探测法处理冲突，建立的Hash表。板书,二次探查法,二次探查法的探查序列依次为：12，-12，22，-22，.，等，也就是说，发生冲突时，将同义词来回散列在第一个地址的两端。求下一个开放地址的公式为：d2i-1=(d+i2)%m d2i=(d i2)%m,链地址法:基本思想是：将所有关键字为同义词的结点链接在同一个单链表中。例:Hash(key)=key%11,0123456789101112,若一组关键字为（26，36，41，38，44，15，68，12，0

23、6，51，25），散列函数定义为：H(key)=key%13。用链地址法建立散列表,4.Hash查找算法及分析,以线性探测法解决冲突建立的Hash表的查找算法int HashSearch_1(int hash,int m,int k)pos=k%m;/计算Hash地址t=pos;while(hashpos!=EMPTY)/当Hash地址中的记录不为空时循环if(hashpos=k)return pos;/查找成功，返回下标elsepos=(pos+1)%m;if(pos=t)return-1;/查找失败，返回-1return-1;/查找失败，返回-1,以链地址法解决冲突建立的Hash表的查找算法,Node*HashSearch_2(Node*hash,int m,int k)pos=k%m;/计算Hash地址 p=hashpos;/p指向对应单链表的表头 while(p/查找失败，返回空指针,本章总结,各种查找算法的基本思想各种查找算法性能的比较查找算法的实现,