8.1查找简述

查找表(Search Table) 是由同一类型的数据元素(或记录)构成的集合

关键字(Key)是数据元素中某个数据项的值，又称为键值，"用它可以标识-一个数 据元素。也可以标识-一个记录的某个数据项(字段)，我们称为关键码

若此关键字可以唯一地标识一 个记录，则称此关键字为主关键字(Primary Key)。 注意这也就意味着，对不同的记录，其主关键字均不相同。主关键字所在的数据项称为主关键码

那么对于那些可以识别多个数据元素(或记录)的关键字，我们称为次关键字(Secondary Key), 次关键字也可以理解为是不以唯一标识一个数据元素(或记录)的关键字，它对应的数据项就是次关键码。

查找( Searching )就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素( 或记录)。

如上表所示，如果查找主关键字“代码”的主关键字“sh601398”的记录时，可以得到一条唯一的记录

如果查找次关键码“涨跌额”为“-0.11”的记录时，就可以得到两条记录

若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给 出一个“空”记录或“空”指针。

查找表按照操作方式来分有两大种:静态查找表和动态查找表。

静态查找表(Static Search Table):只作查找操作的查找表。它的主要操作有:

(1)查询某个“特定的”数据元素是否在查找表中。 (2)检索某个“特定的”数据元素和各种属性。

你想插入的同时进行插入和删除操作，就要用到动态查找表

动态查找表(Dynamic Search Table):在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。 显然动态查找表的操作就 是两个: (1)查找时插入数据元素。 (2)查找时删除数据元素。

为了提高查找的效率，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。

从逻辑上来说，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，我们就不能不改变数据元素之间的关系，在存储时可以将查找集合组织成表、树等结构。

例如，对于静态查找表来说，我们不妨应用线性表结构来组织数据，这样可以使用顺序查找算法，如果再对主关键字排序，则可以应用折半查找等技术进行高效的查找。

如果是需要动态查找，则会复杂一些， 可以考虑二叉排序树的查找技术。

我的理解

什么是顺序查找呢？ 顺序查找的原理很简单，就是遍历整个列表，逐个进行记录的关键字与给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录。 如果直到最后一个记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找失败。

8.2顺序表查找

散落的图书可以理解为一个集合，而将它们排列整齐，就如同是将此集合构造成一个线性表。我们要针对这一线性表进行查找操作，因此它就是静态查找表。

此时图书尽管已经排列整齐，但还没有分类，因此我们要找书只能从头到尾或从尾到头一本一本查看，直到找到或全部查找完为止。这就是我们现在要讲的顺序查找。

顺序查找(Sequential Search) 又叫线性查找，是最基本的查找技术，它的查找过程是:从表中第-一个(或最后-一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录;如果直到最后一个(或第-一个)记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

8.2.1顺序表查找算法

int Sequential_Search(int *a,int n,int key)
 {
     int i;
     for(i = i;i<=n;i++)
     {
         if(a[i] == key)
             return i;
     }
     return 0;
 }

8.2.2顺序表查找优化

到这里并非足够完美，因为每次循环时都需要对i是否越界，即是否小于等于n作判断。事实上，还可以有更好一点的办法，设置一个哨兵，可以解决不需要每次让i与n作比较。看下面的改进后的顺序查找算法代码。

/*有哨兵顺序查找*/
 int Sequential_ Search2 ( int *a,int n,int key )
 {
     int i;
     a[0]=key; /* 设置a[0]为关键字值，我们称之为“哨兵”*/
     i=n;    /* 循环从数组尾部开始 */
     while (a[i] !=key )
     {
         i--;
     }
     returni;/*返回0则说明查找失败; */
 }

此时代码是从尾部开始查找，由于a[0]=key， 也就是说，如果在a[i]中有key 则返回i值，查找成功。否则一定在最终的a[0]处等于key, 此时返回的是0,即说明a[1] ~a[n]中没有关键字key,查找失败。

这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后 都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。当然，“哨兵”也不- -定就一-定要在数组开始，也可以在末

很显然，顺序查找技术是有很大缺点的，n很大时，查找效率极为低下，不过优点也是有的，这个算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的。