查找

1、查找表

可以通过顺序查找和折半查找的来查找关键字。

1）顺序查找的平均查找长度为(n+1)/2。顺序查找适用于任意的查找表。

2）折半查找的平均查找长度约为log(n+1)-1。查找表必须是顺序存储且关键字是有序的。

2、查找树

查找树是将查找表组织成树的形式来实现查找的方法。主要有二叉查找树，平衡二叉树和B-树。

1）二叉查找树

定义：1、若存在左子树，则左子树的所有节点均不大于根节点；2、若存在右子树，则右子树所有节点均不小于根节点；3、左子树和右子树也是二叉查找树。

性质：中序遍历二叉查找树可得到有序递增的关键字序列。

查找方法：若查找树为空，返回空；否则与根节点比较，若查找关键字等于根节点，返回根节点；若小于根节点，则递归的查找左子树；若大于根节点，则递归的查找右子树。

因为二叉查找树的形态不是唯一的（如图，关键字集合相同，形态不同），而平均查找长度与树的形态有关。在最好的情况下，二叉查找树的平均查找长度为log(n+1),在最坏的情况下，查找树退化成顺序表，平均查找长度为（n+1）/2.

2）AWL树

3）B-树

3、哈希

哈希是实现查找的另一种数据结构。哈希函数（h(k),k是关键字）是关键字到数据元素存储地址的一种映射，即关键字k对应的数据元素的存储地址为h(k)。

常用的哈希函数

• 除留余数法

        即h(k)=k%m

      m为散列表大小

• 乘法散列

h(k) = ?m(kA mod 1)?即将关键字k乘以一个(0,1)的常量A，然后去k*A的小数部分，再乘以m，取其底作为散列值。

 冲突解决

哈希函数有可能将不同关键字散列到同一地址中，这种现象叫做冲突，产生冲突的关键字叫做同义词。解决冲突的方法有链接法和开放地址法。

链接法

把散列到同一槽中的所有元素都存放在一个链表中。每个槽中有一个指针，指向由所有散列到该槽的元素构成的链表的头。如果不存在这样的元素，则指针为空。如果链接法使用的是双向链表，那么删除操作的最坏情况运行时间与插入操作相同，都为O(1)，而平均情况下一次成功的查找需要Θ(1+α)时间。α是装填因子。

注：在一个能存放n个元素具有m个位置的哈希表中，装填因子定义为n/m，即一个位置平均存放元素的个数。

开放地址法

所有的元素都存放在散列表中。因此，适用于动态集合大小n不大于散列表大小的情况，即装载因子不超过1。否则，可能发生散列表溢出。有三种技术常用来计算开放寻址法中的探测序列：线性探测、二次探测，以及双重探测。

线性探测

h(k,i)=(h^,(k)+i)%m

线性探测容易出现元素“聚集”现象，即解决了同义词冲突又可能造成非同义词的冲突。 

二次探测

h(k,i)=(h^,(k)+i²)%m

二次探测利用二次函数随着i变大而探测步长迅速增大的特点，避免元素聚集。但是有可能造成哈希表虽然不满但由于循环反弹造成无法插入的情况。

双重探测

h(k,i)=(h₁(k)+ih₂(k))%m，其中h₂(k)任何时候不能为0.

三种方法的具体步骤是：首先计算h(k,0)，如位置空则插入，否则计算h(k,1)，依此进行。

查找,布布扣,bubuko.com

查找

原文：http://www.cnblogs.com/gdyang/p/3617884.html