AB38-删除顺序表中所有值为x的元素

建议优化版本

代码实现

/**
 * 删除顺序表中所有值为x的元素
 * @param L 指向顺序表的指针
 * @param x 要删除的目标值
 * @return 有元素被删除返回true，无元素被删除返回false
 */
bool del(Sqlist *L, int x) {
    // k指向新顺序表的当前位置（重构后顺序表的下标）
    int k = 0;

    // 遍历原顺序表，重构新的顺序表
    for (int i = 0; i < L->length; i++) {
        // 如果当前元素不是要删除的元素
        if (L->data[i] != x) {
            // 将该元素复制到新顺序表的位置
            L->data[k] = L->data[i];
            k++;  // 新顺序表位置后移
        }
        // 如果当前元素是要删除的元素，则跳过不复制
    }

    // 判断是否有元素被删除
    if (L->length == k) {
        // 长度未变，说明没有元素被删除
        return false;
    } else {
        // 长度改变，说明有元素被删除
        L->length = k;  // 更新顺序表长度
        return true;
    }
}

算法执行流程图解

删除过程示例：

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

执行过程：
i=0: data[0]=3 ≠ 2 → data[0]=3, k=1
i=1: data[1]=2 = 2 → 跳过
i=2: data[2]=7 ≠ 2 → data[1]=7, k=2  
i=3: data[3]=2 = 2 → 跳过
i=4: data[4]=9 ≠ 2 → data[2]=9, k=3
i=5: data[5]=2 = 2 → 跳过
i=6: data[6]=5 ≠ 2 → data[3]=5, k=4

结果分析：
原长度：7
新长度：4
有元素被删除

最终结果：[3][7][9][5][9][2][5]  (length=4)
           ↑     ↑
        有效数据  无效数据（但不影响使用）

算法重构过程可视化

原顺序表：[3][2][7][2][9][2][5]
          0  1  2  3  4  5  6

重构过程：
k=0: 检查[3]≠2 → [3][2][7][2][9][2][5]  k=1
                    ↑
k=1: 检查[2]=2 →  [3][2][7][2][9][2][5]  k=1 (跳过)
                       ↑
k=1: 检查[7]≠2 → [3][7][7][2][9][2][5]  k=2
                          ↑
k=2: 检查[2]=2 →  [3][7][7][2][9][2][5]  k=2 (跳过)
                             ↑
k=2: 检查[9]≠2 → [3][7][9][2][9][2][5]  k=3
                                ↑
k=3: 检查[2]=2 →  [3][7][9][2][9][2][5]  k=3 (跳过)
                                   ↑
k=3: 检查[5]≠2 → [3][7][9][5][9][2][5]  k=4
                                      ↑

最终有效部分：[3][7][9][5]  (length=4)

复杂度分析

时间复杂度：O(n)

• 遍历时间：需要遍历整个顺序表一次，O(n)
• 复制时间：最多复制n个元素，O(n)
• 总体时间复杂度：O(n)

空间复杂度：O(1)

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

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

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

    int k = 0;  // 新顺序表的下标

    // 重构顺序表：保留非x元素
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] != x) {
            if (k != i) {  // 避免不必要的自复制
                L->data[k++] = L->data[i];
            }
        }
    }

    // 判断是否有元素被删除并更新长度
    if (L->length != k) {
        L->length = k;
        return true;   // 有元素被删除
    }
    return false;      // 无元素被删除
}

与单个删除算法的对比

特征	删除第一个	删除所有
时间复杂度	O(n)	O(n)
实现复杂度	较复杂（需要前移操作）	较简单（重构方式）
空间利用	原地前移	原地重构
适用场景	只需删除一个	需要删除全部

算法变体：返回删除元素个数

/**
 * 删除所有值为x的元素，并返回删除的个数
 * @param L 指向顺序表的指针
 * @param x 要删除的目标值
 * @return 删除的元素个数
 */
int del_and_count(Sqlist *L, int x) {
    int old_length = L->length;  // 记录原长度
    int k = 0;                   // 新顺序表下标

    // 重构顺序表
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] != x) {
            L->data[k] = L->data[i];
            k++;
        }
    }

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

算法特点

核心思想： 不进行元素前移操作，而是通过重构的方式，将不需要删除的元素依次复制到顺序表前面，形成新的顺序表。

优点： - 实现简单，逻辑清晰 - 只需一次遍历 - 避免了多次元素移动的开销 - 原地操作，空间效率高

关键技巧： 使用双下标：i遍历原表，k构建新表

注意点： - 正确更新顺序表长度 - 准确判断是否有元素被删除 - 理解重构后数组后部数据虽然存在但已无效