经典算法系列之（二）：七大查找——顺序查找

​
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

一.什么是顺序查找？

        顺序查找（sequential search），也称穷举查找，是一种基本的查找算法。顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。静态查找表既可以使用顺序表表示，也可以使用链表结构表示。虽然一个是数组、一个链表，但两者在做查找操作时，基本上都是大同小异。

二.基本思想

        静态查找表用顺序存储结构表示时，顺序查找的查找过程为：从表中的最后一个数据元素开始，逐个同记录的关键字做比较，如果匹配成功，则查找成功；反之，如果直到表中第一个关键字查找完也没有成功匹配，则查找失败。

三.顺序查找的改进

        顺序查找的改进：设置一个“哨兵”，就是等待查询的值，放在查找方向的尽头处，避免了每一次比较后都要判断一下当前的位置是否越界了。

        习惯上我们一般将“哨兵”放在开头，然后逆序查找，放置好“哨兵”以后，从没有“哨兵”的一端依次遍历，如果查找的数据与关键字（key值）相等，则输出，当程序运行到“哨兵”处，查询结束。

 

四.顺序查找的优缺点

         优点：算法简单而且使用面广，
        （a)对表中记录的存储没有任何要求，顺序存储和链接存储均可。
        （b)对表中记录的有序性也没有要求，无论记录是否按关键码有序均可

         缺点：查找效率较低，特别是当待查找集合中元素较多时，不推荐使用顺序查找。

五.时间以及空间复杂度

 1.时间复杂度

        最坏：全部遍历也并未找到目标的key，此时循环被完整的执行，循环执行次数与n相关，所以时间复杂度为O(n)。

        最好：第一次就找到了，时间复杂度为O(1)。

        平均的复杂度为O（n），属于较慢的算法。

   2.空间复杂度

        由于算法不会改变原有的元素集合，只需要一个额外的变量控制索引变化，所以空间复杂度为常数级：O(1)。

六.顺序查找的注意事项

        顺序查找是假设在数组范围内找key，找到就结束，不一定到数据结束。也就是，如果数组中的第一个数据就是我们要找的key，那么找到了，不再继续找第2个。

        枚举是在范围内查找所有可能解，不是找到就结束。

七.代码实现： 

include 
#include 
#define keyType int
typedef struct{
    keyType key;//设置关键值key
    //如果需要，还可以添加其他属性
}ElemType;
 
typedef struct{
    ElemType *elem;//存放查找表中数据元素的数组
    int length;//记录查找表中数据的总数量
}SSTable;
//创建查找表
void Create(SSTable **st,int length)
 {
    (*st)=(SSTable*)malloc(sizeof(SSTable));
    (*st)->length=length;
    (*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
    printf("输入表中的数据元素：\n");
    //根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
    for (int i=1; i<=length; i++) 
    {
        scanf("%d",&((*st)->elem[i].key));
    }
}
//查找表查找的功能函数，其中key为关键字
int Search_seq(SSTable *st,keyType key){
    st->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用
    int i=st->length;
    //从查找表的最后一个数据元素依次遍历，一直遍历到数组下标为0
    while (st->elem[i].key!=key) {
        i--;
    }
    //如果 i=0，说明查找失败；反之，返回的是含有关键字key的数据元素在查找表中的位置
    return i;
}
int main() {
    SSTable *st;
    Create(&st, 6);
    getchar();
    printf("请输入查找数据的关键字：\n");
    int key;
    scanf("%d",&key);
    int location=Search_seq(st, key);
    if (location==0) {
        printf("查找失败");
    }else{
        printf("数据在查找表中的位置为：%d",location);
    }
    return 0;
}