451 lines
10 KiB
Markdown
451 lines
10 KiB
Markdown
# 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. 想一想
|
||
|
||
- 为什么插入和删除都可能需要移动很多个元素？
|
||
- 如果总是在数组最前面插入，会不会很麻烦？
|
||
|
||
如果你能清楚地回答这两个问题，就说明你已经真正理解数组的插入和删除了。 |