【数据结构与算法】【查找】顺序查找（线性查找）的代码实现

秒速五厘米 2022-08-13 15:46 220阅读 0赞

**顺序查找**：也称为 **线性查找**，是最基本的查找技术。查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找失败。

代码实现（基本算法和优化算法）：

// Filename: sequential_search.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "public.h"
    
    // 顺序查找（线性查找）
    // a[n]为待查找数组，a[0]不使用，n为数组长度（不包含a[0]）
    // 查找成功，则返回key所在的地址；查找失败，则返回0
    int SequentialSearch(int a[], int n, int key)
    {
        int i;
        for (i = 1; i <= n; i++)
        {
            if (a[i] == key) return i;
        }
        return 0;
    }
    
    // 顺序查找（线性查找）优化算法（设置哨兵a[0]），减少比较次数
    // a[n]为待查找数组，a[0]不使用，n为数组长度（不包含a[0]）
    // 查找成功，则返回key所在的地址；查找失败，则返回0
    int SequentialSearch2(int a[], int n, int key)
    {
        int i = n;
        a[0] = key;
        while (a[i] != key) i--;
        return i;
    }
    
    // 顺序查找（线性查找）主函数
    int SequentialSearchMain()
    {
        int value;
        int retval;
        int arr[12] = {0xFF, 8, 4, 3, 5, 9, 7, 6, 1, 0, 2, -1};
    
        printf("顺序查找（线性查找）演示(a[0]未使用，不参与排序): \n");
    
        printf("静态查找表数据：\n");
        PrintArray(arr, sizeof(arr) / sizeof(int));
        printf("\n");
    
        // 查找元素
        printf("请输入要查找的数据: \n");
        scanf("%d", &value);
        //retval = SequentialSearch(arr, 10, value);
        retval = SequentialSearch2(arr, 10, value);
    
        if (0 == retval)
        {
            printf("查找失败!\n");
        }
        else
        {
            printf("查找成功，元素所在位置: %d.", retval);
        }
    
        return 0;
    }