顺序表是用一段地址连续的存储单元依次存储线性表中的数据元素。逻辑上相邻的元素在物理存储上也相邻。
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ a₁│ a₂│ a₃│ a₄│ a₅│ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5 6 7 (下标)
↑ ↑
base last#define MaxSize 50
typedef struct {
ElemType data[MaxSize]; // 静态分配
int length; // 当前长度
} SqList;
// 动态分配
#define InitSize 100
typedef struct {
ElemType *data; // 动态数组指针
int MaxSize, length; // 最大容量和当前长度
} SeqList;第 $i$ 个元素的地址：$\text{LOC}(a_i) = \text{LOC}(a_1) + (i-1) \times \text{sizeof}(\text{ElemType})$
下标从 0 开始：$\text{LOC}(a[i]) = \text{LOC}(a[0]) + i \times \text{sizeof}(\text{ElemType})$
ListInsert(&L, i, e)在第 $i$ 个位置插入元素 $e$（$1 \leq i \leq \text{length}+1$）：
bool ListInsert(SqList *L, int i, ElemType e) {
if (i < 1 || i > L->length + 1) // 位置合法性
return false;
if (L->length >= MaxSize) // 存储空间满
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;
}ListDelete(&L, i, &e)删除第 $i$ 个位置的元素（$1 \leq i \leq \text{length}$）：
bool ListDelete(SqList *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;
}LocateElem(L, e)int LocateElem(SqList L, ElemType e) {
for (int i = 0; i < L.length; i++)
if (L.data[i] == e)
return i + 1; // 返回位序
return 0;
}时间复杂度：平均 O(n)。
顺序表 $L = \{1, 3, 5, 7, 9\}$，在第 3 个位置插入元素 4：
data[5]=data[4]=9，data[4]=data[3]=7，data[3]=data[2]=5data[2] = 4{1, 3, 4, 5, 7, 9}移动次数：3 次（$i=3$ 时，移动 $n-i+1=5-3+1=3$ 个元素）。
长度为 $n$ 的顺序表，插入操作平均移动次数：
$$E_{\text{insert}} = \sum_{i=1}^{n+1} p_i \times (n-i+1) = \frac{1}{n+1} \sum_{i=1}^{n+1} (n-i+1) = \frac{n}{2}$$
data[i-1]。length >= MaxSize。| 操作 | 最好 | 最坏 | 平均 |
|---|---|---|---|
| 插入 | O(1) | O(n) | O(n) |
| 删除 | O(1) | O(n) | O(n) |
| 按位查找 | O(1) | O(1) | O(1) |
| 按值查找 | O(1) | O(n) | O(n) |
顺序表核心优势：随机访问 O(1)；存储密度高（无需额外指针）；缓存友好（连续存储）。
顺序表核心劣势：插入删除需移动大量元素 O(n)；静态分配需预估大小，动态分配需复制。
↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。