跳转至

AB34-查找顺序表中第一个值为x的元素的位置

代码实现

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 查找顺序表中第一个值为x的元素的位置
 * @param L 顺序表（传值调用，不修改原表）
 * @param x 要查找的目标值
 * @return 元素位置（从1开始计数），未找到返回0
 */
int find_L(Sqlist L, int x) {
    // 从第一个元素开始逐个查找
    for (int i = 0; i < L.length; i++) {
        // 比较当前元素与目标值
        if (L.data[i] == x) {
            printf("查找成功\n");  // 找到目标元素
            return i + 1;          // 返回位置（从1开始计数）
        }
    }

    // 遍历完整个顺序表都未找到目标元素
    printf("查找失败\n");
    return 0;  // 0表示未找到（约定俗成的返回值）
}

算法执行流程图

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
顺序表：[3][7][2][9][7][1]  查找值x=9

i=0: data[0]=3 ≠ 9  继续查找
     ↑
i=1: data[1]=7 ≠ 9  继续查找
        ↑
i=2: data[2]=2 ≠ 9  继续查找
           ↑
i=3: data[3]=9 = 9  查找成功！返回位置4
              ↑

复杂度分析

时间复杂度：O(n)

  • 最好情况：O(1) - 目标元素在第一个位置
  • 最坏情况：O(n) - 目标元素在最后一个位置或不存在
  • 平均情况：O(n) - 平均需要比较(n+1)/2次
  • 总体：O(n)

空间复杂度：O(1)

  • 分析过程：
  • 只使用了常数个额外变量：i
  • 没有使用额外的数据结构
  • 空间复杂度为 O(1)

优化版本：去除不必要的打印语句，提高执行效率

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
/**
 * 优化版本：去除不必要的打印语句，提高执行效率
 */
int find_L_Optimized(Sqlist L, int x) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == x) {
            return i + 1;  // 找到直接返回，不打印信息
        }
    }
    return 0;  // 未找到返回0
}

算法特点

优点： - 实现简单，逻辑清晰 - 适用于无序顺序表 - 空间效率高

缺点： - 时间复杂度较高O(n) - 对于有序表没有利用有序性优化

核心思想： 线性查找，逐个比较元素值与目标值，找到第一个匹配的元素即返回其位置。