数据结构（10）之查找
1 前言
这节我们简单的介绍一下常见的查找算法。
2 详述2.1 查找概论查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。
关键字（Key）是数据元素中某个数据项的值，又称为键值。
可以识别多个数据元素（或记录）的关键字，我们称为次关键字（Secondary Key）。
查找（Searching）就是根据给定的某个值，在查找中确定一个其关键字等于给定的数据元素（或记录）。
查找按照操作方式来分有两大种：静态查找表和动态查找表。
静态查找表（Static Search Table）：只做查找操作的查找表。
（1）查询某个“特定的”数据元素是否在查找表中。
（2）检索某个“特定的”数据元素和各种属性。
动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
（1）查找时插入数据元素。
（2）查找时删除数据元素。
2.2 顺序查找表顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查找的记录；如果知道最后一个（或第一个）记录，其关键字和给定值比较都不相等，则表中没有所查的记录，查找不成功。
2.2.1 顺序查找算法代码实现：
折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常是从小到大有序），线性表必须采用顺序存储。折半思想：有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，知道查找成功，或所有查找区域无记录，查找失败为止。
算法实现：
时间复杂度O(logn)。
2.3.2 插值查找插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较厚的查找方法，其核心就在于插枝的计算公式(key-a[low])/(a[high]-a[low])。
程序运行：
对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。
2.5.2 分块索引分块有序，是吧数据集的记录分成了若干块，并且：
·快内无序
·块间有序：第二块所有的记录的关键字均大于第一块中所有记录的关键字，第三块的所有记录的关键字均大于第二块的所有记录的关键字。
分块索引的索引项结构分为三个数据项：
·最大关键码，它存储每一块中的最大关键字
·存储了块中的记录个数
·用于指向首数据的指针，便于开始对这一块中记录进行遍历
时间复杂度高于顺序查找，低于折半查找。
2.5.3 倒序索引
索引结构：
·次关键码，例如上面的“英文单词”
·记录号表，例如上面的“文章编号”
其中记录号表存储具有系统次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒序索引（inverted index）。
2.6 二叉树排序二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
·若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；
·若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
·若它的左，右子树也分别为二叉排序树。
查找实现
/*递归查找二叉排序树T种是否存在key*//*指针f指向T的双亲，其初始调用值为NULL*//*若查找成功，则指针p指向该数据元素结点，并返回TRUE*//*否则指针p指向查找路径上访问的最后一个结点并返回FALSE*/Status SearchBST(BiTree T,int key,BiTree f,BiTree *p){ if(!T) { *p = f; return FALSE; } else if(key == T->data) { *p = T; return TRUE; } else if(key<T->data) return SearchBST(T->lchild,key,T,p); /*在左子树继续查找*/ else return SearchBST(T->child,key,T,p); /*在右子树继续查找*/}
3 结语以上是所有内容，希望对大家有所帮助。
