算法【线性表的查找-顺序查找】
线性表的查找-顺序查找
- 顺序查找
- 基本思想
- 应用范围
- 顺序表的表示
- 数据元素类型定义
- 查找算法示例分析
- 时间效率分析
- 顺序查找的特点
- 如何提高查找效率
顺序查找
基本思想
在表的多种结构定义方式中，线性表是最简单的一种。而顺序查找是线性表查找中最简单的一种。
顺序查找的基本思想:
从表的一端开始，顺序扫描线性表，将依次扫描到的结点关键字和给定的K值相比较，若当前扫描到的结点关键字与K相等，则查找成功，若扫描结束后，仍未找到关键字等于 K的结点，则查找失败。
应用范围
顺序表或者线性链式表表示的静态查找表；
表内元素之间无序；
顺序表的表示
数据元素类型定义
typedef struct{keyType key; //关键字域... //其他域
}ElemType;typedef struct{//顺序表结构类型定义ElemType *R; //表地址int length; //表长
}SSTable; //Sequential Search Table
SStable ST; //定义顺序表ST
查找算法示例分析
在顺序表ST中查找值为key的数据元素
从最后一个元素开始查找：
其他形式：
改进：
把待查找的关键字key存入表头（“哨兵”，“监视哨”）从后往前逐个比较，可以免去查找过程中每一步都要检测是否查找完毕，加快查找速度。
时间效率分析
顺序查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后或者目标数据不存在的情况下，比较的次数就会更多，并且也更为耗时。若数据量为 n，线性查找的时间复杂度便为 O(n)。
所以虽然顺序查找比较简单，且对表的结构没有任何要求，但是其查询效率较低，所以当n较大时不宜采用顺序查找。
时间复杂度: O(n)
查找成功时的平均查找长度，设表中各记录查找概率相等
ASL(n)=(1+2+ … +n)/=n(n+1)/2
空间复杂度: 一个辅助空间一O(1)；
顺序查找的特点
优点：算法简单，逻辑次数无要求，且不用的存储结构都适用
缺点：ASL太长，时间效率太低
需要注意的是，顺序查找是一种简单且广泛使用的查找方法，但它并不适合所有情况。例如，当线性表中的元素分布不均匀，或者元素按关键字有序排列时，顺序查找的性能可能会受到影响。
如何提高查找效率
1、记录的查找概率不相等时如何提高查找效率?
查找表存储记录原则：按查找概率高低存储:
1)查找概率越高，比较次数越少
2)查找概率越低，比较次数较多
2、记录的查找概率无法测定时如何提高查找效率?
方法：按查找概率动态调整记录顺序:
1)在每记录中设一不访问频度域
2)始终保持记录按非递增有序的次序排列
3)每次查找后均将刚查到的记录直接移至表头
参考资料：数据结构与算法基础-王卓老师