用数组实现的顺序表(P23-结构定义,参考2.4.2,实现顺序表初始化、实现头部插入任意n个数据,选做删除、查找、取值。
时间: 2024-10-19 09:12:11 浏览: 32
数据结构勘误表202108111
顺序表是一种基于数组的数据结构,它通过连续的内存空间存储元素。用数组实现的顺序表通常包括以下几个部分的实现:
1. 初始化:
- 定义一个数组 `data` 和两个变量 `size` 和 `capacity` 分别表示当前元素的数量和数组的最大容量。
- 在创建顺序表时,可以先设置初始容量,然后将 `size` 设为0,表示列表为空。
```c++
struct SeqList {
int *data;
int size, capacity;
// 初始化函数
SeqList(int initial_capacity = 10) {
data = new int[initial_capacity];
size = 0;
capacity = initial_capacity;
}
};
```
2. 首部插入任意 n 个数据:
- 如果插入位置在头部(索引为0),直接添加到数组开头,并更新大小(size)。
- 如果需要插入的位置超出数组范围,需要检查并可能动态扩容数组(如 `size + n > capacity`)。
```c++
void insertAtHead(int value, int n) {
if (size + n > capacity) resize(capacity * 2); // 扩容
for (int i = 0; i < n; ++i) {
data[size++] = value;
}
}
```
3. 删除、查找、取值操作示例:
- 删除操作通常需要指定一个索引,删除对应位置的数据并将后面的元素向前移动。
```c++
void deleteElement(int index) {
if (index >= 0 && index < size) {
for (int i = index; i < size - 1; ++i) {
data[i] = data[i + 1];
}
--size;
} else {
// 检查边界错误处理
}
}
int search(int target) const {
for (int i = 0; i < size; ++i) {
if (data[i] == target) return i; // 返回目标位置
}
return -1; // 未找到
}
int get(int index) const {
if (index >= 0 && index < size) {
return data[index]; // 返回指定索引处的值
} else {
throw std::out_of_range("Index out of range");
}
}
```
阅读全文