数据结构复习总结第九章查找

数据结构复习总结第九章查找  

　　第九章查找

　　*************************************************************************************

　　查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表 否则称之为静态查找表

　　衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL)

　　*************************************************************************************

　　线性表查找的方法 ·顺序查找 逐个查找 ASL=(n+ )/ ;

　　·二分查找 取中点int(n/ )比较 若小就比左区间 大就比右区间 用二叉判定树表示 ASL=(∑(每层结点数*层数))/N

　　·分块查找 要求 分块有序 将表分成若干块内部不一定有序 并抽取各块中的最大关键字及其位置建立有序索引表

　　*************************************************************************************

　　二叉排序树(BST)定义是 二叉排序树是空树或者满足如下性质的二叉树 ·若它的左子树非空 则左子树上所有结点的值均小于根结点的值;

　　·若它的右子树非空 则右子树上所有结点的值均大于根结点的值;

　　·左 右子树本身又是一棵二叉排序树

　　二叉排序树的插入 建立 删除的算法平均时间性能是O(nlog n)

　　二叉排序树的删除操作可分三种情况进行处理 ·*P是叶子 则直接删除*P 即将*P的双亲*parent中指向*P的指针域置空即可

　　·*P只有一个孩子*child 此时只需将*child和*p的双亲直接连接就可删去*p

　　·*p有两个孩子 则先将*p结点的中序后继结点的数据到*p 删除中序后继结点

　　*************************************************************************************

　　关于B 树(多路平衡查找树) 它适合在磁盘等直接存取设备上组织动态的查找表 是一种外查找算法 建立的方式是从下向上拱起

　　*************************************************************************************

　　散列技术 将结点按其关键字的散列地址存储到散列表的过程称为散列 散列函数的选择有两条标准 简单和均匀

　　常见的散列函数构的造方法 · 平方取中法 hash=int((x^ )% )

　　· 除余法 表长为m hash=x%m

　　· 相乘取整法 hash=int(m*(x*A int(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;

　　·拉链法 ·是将所有关键字为同义词的结点链接在同一个单链表中

　　·拉链法的优点 ·拉链法处理冲突简单 且无堆积现象;

　　·链表上的结点空间是动态申请的适于无法确定表长的情况;

　　·拉链法中α可以大于 结点较大时其指针域可忽略 因此节省空间;

　　·拉链法构造的散列表删除结点易实现