C++ 顺序表删除元素算法优化与解析

本文将分析一段 C++ 代码，该代码用于实现顺序表中删除所有值为 item 的元素。代码中存在一个错误，我们将对其进行修正，并详细解释原因。

代码分析与错误修正

#include<iostream>
#define MAXSIZE 100
using namespace std;
typedef struct {
    int* elem;       //存储空间的基地址
    int length;      //当前长度
}SqList;

void InitList_Sq(SqList& L, int n) {
    //构造顺序表
    L.elem = new int[MAXSIZE];    //为顺序表分配一个大小为MAXSIZE的数组空间
    L.length = n;            //空表长度为0
}

void DeleteItem(SqList& A, int item) {
    int k=0;
    for (int i = 0; i < A.length; i++) {
        if (A.elem[i] == item) {
            k = i;
            do {
                A.elem[k] = A.elem[k + 1];
                k++;
            } while (k < A.length - 1);
            A.length--;
        }
    }
}

void PrintA(SqList A) {//输出数组元素
    for (int i = 0; i < A.length - 1; i++)
        cout << A.elem[i] << ' '; 
    cout << A.elem[A.length - 1] << endl;
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        SqList A;
        InitList_Sq(A, n);
        for (int i = 0; i < n; i++)
            cin >> A.elem[i];
        int item;
        cin >> item;
        DeleteItem(A, item);
        PrintA(A);
    }
    return 0;
}

代码中的错误:

在 DeleteItem 函数中，循环条件应该是 i < A.length 而不是 i < A.length - 1。这是因为循环需要遍历整个顺序表，而 A.length - 1 会导致最后一个元素被遗漏。

修正后的代码：

void DeleteItem(SqList& A, int item) {
    int k=0;
    for (int i = 0; i < A.length; i++) {
        if (A.elem[i] == item) {
            k = i;
            do {
                A.elem[k] = A.elem[k + 1];
                k++;
            } while (k < A.length - 1);
            A.length--;
        }
    }
}

此外，在删除元素后，需要将 A.length 减 1，这是因为顺序表长度需要随着元素的删除而减少。

总结

本文分析了 C++ 中顺序表删除元素的算法，并针对代码中存在的错误进行修正。通过分析代码逻辑，我们详细讲解了循环条件的错误，并提供了修正后的代码，同时解释了为什么需要在删除元素后将长度减一。希望本文能帮助读者更好地理解顺序表删除元素算法的实现。