本文共 1352 字，大约阅读时间需要 4 分钟。

查找的定义

        查找（searching）就是根据给定的某一个值，在查找表中确定一个关键字等于给定值的数据元素（或记录）。查找表（Search Table）是由同一类型的数据元素（记录）构成的集合。，关键字（Key）是数据元素中某一个数据项的值，称为键值，用来标识一个数据元素。若表中不存在关键字等于给定值的记录，则查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。 

        查找按操作方式来分为大概两种：静态查找表和动态查找表。

• 静态查找表（static search table）：只作查找操作的查找表。它的主要操作是：
  • 查询某个“特定的”数据元素是否在查找表中。
  • 检索某个“特定的”数据元素和各种属性。
• 动态查找表（dynamic search table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
  • 查找时插入数据元素
  • 查找时删除数据元素

顺序查找（线性查找）

int Sequential_Search(int *a,int n,int key){//a为数组名，n为数组长度，key为要查找的关键字    int i;    for（i = 0;i < n;++i）    {        if(a[i] == key)            return i;    }    return -1;}

        上面的程序每次循环都需要判断数组是否越界，可通过设置哨兵的方法而不必每次进行比较。在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧。在总数据较多时，效率却提高很大。

int Sequential_Search(int *a,int n,int key)//数组定义长度为a[n+1]{    int a[0] = key;//哨兵    int i = n;    while(a[i] != key)        i--;    //对于内置数据类型，--i和i--的效率一样，而对于自定义类型（类）的重载--运算符函数效率不同。（前者效率更高。）    return i;   //返回0表示没有匹配的值。查找失败必然会返回0（以为a[0]值即为key，跳出循环）}

转载地址：http://ezbin.baihongyu.com/