美文网首页数据结构与算法
14 基本查找算法概述

14 基本查找算法概述

作者: GoFuncChan | 来源:发表于2020-02-18 15:07 被阅读0次

    基本查找算法概述

    在之前的文章中已经数据结构的基本知识,包括线性表、哈希表、树、图结构,并讨论了这些结构的存储映像,以及定义在其上的相应运算,并且我们概述了几种排序算法。除了基本排序算法外,我们接下来了解几种基于基本数据结构的查找算法,包括基于线性表的查找、基于树的查找、基于哈希的查找等。

    在同样的数据结构中,我们通过前面介绍的线性结构、树和图保存数据以后,在使用时也需要通过查找来调用这个数据。由此可见,查找是数据结构算法中必须学习的内容之一。
    在学习查找之前,需要先理解如下几个概念:

    (1)列表:是由同一类型的数据元素或记录构成的集合,可以使用任意数据结构实现。
    (2)关键字:是数据元素的某个数据项的值,能够标识列表中的一个或一组数据元素。如果一个关键字能够唯一标识列表中的一个数据元素,则称其为主关键字,否则称为次关键字。当数据元素中仅有一个数据项时,数据元素的值就是关键字。
    (3)查找:根据指定的关键字的值,在某个列表中查找与关键字值相同的数据元素,并返回该数据元素在列表中的位置。如果找到相应的数据元素,则查找是成功的,否则查找就是失败的,此时应返回空地址及失败信息,并可根据要求插入这个不存在的数据元素。显然,查找算法中涉及了如下3类参量。

    ①查找对象K,即具体找什么。
    ②查找范围L,即在什么地方找。
    ③K在L中的位置,即查找的结果是什么。

    其中①、②是输入参量,③是输出参量。在函数中不能没有输入参量,可以使用函数返回值来表示输出参量。

    (4)平均查找长度:为确定数据元素在列表中的位置,需要将关键字个数的期望值和指定值进行比较,这个期望值被称为查找算法在查找成功时的平均查找长度。如果列表的长度为n,查找成功时的平均查找长度为:

    平均查找长度.png

    上述格式中各个参数的具体说明如下所示:

    Pi :表示查找列表中第i个数据元素的概率。
    Ci :当找到列表中第i个数据元素时,已经进行过的关键字比较次数。因为查找算法的基本运算是在关键字之间的比较操作,所以可用平均查找长度来衡量查找算法的性能。
    有两大类查找的基本方法,分别是比较式查找法和计算式查找法。其中,比较式查找法又可以分为基于线性表的查找法和基于树的查找法,通常将计算式查找法称为哈希(Hash)查找法。

    查找算法分类

    从数据结构方面看,多数查找算法是基于线性表的查找,而基于线性表的查找也可以用多种思想实现,
    如暴力枚举思想的顺序查找算法,也有分治思想的分块查找算法,当然也有递归和迭代思想组合实现的折半查找算法,插值查找算法、还有斐波那契查找算法。

    而基于二叉树数据结构的还有树表查找算法,我们在讲二叉树数据结构时已经了解并实现了,具体可以查看树的节点查找。此外还有基于哈希表的哈希查找算法,我们在讲数据结构哈希表时已经了解并实现了,具体可以查看哈希关键字的查找。在讲解图数据结构时,我们也顺带实现了深度优先搜索法和广度优先搜索法。以上这些查找方法都是基于数据结构,这里就不再赘述。

    相关文章

      网友评论

        本文标题:14 基本查找算法概述

        本文链接:https://www.haomeiwen.com/subject/ihrgfhtx.html