学到这里，相信大家对基本的数据结构都有了一定的认识，当然，我们还有一些数据结构没有讲解，比如：图、广义表、数组等。这些内容我都会在后续进行更新。

不过这段时间，我主要还是先介绍一下查找和排序算法，在这些算法中如果涉及到还未介绍的数据结构，我就会对该数据结构进行介绍。

本篇文章将介绍顺序查找算法。

@[toc]

何为顺序查找？

看到这个算法的名字不难理解，它是一种按照序列原有顺序对数组进行遍历比较查询的基本查找算法。

该算法其实非常简单，大家肯定都会写，若是想查找一个序列中的某个元素值，我们只需遍历该序列，依次与序列中的每一个元素进行比较即可。

先来构造一个查找表：

#include <stdio.h>
#include <malloc.h>

#define LENGTH 10

typedef struct{
   
   
    int key;    //数据域
    //...还可以指定数据的其它信息
}ElemType;

typedef struct{
   
   
    ElemType *elem;
    int length;
}SSTable;

SSTable CreateTable(){
   
   
    SSTable st;
    st.length = LENGTH;
    st.elem = (ElemType*) malloc(sizeof(ElemType) * (LENGTH + 1));

    //为元素赋值
    st.elem[1].key = 1;
    st.elem[2].key = 2;
    st.elem[3].key = 3;
    st.elem[4].key = 4;
    st.elem[5].key = 5;
    st.elem[6].key = 6;
    st.elem[7].key = 7;
    st.elem[8].key = 8;
    st.elem[9].key = 9;
    st.elem[10].key = 10;

    return st;
}

数组的元素值我就直接写死了，大家也可以利用循环来自己输入。

对于初学者，这里的很多地方他们可能会有些疑惑，比如：为什么在申请内存的时候要多申请一个空间；在为数组赋值的时候为什么从下标为1的位置开始，这些我都放到后面解释。

先来看看查找算法的实现：

//顺序查找算法
int SequentialSearch(SSTable st,int key){
   
   
    int i;
    for(i = 1;i <= st.length;++i){
   
   
        if(st.elem[i].key == key){
   
   
            return i;
        }
    }
    return 0;
}

算法非常简单，遍历依次比较即可，若找到则直接返回当前下标；若没找到，则返回0。

算法改进

刚才虽然实现了顺序查找算法，但有些欠缺，因为每次循环都需要进行两次比较：比较下标是否越界；比较当前值是否等于待查找值。

当数据量非常庞大的时候，显然效率就比较低下了，那么有没有一种办法能够让它只比较一次就能够实现查找呢？这就是刚才为什么要多申请一个内存空间的原因了。

原数组中共有10个有效元素，但是在申请空间时要去申请11个内存空间，并且赋值要从下标为1的位置开始，目的就是空出下标为0的位置，如下图：

空出这个位置做什么呢？做一个监视哨，即：这个下标为0的位置要起一个哨兵的作用，举个例子：

我现在要查找值为8的元素，那么在查找开始之前，我先将元素值8放入下标为0的位置作为哨兵：

此时查找就很容易了，同样地，先遍历序列，但是无需比较下标是否越界了，我们直接让当前元素值与哨兵进行比较，若找到，则返回当前下标；
若当前序列中没有哨兵位置的元素值，则从下标为1开始到最后一个元素都将找不到待查找元素，此时一定会在哨兵位置找到，这个时候也直接返回当前下标即可，0则代表未找到。

带哨兵的顺序查找算法实现如下：

//带哨兵的顺序查找算法
int SequentialSearch(SSTable st,int key){
   
   
    int i;
    //设置哨兵
    st.elem[0].key = key;
    for(i = st.length;st.elem[i].key != key;--i);
    return i;
}

记得从数组最后一个元素开始遍历，这样如果在哨兵位置遍历结束，就证明查找失败。

时间效率分析

下面来分析一下带哨兵的顺序查找算法的时间效率。

若要在该序列中查找值为10的元素，则只需进行一次比较就查找到了；
若要在该序列中查找值为9的元素，则需进行两次比较才能找到，以此类推。

查找次数是受查找的值影响的，若要查找第i个元素，则需比较length + 1 - i次；查找失败则需比较length + 1次。

假设表中各记录的查找概率相同，则其查找的平均查找长度为：
$$ASL_s = (1 + 2 + ... + length) / length = (n + 1) / 2$$
则其时间复杂度为O(n)。

顺序查找算法的优点是：

算法简单，逻辑次序无要求，且不同存储结构均适用

缺点：

平均查找长度太长，时间效率太低