C语言顺序查找算法介绍及示例

C语言顺序查找算法介绍及示例攻略

什么是顺序查找算法？

顺序查找算法，也叫线性查找算法，是一种最基本的查找算法。是通过一次次的比较目标值与列表中的每一个元素来实现查找的。

顺序查找算法的实现方法

实现顺序查找，需要下面两个步骤：

• 从列表中的第一个元素开始，逐个与目标值进行比较，直到查找到目标值，或者搜索完整个列表。
• 如果在列表中找到了目标值，返回其在列表中的位置。如果没有找到，则返回 -1，表示查找失败。

具体实现方法可以参考下面的C语言代码例子：

int SequentialSearch(int list[], int length, int target){
    for(int i = 0; i < length; i++){
        if(list[i] == target){
            return i;
        }
    }
    return -1;
}

顺序查找算法实现比较简单，时间复杂度为 O(n)。

顺序查找算法示例

示例1

假设我们有一个整型列表，需要查找其中是否存在一个元素值为35的元素。代码实现如下：

#include <stdio.h>

int SequentialSearch(int list[], int length, int target){
    for(int i = 0; i < length; i++){
        if(list[i] == target){
            return i;
        }
    }
    return -1;
}

int main(){
    int length = 10;
    int list[length] = {2, 4, 6, 8, 10, 12, 35, 67, 89, 100};
    int target = 35;
    int index = SequentialSearch(list, length, target);
    if(index == -1){
        printf("未找到元素%d", target);
    }
    else{
        printf("元素%d在列表中的位置为%d", target, index);
    }
    return 0;
}

上面代码输出结果为：元素35在列表中的位置为6。

示例2

假设我们有一个字符串列表，需要查找其中是否存在一个元素值为“world”的元素。代码实现如下：

#include <stdio.h>
#include <string.h>

int SequentialSearch(char list[][20], int length, char target[]){
    for(int i = 0; i < length; i++){
        if(strcmp(list[i], target) == 0){
            return i;
        }
    }
    return -1;
}

int main(){
    int length = 4;
    char list[][20] = {"hello", "world", "my", "friend"};
    char target[] = "world";
    int index = SequentialSearch(list, length, target);
    if(index == -1){
        printf("未找到元素%s", target);
    }
    else{
        printf("元素%s在列表中的位置为%d", target, index);
    }
    return 0;
}

上面代码输出结果为：元素world在列表中的位置为1。

总结

顺序查找算法虽然时间复杂度比其他查找算法要高，但是相对来说实现简单。使用场景包括数据量较小的情况下，对查询效率要求不高的场合。