常用的7大查找算法之一：顺序查找（基本思想+具体流程+复杂度分析）

2017-04-23 17:15 阅读 5,023 次 评论 0 条

1.查找算法概述

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。

（1）查找定义

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

（2）查找算法分类

1）静态查找和动态查找

注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2）无序查找和有序查找

无序查找：被查找数列有序无序均可；

有序查找：被查找数列必须为有序数列。

（3）查找算法分析

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。

Pi：查找表中第i个数据元素的概率。

Ci：找到第i个数据元素时已经比较过的次数。

 

2.顺序查找

（1）方法说明

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

（2）基本思想

顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

（3）复杂度分析

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;当查找不成功时，需要n+1次比较，时间复杂度为O(n);所以，顺序查找的时间复杂度为O(n)。

（4）顺序查找C语言源代码

顺序查找算法C/C++源代码
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 算法君：一个专业的算法学习分享网站
* 算法君：专业分享--数据剖析--算法精解
* 算法君：http://www.suanfajun.com
*/
 
 
//基本思路：用顺序结构存储数据（数组、链表），从前到后依次查询目标值，
#include<stdio.h>
 
// 顺序查找--如果发现则返回查找到的值，否则返回0.
int FindBySeq(int *ListSeq, int ListLength, int KeyData)
{
    int tmp = 0;
    int length = ListLength;
    for (int i = 0; i < ListLength; i++)
    {
        if (ListSeq[i] == KeyData)
            return i;
    }
    return 0;
}
 
int main()
{
    int TestData[5] = { 34, 35, 26, 89, 56 };
    int retData = FindBySeq(TestData, 5, 89);
    printf("retData: %d\n", retData);
    return 0;
}

（5）顺序查找C++源代码

顺序查找算法C++源代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 算法君：一个专业的算法学习分享网站
* 算法君：专业分享--数据剖析--算法精解
* 算法君：http://www.suanfajun.com
*/
 
 
#include<iostream>
using namespace
std; #define M 10  
 
//定义【查找函数】 定义形参为实型数组a[]（被查找的数组） ， 实型数x（需要查找的数） ，实型数n（数组内元素的个数）  
int search(int a[ ],int x,int n)                  
{  int p=n;  
    while(p>=0&&a[p]!=x) //依次查找  
    {  
        p--;
    }  
    return p;   //查找成功，则返回给【主函数】下标  
}  
 
void main( )                                
{  
    int array[ ]={1,45,85,12,36,2,49,6,13,8};     //初始化查找数组  
    int i,p,x;  cout<< "输入要查找的数：";    
    cin>>x;      
 
    p=search(array,x,M);   //调用【查找函数】，同时接受返回值  
    cout<< "原始数组：" <<endl;  
    for(i=0;i<M;i++)  
        cout<< array[i] <<"\t";  
    if(p>=0)
        cout<< "查找成功!该数的下标为：" << ++p <<endl;  
    else      
        cout<< "未找到该数!" <<endl;  
}

 

 

版权声明：本文著作权归原作者所有，欢迎分享本文，谢谢支持！
转载请注明：常用的7大查找算法之一：顺序查找（基本思想+具体流程+复杂度分析） | 算法君
分类：数据结构 标签：,

发表评论


表情