美文网首页
数据结构—查找

数据结构—查找

作者: 乳酸菌_c966 | 来源:发表于2019-04-12 08:57 被阅读0次

    给定一个值K,在含有n个记录的文件中进行搜索,寻找一个关键值等于K的记录,如找到则输出该记录,负责输出查找不成功的信息。

    静态查找表

    1、顺序查找
    用逐一比较的办法顺序查找关键字。

    • 性能分析:顺序查找平均查找长度为(n+1)/2,时间效率为O(n)
    • 优点:算法简单、适应面广,对查找表的结构没有要求,无论记录是否按关键字有序排列均可使用。
      缺点:在n值较大时,平均查找长度较大,查找效率较低。

    2、折半查找(二分查找)
    先给数据排序,形成有序表,把待查数据值与查找范围的中间元素值进行比较,会有四种情况出现:
    1)待查找数值与中间元素值相等,返回中间元素值的索引。
    2)待查找数值比中间元素值小,则以整个查找范围的前半部分作为新的查找范围,执行1),直到找到相等的值。
    3)待查找数值比中间元素值大,则以整个查找范围的后半部分作为新的查找范围,执行1),直到找到相等的值
    4)如果最后找不到相等的值,则返回错误提示信息。
    折半查找比顺序查找效率高
    3、分块查找
    又称索引顺序查找,是对顺序查找方法的一种改进,其性能介于顺序查找和折半查找之间。
    在分块查找过程中,首先把表分成若干块,每一块中的关键字不一定有序,但块之间是有序的,即后一块中所有记录的关键字均大于前一块中最大的关键字,还建立了一个索引表,索引表按关键字有序。


    分块查找示意图
    哈希表

    是根据关键码值(Key value)而直接进行访问的数据结构。由关键码的值决定数据的存储地址,以加快查找速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    优点:查找速度极快(O(1)),查找效率与元素个数n无关!

    相关文章

      网友评论

          本文标题:数据结构—查找

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