7.1 顺 序 查 找
从本章开始，将介绍数据结构中的重要技术——查找和排序。通常，在非数值运算问题中，数据存储量很大，要在大量信息中找到某些值，就需要用到查找技术；而为了提高查找效率，就需要对一些数据进行排序。查找和排序的数据处理量几乎占到总处理量的80%以上，因此查找和排序的有效性直接影响到基本算法的有效性。
查找又称为检索，是指在某种数据结构中找出满足给定条件的节点，若找到满足给定条件的元素，则表示查找成功，否则查找失败。查找是数据结构中很常用的技术，例如，在学生成绩表中查找某位学生的成绩、在图书馆的书目文件中查找某编号的图书等。本章将介绍常用的几种查找算法。
本章主要内容
& 顺序查找、对分查找和分块查找的基本算法
& 二叉排序树的基本算法以及对二叉平衡树的调整方法
& 构造哈希函数的方法和哈希冲突解决方法
& B-和B+树的定义、查找、插入和删除算法
7.1 顺 序 查 找
顺序查找是最简单的查找方法。它是从线性表的一端开始，顺序地扫描线性表，依次将扫描到的节点关键字和给定值k相比较，若当前扫描到的元素关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的节点，则查找失败。
【例7-1】 在关键字序列为{3,9,1,5,8,10,6,7,2,4}的线性表中从前往后查找关键字为6的元素。
解：顺序查找过程如图7-1所示。
顺序查找的线性表定义如下：
#define MaxSize /*最多项数*/
typedef struct
{
KeyType key; /*存放关键字，KeyType为关键字的类型*/
ElemType data; /*其他数据，ElemType为其他数据的类型*/
} LineList;
这里，KeyType和ElemType分别为关键字的数据类型和其他数据的数据类型，均可以是任何相应的数据类型，这里KeyType默认为int型。
顺序查找的算法如下（在含n个元素的线性表R中顺序查找关键字为k的元素，若查找到，则返回其序号i；若未查找到，则返回-1）：
int SeqSearch(LineList R[ ],int n,KeyType k)
{
int i=0;
while(i<n && R[i].key!=k) i++;
if(i>=n)
return(-1);
else
return(i);
}
图7-1 顺序查找过程
查找成功，返回序号6。
算法分析：对于含有n个元素的线性表，元素查找在等概率的前提下，查找成功的概率pi=
。另外，第1个元素（序号为0的元素）查找成功需比较1次，第2个元素（序号为1的元素）查找成功需比较2次，……，第n个元素（序号为n-1的元素）查找成功需比较n次。所以查找成功时的平均查找长度为：
其中，Ci是查找R[i].key关键字需要比较的次数。因此，顺序查找的缺点是速度较慢，在成功的情况下平均查找长度为O(n)。在不成功的情况下需要与这n个元素的关键字进行比较，所以平均查找长度为n。