(55)王道数据结构-顺序查找

基本概念

顺序查找又称线性查找，主要用于在线性表中进行查找。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的顺序表的顺序查找。

代码逻辑

typedef struct { //查找表的数据结构
    ElemType *elem; //动态数组基址，建表时按实际长度分配，0号单元留空
    Int TableLen; //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST, ElemType key) {
//在顺序表ST中顺序查找关键字为key的元素。若找到则返回该元素在表中的位置
    for(i=ST.TableLen; ST.elem[i]!=key; --i); //从后往前找
    return i; //若表中不存在关键字为key的元素，将查找到i为0时退出for循环
}

引入哨兵

typedef struct { //查找表的数据结构（顺序表）
    ElemType *elem; //动态数组基址，建表时按实际长度分配，0号单元留空
    Int TableLen; //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST, ElemType key) {
//在顺序表ST中顺序查找关键字为key的元素。若找到则返回该元素在表中的位置
    ST.elem[0]=key; //哨兵
    int i;
    for(i=ST.TableLen; ST.elem[i]!=key; --i); //从后往前找
    return i; //若表中不存在关键字为key的元素，将查找到i为0时退出for循环
}

上述算法中，将ST.elem[0]称为”哨兵”。引入它的目的是使得Search_Seq内的循环不必判断数组是否会越界，因为满足i==0时，循环一定会跳出。需要说明的是，在程序中引入”哨兵”并不是这个算法独有的。引入”哨兵”可以避免很多不必要的判断语句，从而提高程序效果。

效率分析

$$
ASL_T = \frac{1+2+3+…+n}{n} = \frac{n+1}{2}
$$

$$
ASL_F = n + 1
$$
通常，查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列。

综上所述，顺序查找的缺点是当n较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键码有序，均可应用。同时还需注意，对线性的链表只能进行顺序查找。

算法优化

优化是针对有序表的。若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

假设表L是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为key，当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+ 1个元素对应的关键字大于key，这时就可返回查找失败的信息，因为第i个元素之后的元素的关键字均大于key，所以表中不存在关键字为key的元素。

$$
ASL_F = \frac{1+2+3+…+n+n}{n+1} = \frac{n}{2} + \frac{n}{n+1}
$$
在有序表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数。