第九章查找
*************************************************************************************
查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表否则称之为静态查找表
衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL)
*************************************************************************************
线性表查找的方法 ·顺序查找逐个查找ASL=(n+)/;
·二分查找取中点int(n/)比较若小就比左区间大就比右区间用二叉判定树表示ASL=(∑(每层结点数*层数))/N
·分块查找要求分块有序将表分成若干块内部不一定有序并抽取各块中的最大关键字及其位置建立有序索引表
*************************************************************************************
二叉排序树(BST)定义是二叉排序树是空树或者满足如下性质的二叉树 ·若它的左子树非空则左子树上所有结点的值均小于根结点的值;
·若它的右子树非空则右子树上所有结点的值均大于根结点的值;
·左右子树本身又是一棵二叉排序树
二叉排序树的插入建立删除的算法平均时间性能是O(nlogn)
二叉排序树的删除操作可分三种情况进行处理 ·*P是叶子则直接删除*P即将*P的双亲*parent中指向*P的指针域置空即可
·*P只有一个孩子*child此时只需将*child和*p的双亲直接连接就可删去*p
·*p有两个孩子则先将*p结点的中序后继结点的数据到*p删除中序后继结点
*************************************************************************************
关于B树(多路平衡查找树)它适合在磁盘等直接存取设备上组织动态的查找表是一种外查找算法建立的方式是从下向上拱起
*************************************************************************************
散列技术将结点按其关键字的散列地址存储到散列表的过程称为散列散列函数的选择有两条标准简单和均匀
常见的散列函数构的造方法 ·平方取中法hash=int((x^)%)
·除余法表长为mhash=x%m
·相乘取整法hash=int(m*(x*Aint(x*A));A=
·随机数法hash=random(x)
*************************************************************************************
处理沖突的方法·开放定址法 ·一般形式为hi=(h(key)+di)%m≤i≤m开放定址法要求散列表的装填因子α≤
·开放定址法类型 ·线性探查法address=(hash(x)+i)%m;
·二次探查法address=(hash(x)+i^)%m;
·双重散列法address=(hash(x)+i*hash(y))%m;
·拉链法 ·是将所有关键字为同义词的结点链接在同一个单链表中
·拉链法的优点 ·拉链法处理沖突简单且无堆积现象;
·链表上的结点空间是动态申请的适于无法确定表长的情况;
·拉链法中α可以大于结点较大时其指针域可忽略因此节省空间;
·拉链法构造的散列表删除结点易实现
·拉链法也有缺点当结点规模较小时用拉链法中的指针域也要占用额外空间还是开放定址法省空间
