AB37-删除顺序表中第一个值为x的元素

代码实现

/**
 * 删除顺序表中第一个值为x的元素
 * @param L 指向顺序表的指针
 * @param x 要删除的目标值
 * @return 删除成功返回true，未找到返回false
 */
bool del_x(Sqlist *L, int x) {
    // 遍历顺序表查找目标元素
    for (int i = 0; i < L->length; i++) {
        // 找到第一个值为x的元素
        if (L->data[i] == x) {
            // 将该位置之后的所有元素前移一位（覆盖要删除的元素）
            for (int j = i + 1; j < L->length; j++) {
                L->data[j - 1] = L->data[j];
            }

            // 更新顺序表长度
            L->length--;

            // 删除成功，返回true
            return true;
        }
    }

    // 遍历完整个顺序表都未找到目标元素，删除失败
    return false;
}

算法执行流程图解

删除过程示例：

原顺序表：[3][7][2][9][2][5]  (length=6)  删除x=2

查找过程：
i=0: data[0]=3 ≠ 2  继续查找
i=1: data[1]=7 ≠ 2  继续查找
i=2: data[2]=2 = 2  找到目标元素！

删除操作：
位置i=2的元素2需要被删除

元素前移过程：
j=3: data[2] = data[3] = 9  → [3][7][9][9][2][5]
j=4: data[3] = data[4] = 2  → [3][7][9][2][2][5]  
j=5: data[4] = data[5] = 5  → [3][7][9][2][5][5]

更新长度：
length = 5

最终结果：[3][7][9][2][5]  (length=5)

前移操作详细图解

删除前：[A][B][C][D][E][F]
         0  1  2  3  4  5
            ↑
          删除C

前移过程：
j=3: data[2] = data[3]  → [A][B][D][D][E][F]
j=4: data[3] = data[4]  → [A][B][D][E][E][F] 
j=5: data[4] = data[5]  → [A][B][D][E][F][F]

结果：[A][B][D][E][F][F]  length=5
                   ↑
               新的有效范围

复杂度分析

时间复杂度：O(n)

• 查找时间：
• 最好情况：O(1) - 目标元素在第一个位置
• 最坏情况：O(n) - 目标元素在最后一个位置或不存在

• 平均情况：O(n)

• 前移时间：

• 最好情况：O(1) - 删除最后一个元素（无需前移）
• 最坏情况：O(n) - 删除第一个元素（需要前移n-1个元素）

• 平均情况：O(n)

• 总体时间复杂度：O(n)

空间复杂度：O(1)

• 只使用了常数个额外变量：i、j
• 原地操作，无需额外存储空间
• 空间复杂度：O(1)

优化版本：添加边界检查和更清晰的逻辑

/**
 * 优化版本：添加边界检查和更清晰的逻辑
 */
bool del_x_Optimized(Sqlist *L, int x) {
    // 边界条件检查
    if (L == NULL || L->length <= 0) {
        return false;
    }

    // 查找目标元素
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == x) {
            // 元素前移（从后往前移动，减少赋值次数）
            for (int j = i; j < L->length - 1; j++) {
                L->data[j] = L->data[j + 1];
            }

            L->length--;
            return true;
        }
    }

    return false;  // 未找到目标元素
}

算法变体：删除所有值为x的元素

/**
 * 删除顺序表中所有值为x的元素
 * @param L 指向顺序表的指针
 * @param x 要删除的目标值
 * @return 删除的元素个数
 */
int del_all_x(Sqlist *L, int x) {
    int count = 0;  // 记录删除的元素个数
    int k = 0;      // 新顺序表的下标

    // 遍历原顺序表
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] != x) {
            // 不是要删除的元素，保留在新顺序表中
            L->data[k] = L->data[i];
            k++;
        } else {
            // 是要删除的元素，计数器加1
            count++;
        }
    }

    L->length = k;  // 更新顺序表长度
    return count;   // 返回删除的元素个数
}

算法特点

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

缺点： - 时间复杂度较高O(n) - 只删除第一个匹配元素

核心思想： 先查找目标元素位置，然后将该位置之后的所有元素整体前移一位，实现删除效果。

注意点： - 前移操作要从前往后进行，避免数据覆盖 - 及时更新顺序表长度 - 正确处理未找到目标元素的情况