数组

数组把相同类型的元素按顺序放在一块连续内存里。你可以用下标 $i$ 在 $O(1)$ 时间内访问第 $i$ 个元素——这是它最重要的能力。

多维数组（如矩阵）可看成「数组的数组」，逻辑上按行/列组织，物理上仍常映射到一维连续空间。

本文解决什么问题

• 随机访问为何是 $O(1)$
• 插入删除代价从何而来
• 定长数组与 std::vector 如何对照
• 和 顺序表 的关系

特点

操作	平均时间	说明
按下标读写	$O(1)$	随机访问
末尾追加（容量足够）	$O(1)$	动态数组均摊常为 $O(1)$
中间插入 / 删除	$O(n)$	要搬移后面的元素
按值查找（无序）	$O(n)$	一般要扫一遍

优点：访问快、缓存友好、实现简单。
缺点：中间改动贵；定长数组大小不灵活；动态扩容会有拷贝成本。

随机访问的本质

若元素类型大小为 $s$ 字节，首地址为 $base$，则下标 $i$ 的地址为：

$$address(i) = base + i \times s$$

CPU 一次加法即可定位，因此是 $O(1)$。链表做不到这一点，因为结点地址不连续。

C：定长数组

#include <stdio.h>

int main(void) {
    int a[8] = {10, 20, 30, 40, 50};
    int n = 5;

    printf("a[2] = %d\n", a[2]);  /* O(1) */

    /* 在下标 2 处插入 99：从后往前挪 */
    for (int i = n; i > 2; i--) {
        a[i] = a[i - 1];
    }
    a[2] = 99;
    n++;

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

上面假定 a 后面还有空位。真实定长数组不能无限增长；越界是未定义行为。

二维数组与按行主序

C 中 int m[2][3] 按行主序存放：先放完第 0 行，再放第 1 行。映射到一维下标时常写作 i * cols + j。

int m[2][3] = {{1, 2, 3}, {4, 5, 6}};
/* 等价一维视角大致是: 1 2 3 4 5 6 */
printf("%d\n", m[1][2]);  /* 6 */

特殊矩阵的压缩存储见 特殊矩阵。

C++：std::vector（动态数组）

#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {10, 20, 30, 40, 50};

    std::cout << "a[2] = " << a[2] << '\n';
    a.insert(a.begin() + 2, 99);  // 中间插入
    a.push_back(60);              // 末尾追加

    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

容量不够时会扩容（常见约 1.5～2 倍），单次 push_back 偶发 $O(n)$，均摊仍为 $O(1)$。

提示

operator[] 不检查边界；需要检查时用 at()（越界抛异常）。调试阶段宁可用 at()，或自己断言。

和顺序表的关系

顺序表 是「用顺序存储实现的线性表 ADT」；数组是语言提供的连续存储机制。教学上二者经常一起讲：顺序表 = 数组 + 长度等管理信息。

什么时候用数组

• 需要按下标频繁读写
• 元素数量大致已知，或主要在末尾增减
• 对遍历性能敏感（连续内存、缓存友好）

若频繁在头部或中间插入删除，再考虑链表，或「与末尾交换后删除」等技巧。

小结

数组擅长随机访问，不擅长中间插入删除。几乎所有更复杂的结构，底层都会用到数组或「数组 + 下标/指针」的思想。

下一篇：特殊矩阵。