本章介绍了 线性表 树和散列表 的查找方法算法实现以及各种查找方法的时间性能分析 重点 是 顺序查找 二分查找 二叉树查找 以及 散列表上查找 的基本思想和算法实现
一基本概念( 识记 )
查找的同时对表做修改操作(如插入或删除)则相应的表称之为 动态查找表 否则称之为 静态查找表
衡量一个查找算法次序优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL)
二线性表的查找( 简单应用 )
线性表 上进行查找的方法主要有 三种 顺序查找 二分查找 和 分块查找
顺序查找的算法基本思想是从表的一端开始顺序扫描线性表依次将扫描到的结点关键字与给定值K比较若当前扫描到的结点关键字与k相等则查找成功;若扫描结束后仍未找到关键字等于K的结点则查找失败
顺序查找 方法可用 链式 存储结构和 顺序存储结构 实现
在 顺序存储结构的顺序查找算法 中所设的 哨兵 是为了简化循环的边界条件而引入的附加结点(元素)其作用是使for循环中省去判定防止下标越界的条件从而节省了比较的时间
在等概率情况下 查找成功 时其平均查找长度约为表长的一半(n+)/ 查找失败 的话其平均查找长度为n+
二分查找 (又称折半查找)它的算法思想是对一有序表中的元素从初始的查找区间开始每经过一次与当前查找区间的中点位置上的结点关键字进行比较若相等则查找成功否则当前查找区间的缩小一半按k值大小在某半个区间内重复相同的步骤进行查找直到查找成功或失败为止
二分查找的递归算法如下(看看就行)
int BinSearch (SeqList Rint low int hightRecType k)
{
int mid=(low+hight)/;
if(low<=hight)
{
if(R[mid]key==k)return mid;//查找成功返回
if(R[mid]key>k)return BinSearch(Rlowmidk);
else return BinSearch(Rmid+hightk);
}
else return ;
}//BinSearch
二分查找在等概率的情况下查找成功的平均查找长度ASL为lg(n+)在查找失败时所需比较的关键字个数不超过判定树的深度最坏情况下查找成功的比较次数也不超过判定树的深度┌lg(n+)┐(不小于lg(n+)的最小整数)
二分查找 只适用 于 顺序存储结构 而 不能 用 链式存储结构 实现因为链表无法进行随机访问如果要访问链表的中间结点就必须先从头结点开始进行依次访问这就要浪费很多时间还不如进行顺序查找而且用链存储结构将无法判定二分的过程是否结束因此无法用链表实现二分查找
分块查找 (又称索引顺序查找)的基本思想是将原表分成若干块各块内部不一定有序但表中的块是分块有序的并抽取各块中的最大关键字及其起始位置建立索引表因为索引表是有序的分块查找就是先用二分查找或顺序查找确定待查结点在哪一块然后在已确定的块中进行顺序查找(不能用二分查找因为块内是无序的)分块查找实际上是两次查找过程它的算法效率介与顺序查找和二分查找之间
以上三种查找方法的比较如下表
查找算法 存储结构 优点 缺点 适用于
顺序查找 顺序结构
链表结构 算法简单且对表的结构无任何要求 查找效率低 n较小的表的查找和查找较少但改动较多的表(用链表作存储结构)
二分查找 顺序结构 查找效率高 关键字要有序且只能用顺序存储结构实现 特别适用于一经建立就很少改动又经常需要查找的线性表
分块查找 顺序结构
链表 在表中插入或删除记录时就只要在该记录所属块内操作因为块内记录的存放是随意的所以插入和删除比较容易 要增加一个辅助数组的存储空间并要进行将初始表分块排序运算 适用于有分块特点的记录如一个学校的学生登记表可按系号或班号分块
三树的查找( 简单应用 )
以 树 做为表的组织形式有一个好处就是可以实现对 动态查找表 进行 高效率 的查找这里讲到了二叉排序树和B树以及在这些树表上进行查找和修改操作的方法
二叉排序树 (BST)又称二叉查找树其定义是二叉排序树要或者是空树或者满足如下性质的二叉树
()若它的左子树非空则左子树上所有结点的值均小于根结点的值;
()若它的右子树非空则右子树上所有结点的值均大于根结点的值;
()左右子树本身又是一棵二叉排序树
二叉排序树实际上是满足BST性质的二叉树
二叉排序树的插入建立的算法平均时间性能是O(nlgn)但其执行时间约为堆排序的至倍二叉排序树的删除操作可分三种情况进行处理
()*P是叶子则直接删除*P即将*P的双亲*parent 中指向*P的指针域置空即可
()*P只有一个孩子*child此时只需将*child和*p的双亲直接连接就可删去*p
()*p有两个孩子则将操作转换成删除*p结点的中序后继在删去它之前把这个结点的数据复制到原来要删的结点位置上就完成了删除
二叉排序树上的查找和二分查找类似它的关键字比较次数不超过树的深度在最好的情况下二叉排序树在生成的过程中比较匀称此时的叉排序树是平衡的二叉树(也就是树中任一结点的左右子树的高度大致相同)它的高度约为lgn完全平衡的二叉树高度约为lgn在最坏的情况下输入的实例产生的二叉排序树的高度将达到O(n)这种情况应当避免
关于 B树 (多路平衡查找树)它 适合 在 磁盘等直接存取设备 上组织动态的查找表是一种 外查找算法
B树的 阶 是指B树的度数B树的结点具有 k 个孩子时该结点必有 k(k>=) 个关键字
实际上B树是二叉排序树的推广它就是一棵m叉树且满足四个性质这些性质与二叉排序树有相似之处请仔细理解之
有关B树的其他内容比较复杂领略一番也就是了
四散列技术( 简单应用 )
上面的几种查找方法均是建立在比较关键字的基础上因此它们的平均和最坏情况下所需的比较次数的下界是lgn+O()
而 散列技术 可以 无需任何比较 就找到待查关键字其查找的期望时间为O()
散列表的概念不容易用一两句话说清楚简单的理解就是将所有可能出现的关键字的集合U(全集)映射到一个表T[m]的下标集上这个表就是散列表
而关键字与这个表地址之间以什么样的关系发生联系呢这就要通过一个函数来建立这个函数是以U中的关键字为自变量以相应结点的存储地址为函数值它就称为 散列函数 将结点按其关键字的散列地址存储到散列表的过程称为 散列
根据某种散列函数一个关键字的散列函数值是唯一的但是有可能两个或多个不同关键字的函数值是相同的这时就会把几个结点存储到同一个表位置上这时就造成 沖突 (或 碰撞 )现象这两个关键字称为该散列函数的 同义词
要完全(不是安全)避免沖突需满足 两个条件 一是关键字集合U不大于散列表长m另一个是选择合适的散列函数如果用h(k i )=)这样的函数的话看看有什么结果?:)
通常情况下U总是大大于m的因此不可能完全避免沖突沖突的频繁程度还与表的填满程度相关 装填因子 α表示表中 填入的 结点数 与 表 长 的比值 通常取α ≤ 因为α越大表越满沖突的机会也越大
散列函数 的选择有 两条标准 简单和均匀 看看h(k i )=这样的函数简单是简单但绝不均匀下面是常见的几种散列函数构的造方法
平方取中法
除余法 它是用表长m来除关键字取余数作为散列地址若选除数m是关键字的基数的幂次就会使得高位不同而低位相同的关键字互为同义词因此最好选取素数为除数
相乘取整法 有两个步骤先用关键字key乘上某个常数A(
4.随机数法 ，此法以关键字为自变量，通过一随机函数得到的值作为散列地址。TW.WinGWIT.com
处理沖突的方法 ：当不可避免发生沖突时，就必须对沖突加以解决，使发生沖突的同义词能存储到表中。通常有两类方法处理沖突： 开放定址法和拉链法 。前者是将所有结点均存放在散列表T[0..m-1]中，后者是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表中。
开放定址法的一般形式为：
h i =(h(key)+d i )%m 1 ≤ i ≤ m-1
开放定址法要求散列表的装填因子α ≤1。 开放定址法又有线性探查法、二次探查法和双重散列法之分。
由于线性探查法在构造散列表时，遇到沖突(有同义词)的时候会按探查序列向后面的空地址插入，从而使原来应插入到此位置的结点又与它发生沖突，当一连串的位置均已有结点时，本应插入到这些位置的结点又只能将其插入到更后面的同一个空结点上，这种散列地址不同的结点争夺同一个后继散列地址的现象就是 聚集 或 堆积 。(注意， 同义词 发生 沖突不是堆积 )
为了减小堆积现象的发生，可以用 二次探查法 和 双重散列法 进行探查。
拉链法 解决沖突的做法是，将所有关键字为 同义词的结点 链接 在同一个单链表中。与开放定址法相比，拉链法有如下几个 优点 ：
(1)拉链法处理沖突简单，且无堆积现象，即非同义词决不会发生沖突，因此平均查找长度较短;( 简单无堆积 )
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适于造表前无法确定表
