实验要求,创建顺序存储的线性表,实现,创建、展示、插入、删除操作
时间: 2024-09-18 16:13:55 浏览: 3
实验通常会要求学生设计并实现一种简单的数据结构,如顺序存储的线性表,也称为数组列表。以下是实现这个数据结构的基本步骤:
1. 创建(Construction):
- 定义一个结构体或类,例如`SequentialList`,包含两个部分:元素集合和一个指向当前元素位置的指针(或索引)。
- 初始化时,可以创建一个固定大小的数组作为元素集合,并设置初始指针。
```cpp
class SequentialList {
private:
int* elements;
int size;
int cursor;
public:
SequentialList(int capacity);
};
```
2. 展示(Display):
- 提供一个方法`display()`来遍历列表并打印元素。从起始位置开始,直到达到`cursor`或数组末尾。
```cpp
void SequentialList::display() {
if (cursor < size) {
for (int i = 0; i <= cursor; ++i) {
cout << elements[i] << " ";
}
cout << endl;
} else {
cout << "The list is empty or has reached its end." << endl;
}
}
```
3. 插入(Insertion):
- 根据需求提供插入操作。如果要在列表末尾添加元素,只需将`elements[cursor]`更新为新值,然后`++cursor`。若空间不够,需要动态扩展数组容量。
```cpp
void SequentialList::insert(int value) {
// 检查是否有空余空间
if (cursor == size) {
resize(size * 2); // 扩展数组
}
elements[cursor++] = value;
}
```
4. 删除(Deletion):
- 可以有两种删除策略:按位置删除和按值删除。按位置删除时,将`elements[cursor]`的值替换为最后一个元素,然后缩小数组容量。按值删除则需查找目标元素的位置。
```cpp
void SequentialList::deleteByValue(int value) {
for (int i = cursor - 1; i >= 0; --i) {
if (elements[i] == value) {
memmove(&elements[i], &elements[i + 1], sizeof(elements[i]));
cursor--;
if (cursor == size - 1 && cursor != 0) { // 如果只剩最后一个元素,缩小数组
resize(size / 2);
}
break;
}
}
}
```