数组（Array）

一、 静态数组

在 C/C++ 中，静态数组通常指的是在 栈（Stack） 上分配内存的固定大小数组，也就是最基础的 C 风格数组。它是 C/C++ 中最原始的容器，其大小必须在编译期确定，且在其生命周期内不可改变。

1.1 存储机制与内存寻址

静态数组最大的优势是：能在 $O(1)$ 时间复杂度内通过下标随机访问任意元素。下标从 0 开始，到 length - 1 结束。

下标访问的本质是数学上的地址偏移计算。 假设数组最大容量为 MAXSIZE，数组的实际长度用 length 维护：

const int MAXSIZE = 100; // 数组物理长度
int arr[MAXSIZE];        // 底层静态数组
int length = 0;          // 线性表当前的有效长度（逻辑长度）

若声明一个静态数组 int arr[5] = {10, 20, 30, 40, 50}，操作系统会在内存中分配一块物理上连续的存储空间。 假设这块内存的起始地址（即 arr[0] 的地址）是 0x1000，在 64 位系统中一个 int 类型占用 4 个字节，则该数组在内存中的分布如下：

任何元素的内存地址都可以通过简单的公式直接计算出来： $$Loc(arr[i]) = Loc(arr[0]) + i \times d \quad (0 \le i < \text{length})$$ 其中 $d$ 为每个元素占用的内存大小（如 sizeof(int) = 4 字节）。

⚠️ DANGER（越界安全漏洞） C++ 原生静态数组不会进行越界检测。访问 arr[5] 或 arr[-1] 在编译时通常不会报错，而是直接读写相邻的内存，这会导致未定义行为（Undefined Behavior, UB），是无数内存泄漏、Bug 和安全溢出漏洞的根源。

1.2 二维静态数组

二维数组在内存中其实也是一维线性排列的，采用行优先存储。例如：

int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};

它在内存中实际的物理布局为：1, 2, 3, 4, 5, 6。 访问 matrix[i][j] 的寻址公式为： $$Loc(matrix[i][j]) = Loc(matrix[0][0]) + (i \times \text{列数} + j) \times d \quad (0 \le i < \text{行数})$$

提示：这就是为什么在 C++ 中将二维数组作为函数参数传递时，必须指明列数（Columns） 的原因。编译器必须依靠列数才能正确计算出跨行的地址偏移量。

1.3 静态数组的基本操作（C++）

1. 数组遍历

注意：在维护线性表时，只应当遍历逻辑有效长度 length，而不是整个物理长度 MAXSIZE。

// 方式 1：传统 for 循环（按索引访问）
for (int i = 0; i < length; i++) {
    cout << arr[i] << " ";
}

// 方式 2：C++11 范围 for 循环（适用于遍历整个物理数组）
for (int val : arr) {
    cout << val << " ";
}

// 方式 3：引用遍历（用于修改数组元素）
for (int& val : arr) {
    val *= 2; // 数组内所有元素全部乘 2
}

2. 按值查找

从头遍历有效区间，找到则返回索引，未找到则返回 -1。时间复杂度为 $O(n)$。

int findByValue(int val) {
    for (int i = 0; i < length; i++) { // 只遍历有效长度
        if (arr[i] == val) {
            return i;
        }
    }
    return -1; // 未找到
}

3. 元素插入

在指定索引 index 处插入元素：必须将该位置及之后的所有有效元素向后移动，腾出位置。平均需要移动一半的元素，时间复杂度为 $O(n)$。

void insertAtIndex(int index, int val) {
    if (index < 0 || index > length) return; // 允许 index == length，相当于尾插
    if (length >= MAXSIZE) return;           // 数组已满

    // 从后往前移动元素，为 index 腾出位置
    for (int i = length; i > index; i--) {
        arr[i] = arr[i - 1];
    }

    arr[index] = val; // 插入新值
    length++;         // 有效长度加 1
}

4. 元素删除

删除指定索引 index 处的元素：必须将其后面的所有元素向前移动覆盖该位置。平均也需要移动一半的元素，时间复杂度为 $O(n)$。

void deleteAtIndex(int index) {
    if (index < 0 || index >= length) return; // 索引非法

    // 从前往后移动元素，覆盖掉被删除的元素
    for (int i = index; i < length - 1; i++) {
        arr[i] = arr[i + 1];
    }

    length--; // 有效长度减 1
}

二、 STL array

std::array 在 C++11 中引入。它同样在栈上分配内存且大小在编译期固定，可以完美替代 C 风格的静态原生数组，并提供了更安全的 STL 容器特性。

#include <array>

std::array<int, 5> arr = {1, 2, 3, 4, 5};
arr[0] = 10;                    // 使用 [] 访问
arr.at(1) = 20;                 // at() 会进行越界检查，若越界会抛出异常

int size = arr.size();          // 随时获取大小
arr.fill(0);                    // 整体一键填充为 0
std::array<int, 5> arr2 = arr;  // 支持直接赋值拷贝

2.1 std::array 常用操作表

💡 使用要领与避坑提示： * arr[i] 与 arr.at(i) 的抉择：若确信下标不可能越界（如正常写法的 for 循环内），使用 arr[i]（无额外开销）；若下标来自外部输入或不可信数据源，推荐使用 arr.at(i) 用极小的性能代价确保系统安全。 * 无法增删：std::array 是静态定长容器，绝不支持 push_back 或 insert 等增删操作。若有动态改变容量的需求，应使用 std::vector。

三、 动态数组 vector

std::vector 是 C++ 标准库中最常用、最强大的顺序容器。它是可变长度的“动态数组”，能随着元素的增加自动在堆（Heap）上扩容。

3.1 std::vector 常用操作表

⚠️ 高频踩坑点与优化细节： 1. push_back vs emplace_back：对于基本数据类型（如 int），两者无异。但对于复杂对象（如 std::string 或自定义结构体），emplace_back 允许直接传入构造函数所需的参数，在堆底内存处直接构造，避免了不必要的临时拷贝。 2. 扩容代价与 reserve 优化：当 size == capacity 时再追加元素，vector 会触发自动扩容（一般为原容量的 $1.5$ 或 $2$ 倍），并在堆上寻找新地址，将旧数据整体拷贝迁移。若能提前预估数据规模，使用 v.reserve(n) 提前分配好空间，可以避免多次扩容迁移带来的巨大开销。 3. clear() 并不释放内存：执行 v.clear() 后，capacity 仍保持原样，并不会将内存还给系统。若要强制彻底归还内存，建议使用：vector<T>().swap(v); 或调用 v.shrink_to_fit();。 4. 迭代器失效问题：执行 insert 或 erase 后，由于内部元素发生了连续搬家，受影响位置之后的所有指针、引用和迭代器都将失效。在循环中删除元素时，必须使用返回的新迭代器更新当前位置：it = v.erase(it);。

四、 综合实例：木块问题（Blocks Problem）

下面通过一个综合实例，直观地对比静态数组、std::vector 以及 Python 解决数组元素查找、插入与删除的具体差异。

4.1 问题描述

最初平台上有 $n$ 个积木（编号从 $0$ 到 $n-1$），每一个积木 $b_i$ 初始都在第 $i$ 堆。机械臂操作指令如下： * move a onto b：先将 $a$ 和 $b$ 上面所有的积木放回各自的初始原堆，再将 $a$ 放在 $b$ 上。 * move a over b：先将 $a$ 上面的积木放回原堆，再将 $a$ 放在有 $b$ 的那一堆的最上方。 * pile a onto b：先将 $b$ 上面的积木放回原堆，然后将 $a$ 以及其上面所有的积木组成的一摞整体移动到 $b$ 上（保持原有顺序不变）。 * pile a over b：将 $a$ 以及其上面所有的积木组成的一摞整体移动到 $b$ 所在那一堆的最上面（保持原有顺序不变）。 * quit：结束操作，并输出最终每堆积木的状态。

4.2 代码实现对比

=== "静态数组实现（C++）" ```cpp #include #include

const int maxn = 30;
int n;
int pile[maxn][maxn];     // 二维静态数组存储积木
int pile_size[maxn];      // 手动维护每堆的实际逻辑长度

// 查找积木 a 所在的堆 p 和高度 h
void find_block(int a, int &p, int &h) {
    for (p = 0; p < n; p++) {
        for (h = 0; h < pile_size[p]; h++) { 
            if (pile[p][h] == a) return;
        }
    }
}

// 把堆 p 中高度 h 以上的所有积木放回原处
void clear_above(int p, int h) {
    for (int i = h + 1; i < pile_size[p]; i++) {
        int b = pile[p][i];
        pile[b][pile_size[b]] = b;   // 相当于 push_back
        pile_size[b]++;              // 维护长度
    }
    pile_size[p] = h + 1;           // 相当于 resize(h + 1)
}

// 把堆 p 中高度 h 及以上的一摞积木整体移动到堆 p2 的顶部
void pile_onto(int p, int h, int p2) {
    for (int i = h; i < pile_size[p]; i++) {
        pile[p2][pile_size[p2]] = pile[p][i]; // 拷贝
        pile_size[p2]++;                      // 维护长度
    }
    pile_size[p] = h;               // 截断该堆
}

void print() {
    for (int i = 0; i < n; i++) {
        printf("%d:", i);
        for (int j = 0; j < pile_size[i]; j++) 
            printf(" %d", pile[i][j]);
        printf("\n");
    }
}

int main() {
    int a, b; 
    char s1[10], s2[10];
    if (scanf("%d", &n) != 1) return 0;

    for (int i = 0; i < n; i++) {
        pile[i][0] = i;    // 初始化底座
        pile_size[i] = 1;  
    }

    while (scanf("%s %d %s %d", s1, &a, s2, &b) == 4) {
        if (strcmp(s1, "quit") == 0) break;
        int pa, pb, ha, hb;
        find_block(a, pa, ha);
        find_block(b, pb, hb);
        if (pa == pb) continue; // 同一堆的指令非法

        if (strcmp(s2, "onto") == 0) clear_above(pb, hb);
        if (strcmp(s1, "move") == 0) clear_above(pa, ha);
        pile_onto(pa, ha, pb);
    }
    print();
    return 0;
}
```

=== "std::vector 实现（现代 C++ 最佳实践）" ```cpp #include #include #include #include using namespace std;

int n;
vector<vector<int>> pile; // 使用二维动态 vector 存储积木，无需手动维护大小

// 查找积木 a 所在的堆 p 和高度 h
void find_block(int a, int &p, int &h) {
    for (p = 0; p < n; p++) {
        for (h = 0; h < (int)pile[p].size(); h++) {
            if (pile[p][h] == a) return;
        }
    }
}

// 把堆 p 中高度 h 以上的所有积木放回各自的初始位置
void clear_above(int p, int h) {
    for (int i = h + 1; i < (int)pile[p].size(); i++) {
        int b = pile[p][i];
        pile[b].push_back(b); // 直接放入对应编号的堆底
    }
    pile[p].resize(h + 1); // 一键缩减/截断堆，自动释放后面的元素
}

// 将堆 p 中从高度 h 开始的所有积木整体移动到堆 p2 的顶部
void pile_onto(int p, int h, int p2) {
    for (int i = h; i < (int)pile[p].size(); i++) {
        pile[p2].push_back(pile[p][i]);
    }
    pile[p].resize(h); // 截断
}

void print() {
    for (int i = 0; i < n; i++) {
        cout << i << ":";
        for (int val : pile[i]) {
            cout << " " << val;
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n)) return 0;
    pile.resize(n);
    for (int i = 0; i < n; i++) {
        pile[i].push_back(i);
    }

    string s1, s2;
    int a, b;
    while (cin >> s1 && s1 != "quit") {
        cin >> a >> s2 >> b;
        int pa, pb, ha, hb;
        find_block(a, pa, ha);
        find_block(b, pb, hb);
        if (pa == pb) continue;

        if (s2 == "onto") clear_above(pb, hb);
        if (s1 == "move") clear_above(pa, ha);
        pile_onto(pa, ha, pb);
    }
    print();
    return 0;
}
```

=== "Python 列表实现（简洁而动态）" ```python import sys

def find_block(a, n, pile):
    for p in range(n):
        for h in range(len(pile[p])):
            if pile[p][h] == a:
                return p, h
    return -1, -1

def clear_above(p, h, pile):
    # 将高度 h 以上的所有积木送回初始位置
    for i in range(h + 1, len(pile[p])):
        b = pile[p][i]
        pile[b].append(b)
    pile[p] = pile[p][:h + 1] # 切片截断

def pile_onto(p, h, p2, pile):
    # 整体搬运
    pile[p2].extend(pile[p][h:])
    pile[p] = pile[p][:h] # 切片截断

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    pile = [[i] for i in range(n)] # 列表初始化

    idx = 1
    while idx < len(input_data):
        s1 = input_data[idx]
        if s1 == "quit":
            break
        a = int(input_data[idx + 1])
        s2 = input_data[idx + 2]
        b = int(input_data[idx + 3])
        idx += 4

        pa, ha = find_block(a, n, pile)
        pb, hb = find_block(b, n, pile)
        if pa == pb:
            continue

        if s2 == "onto":
            clear_above(pb, hb, pile)
        if s1 == "move":
            clear_above(pa, ha, pile)
        pile_onto(pa, ha, pb, pile)

    # 打印结果
    for i in range(n):
        blocks_str = "".join(f" {x}" for x in pile[i])
        print(f"{i}:{blocks_str}")

if __name__ == "__main__":
    main()
```

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com