9.2 静态查找表

01

顺序表的查找

1、顺序查找(Sequential Search)的查找过程为:从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录。

2、反之若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录,查找不成功。

3、衡量一个算法的好坏的量度有3条:时间复杂度、空间复杂度和算法的其他性能。

4、对于查找算法来说,通常只需要一个或几个辅助空间。

5、为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。

6、顺序查找的缺点是平均查找长度较大,查找效率较低。然而,它有很大的优点是:算法简单且适应面广。

02

有序表的查找

1、以有序表表示静态查找表时,Search函数可用折半查找来实现。

2、折半查找(Binary Search)的查找过程是:先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。

03

静态树表的查找

1、称PH值取最小的二叉树为静态最优查找树(Static Optimal Search Tree)。

2、构造一棵二叉树,使这棵二叉树的带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小,称这类二叉树为次优查找树。

04

索引顺序表的查找

1、若以索引顺序表表示静态查找表,则Search函数可用分块查找来实现。

2、分块查找又称索引顺序查找,这是顺序查找的一种改进方法。

如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

有时候,正是那些意想不到之人,成就了无人能成之事。

本文分享自微信公众号 - C语言入门到精通(gh_780327809188),作者:闫小林

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 9.1 查找

    1、查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合。

    闫小林
  • 数据结构 | 每日一练(41)

    ——老子

    闫小林
  • 数据结构 | 每日一练(66)

    ——老子

    闫小林
  • Linux中find命令用法全汇总,看完就没有不会用的!

    糖豆贴心提醒,本文阅读时间7分钟 Linux 查找命令是Linux系统中最重要和最常用的命令之一。查找用于根据与参数匹配的文件指定的条件来搜索和查找文件和目录...

    小小科
  • 文件查找

    文件查找:locate, find 实时查找:遍历所有文件进行条件匹配 非实时查找:根据索引查找 locate...

    零月
  • 算法与数据结构(九) 查找表的顺序查找、折半查找、插值查找以及Fibonacci查找(Swift版)

    今天这篇博客就聊聊几种常见的查找算法,当然本篇博客只是涉及了部分查找算法,接下来的几篇博客中都将会介绍关于查找的相关内容。本篇博客主要介绍查找表的顺序查找、折半...

    lizelu
  • Linux中find命令用法全汇总,看完就没有不会用的!

    Linux 查找命令是Linux系统中最重要和最常用的命令之一。查找用于根据与参数匹配的文件指定的条件来搜索和查找文件和目录列表的命令。查找可以在各种条件下使用...

    小小科
  • 正则表达式-6.查找方向

    如果,需要一个模式,它包含的匹配本身并不返回,而是用于确认正确的匹配位置,它并不是匹配结果的一部分。这时就需要进行“前后查找”(一般而言,前后查找模式是相对于查...

    悠扬前奏
  • Visual Studio 2008 每日提示(八)

    #071、给所有快速查询的结果标记上书签 原文链接:Did you know… You can bookmark all of your Quick Find...

    Jianbo
  • 查找一 线性表的查找

    查找的基本概念 什么是查找? 查找是根据给定的某个值,在表中确定一个关键字的值等于给定值的记录或数据元素。 查找算法的分类 若在查找的同时对表记录做修改操作(...

    静默虚空

扫码关注云+社区

领取腾讯云代金券