梳理顺序表的地址计算、静态实现、插入删除、查找取值和有序表合并，明确元素移动次数与各操作的时间复杂度。
# 一、线性表的顺序表示
# 1. 定义、地址计算与特点
顺序表用一组地址连续的存储单元依次保存线性表元素。若每个元素大小为 s，首元素地址为 LOC(a1)，则第 i 个元素地址为
LOC(ai)=LOC(a1)+(i−1)s.
故顺序表可随机访问第 i 个元素。顺序表的存储空间可以是静态数组，也可以是动态扩容数组；二者的逻辑结构相同，但容量管理方式不同。
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <stdbool.h>
#define MAX_SIZE 100
typedef int ElemType;
typedef struct {
ElemType data[MAX_SIZE];
int length;
} SeqList;
void InitList(SeqList *L) {
L->length = 0;
}
|
上述实现中，有效元素为 data [0] 到 data [length - 1]。空表满足 length == 0；满表满足 length == MAX_SIZE。
# 2. 插入与删除
在第 i 个逻辑位置插入元素，合法范围是 1≤i≤Length(L)+1。必须从后向前移动，避免尚未复制的元素被覆盖。
1
2
3
4
5
6
7
8
9
10
11
12
| bool ListInsert(SeqList *L, int i, ElemType e) {
if (i < 1 || i > L->length + 1 || L->length == MAX_SIZE) {
return false;
}
for (int j = L->length; j >= i; j--) {
L->data[j] = L->data[j - 1];
}
L->data[i - 1] = e;
L->length++;
return true;
}
|
删除第 i 个元素的合法范围是 1≤i≤Length(L)。删除后从前向后移动后继元素。
1
2
3
4
5
6
7
8
9
10
11
12
| bool ListDelete(SeqList *L, int i, ElemType *e) {
if (i < 1 || i > L->length) {
return false;
}
*e = L->data[i - 1];
for (int j = i; j < L->length; j++) {
L->data[j - 1] = L->data[j];
}
L->length--;
return true;
}
|
插入时移动元素个数为 n−i+1；删除时移动元素个数为 n−i。因此在表尾插入或删除为 O(1)，在表头进行则为 O(n)，平均情况下也是 O(n)。
例题 2.1：顺序表的移动次数
长度为 n 的顺序表中，在第 i 个位置插入元素，需要移动多少个元素？删除第 i 个元素呢？
【解】
- 插入：原第 i 至第 n 个元素均后移一位，共 n−i+1 个。
- 删除：原第 i+1 至第 n 个元素均前移一位，共 n−i 个。
注意，若题目要求 “赋值次数”，还要计入把新元素写入空位或把被删元素赋给输出变量的次数；“移动次数” 通常只计已有表元素的迁移。
# 3. 查找、取值和顺序表合并
按下标取值只需一次边界检查和一次数组访问，故为 O(1)：
1
2
3
4
5
6
7
| bool GetElem(const SeqList *L, int i, ElemType *e) {
if (i < 1 || i > L->length) {
return false;
}
*e = L->data[i - 1];
return true;
}
|
按值查找需要顺序比较：
1
2
3
4
5
6
7
8
| int LocateElem(const SeqList *L, ElemType e) {
for (int i = 0; i < L->length; i++) {
if (L->data[i] == e) {
return i + 1;
}
}
return 0;
}
|
若两个递增顺序表合并为一个递增表，可从两个表头开始比较，每次取较小者；两个指针均只单调前进，时间复杂度为 O(m+n)。
