一查找的基本概念

Ø 查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。

Ø 在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。

Ø 在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。

9.1 静态查找表

Ø 抽象数据类型静态查找表的定义：

    ADT  StaticSearchTable{

   基本操作P:  Create(&ST,n); Destroy(&ST);

      Search(ST,key);Traverse(ST,Visit());

     } ADT  StaticSearchTable

一、顺序查找

Ø 顺序查找的基本思想是：

从线性表的一端开始，依次将扫描到得结点关键字和给定值K相比较。若当前扫描到得结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。

Ø 顺序查找的存储结构要求：

 顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作为存储结构时，扫描必须从第一个结点开始），顺序查找对数据在表中存放的先后次序没有任何要求。

顺序查找的算法：

int Search_seq(SSTable ST[ ],  int n,  int key)

 { int  i=n;

   ST[0].key=key;

  for( i=ST.length; ST.elem[ i ].key!=key;  - - i  );/*从表尾往前查*/

   return i;

}

二、有序表的查找(折半查找)

Ø 折半查找(Birary search)也称为二分查找，它的查找速度比顺序查找快，但它要求数据在线性表中按查找的关键字域有序排列。

Ø 设n个数据存放于数组r中，且已经过排序，按由小到大递增的顺序排列。

Ø 采用二分查找，首先用要查找的给定值k与表正中间元素的关键值相比较，此元素的下标：

二分查找的性能分析

Ø 查找成功时进行比较的

    关键字个数最多不超过

    树的深度ëlog2nû +1

Ø 当n较大时，平均查找长度为

     ASLbs= log2( n+1) –1

三、静态树表的查找

u 当有序表中各记录的查找概率相等时，按照判定树描述的查找过程来进行折半查找，性能最优；

    有序表中各记录的查找概率不等时，二分查找性能不一定最优。

u  可由具体例子说明。

u  静态最优查找树和次优查找树方法可解决这一问题。

四、分块查找（索引顺序查找）

这是一种顺序查找的另一种改进方法。

先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。

然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。