【10.2】检索--线性表的检索

一、顺序检索

  • 针对线性表里的所有记录,逐个进行关键 码和给定值的比较

    • 若某个记录的关键码和给定值比较相等,则 检索成功
    • 否则检索失败(找遍了仍找不到)
  • 存储:可以顺序、链接

  • 排序要求:无

“监视哨”顺序检索算法

顺序检索性能分析

检索成功:假设检索每个关键码等概率 Pi = 1/n

检索失败:假设检索失败时都需要比较 n+1 次 (设置了一个监视哨)

顺序检索平均检索长度

假设检索成功的概率为 p,检索失败的概率为 q=(1-p)

顺序检索优缺点

  • 优点:插入元素可以直接加在表尾 Θ(1)
  • 缺点:检索时间太长 Θ(n)

二、 二分检索

  • 将任一元素 dataList[i] .Key 与给定值 K 比较, 三种情况:

    • (1)Key = K,检索成功,返回 dataList[i]
    • (2)Key > K,若有则一定排在 dataList[i]前
    • (3)Key < K,若右则一定排在 dataList[i]后
  • 缩小进一步检索的区间

二分法检索算法

二分法检索性能分析

三、 分块检索

  • “按块有序”

    • 设线性表中共有 n 个数据元素,将表分成 b 块
    • 前一块最大关键码必须小于后一块最小关键码
    • 每一块中的关键码不一定有序
  • 顺序与二分法的折衷

    • 既有较快的检索
    • 又有较灵活的更改

分块检索——索引顺序结构

分块检索性能分析

分块检索为两级检索:

  • 先在索引表中确定待查元素所在的块,ASLb * 然后在块内检索待查的元素,ASLw

  • 假设在索引表中用顺序检索,在块内也用顺序检索

当 n=10,000 时:

  • 顺序检索 5,000 次
  • 二分法检索 14 次
  • 分块检索 100 次

分块检索的优缺点

  • 优点:

    • 插入、删除相对较易
    • 没有大量记录移动
  • 缺点:

    • 增加一个辅助数组的存储空间
    • 初始线性表分块排序
    • 当大量插入/删除时,或结点分布不均匀时, 速度下降

四、思考

  • 试比较顺序检索、二分检索和分块检索的 优缺点。 这几种检索方法适合的应用场景分别是什 么?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学