C++实现顺序表：删除、插入和特定元素删除

本文将介绍如何使用C++定义一个长度为n的顺序表，并实现以下操作：

删除表中第1个元素。2. 在表尾插入元素item。3. 设计一个时间复杂度为O(n)，空间复杂度为O(1)的算法，删除顺序表中所有值为item的数据元素（item在表中可能不唯一）。

代码实现cpp#include #include using namespace std;

// 定义顺序表结构struct SeqList { vector data; // 存储数据的向量};

// 删除顺序表中的第一个元素void DeleteFirstElement(SeqList& L) { if (L.data.empty()) { cout << '顺序表为空，无法删除元素' << endl; return; } L.data.erase(L.data.begin());}

// 在顺序表末尾插入元素void InsertAtEnd(SeqList& L, int item) { L.data.push_back(item);}

// 删除顺序表中所有值为item的数据元素void DeleteAllElements(SeqList& L, int item) { L.data.erase(remove(L.data.begin(), L.data.end(), item), L.data.end());}

int main() { int n, item; cin >> n >> item; // 输入表长n和元素item SeqList L; for (int i = 0; i < n; i++) { int elem; cin >> elem; L.data.push_back(elem); } // 删除顺序表中的第一个元素 DeleteFirstElement(L); // 在顺序表末尾插入元素 InsertAtEnd(L, item); // 输出删除第一个元素并插入新元素后的顺序表 for (int i = 0; i < L.data.size(); i++) { cout << L.data[i] << ' '; } cout << endl; // 删除顺序表中所有值为item的数据元素 DeleteAllElements(L, item); // 输出删除元素后的顺序表 for (int i = 0; i < L.data.size(); i++) { cout << L.data[i] << ' '; } cout << endl; return 0;}

代码说明

使用C++的vector容器来实现顺序表，方便动态调整大小。- DeleteFirstElement函数删除顺序表中的第一个元素，时间复杂度为O(n)，因为删除第一个元素后需要将后续元素向前移动。- InsertAtEnd函数在顺序表末尾插入元素，时间复杂度为O(1)。- DeleteAllElements函数删除顺序表中所有值为item的元素，使用remove和erase函数组合实现，时间复杂度为O(n)，空间复杂度为O(1)。

输入输出

输入形式:

第一行：n item (n为表长，item为一个整型数据，n和item中间用空格隔开)第二行：原顺序表中的数据元素 (元素之间用空格隔开)

输出形式:

第一行：删除元素item前（即实验内容1、2）表中的所有元素，元素之间空格隔开。第二行：删除元素item后（即实验内容3）表中的所有元素，元素之间空格隔开。

总结

本文介绍了如何使用C++实现一个简单的顺序表，并完成了删除、插入和特定元素删除等操作。代码简洁易懂，并对算法复杂度进行了分析，希望对你理解顺序表有所帮助。