基础：查找的基本概念

查找表：由同一类数据元素构成的集合。（线性表、数表、散列表）

关键字：是数据元素中某个数据项的值，用它可以表示一个数据元素。（主关键字：唯一地标识；次关键字：不唯一地标识）

查找：根据制定的某个值，在查找表中确定一个其关键字等于给定的这个值的数据元素

动态/静态查找：查表的同时改表成为动态查找，反之为静态查找

平均查找长度：ASL=∑PiCi (i=1,2,3,…,n)，Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。

*线性表的查找*

（1）顺序查找

（2）二分查找（折半查找）

（3）分块查找

（1）顺序查找

从表的一端开始，依次将记录的关键字与给定的值进行比较。

顺序查找既适用于顺序存储结构（数组），又适用于链式存储结构（链表），以下介绍顺序存储结构：

数据元素的类型：

 

复制代码
1 typedef struct{ 2     KeyType key; 3     InfoType otherinfo 4 }ElemType
复制代码
复制代码
1 typedef struct { 2           ElemType   *R; //表基址 3           int    length;     //表长 4 }SSTable;
复制代码

代码：

复制代码
1 int LocateELem(SqList L,ElemType e) 2 {  for (i=0;i< L.length;i++) 3         if (L.elem[i]==e) return i+1;                 4     return