C++ 顺序表删除元素优化：时间复杂度和输出格式改进

#include #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) { A.elem[k++] = A.elem[i]; } } A.length = k; }

void PrintA(SqList A) { for (int i = 0; i < A.length - 1; i++) { cout << A.elem[i] << ' '; } if (A.length > 0) { 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 函数优化：
- 原代码中，删除元素后将后面的元素依次覆盖前一个元素，导致时间复杂度较高。
- 改进后的代码使用一个索引 k 来记录有效元素的位置，并将非目标元素复制到 k 处，最后将 A.length 设置为 k，有效地减少了元素移动次数，提高了时间复杂度。
PrintA 函数优化：
- 原代码中，最后一个元素的输出格式与前面的不一致，导致输出结果不美观。
- 改进后的代码使用一个 if 语句来判断 A.length 是否大于 0，确保最后一个元素也能正确输出，并使用空格分隔输出元素，使输出结果更加美观。

优化后的代码不仅提高了程序的效率，也改善了输出结果，使其更易于阅读和理解。