【数据结构】静态查找之顺序查找

发布时间：2020-12-15 06:00:07 所属栏目：安全来源：网络整理

导读：【思想】从表的最后一个数据元素位置开始，从后往前依次将各个位置上的数据元素的键值与给定值比较。若某个位置上的数据元素的键值与给定值相等，则查找成功，并返回该位置作为结果；反之，若查找至第一个元素，所有数据元素的键值均与给定值不等，则查找不

【思想】

从表的最后一个数据元素位置开始，从后往前依次将各个位置上的数据元素的键值与给定值比较。若某个位置上的数据元素的键值与给定值相等，则查找成功，并返回该位置作为结果；反之，若查找至第一个元素，所有数据元素的键值均与给定值不等，则查找不成功。

【ASL】

ASL指的是平均查找长度，是指为找到数据元素在查找表中的位置，与给定值进行比较的键值个数的期望值。

1、在等概率查找的情况下，顺序表查找成功的平均查找长度为

ASL= ∑P_iC_i = （n+1）/2，（i=1,2，...n），

（其中n为表长，P_i为查找表中第i个元素的概率 ∑ P_iC_i=1 ，C_i为找到该元素时，曾和给定值比较过的关键字的次数）

2、若给定值key不在表中，则需要（n+1）次查找比较，才可确定查找失败。

【时间复杂度】

时间复杂度为O(n)

【优缺点】

（1）优点：①算法简单②适用性广泛（对表的结构无任何要求）

（2）缺点：查找效率低

【算法描述】

int SearchSqTable (SqTable T,KeyType key)
{
T.elem[0].key=key;  //设置岗哨
i=T.n  //设置比较位置初值
while(T.elem[i].key !=key)
i--;  //未找到时，修改比较位置继续查找
return i;  //若找到，则返回当前位置
}

注：上例是从后往前找，所以i初值为顺序表表长。若从前往后找，则i初值为0.