# 2.2 数组的插入与删除

---

## 一、先把数组想成一排固定座位

今天我们只学两件事：

- 往数组里放进一个新元素，这叫**插入**。
- 从数组里拿走一个元素，这叫**删除**。

数组可以想成教室里一排**紧紧挨着的固定座位**，每个位置都不能乱跳。

比如下面这个数组：

| 位置（第几个） | 第1个 | 第2个 | 第3个 | 第4个 | 第5个 |
|:---:|:---:|:---:|:---:|:---:|:---:|
| 下标 | 0 | 1 | 2 | 3 | 4 |
| 内容 | 12 | 18 | 23 | 31 | 40 |

这里要特别注意：

- 平时说“第 1 个位置、第 2 个位置”，是按照人的习惯数的。
- 在 C++ 数组里，下标从 `0` 开始。

所以：

- 第 1 个位置，对应下标 `0`
- 第 3 个位置，对应下标 `2`
- 第 `pos` 个位置，对应下标 `pos - 1`

> 这节课讲图的时候，我们主要说“第几个位置”；写代码的时候，再换成下标。

---

## 二、为什么数组的插入和删除要“搬家”？

数组里的元素是**连续排在一起**的。

这就像一排已经坐好的同学：

- 想在中间插入一个人，就得有人挪一挪，腾出空位。
- 想删掉中间一个人，就会空出一个洞，后面的人要补上来。

所以数组的插入和删除，最关键的不是“放进去”或“拿出来”，而是：

> **怎样移动其他元素，才能既不丢数据，也不弄乱顺序。**

这就是本节最重要的地方。

---

## 三、数组插入：先腾位置，再放新元素

### 1. 例子：在第 3 个位置插入 20

原数组：

```text
位置：   1    2    3    4    5    6
内容： [12] [18] [23] [31] [40] [  ]
```

注意：这里第 6 个位置先留空，表示数组容量足够大，可以插入新元素。

现在要把 `20` 插入到**第 3 个位置**。

插入后应该变成：

```text
位置：   1    2    3    4    5    6
内容： [12] [18] [20] [23] [31] [40]
```

### 2. 插入时，元素是怎样移动的？

要想让第 3 个位置空出来，原来第 3、4、5 个位置上的元素都要向后移动一格。

但一定要记住：

> **插入时，要从后往前移。**

移动过程如下：

```text
原来：   [12] [18] [23] [31] [40] [  ]
第1步：  [12] [18] [23] [31] [40] [40]   把 40 往后移
第2步：  [12] [18] [23] [31] [31] [40]   把 31 往后移
第3步：  [12] [18] [23] [23] [31] [40]   把 23 往后移
第4步：  [12] [18] [20] [23] [31] [40]   把 20 放进第 3 个位置
```

### 3. 为什么插入要从后往前移？

因为如果你从前往后移，前面的数据会把后面的数据盖掉。

来看一个错误示范。还是在第 3 个位置插入 `20`：

```text
原来：   [12] [18] [23] [31] [40] [  ]

错误地从前往后移：
第1步：  [12] [18] [23] [23] [40] [  ]
第2步：  [12] [18] [23] [23] [23] [  ]
第3步：  [12] [18] [23] [23] [23] [23]
```

你会发现：原来的 `31` 和 `40` 都不见了！

原因是：

- 你先把 `23` 复制到了后面。
- 后面的位置被改掉以后，再继续搬，就只能搬到已经改坏的数据。

所以插入时一定要：

> **从最后一个元素开始，倒着往前挪。**

### 4. 插入的步骤口诀

可以记成一句话：

> **先留空，从后搬，最后放。**

具体就是：

1. 先保证数组后面有空位置。
2. 从最后一个元素开始，依次向后移动一格。
3. 移到目标位置后停下。
4. 把新元素放进去。
5. 数组长度 `n` 加 1。

### 5. 插入的课堂版 C++ 代码

下面的代码约定：

- 数组现在有 `n` 个元素。
- 要把 `x` 插入到第 `pos` 个位置。
- `pos` 从 `1` 开始数。
- 数组容量足够大。

```cpp
for (int i = n; i >= pos; i--) {
    a[i] = a[i - 1];
}
a[pos - 1] = x;
n++;
```

你可以这样理解这段循环：

- `i = n` 时，把最后一个元素搬到新位置。
- `i = n - 1` 时，把倒数第二个元素往后搬。
- 一直搬到第 `pos` 个位置为止。

---

## 四、数组删除：先补空位，再缩短长度

### 1. 例子：删除第 3 个位置的元素

原数组：

```text
位置：   1    2    3    4    5
内容： [ 8] [11] [14] [17] [20]
```

现在要删除第 3 个位置上的 `14`。

删除后应该变成：

```text
位置：   1    2    3    4
内容： [ 8] [11] [17] [20]
```

### 2. 删除时，元素是怎样移动的？

第 3 个位置删掉以后，会空出一个位置。后面的元素要依次往前补。

注意：

> **删除时，要从前往后移。**

移动过程如下：

```text
原来：   [ 8] [11] [14] [17] [20]
第1步：  [ 8] [11] [17] [17] [20]   把 17 往前移
第2步：  [ 8] [11] [17] [20] [20]   把 20 往前移
最后：   [ 8] [11] [17] [20]        长度减 1
```

最后那个多出来的 `20` 虽然还留在原来的地方，但因为数组长度已经减 1，所以它已经**不算数组的一部分了**。

### 3. 为什么删除要从前往后移？

因为空位在前面，应该让后面的元素一个一个补上来。

如果你反过来，从后往前移，也会出问题。还是删除第 3 个位置：

```text
原来：   [ 8] [11] [14] [17] [20]

错误地从后往前移：
第1步：  [ 8] [11] [14] [20] [20]
第2步：  [ 8] [11] [20] [20] [20]
```

原来的 `17` 被弄丢了。

所以删除时要记住：

> **从缺口的后面开始，按顺序往前补。**

### 4. 删除的步骤口诀

可以记成一句话：

> **先删掉，从前搬，最后减。**

具体就是：

1. 找到要删除的位置。
2. 让后面的元素依次向前移动一格。
3. 数组长度 `n` 减 1。

### 5. 删除的课堂版 C++ 代码

下面的代码约定：

- 数组现在有 `n` 个元素。
- 删除第 `pos` 个位置上的元素。
- `pos` 从 `1` 开始数。

```cpp
for (int i = pos; i < n; i++) {
    a[i - 1] = a[i];
}
n--;
```

你可以这样理解这段循环：

- `i = pos` 时，把后一个元素补到空位上。
- `i = pos + 1` 时，再把更后面的元素补上来。
- 一直补到最后一个元素为止。

---

## 五、插入和删除放在一起比较

| 操作 | 会发生什么 | 正确移动方向 | 为什么 |
|:---:|:---|:---:|:---|
| 插入 | 中间要腾出一个空位 | 从后往前 | 先保护后面的数据，不让它们被覆盖 |
| 删除 | 中间会出现一个缺口 | 从前往后 | 让后面的数据按顺序补上来 |

再记一遍：

- **插入：从后往前移**
- **删除：从前往后移**

这是本节最重要的结论。

---

## 六、两个最容易忽略的小细节

### 1. 插入前，数组要有空位

如果数组已经装满了，就不能直接插入。

比如数组最多只能放 5 个数，现在已经有 5 个数了，再插入第 6 个，就没有地方放了。

所以写程序时，常常会这样做：

- 开一个更大的数组，比如最多放 `100` 个数。
- 实际已经用了多少个，用变量 `n` 记录。

### 2. 删除后，不是把数“擦掉”，而是把长度减 1

数组删除一个元素后，最后那个位置里可能还保留着旧数值，但这已经不重要了。

因为程序只看前 `n` 个元素：

- 删除前看前 `n` 个
- 删除后只看前 `n - 1` 个

所以真正关键的是：

> **长度变了，数组有效范围也变了。**

---

## 七、特殊情况也要会判断

### 1. 在最后面插入

如果要在第 `n + 1` 个位置插入，也就是直接接到数组末尾：

```text
[12] [18] [23] [31] [40]  ->  [12] [18] [23] [31] [40] [50]
```

这时不需要搬动任何元素，直接放进去即可。

### 2. 删除最后一个元素

如果删除的是最后一个元素：

```text
[12] [18] [23] [31] [40]  ->  [12] [18] [23] [31]
```

这时也不需要搬动任何元素，只要把长度减 1 就行。

---

## 八、最容易犯的 5 个错误

### 错误 1：插入时移动方向写反

结果：后面的数据会被覆盖。

### 错误 2：删除时移动方向写反

结果：中间的数据会丢失。

### 错误 3：忘记更新 `n`

插入后忘记 `n++`，新元素虽然放进去了，但程序可能不把它算进去。

删除后忘记 `n--`，旧数据虽然应该消失了，但程序还会把它输出出来。

### 错误 4：把“第几个位置”和“下标”搞混

记住：

- 第 `1` 个位置，对应下标 `0`
- 第 `pos` 个位置，对应下标 `pos - 1`

### 错误 5：插入时没有预留空间

结果：数组越界，程序可能出错。

---

## 九、一张总图记住本节内容

```text
数组插入：先腾空位

[12] [18] [23] [31] [40] [  ]
                    ←  ←  ←
[12] [18] [20] [23] [31] [40]


数组删除：先补缺口

[ 8] [11] [14] [17] [20]
               →   →
[ 8] [11] [17] [20]
```

记忆口诀：

> **插入看后面，从后往前搬；删除看前面，从前往后搬。**

---

## 十、课堂版完整示例

下面是一份把“插入”和“删除”都写进去的课堂版程序。为了简单起见，输入位置 `pos` 按“第几个位置”来理解，也就是从 `1` 开始数。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
int a[MAXN];
int n;

void insertValue(int pos, int x) {
    for (int i = n; i >= pos; i--) {
        a[i] = a[i - 1];
    }
    a[pos - 1] = x;
    n++;
}

void deleteValue(int pos) {
    for (int i = pos; i < n; i++) {
        a[i - 1] = a[i];
    }
    n--;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int pos, x;
    cin >> pos >> x;
    insertValue(pos, x);

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";

    cin >> pos;
    deleteValue(pos);

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";

    return 0;
}
```

---

## 十一、自己试一试

### 1. 观察移动过程

把 `9` 插入到下面数组的第 2 个位置，请你把每一步移动都画出来：

```text
[3] [7] [12] [15] [  ]
```

### 2. 观察删除过程

删除下面数组的第 4 个位置，请你把每一步移动都画出来：

```text
[5] [8] [11] [14] [20]
```

### 3. 想一想

- 为什么插入和删除都可能需要移动很多个元素？
- 如果总是在数组最前面插入，会不会很麻烦？

如果你能清楚地回答这两个问题，就说明你已经真正理解数组的插入和删除了。