C语言数据结构——查找(检索)

一、查找的基本概念

查找:查询某个关键字是否在(数据元素集合）表中的过程。也称作检索。
查找表: 由同一类型的数据元素（或记录）构成的集合。
主关键字: 能够惟一区分各个不同数据元素的关键字
次关键字: 通常不能惟一区分各个不同数据元素的关键字
查找成功: 在数据元素集合中找到了要查找的数据元素
查找不成功:在数据元素集合中没有找到要查找的数据元素
静态查找: 只查找，不改变数据元素集合内的数据元素
动态查找: 既查找，又改变（增减）集合内的数据元素
静态查找表: 静态查找时构造的存储结构
动态查找表: 动态查找时构造的存储结构

定义要查找数据元素的结构体为：
typedef struct
{
KeyType key;
} DataType;

平均查找长度ASL(Average Search Length):查找过程所需进行的关键字比较次数的平均值,是衡量查找算法效率的最主要标准,其数学定义为：

其中，Pi是要查找数据元素出现的概率，Ci是查找相应数据元素的比较次数。

二、查找算法分类

1、线性表方法
2、二叉排序树
3、根据关键字码值直接访问方法（哈希法）
4、索引方法