查找
一、查找基本概念
- 查找是什么
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录。有主关键字和次关键字之分。
- 在哪里查找
在查找表查找，查找表：是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵活方便的结构。
- 查找什么
查找某个“特定的”数据元素是否在查找表中，检索数据元素属性，插入数据元素，删除数据元素。
- 查找表分类：
静态查找表：仅作“查询”操作的查找表
动态查找表：作“插入”和“删除”操作的查找表。
- 查找算法的评价指标：
平均查找长度（ASL,average search length）:关键字的平均比较次数
- 查找过程中我们要研究什么
查找的方法取决于查找表的结构，即表中数据元素是依何种关系组织在一起的。
二、线性表的查找
（1）顺序查找
对于顺序表或线性表表示的且无序的静态查找表可以顺序查找。
直接实现程序过于简单，略。
改进：可以把待查关键字存入表头，可免去查找过程中每一步都要检测是否查找完毕，加快速度。程序如下
int Search_Seq(int a[20],int key) { a[0]=key; for(i=20-1;a[i]!=key;--i); return i; }
（2）折半查找
每次将待查记录所在区间缩小一半
缺点：只适用于有序表，且限于顺序存储结构（对链式存储而言很麻烦）
程序简单，略
（3）分块查找（也叫索引顺序查找）
实际例子：查字典，a开头一块，b开头一块等等……
实际步骤：
需要额外一个数组，存储每一块的开头元素的下标。