数据结构课件第8章查找幻灯片.ppt

②二分查找的判定树（中序序列为从小到大排列的有序序列）如图所示， 可以得到二分查找的成功平均查找长度为： ASL=(1+2*2+3*4+4)/8=2.625； ③二叉排序树（关键字顺序已确定，该二叉排序树应唯一），如图所示， 可以得到二叉排序树查找的成功平均查找长度为： ASL=(1+2*2+3*2+4+5*2)=3.125； ④线性探查法解决冲突的散列表如图所示， 可以得到线性探查法的成功平均查找长度为： ASL=（1+1+2+1+3+2+1+8）/8=2.375； ⑤拉链法解决冲突的散列表如图所示， 可以得到拉链法的成功平均查找长度为： ASL=(1*6+2*2)/8=1.25 例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序树过程如下图所示。 注：二叉排序树与关键字排列顺序有关，排列顺序不一样，得到的二叉排序树也不一样。 图 二叉排序树的生成过程 8.3.4 二叉排序树上的查找⑴ 二叉排序树的查找思想 若二叉排树为空，则查找失败， 否则，先拿根结点值与待查值进行比较， 若相等，则查找成功， 若根结点值大于待查值，则进入左子树重复此步骤， 否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。 ⑵ 二叉排序树查找的算法实现 BtreeNode* Find(BtreeNode *BST,ElemType e){ //在以BST为根指针的二叉排队 树中查找值为e的结点 if(BST==NULL) return NULL; //查找失败 else{ if(BST-data==x) //查找成功 return BST; else if(BST-datae) //进入左子树查找 return Find(BST-left,e); else //进入右子树查找 return Find(BST-right,e); } } 8.3.5 二叉排序树查找的性能分析 在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差 8.4 散列查找8.4.1 基本概念 散列查找，也称为哈希查找。它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为散列表（哈希表）。 散列查找，与前面介绍的查找方法完全不同，前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，而散列查找是通过构造散列函数来得到待查关键字的地址。 散列查找是按理论分析真正不需要用到比较的一种查找方法。 例如，要找关键字为k的元素，则只需求出函数值H(k)，H(k)为给定的散列函数，代表关键字k在存贮区中的地址，而存贮区为一块连续的内存单元，可用一个一维数组(或链表)来表示。 例，假设有一批关键字序列18,75,60,43,54,90,46，给定散列函数H(k)=k%13，存贮区的“内存地址”从0到15，则可以得到每个关键字的散列地址为： H(18)=18%13=5 H(75)=75%13=10 H(60)=60%13=8 H(43)=43%13=4 H(54)=54%13=2 H(90)=90%13=12 H(46)=46%13=7 于是，根据散列地址，可以将上述7个关键字序列存贮到一个一维数组HT（散列表）中，具体表示为： 其中HT就是散列存贮的表，称为散列表。从散列表中查找一个元素相当方便，例如，查找75，只需计算出H(75)=75%13=10，则可以在HT[10]中找到75。 上面讨论的散列表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形，两个不同的关键字有可能对应同一个内存地址，这样，将导致后放的关键字无法存贮，我们把这种现象叫做冲突（collision）。 在散列存贮中，冲突是很难避免的，除非构造出的散列函数为线性函数。散列函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为同义词。 在散列存贮中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使散列查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。 第一是与装填因子α有关，所谓装填因子是指散列表中己存入的元素个数n与散列表的大小m的比值，即α=n/m。当α越小时，发生冲突的可能性越小，α越大（最大为1