数据结构与算法8

第8章查找算法（4课时）8.3动态查找及其实现8.5应用实例8.1查找算法及常见查找算法比较8.4哈希查找及其实现8.2静态查找及其实现目录查找是指根据给定值从一个数据集合中搜索某个元素的过程。若某个元素的关键字值与给定值相等，则查找成功；否则查找失败。本教材给出的代码都是基于给定元素K进行查找，即将待查找数据集合中每一元素的关键字值与元素K的关键字值比较，若相等则查找成功。8.1查找算法及常见查找算法比较查找可以分为静态查找和动态查找静态查找只根据给定值在数据集合中按关键字查找匹配元素、访问匹配元素的属性，而不对数据集合进行插入元素、删除元素等操作动态查找可能会在查找过程中向数据集合中插入一个新元素或从数据集合中删除一个已有元素8.1查找算法及常见查找算法比较平均比较次数（也称为平均查找长度，AverageSearchLength，简写为ASL）衡量查找算法性能优劣的标准其中，n是待查找数据集合中的元素数目，pi是查找第i个元素的概率，ci是找到第i个元素所需的比较次数。8.1查找算法及常见查找算法比较8.1查找算法及常见查找算法比较类别查找算法平均查找长度数据集合要求静态查找顺序查找(n+1)/2任何存储结构，对数据集合无特别要求折半查找log2(n+1)-1数据集合采用顺序表存储结构，且数据集合中的元素是按关键字大小有序排列的分块查找介于顺序查找和折半查找之间除了待查找的数据集合外，还需建立一个索引表动态查找二叉排序树查找O(log2n)采用二叉排序树作为数据集合的存储结构哈希查找哈希查找O(1)采用哈希表作为数据集合的存储结构8.2静态查找及其实现8.2.1顺序查找.8.2.2折半查找8.2.3分块查找顺序查找的步骤按预先规定的顺序依次将数据集合中每个元素的关键字与给定值进行比较，若某个元素的关键字与给定值相同，则查找成功；若遍历所有元素后，仍没有找到关键字与给定值相同的元素，则查找失败。8.2静态查找及其实现8.2.1顺序查找【描述8-1】顺序查找的算法描述。//根据给定元素K对R进行顺序查找template<classT>intSeqSearch(TR[],intnSize,TK){ intnI; R[0]=K; //R[0]作为监视哨

for(nI=nSize;R[nI]!=K;nI--) //从表尾开始向前进行查找

; returnnI;//将匹配元素在数组中的下标返回，查找失败则返回0}8.2静态查找及其实现8.2.1顺序查找折半查找（二分查找）要求数据集合采用顺序表存储结构，且数据集合中的元素是按关键字大小有序排列的。具体步骤为：对于包含n个元素的递增数据集合R={R[1],R[2],…,R[n]}（R[i]≤R[i+1]），根据给定元素K进行折半查找，初始化待查找数据集合的下标起始位置low=1和结束位置high=n。计算中间元素下标(low+high)/2

，若R[mid]==K，则查找成功，折半查找算法结束；若R[mid]<K，则令low=mid+1；否则，若R[mid]>K，则令high=mid-1。若新的待查找数据集合不为空，即low≤high，则返回到上一步在新的数据集合（R[low],R[low+1],…,R[high]）上继续进行折半查找；否则查找失败。8.2静态查找及其实现.8.2.2折半查找例如，对于一组具有关键字值{17,22,28,30,37,43,56,70}的数据元素集合{R1,R2,…,R8}，分别根据给定值k=56和k=25进行折半查找，其过程如图8-1（a）和（b）所示。8.2静态查找及其实现.8.2.2折半查找【描述8-2】折半查找的算法描述。//根据给定元素K对R进行折半查找template<classT>intBinSearch(TR[],intnSize,TK){ intlow=1,high=nSize,mid; while(low<=high) { mid=(low+high)/2; if(R[mid]==K) returnmid; //查找成功，返回匹配元素下标

elseif(R[mid]>K) high=mid-1; //在前半部分进行折半查找

else low=mid+1; //在后半部分进行折半查找

} return0; //查找失败}8.2静态查找及其实现.8.2.2折半查找分块查找，又称索引顺序查找，它是顺序查找的一种改进算法性能和对待查找数据集合的要求均介于顺序查找和折半查找之间除了待查找的数据集合外，还需建立一个索引表待查数据集合与索引表的关系将包含n个元素的待查找数据集合均匀分为b块（即b个子集合），前b-1块中元素数目s=n/b，最后一块中元素数目小于等于s。分块后块内元素可以无序，但块间必须有序，这里假设块间为递增排列，即第i+1块中的任一元素大于第i块中的任一元素（i<b）。构造一个包含b个元素的索引表，用于记录每块的起始位置和最大元素值。8.2静态查找及其实现8.2.3分块查找8.2静态查找及其实现分块查找算法的具体步骤在索引表中查找，确定待查找元素在哪一块，由于索引表有序，因此可以使用二分查找算法。在已确定的块中，进行顺序查找。8.2.3分块查找8.3动态查找及其实现若待查找的数据集合在查找过程中会动态变化，则这样的查找过程称为动态查找。动态查找的数据集合通常采用树型存储结构，主要有二叉排序树、平衡二叉树、红黑树、B树等，这里仅介绍二叉排序树及基于二叉排序树的动态查找。8.3动态查找及其实现8.3.1二叉排序树的定义8.3.3二叉排序树的查找8.3.2二叉排序树的生成8.3动态查找及其实现二叉排序树，又称二叉查找树，它或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值。若它的右子树非空，则右子树上所有结点的值均大于根结点的值。左、右子树也分别是二叉排序树。8.3.1二叉排序树的定义8.3动态查找及其实现8.3.2二叉排序树的生成8.3动态查找及其实现8.3.2二叉排序树的生成8.3动态查找及其实现【描述8-6】以递归方式实现的二叉排序树查找的算法描述。template<classT>LinkedNode<T>*SearchBST(LinkedNode<T>*pRoot,TK){ LinkedBinTree<T>btree; Tx; if(pRoot==NULL) //若子树为空，则查找失败

returnNULL; btree.GetNodeValue(pRoot,x); if(K==x) //若K等于根结点的值，则查找成功

returnpRoot; elseif(K<x)//若K小于根结点的值，则在左子树中继续进行二叉排序树的查找

returnSearchBST(btree.GetLeftChild(pRoot),K); else //否则，若K大于根结点的值，则在右子树中继续进行二叉排序树的查找

returnSearchBST(btree.GetRightChild(pRoot),K);}8.3.3二叉排序树的查找8.3动态查找及其实现【例8-1】基于描述8-4至描述8-7中二叉排序树的C++实现代码，完成如下操作：创建一个包含整型元素43、56、37、28、17、39、22的二叉排序树，并显示二叉排序树中的所有元素。根据给定值在二叉排序树中进行查找，若查找成功则输出找到的元素值，否则输出“查找失败”。8.3.3二叉排序树的查找8.4哈希查找及其实现前面学习的查找算法的查找效率取决于比较的次数。哈希查找采用了一种截然不同的方式，它的思想类似于7.6节学习的分配排序，即直接根据待查找元素的值确定该元素所在的位置。哈希查找利用哈希表（又称散列表）作为待查找数据集合的存储结构，与前面学习的查找算法相比，哈希查找具有更高的效率。8.4.1哈希表8.4.2哈希函数8.4哈希查找及其实现8.4.3冲突的处理方法哈希表是线性表的一种重要存储方式，数据元素自身的值决定了它的存储位置。哈希表的基本思想确定一函数h，对于关键字值是k的元素，以k为自变量计算函数值h(k)，这个函数值被解释为一片连续存储空间中的一个地址（即数组中的一个下标值），元素即被存入到这个地址中。8.4哈希查找及其实现8.4.1哈希表例如，对于具有关键字值{43,56,37,28,16,30,22}的数据集合R={R1,R2,…,R7}，假设选取的哈希函数为h(k)=k%11，元素存储在一维数组中，则可得到图8-7所示的哈希表。8.4哈希查找及其实现8.4.1哈希表8.4哈希查找及其实现常用的哈希函数构造方法除余法数字分析法折叠法平方取中法8.4.2哈希函数开放定址法8.4哈希查找及其实现8.4.3冲突的处理方法拉链法8.4哈希查找及其实现8.4.3冲突的处理方法

【例8-2】基于描述8-8中哈希表类的C++实现代码，完成如下操作：创建一个包含整型元素43、56、37、28、17、39、22的哈希表（其哈希函数为h(x)=x%11），并显示哈希表中的所有元素。根据给定值在哈希表中进行哈希查找，若查找成功则输出找到的元素值，否则输出“查找失败”。8.4哈希查找及其实现8.4.3冲突的处理方法

编写学生信息管理程序，要求可以按学号、姓名或成绩对学生信息查找。求解思路：在实际中，通常需要按照不同关键字对数据集合中的元素进行查找。例如，可以按学号、姓名、成绩等查找学生。若是使用顺序查找，则只存储一份学生信息就可以，占