定义SqList类型,实现顺序表的基本操作。基本操作的定义参照教材抽象数据类型ADT List的定义。 设顺序表的初始存储空间的容量LIST_INIT_SIZE是10,当顺序表的存储空间已满,扩容时的增量LISTINCREMENT是2。
时间: 2024-09-24 22:22:08 浏览: 48
在C++中,我们可以这样定义`SqList`类型(顺序表)及其基本操作,假设我们使用动态数组来实现:
```cpp
#include <vector>
// 定义 SqList 类型,初始化容量为10,扩容增量为2
template <typename T>
class SqList {
private:
std::vector<T> elements; // 使用 vector 存储,便于动态调整大小
int size;
static const int LIST_INIT_SIZE = 10;
static const int LIST_INCREMENT = 2;
public:
SqList() : size(0) { } // 构造函数,初始容量
// 操作:
// 插入元素
void insert(int index, const T& value) {
if (index < 0 || index > size) {
throw std::out_of_range("Index out of range");
}
if (size == elements.size()) {
resize(size + LIST_INCREMENT);
}
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];
}
elements[index] = value;
size++;
}
// 删除元素
void remove(const T& value) {
auto it = find(value);
if (it != end(elements)) {
for (int i = it - 1; i < size - 1; ++i) {
elements[i] = elements[i + 1];
}
elements.pop_back();
size--;
}
}
// 查找元素
typename std::vector<T>::iterator find(const T& value) {
return std::find(elements.begin(), elements.end(), value);
}
// 返回元素数量
int length() const {
return size;
}
// 判断是否为空
bool empty() const {
return size == 0;
}
// 调整存储空间大小
void resize(int newSize) {
if (newSize < 0) {
throw std::invalid_argument("Invalid new size");
}
elements.resize(newSize);
}
};
```
这里定义了一个模板类`SqList`,实现了插入、删除、查找以及一些辅助方法如判断空和调整大小等。每当存储空间满时,通过`resize()`函数自动扩容,并保持一定的增量。
阅读全文