Lesson 0401 · 线性表与顺序表

④ 数据结构与算法 — 第 1 课

1. 什么是数据结构

数据结构 = 数据的组织方式 + 对这些数据能做什么操作。

同一个「学生名单」，你可以：

• 用数组存：按下标直接找第 3 个同学
• 用链表存：方便在中间插入/删除
• 用树存：方便快速查找

选择不同的结构，同样操作的速度可能天差地别。数据结构课就是教你：什么场景选什么结构。

2. 线性表：一串排好队的数据

线性表是最简单的结构：元素一个接一个，有顺序。比如：

[10] -> [20] -> [30] -> [40]

它需要支持这些操作：

• 查找：第 2 个元素是什么？
• 插入：在某个位置插一个元素
• 删除：删掉某个位置或某个值的元素
• 遍历：从头到尾全部访问一遍

线性表有两种经典实现：顺序表（数组/vector） 和 链表。这节课先学顺序表。

3. 顺序表：连续内存放数据

顺序表就是一块连续内存，像一排连号的柜子。你早就在用了：

int a[5] = {10, 20, 30, 40, 50};
vector<int> v = {10, 20, 30, 40, 50};

「顺序」的意思是：第 i 个元素的地址 = 首地址 + i × 元素大小。所以按下标访问非常快。

v[2]             // 直接算出地址，一步拿到
*(v.data() + 2)  // 本质上是这个

这就是它能做到 O(1) 按下标访问的全部原因：地址是算出来的，不是走过去的。链表的第 i 个元素可没法这么算，下一课会看到代价。

4. vector 的中间插入：insert

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4};

    // 在下标 2 的位置插入 99
    v.insert(v.begin() + 2, 99);
    // v 变成：1 2 99 3 4

    for (int x : v) cout << x << " ";
    return 0;
}

为什么插入后下标 2 后面的元素都往后挪？因为顺序表必须保持连续，所以要先腾位置。

注意 insert 的第一个参数是迭代器，不是下标：要写 v.begin() + 2。

5. vector 的中间删除：erase

vector<int> v = {1, 2, 3, 4, 5};

// 删除下标 2 的元素（值为 3）
v.erase(v.begin() + 2);
// v 变成：1 2 4 5

同样，删除中间元素后，后面的元素要往前挪，补上空位。

6. 顺序表操作复杂度速查

7. 坑点清单

• 下标越界：v[i] 不做检查，i 超出 [0, size()) 就是未定义行为，可能读到垃圾值、也可能直接崩。at() 才会抛异常。
• 把下标当迭代器：v.insert(2, 99) 编译不过，要写 v.insert(v.begin() + 2, 99)；erase 同理。
• 循环里删元素跳着删：erase 之后后面元素整体前移，再 i++ 就跳过了一个。删完不要急着自增。
• 在循环里频繁中间插删：每次都是 O(n)，套一层循环就变成 O(n²)，数据一大直接超时。
• 以为 push_back 永远 O(1)：它是均摊 O(1)，扩容那一次要把旧数据全搬走，偶尔会慢一下——但整体仍然划算。

8. 小测

9. 动手练习

本课小结

• 数据结构 = 数据组织方式 + 支持的操作。
• 线性表：一串有顺序的元素，支持查找、插入、删除、遍历。
• 顺序表 = 连续内存的数组/vector；第 i 个地址 = 首地址 + i × 元素大小。
• 按下标访问 O(1)；中间插入/删除 O(n)；查找值 O(n)。
• 末尾 push_back / pop_back 是最快的 vector 操作。