顺序表的定义,初始化,插入和删除
时间: 2023-06-19 12:09:35 浏览: 51
顺序表是一种数据结构,它以数组的形式存储数据元素,每个元素占据一个数组下标位置。顺序表具有随机访问的特点,可以通过下标直接访问指定位置的元素。
初始化:顺序表的初始化即为创建一个空的顺序表,需要为其分配一定的内存空间。可以通过以下代码实现:
```c
#define MAXSIZE 100 // 定义顺序表的最大长度
typedef struct {
int data[MAXSIZE]; // 用数组存储数据元素
int length; // 顺序表的当前长度
} SqList;
// 初始化顺序表
void InitList(SqList *L) {
L->length = 0; // 初始化长度为0
}
```
插入:在顺序表中插入一个数据元素,需要将该元素插入到指定的位置,并将该位置后面的元素依次向后移动一位。可以通过以下代码实现:
```c
// 在顺序表 L 中的第 i 个位置插入元素 e
bool ListInsert(SqList *L, int i, int e) {
if (i < 1 || i > L->length+1) { // 判断 i 的范围是否有效
return false;
}
if (L->length >= MAXSIZE) { // 判断顺序表是否已满
return false;
}
for (int j = L->length; j >= i; j--) { // 将第 i 个位置及其后面的元素依次后移
L->data[j] = L->data[j-1];
}
L->data[i-1] = e; // 将新元素插入到第 i 个位置
L->length++; // 长度加1
return true;
}
```
删除:在顺序表中删除一个数据元素,需要将该元素删除后,将该位置后面的元素依次向前移动一位。可以通过以下代码实现:
```c
// 删除顺序表 L 中第 i 个位置的元素,并将删除的元素存储到 e 中
bool ListDelete(SqList *L, int i, int *e) {
if (i < 1 || i > L->length) { // 判断 i 的范围是否有效
return false;
}
*e = L->data[i-1]; // 将删除的元素存储到 e 中
for (int j = i; j < L->length; j++) { // 将第 i 个位置后面的元素依次前移
L->data[j-1] = L->data[j];
}
L->length--; // 长度减1
return true;
}
```
需要注意的是,顺序表的插入和删除操作的时间复杂度为 O(n),其中 n 为顺序表的长度。因为在插入和删除操作中,需要将该位置后面的元素依次移动,所以时间复杂度较高。