顺序存储结构

学习目标

本节学习线性表的第一种常见实现方式：顺序存储结构。

顺序存储的核心特点是：用一段连续的存储空间保存线性表中的元素。数组和动态数组都是典型例子。它的优势是按位置访问非常直接，劣势是在中间插入和删除时可能需要移动大量元素。

---

什么是顺序存储

顺序存储把线性表中的元素按照逻辑顺序，依次放在连续位置中。

可以把它想象成一排连续编号的柜子：

下标:   0    1    2    3
元素:  10   20   30   40

元素的逻辑顺序和存储顺序一致。第 0 个位置保存 10，第 1 个位置保存 20，第 2 个位置保存 30，第 3 个位置保存 40。

因为元素位置连续，所以只要知道起始位置和下标，就能直接定位到某个元素。这就是顺序存储按下标访问高效的原因。

---

按下标访问元素

顺序存储最突出的优点是可以快速按下标访问元素。

C++

vector<int> numbers = {10, 20, 30, 40};

int value = numbers[2];

Java

int[] numbers = {10, 20, 30, 40};

int value = numbers[2];

Python

numbers = [10, 20, 30, 40]

value = numbers[2]

C#

int[] numbers = { 10, 20, 30, 40 };

int value = numbers[2];

这四段代码都访问了下标为 2 的元素，也就是第三个元素 30。

按下标访问不需要从第一个元素一个一个找过去，因此通常可以看作 $O(1)$ 操作。

---

遍历顺序表

遍历是线性表最常见的操作之一。顺序存储的遍历通常很直观：从第一个位置访问到最后一个位置。

C++

vector<int> numbers = {10, 20, 30, 40};

for (int number : numbers) {
    cout << number << endl;
}

Java

int[] numbers = {10, 20, 30, 40};

for (int number : numbers) {
    System.out.println(number);
}

Python

numbers = [10, 20, 30, 40]

for number in numbers:
    print(number)

C#

int[] numbers = { 10, 20, 30, 40 };

foreach (int number in numbers)
{
    Console.WriteLine(number);
}

如果线性表中有 $n$ 个元素，遍历通常需要访问每个元素一次，所以时间复杂度是 $O(n)$。

---

在中间插入元素

顺序存储的插入操作需要特别注意。

假设当前元素如下：

10  20  30  40

如果要在 20 和 30 之间插入 25，后面的 30 和 40 通常需要向后移动，给新元素腾出位置：

10  20  25  30  40

这说明顺序表在中间插入元素时，成本主要来自元素移动。最坏情况下，如果在开头插入，需要移动几乎所有元素，所以时间复杂度通常是 $O(n)$。

---

删除元素也可能需要移动

删除中间元素也类似。

如果删除下面的 20：

10  20  30  40

删除后，为了保持连续存储，后面的 30 和 40 通常需要向前移动：

10  30  40

所以，顺序存储删除元素的最坏时间复杂度通常也是 $O(n)$。

---

顺序存储的特点

顺序存储的优势很明显：

• 按下标访问快。
• 遍历简单。
• 存储紧凑。
• 对 CPU 缓存比较友好。

它的劣势也很明确：

• 中间插入可能需要移动元素。
• 中间删除可能需要移动元素。
• 如果底层容量固定，可能需要提前估计空间。
• 如果使用动态数组，容量不足时可能触发扩容。

这些特点决定了顺序存储适合频繁访问、较少在中间插入删除的场景。

---

本节小结

顺序存储用连续空间保存线性表元素，逻辑顺序和存储顺序一致。

它支持高效的按下标访问，通常是 $O(1)$；遍历需要访问所有元素，通常是 $O(n)$；中间插入和删除可能移动大量元素，最坏情况下是 $O(n)$。