6.2 顺序查找

6.2.1 顺序查找的定义

顺序查找，又叫线性查找。

6.2.2 顺序查找的实现

算法思想：从头挨个查找。

普通代码：

//查找表的数据结构（动态分配的顺序表）
typedef struct{
    ElemType *elem;      //指向“动态”分配的数组的指针
    int TableLen;        //查找表的当前长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST, ElemType key){
    int i;
    for(i=0; i<ST.TableLen && ST.elem[i]!=key; ++i){//从前往后找，判断是否越界
        return i==ST.TableLen? -1 : i;   //查找成功，则返回元素下标；查找失败，则返回-1
    }
}

有哨兵的代码：不用判断越界，效率更高

//查找表的数据结构（动态分配的顺序表）
typedef struct{
    ElemType *elem;      //指向“动态”分配的数组的指针
    int TableLen;        //查找表的当前长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST, ElemType key){
    ST.elem[0] = key;    //设置"哨兵"
    int i;
    for(i=ST.TableLen; ST.elem[i]!=key; --i){//从后往前找，不用判断越界
        return i;        //查找成功，则返回元素下标；查找失败，则返回0
    }
}

6.2.3 查找效率分析

查找成功：$ASL_{成功}=\frac{1}{n}+\frac{2}{n}+\cdots+\frac{n}{n}=\frac{n+1}{2}$，时间复杂度=$O(n)$

查找成功：$ASL_{失败}=n+1$，时间复杂度=$O(n)$

则，时间复杂度=$O(n)$

6.2.4 顺序查找的优化

若查找表是有序表，可优化查找失败的ASL

若查找元素的查找概率不同，将概率高的放前面排序，可优化查找成功的ASL