Lecture 4：线性表的顺序实现

This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

4.1 顺序表的定义

4.1.1 什么是顺序表

定义：#顺序表

描述：顺序表是用顺序存储方式实现的线性表，即把逻辑上相邻的元素存储在物理位置也相邻的存储单元中。

解释

顺序表本质上是线性表的一种存储实现。
线性表强调逻辑结构；
顺序表强调存储结构。
顺序表中，元素之间的逻辑关系由存储单元的邻接关系体现。

地址计算

若线性表第一个元素的存放地址为 $LOC(L)$；
每个数据元素占用空间大小为 $sizeof(ElemType)$；
第 $n$ 个元素的存储地址为： $$ LOC(a_n)=LOC(L)+(n-1)\times sizeof(ElemType) $$

注意

PDF 中写法类似 LOC(L)+n*数据元素的大小，更严格时要看 $n$ 表示位序还是偏移量：
- 若 $n$ 表示第 $n$ 个元素位序，则应使用 $n-1$；
- 若 $n$ 表示从 0 开始的下标，则可写成 $LOC(L)+n\times sizeof(ElemType)$。
C 语言中可以使用：

sizeof(ElemType)

来获得一个数据元素所占空间大小。

4.2 顺序表的静态分配

4.2.1 静态分配的定义

定义：#静态分配

描述：静态分配是在定义顺序表时预先分配固定大小的数组空间。

结构定义

#define MaxSize 10

typedef struct {
    ElemType data[MaxSize];  // 用静态数组存放数据元素
    int length;              // 顺序表当前长度
} SqList;

解释

data[MaxSize] 是顺序表的存储空间。
length 是当前已经存放的数据元素个数。
MaxSize 是顺序表最大容量。

4.2.2 静态顺序表初始化

代码

#define MaxSize 10

typedef struct {
    int data[MaxSize];
    int length;
} SqList;

void InitList(SqList &L) {
    L.length = 0;
}

int main() {
    SqList L;
    InitList(L);
    return 0;
}

解释

SqList L：声明一个顺序表。
InitList(L)：初始化顺序表。
L.length=0：表示当前顺序表为空。
初始化空表时不必清零全部数组单元；只有下标范围 $[0,L.length-1]$ 内的元素属于当前顺序表，读取其余未初始化单元本身就是越界于逻辑表长的错误。

静态分配的特点

优点：
- 实现简单；
- 不需要手动申请和释放空间。
缺点：
- 内存空间大小固定；
- 如果数据存满，再插入就会溢出；
- 如果初始空间分配过多，会浪费内存。

4.3 顺序表的动态分配

4.3.1 动态分配的定义

定义：#动态分配

描述：动态分配是在程序运行时根据需要申请连续存储空间，顺序表容量可以通过重新申请空间进行扩展。

结构定义

#define InitSize 10

typedef struct {
    ElemType *data;  // 指向动态分配数组的指针
    int MaxSize;     // 顺序表最大容量
    int length;      // 顺序表当前长度
} SeqList;

解释

data 不再是固定数组，而是指向动态数组的指针。
MaxSize 记录当前最大容量。
length 记录当前已有元素个数。

4.3.2 C 语言动态申请空间

malloc/free

L.data = malloc(sizeof(ElemType) * InitSize);
free(L.data);

注意

malloc 返回的是 void * 类型指针。
在 C 语言中，void * 可以隐式转换为对象指针，通常不需要也不建议强制转换；应包含 <stdlib.h> 以获得正确函数声明。
在 C++ 中，void * 不能隐式转换为其他对象指针，但更推荐使用 new[]/delete[]、std::vector 或其他 RAII 容器，而不是把 C 风格分配机械地强制转换。
使用 malloc 后，空间不再使用时应使用 free 释放。

4.3.3 C++ 动态申请空间

new/delete

L.data = new ElemType[InitSize];
delete[] L.data;

解释

new 用于申请动态数组。
delete[] 用于释放动态数组。

4.3.4 动态顺序表初始化

代码

#define InitSize 10

typedef struct {
    int *data;
    int MaxSize;
    int length;
} SeqList;

void InitList(SeqList &L) {
    L.data = new int[InitSize];
    L.length = 0;
    L.MaxSize = InitSize;
}

解释

new[] 申请一片连续的存储空间。
length=0 表示当前没有元素。
MaxSize=InitSize 表示当前容量为初始容量。

4.3.5 增加动态数组长度

代码

void IncreaseSize(SeqList &L, int len) {
    int *p = L.data;
    L.data = new int[L.MaxSize + len];

    for (int i = 0; i < L.length; i++) {
        L.data[i] = p[i];
    }

    L.MaxSize = L.MaxSize + len;
    delete[] p;
}

解释

第一步：用 p 保存原来的存储空间地址。
第二步：重新申请更大的连续空间。
第三步：把原数据复制到新空间。
第四步：更新最大容量。
第五步：用与申请方式匹配的 delete[] 释放旧空间。

注意

动态分配不是在原数组后面直接追加空间。
本质上是：
- 重新申请；
- 复制数据；
- 释放旧空间。
因此扩容的时间复杂度较高。

主函数示例

int main() {
    SeqList L;
    InitList(L);

    // 此处可以插入若干元素
    IncreaseSize(L, 5);

    delete[] L.data;  // 与 InitList/IncreaseSize 中的 new[] 配对
    return 0;
}

4.4 顺序表的特点

四个特点

1. 随机访问。
1. 存储密度高。
1. 扩展容量不方便。
1. 插入、删除不方便。

4.4.1 随机访问

定义：#随机访问

描述：顺序表可以在 $O(1)$ 时间内找到第 $i$ 个元素。

解释

顺序表元素连续存放。
只要知道首地址和元素大小，就能直接计算目标地址。
因此按位查找效率高。

4.4.2 存储密度高

解释

每个结点只存储数据元素本身。
不需要像链表一样额外存储指针。
因此顺序表存储密度高。

4.4.3 扩展容量不方便

解释

静态分配时容量固定，无法直接扩展。
动态分配虽然可以扩展，但需要：
- 重新申请空间；
- 复制原有元素；
- 释放旧空间。
所以扩容时间复杂度较高。

4.4.4 插入删除不方便

解释

插入时，需要把插入位置及其之后的元素后移。
删除时，需要把删除位置之后的元素前移。
因此插入和删除通常需要移动大量元素。

4.5 顺序表的插入

4.5.1 插入操作定义

定义：#ListInsert

描述： ListInsert(&L, i, e) 表示在表 $L$ 中第 $i$ 个位置插入指定元素 $e$。

合法条件

插入位序必须合法： $$ 1\le i\le L.length+1 $$
顺序表不能已满： $$ L.length<MaxSize $$

解释

$i=1$：在表头插入。
$i=L.length+1$：在表尾插入。
插入位置之后的元素都要后移。

4.5.2 插入代码

代码

#define MaxSize 10

typedef struct {
    int data[MaxSize];
    int length;
} SqList;

bool ListInsert(SqList &L, int i, int 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;
}

解释

i < 1 || i > L.length + 1：判断插入位置是否合法。
L.length >= MaxSize：判断顺序表是否已满。
for (int j = L.length; j >= i; j--)：
- 从后往前移动元素；
- 防止前面的元素被覆盖。
L.data[i-1]=e：
- 位序 $i$ 对应数组下标 $i-1$。

PDF 笔误修正

PDF 中出现 L.lenght，应为 L.length。

4.5.3 插入时间复杂度

题型：#顺序表插入复杂度

第一部分：解题方法

插入复杂度取决于要移动多少个元素。
设插入前表长为 $n$。

第二部分：典型分析

最好情况

在表尾插入： $$ i=n+1 $$
不需要移动元素。
时间复杂度： $$ O(1) $$

最坏情况

在表头插入： $$ i=1 $$
需要移动 $n$ 个元素。
时间复杂度： $$ O(n) $$

平均情况

插入位置可能为： $$ i=1,2,3,\cdots,n+1 $$
假设插入到任意位置的概率相同： $$ p=\frac{1}{n+1} $$
各位置需要移动元素个数：
- $i=1$：移动 $n$ 次；
- $i=2$：移动 $n-1$ 次；
- $i=3$：移动 $n-2$ 次；
- $\cdots$
- $i=n+1$：移动 $0$ 次。
平均移动次数： $$ \begin{aligned} E &=n\cdot\frac{1}{n+1}+(n-1)\cdot\frac{1}{n+1}+\cdots+1\cdot\frac{1}{n+1}+0\cdot\frac{1}{n+1}\ &=\frac{n+(n-1)+\cdots+1+0}{n+1}\ &=\frac{\frac{n(n+1)}{2}}{n+1}\ &=\frac{n}{2} \end{aligned} $$
因此平均时间复杂度： $$ O(n) $$

第三部分：知识点复盘

顺序表插入的核心成本是移动元素。
表尾插入最快。
表头插入最慢。
平均复杂度仍然是 $O(n)$。

4.6 顺序表的删除

4.6.1 删除操作定义

定义：#ListDelete

描述： ListDelete(&L, i, &e) 表示删除表 $L$ 中第 $i$ 个位置的元素，并用 $e$ 返回被删除元素的值。

合法条件

删除位序必须合法： $$ 1\le i\le L.length $$

解释

删除的是已有元素，所以 $i$ 不能等于 $L.length+1$。
删除后，第 $i+1$ 个元素及其之后的元素都要前移。

4.6.2 删除代码

代码

bool ListDelete(SqList &L, int i, int &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;
}

解释

i < 1 || i > L.length：判断删除位置是否合法。
e = L.data[i - 1]：保存被删除元素的值。
for (int j = i; j < L.length; j++)：
- 把第 $i$ 个位置之后的元素依次前移。
L.length--：删除后表长减 1。

PDF 笔误修正

PDF 中 L.date 应为 L.data。
PDF 中 ListDelete(L,3,E) 应为 ListDelete(L,3,e)，变量名大小写要一致。

4.6.3 删除示例

代码

int main() {
    SqList L;
    InitList(L);

    // 此处省略若干插入操作
    int e = -1;

    if (ListDelete(L, 3, e)) {
        printf("已删除第3个元素，删除元素之值为%d\n", e);
    } else {
        printf("位序i不合法，删除失败\n");
    }

    return 0;
}

解释

e 用来保存被删除的元素。
如果删除成功，就输出删除值。
如果位序不合法，就输出删除失败。

4.6.4 删除时间复杂度

题型：#顺序表删除复杂度

第一部分：解题方法

删除复杂度取决于要前移多少个元素。
设删除前表长为 $n$。

第二部分：典型分析

最好情况

删除表尾元素： $$ i=n $$
不需要移动元素。
时间复杂度： $$ O(1) $$

最坏情况

删除表头元素： $$ i=1 $$
需要移动 $n-1$ 个元素。
时间复杂度： $$ O(n) $$

平均情况

删除位置可能为： $$ i=1,2,3,\cdots,n $$
假设删除任意位置的概率相同： $$ p=\frac{1}{n} $$
各位置移动次数：
- $i=1$：移动 $n-1$ 次；
- $i=2$：移动 $n-2$ 次；
- $\cdots$
- $i=n$：移动 $0$ 次。
平均移动次数： $$ \begin{aligned} E &=(n-1)\cdot\frac{1}{n}+(n-2)\cdot\frac{1}{n}+\cdots+1\cdot\frac{1}{n}+0\cdot\frac{1}{n}\ &=\frac{(n-1)+(n-2)+\cdots+1+0}{n}\ &=\frac{\frac{n(n-1)}{2}}{n}\ &=\frac{n-1}{2} \end{aligned} $$
因此平均时间复杂度： $$ O(n) $$

第三部分：知识点复盘

顺序表删除的核心成本是移动元素。
删除表尾最快。
删除表头最慢。
平均复杂度仍然是 $O(n)$。

4.7 插入和删除对比

对比表

操作	合法位序	最好情况	最坏情况	平均移动次数	平均复杂度
插入	$1\le i\le n+1$	表尾插入，移动 0 次	表头插入，移动 $n$ 次	$\frac{n}{2}$	$O(n)$
删除	$1\le i\le n$	表尾删除，移动 0 次	表头删除，移动 $n-1$ 次	$\frac{n-1}{2}$	$O(n)$

记忆

插入：可以插在第 $n+1$ 个位置。
删除：只能删除已有的 $1$ 到 $n$ 个位置。
插入是“后移”，删除是“前移”。

4.8 本节复盘

必须掌握

顺序表是线性表的顺序存储实现。
顺序表支持随机访问： $$ O(1) $$
顺序表插入、删除通常需要移动元素： $$ O(n) $$
静态分配容量固定。
动态分配可以扩容，但扩容成本较高。

易错点

第 $i$ 个元素对应数组下标 $i-1$。
插入合法范围： $$ 1\le i\le L.length+1 $$
删除合法范围： $$ 1\le i\le L.length $$
插入时从后往前移动，防止覆盖元素。
删除时从前往后移动，覆盖被删除元素的位置。

代码题抓手

写插入代码时，先判位序，再判是否满。
写删除代码时，先判位序，再保存删除值。
看到 &L，说明操作会修改线性表。
看到 &e，说明需要把结果带回调用处。

4.1 顺序表的定义

4.1.1 什么是顺序表

定义：#顺序表

4.2 顺序表的静态分配

4.2.1 静态分配的定义

定义：#静态分配

4.2.2 静态顺序表初始化

4.3 顺序表的动态分配

4.3.1 动态分配的定义

定义：#动态分配

4.3.2 C 语言动态申请空间

4.3.3 C++ 动态申请空间

4.3.4 动态顺序表初始化

4.3.5 增加动态数组长度

4.4 顺序表的特点

4.4.1 随机访问

定义：#随机访问

4.4.2 存储密度高

4.4.3 扩展容量不方便

4.4.4 插入删除不方便

4.5 顺序表的插入

4.5.1 插入操作定义

定义：#ListInsert

4.5.2 插入代码

4.5.3 插入时间复杂度

题型：#顺序表插入复杂度

第一部分：解题方法

第二部分：典型分析

第三部分：知识点复盘

4.6 顺序表的删除

4.6.1 删除操作定义

定义：#ListDelete

4.6.2 删除代码

4.6.3 删除示例

4.6.4 删除时间复杂度

题型：#顺序表删除复杂度

第一部分：解题方法

第二部分：典型分析

第三部分：知识点复盘

4.7 插入和删除对比

相关知识

4.8 本节复盘