3.3 数组元素的插入

“小朋友们，”我转向另一个话题，”如果我们想在玩具箱中间添加一个新玩具，其他玩具需要向后移动，给新玩具腾出位置。数组的插入操作也是这样的原理！”

3.3.1 指定位置插入元素

题目描述： 在一个数组的第 x 个位置插入一个新的数y。

输入格式：

• 第一行有一个整数 n (5≤n≤10）
• 第二行有 n 个整数，用空格隔开
• 第三行有一个整数 x，为要插入的位置
• 第四行有一个整数 y，为要插入的整数

输出格式： 更新后的数组。

样例输入：

5
7 2 3 4 5
2
9

样例输出：

7 9 2 3 4 5

代码实现：

#include <iostream>
using namespace std;

int main() {
    int a[15];    // 定义数组，预留足够空间
    int n;        // 数组长度
    cin >> n;
    
    for(int i = 1; i <= n; i++) 
        cin >> a[i];    // 输入n个数
    
    int x, y;    // x为插入位置，y为插入的值
    cin >> x >> y;
    
    // 方法一：直接输出，在指定位置插入新元素
    for(int i = 1; i <= n; i++) {
        if(i == x) 
            cout << y << " ";    // 在插入位置输出新值
        cout << a[i] << " ";     // 输出原有元素
    }
    if(x > n) 
        cout << y;    // 如果插入位置在数组末尾之后，则单独输出
    
    /*
    // 方法二：移动元素后插入
    for(int i = n; i >= x; i--) {
        a[i+1] = a[i];    // 将插入位置及其后的元素向后移动一位
    }
    a[x] = y;             // 在空出的位置插入新值
    
    for(int i = 1; i <= n+1; i++) 
        cout << a[i] << " ";    // 输出n+1个元素
    */
    
    return 0;
}

算法解析：

方法一：

1. 遍历原数组的元素
2. 当到达插入位置时，先输出新值，再输出原有元素
3. 如果插入位置超出数组原有长度，则在最后单独输出新值

方法二：

1. 从数组末尾开始向前遍历，将元素向后移动一位
2. 在空出的位置插入新值
3. 输出包含新元素的数组（长度增加了1）