定义一个顺序表的结构,然后分别设计两个子函数实现顺序表的插入和删除操作
时间: 2024-11-12 12:36:32 浏览: 23
顺序表是一种线性数据结构,通常通过数组来实现,每个元素都有一个固定的索引位置。下面是一个简单的顺序表的定义,包含一个整型数组作为存储元素的空间和两个指针变量指向表头和表尾:
```c++
typedef struct {
int* elements; // 存储元素的数组
int capacity; // 表的最大容量
int size; // 当前元素的数量
} SeqList;
```
接下来,我们可以定义两个函数来操作顺序表:
1. **插入操作(insert)**:
这个函数会向顺序表末尾添加一个新元素。如果还有空间可用,直接将新元素放在`elements[size]`的位置;若已满,则需要先扩容。
```c++
void insert(SeqList& list, int value) {
if (list.size == list.capacity) { // 扩容
list.capacity *= 2; // 双倍当前容量
list.elements = (int*)realloc(list.elements, sizeof(int) * list.capacity);
}
list.elements[list.size++] = value;
}
```
2. **删除操作(delete)**:
删除指定索引处的元素。这里假设`index`合法,并确保不会引起数组越界。如果删除的是最后一个元素,只需更新大小即可;否则,后面的元素需要向前移动一位。
```c++
void delete(SeqList& list, int index) {
if (index >= 0 && index < list.size) {
for (int i = index; i < list.size - 1; ++i) {
list.elements[i] = list.elements[i + 1]; // 将下一个元素移到当前位置
}
--list.size; // 减少元素数量
if (index != list.size) { // 如果不是删除最后一个元素,还需要调整引用
list.elements[list.size] = INT_MAX; // 或者设置成某种标记值,表示已删除
} else {
list.elements[list.size] = nullptr; // 清空最后的引用
}
} else {
// 对于非法索引,可以添加错误处理代码
printf("Delete operation failed: Index out of bounds.\n");
}
}
```
阅读全文