1、查找表和查找效率的概念

查找表是指由同一类型的数据元素构成的集合。分为静态查找表和动态查找表。

1.1 静态查找表

1、查询某个特定元素是否在查找表的集合当中

2、查询某个特定元素的各种属性

1.2 动态查找表

1、在查找表中插入一个数据元素

2、在查找表中删除一个元素

1.3 关键字

它是数据元素的某个数据项的值。用来识别该元素。主关键字是唯一能表示该元素的值。次关键字用来表示多个数据元素的关键字。

1.4 查找

根据给定的值在查找表中查询是否存在一个其关键字等于给定值的记录或者数据元素。

1.5 平均查找长度

关键字和给定值进行比较的记录个数的平均值。也是衡量查找算法好坏的依据。

2、顺序查找

从数据集合的一端，逐个记录的关键字和给定值进行比较，找到则为查找成功。整个数据集合比较完后仍然找不到，则为查找失败。

顺序查找适用于顺序存储和链式存储。其平均查找长度为(n+1)/2.

顺序查找算法简单、适应性广。当数据集合数据量大的话，查询效率会较低。

3、折半查找

折半查找也称为二分查找。

平均查找长度：(n+1)/n*log^2(n+1) -1,当n值较大 log^2(n+1) -1

折半查找效率比顺序查找高，它比较合适顺序存储和关键字有序排列。所以折半查找适合数据表不经常变动，查询频率较高的情况。

4、索引顺序查找

索引顺序查找又称为分块查找，是顺序查找的一个改进查找算法。

原理：分块查找首先将表分为若干块。每一块可以无序。但块之间是要有序的。即后一块所记录的关键字均大于前一块的关键字。另外还会创建一个索引块表，索引块表关键字有序。

查询过程：1、在索引表中确认待查记录所在数据块。2、在该数据块内顺序查找。

平均查找长度：1/2(n/s + s) +1

它的效率优于顺序查找，比不上折半查找。

5、树表查找

常见的树表查找有二叉查找树、B-树、红黑树等常见查找算法。二叉查找树是一种动态查找表

5.1 二叉查找树查找过程

利用二叉查找树左小右大的特性，可以很容易实现查找任意值和最大/小值。

在二叉查找树中查找一个给定的关键字n的过程与折半查找很类似，

查找过程如下：

1.若二叉树是空树，则查找失败。

2.若x等于根节点的数据，则查找成功，否则。

3.若x小于根节点的数据，则递归查找其左子树，否则。

4.递归查找其右子树。

5.2 二叉树查找树b插入操作x的过程

1.若b是空树，则直接将插入的节点作为根节点插入。

2.x等于b的根节点的数据的值，则直接返回，否则。

3.若x小于b的根节点的数据的值，则将x要插入的节点的位置改变为b的左子树，否则。

4.将x要插入的节点的位置改变为b的右子树。

注：如果二叉树是单枝树。查询效率和顺序查找相当。

6、哈希查找

6.1 概念

通过计算数据元素的存储地址进行元素查找的一种查找算法。

根据设定的哈希函数和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表。这一映射过程称为哈希造表或散列。所得的存储位置称为哈希位置或者散列地址。

哈希算法要解决两个问题：哈希函数的构造、冲突的解决。

6.2 解决冲突

解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。

常用的解决冲突的方法有：开放定址法、链地址法、再哈希法、建立公共溢区法。

6.2.1开放定址法

最简单的产生探测序列的方法是进行线性探测，发生冲突后，顺序到下一个存储单元进行探测。

6.2.2 链地址法

链地址法是常用并且很有效的方法。它将具有相同哈希函数值记录组成一个链表，当链域值为NULL时，表示没有后继记录。

6.2.3 哈希查找

线性探测解决冲突的方式下：某一个位置上找到关键字等于key的记录，表示查找成功；探测序列查不到key关键字的记录，又遇到了空单元，表示找不到该元素，查找失败。

链地址法解决冲突构造的哈希表中查找元素，就是根据哈希函数得到的元素所在链表的头指针，然后在链表中顺序查找的过程。