美文网首页C++数据结构和算法分析程序员
小朋友学数据结构(5):顺序查找法

小朋友学数据结构(5):顺序查找法

作者: 海天一树X | 来源:发表于2018-05-09 16:51 被阅读40次

    查找是最常见的数据操作之一,也是数据结构的核心运算之一,其重要性不言而喻。
    顺序查找是最简单的查找策略,对于小规模的数据,顺序查找是个不错的选择。

    (一)基本思想

    从数据的第一个元素开始,依次比较,直到找到目标数据或查找失败。
    1 从表中的第一个元素开始,依次与关键字比较。
    2 若某个元素匹配关键字,则查找成功。
    3 若查找到最后一个元素还未匹配关键字,则查找失败。

    1.png

    (二)时间复杂度

    顺序查找平均关键字匹配次数为表长的一半,其时间复杂度为O(n)。

    (三)顺序查找的优缺点

    优点:对于待查的结构没有任何要求,而且算法非常简单,当待查表中的记录个数较少时,采用顺序查找较好,顺序查找既适用于顺序存储结构,又使用于链接存储结构。
    缺点:时间复杂度较大,数据规模较大时效率较低。

    (四)C语言实现

    #include <stdio.h>
    
    int seq_search(int array[], int n, int key)
    {
        int i;
        for(i = 0; i < n; i++)
        {
            if(key == array[i])
            {
                return i;   //查找成功
            }   
        }
        return -1;          //查找失败
    }
    
    int main()
    {
        int array[] = {3, 5, 2, 7, 6};
        int num = 7;
        int len = sizeof(array) / sizeof(int);
        int index = seq_search(array, len, num);
        if(-1 != index)
        {
            printf("%d的位置为%d\n", num, index);
        }
        else
        {
            printf("没有找到此元素");
        }
    
        return 0;
    }
    

    运行结果:

    7的位置为3
    

    TopCoder & Codeforces & AtCoder交流QQ群:648202993
    更多内容请关注微信公众号


    wechat_public_header.jpg

    相关文章

      网友评论

        本文标题:小朋友学数据结构(5):顺序查找法

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