《实用数据结构（修订版） 教学课件 ppt 作者 佟维 谢爽爽 第八章 查找》由会员分享，可在线阅读，更多相关《实用数据结构（修订版） 教学课件 ppt 作者 佟维 谢爽爽 第八章 查找（73页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第八章 查找,第八章 查找,第八章 查找,知 识 点 查找的基本概念 三种基本查找方法：顺序查找、二分查找和分块查找 树型查找的基本概念和查找算法 散列法、散列函数冲突的基本概念和解决冲突方法 难 点 二叉排序树查找 平衡树及平衡树的调整,第八章 查找,要 求 熟练掌握以下内容： 三种基本查找方法的基本思想和算法 二叉排序树查找的基本思想和算法 散列法基本思想、散列函数的常用构造方法及解决冲突方法 了解以下内容： 平衡树及平衡树的调整 B-树查找,第八章 查找,第八章目录,8.1 查找的基本概念 8.2 基本查找方法 8.3 树型查找 8.4 散列法 8.5 应用举例及分析 小 结
2、习题与练习,第八章 查找,8.1 查找的基本概念,查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。 在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。 在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。,第八章 查找,对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。 查找算法中的基本运算是记录
3、的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数的平均值，作为衡量查找算法好坏的依据。,返回,第八章 查找,8.2.1 顺序查找,顺序查找(Sequential search)也称为线性查找，是采用线性表作为数据的存储结构，对数据在表中存放的先后次序没有任何要求。 顺序查找是最简单的查找方法，它的基本思想是：查找从线性表的一端开始，顺序将各单元的关键字与给定值k进行比较，直至找到与k相等的关键字，则查找成功，返回该单元的位置序号；如果进行到表的另一端，仍未找到与k相等的关键字，则查找不成功，返回0作为查找失败的信息。,第八章 查找,顺序
4、查找的线性表定义如下： #define MAXITEM 100 /*最多项数*/ struct element keytype key; Elemtype data; ; typedef struct sqlistMAXITEM; 这里keytype和ElemType可以是任何相应的数据类型，如int、float或char等，在算法中我们规定它们缺省是int类型。,第八章 查找,顺序查找算法,int sequsearch (sqlist r, int k, n) /*n为线性表r中元素个数*/ i=1 while (ri.key!=k ,第八章 查找,顺序查找算法分析,此函数的主要运算时间是用
5、于循环语句逐单元进行比较判断ri.key是否等于k，因此顺序查找的速度较慢，最坏的情况查找成功需比较n次，最好的情况是比较1次，如果对每个关键字进行查找的概率相等，则查找成功所需的平均比较次数为(n+1)/2，而查找失败则需比较(n+1)次，时间复杂度为O（n）。 顺序查找的优点是算法简单、适应面广，且不要求表中数据有序。缺点是平均查找长度较大，特别是当n较大时，查找效率较低，不宜采用。,第八章 查找,8.2.2 二分查找,二分查找(Birary search)也称为折半查找，它的查找速度比顺序查找快，但它要求数据在线性表中按查找的关键字域有序排列。 设n个数据存放于数组r中，且已经过排序，按
6、由小到大递增的顺序排列。 采用二分查找，首先用要查找的给定值k与表正中间元素的关键值相比较，此元素的下标 。,第八章 查找,比较结果有三种可能： 如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的前半部分，查找范围缩小了一半，修改查找范围的的上界high=m-1，继续对数组的前半部分进行二分查找； 如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的后半部分，查找范围缩小了一半，修改查找范围的的下界low=m+1，继续对数组的后半部分进行二分查找； 如果rm.key=k，查找成功，m所指的记录就是查找到的数据。,第八章 查找,重复上述过程，查找范围每次缩小1/2，当范
7、围不断缩小，出现查找范围的下界大于上界时，则查找失败，确定关键字为key的记录不存在。 二分查找是一种效率较高的算法，最好的情况是第一次比较即找到所查元素，即使一次比较没有找到，也把进一步查找的范围了缩小一半。与此类似，每比较一次均使查找范围减半，故最坏的情况所需比较次数为O(logn)，对于较大的n显然较顺序查找速度快得多。,第八章 查找,二分查找算法,int binsearch(sqlist r,int k,n) int i,low=1,high=n,m,find=0; /*low和high分别表示查找范围的起始单元下标和终止单元下标，find为查找成功的标志变量*/ while (low
8、rm.key),第八章 查找,二分查找算法续,low=m+1; else i=m; find=1; if (!find) i=0; return(i); ,第八章 查找,8.2.3 分块查找,分块查找又称为索引顺序查找，是顺序查找方法的另一种改进，其性能介于顺序查找和二分查找之间。 分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但块与块之间必须按关键字大小有序排列，即前一块中的最大关键字值小于后一块中的最小关键字值。 还需要建立一个索引表，索引表中的一项对应于线性表中的一块，索引项由键域和链域组成，键域存放相应块的最大关键字，链域存放指向本块第一个结点和最末一个结点的指针。索引表
9、按关键字值的递增顺序排列。,第八章 查找,分块查找的算法分两步进行，首先确所查找的结点属于哪一块，即在索引表中查找其所在的块，然后在块内查找待查的数据。由于索引表是递增有序的，可采用二分查找，而块内元素是无序的，只能采用顺序查找。如果块内元素个数较少，则不会对执行速度有太大的影响。 例如线性表中关键字为: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 s
10、truct indexterm indexMAXITEM; 这里的keytype可以是任何相应的数据类型，如int、float、或char等，在算法中，我们规定keytype缺省是int类型。,第八章 查找,分块查找算法,int blksearch (sqlist r,index idx,int k,bn) /*bn为块的个数*/ int i,high=bn,low=1,mid,j,find=0; while (lowidxmid.key) low=mid+1;,第八章 查找,分块查找算法续,else find=1; if(find=1) i=idxmid.low; j=idxmid.high
11、; else if (lowbn) /*k小于索引表内最大值*/,第八章 查找,分块查找算法续, i=idxlow.low; j=idxlow.high; while (ij) i=0; return(i); ,返回,第八章 查找,8.3.1 二叉排序树查找,将原始数据表示成二叉排序树，树的每个结点对应一个记录，则可利用此二叉排序树进行类似于二分查找思想的数据查找，这也是一个逐步缩小查找范围的过程。这种查找方法称为树型查找。 基本思想：查找过程从根结点开始，首先将它的关键字与给定值k进行比较，如果相等，则查找成功，输出有关的信息；如果不等，若根结点关键字大于给定值k，向左子树继续查找，否则向右
12、子树继续查找。 向子树查找又是树型查找，先以子树的根结点数据与k进行比较，如果不相等又转向它的左或右子树继续查找。,第八章 查找,树型查找是一种递归的查找过程。 在二叉排序树上查找关键字为k的结点，成功时返回该结点位置，否则返回NULL，递归函数如下： btree *search (btree *b,int k) if (b=NULL) return (NULL); else if(b-data=k) return (b);,第八章 查找,二叉排序树查找递归算法,if(kdata) return (search (b-left,k); else return (search (b-right,
13、k); ,第八章 查找,非递归算法,btree *treesearch (btree *b,int k) btree *p; p=b; while(p!=NULL); if (p-data=k) return (p); else if (kdata) p=p-left; else p=p-right; return (NULL); ,第八章 查找,在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根结点到所查找结点的路径；若查找不成功，则是从根结点出发走了一条从根结点到某个终端叶子结点的路径。与二分查找类似，和关键字比较的次数不超过二叉排序树的深度。 但是，含有n个结点的二叉树不是
14、唯一的，由于对其结点插入的先后次序不同，所构成的二叉树的形态和深度也可能不同。例如，图8.2是按不同插入次序得到的两个二叉排序树。,第八章 查找,图8.2 两个二叉排序树,在查找失败的情况下，在这二个树上所进行的关键字比较次数分别为3和6次。,第八章 查找,二叉排序树查找分析,树型查找最坏情况时，需要的查找时间取决于树的高度，当二叉排序树接近满二叉树时，其高度为log2n，最坏情况下查找时间为O(log n)，与二分查找是同样数量级的；当二叉排序树为只有一个端结点的所谓“退化树”时，其高度等于n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。 为了保证树型查找有较高的查找速度，我们希
15、望该二叉树接近满二叉树，也就是希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树。,第八章 查找,8.3.2 平衡树,平衡树(Balanced tree)也称为AVL树，是由阿德尔森维尔斯基和兰迪斯(Adelson-velskii and landis)于1962年首先提出的。 这是一种附加了一定限制条件的二叉树。我们定义二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子（Balance factor），所谓平衡树，是指一个二叉树其任一结点的平衡因子值只能是+1，0或-1，即任一结点的左、右子树高度之差不超过1。 如图8.3所示，图
16、中数字为该结点的平衡因子。,第八章 查找,平衡树,平衡二叉树,不平衡二叉树,第八章 查找,假设给平衡树某个结点的左子树插入一个新结点，且此新结点使左子树的高度加1，我们可能会遇到以下三种情况： (1) 如果原来其左子树高度hl与右子树高度hr相等，即原来此结点的平衡因子等于0,插入新结点后将使平衡因子变成+1，但仍符合平衡树的条件，不必对其加以调整； 如果原来hlhr，即原来此结点的平衡因子等于+1,插入新结点后将使平衡因子变成+2，破坏了平衡树的限制条件，需对其加以调整； 如果原来hlhr，即原来此结点的平衡因子等于-1，插入新结点后将使平衡因子变成0，平衡更加改善，不必加以调整。,第八章 查找,如果给平衡树某结点的右子树插入一个结点，且设此新结点使右子树的高度增加1，则也会遇到与之相对应的三种情况。 以图8.4所示的树为例，设原已有关键字为51，2
