做哪个网站好,深圳购物网站建设,wordpress登录后页面,小程序api接口怎么对接线性表的查找-顺序查找 顺序查找基本思想应用范围顺序表的表示数据元素类型定义查找算法示例分析 时间效率分析顺序查找的特点如何提高查找效率 顺序查找
基本思想
在表的多种结构定义方式中#xff0c;线性表是最简单的一种。而顺序查找是线性表查找中最简单的一种。 顺序查… 线性表的查找-顺序查找 顺序查找基本思想应用范围顺序表的表示数据元素类型定义查找算法示例分析 时间效率分析顺序查找的特点如何提高查找效率 顺序查找
基本思想
在表的多种结构定义方式中线性表是最简单的一种。而顺序查找是线性表查找中最简单的一种。 顺序查找的基本思想: 从表的一端开始顺序扫描线性表将依次扫描到的结点关键字和给定的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)(12 … n)/n(n1)/2 空间复杂度: 一个辅助空间一O(1)
顺序查找的特点
优点算法简单逻辑次数无要求且不用的存储结构都适用 缺点ASL太长时间效率太低
需要注意的是顺序查找是一种简单且广泛使用的查找方法但它并不适合所有情况。例如当线性表中的元素分布不均匀或者元素按关键字有序排列时顺序查找的性能可能会受到影响。
如何提高查找效率
1、记录的查找概率不相等时如何提高查找效率? 查找表存储记录原则按查找概率高低存储: 1)查找概率越高比较次数越少 2)查找概率越低比较次数较多
2、记录的查找概率无法测定时如何提高查找效率? 方法按查找概率动态调整记录顺序: 1)在每记录中设一不访问频度域 2)始终保持记录按非递增有序的次序排列 3)每次查找后均将刚查到的记录直接移至表头
参考资料数据结构与算法基础-王卓老师
