首页 > 编程语言 >【NOI】C++数据结构入门之一维数组（三）元素移动

【NOI】C++数据结构入门之一维数组（三）元素移动

时间：2024-08-26 15:23:59浏览次数：15  
标签：NOI int 元素 C++ 插入 数组 数据结构 输入 逆序

文章目录

前言

在继续我们的C++数据结构学习之旅中，今天我们深入探讨了一维数组的元素移动，这是全国青少年信息学奥林匹克竞赛（NOI）准备过程中的一个重要环节。上一讲我们讨论了数组的基础操作，包括创建、访问、修改和遍历，以及如何在数组中查找特定的元素。今天，我们进一步拓展了知识面，学习了如何通过逆序、删除和插入操作来动态调整数组中的元素位置，这是解决复杂算法问题和优化数据结构管理的关键技能。

在这一讲中，我们不仅讲解了理论概念，还通过具体的例题演示了如何在C++中实现这些操作。我们从逆序数组开始，介绍了两种方法：一种是通过逆序遍历来“假装”逆序，适用于仅需输出逆序数组的情况；另一种是真正的逆序，通过交换数组元素来实现。随后，我们探讨了数组元素的删除，同样提供了两种方法：一种是通过“忽略”特定位置的元素来模拟删除，适用于仅需输出修改后的数组的情况；另一种是通过覆盖元素来真正实现删除。最后，我们讲解了数组元素的插入，通过移动数组元素为新元素腾出空间，再将新元素置入。

欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》

学习路线：C++从入门到NOI学习路线

学习大纲：C++全国青少年信息学奥林匹克竞赛（NOI）入门级-大纲

一、概念

1.导入

上一讲中，我们在学习了数组创建、访问、修改、遍历的基础上解决了数组找数（在给定的数组中寻找特定元素、满足一定条件的元素或执行某种操作的问题。）的问题。

今天我们将要通过“逆序”、“删除”和“插入”的操作来解决数组元素移动的问题。

在这里插入图片描述

2.元素移动

2.1 逆序

在数组问题中，常常会要求你将数组逆序后输出，或者需要在逆序后进行其他操作，面对这种问题，我们应该如何解决呢？

  1. 方法一：假逆序

不进行逆序操作，而是逆序遍历数组输出。以“骗样例”的方式，通过oj的检查。

在这里插入图片描述

该方法只适合输出逆序数组的问题，如果还有其他操作就得学会方法二。

  1. 方法二：真逆序

逆序，无非就是让前面的元素挪到后面去。

因此我们可以将将前面的元素和后面的元素进行交换即可。

在这里插入图片描述

当然，肯定要对称才行。例如第一元素和最后一个元素交换，第二个元素和倒数第二个元素交换。由此也能看出交换的次数是数组长度的一半。

具体怎么做请看后面的例题《1009. 数组逆序》。

2.2 删除

首先需要知道的是，我们学习的静态数组并没有直接进行删除的方法，而是通过一系列的操作，模拟删除的效果。

  1. 方法一：假删除

和我们假逆序的方法一是一样的，以“骗样例”的方式，通过oj的检查。

在这里插入图片描述

具体操作是：不删除，输出数组所有元素，如果遇到下标为x(i==x)，则不输出!

该方法一样只适合输出数组元素的问题，如果还有其他操作就得学会方法二。

  1. 方法二：真删除

在C++中，静态数组（即在声明时就确定了大小的数组）的内存是静态分配的，这意味着一旦创建，其大小就不能改变。因此，如果您想从静态数组中“删除”一个元素，实际上不能真正地缩小该数组的大小或重新分配内存。

相反，常见的做法是将数组中您希望保留的元素移动到被“删除”元素的前面，覆盖掉不需要的元素，从而实现元素的移除效果。

可以用一句话简单理解，长江后浪推前浪。

在这里插入图片描述

具体怎么做请看后面的例题《1162. 数组元素的删除》。

2.3 插入

这次只有真的QAQ。

在这里插入图片描述

方法：

逆序循环下标为 n-1~x结束（数组从0开始），将元素顺序后移(a[i+1]=a[i])，空出下标为x的位置。然后将a[x]赋值为你想插入的数即可。

具体怎么做请看后面的例题《1211. 数组元素的插入》。

二、例题讲解

问题：1009 - 数组逆序

类型：数组元素移动

题目描述：

给你 m 个整数，将其逆序输出。

输入：

第一行一个整数 m （3≤m≤100)代表数的个数。

第二行 m 个整数（空格隔开）（这些数在 0∼10^6之间)。

输出：

m 个整数（空格隔开）。

样例：

输入：

3
1 7 5

输出：

5 7 1

在这里插入图片描述

1.分析问题

  1. 已知：用户将输入m个整数。
  2. 未知：需要逆序输出这些整数。
  3. 关系：通过交换数组元素的位置实现逆序。

2.定义变量

  • 用于存储数组的长度，即用户将输入的整数的数量。
  • 定义一个最大长度为100的数组，用于存储用户输入的整数。
    // 二、数据定义
    int n; 
    int a[100];

3.输入数据

  • 输入数组的长度。
  • 逐个输入整数，并存储在数组中。
 // 三、数据输入
    cin >> n; 
    for(int i = 0; i < n; i++){
        cin >> a[i]; 
    }

4.数据计算

  • 使用一个循环遍历数组的前半部分，通过交换数组两端的元素来实现逆序。
  	// 四、数据计算 - 实现逆序
    int temp; 
    for(int i = 0; i < n / 2; i++){ 
        temp = a[i];
        a[i] = a[n - i - 1]; 
        a[n - i - 1] = temp; 
    }

5.输出结果

  • 逐个输出逆序后的数组元素。
  // 五、输出结果
    for(int i = 0; i < n; i++){
        cout << a[i] << " "; 
    }

完整代码如下：

#include<iostream>
using namespace std;
int main(){
    // 一、分析问题
    // 已知：用户将输入m个整数
    // 未知：需要逆序输出这些整数
    // 关系：通过交换数组元素的位置实现逆序
    
    // 二、数据定义
    int n; // 用于存储数组的长度，即用户将输入的整数的数量
    int a[100]; // 定义一个最大长度为100的数组，用于存储用户输入的整数
    
    // 三、数据输入
    cin >> n; // 输入数组的长度
    for(int i = 0; i < n; i++){
        cin >> a[i]; // 逐个输入整数，并存储在数组中
    }
    
    // 四、数据计算 - 实现逆序
    int temp; // 用于临时存储数组元素，以便交换
    for(int i = 0; i < n / 2; i++){ // 只需遍历数组前半部分
        temp = a[i]; // 将当前元素存储在temp中
        a[i] = a[n - i - 1]; // 将对应位置的后半部分元素放到前半部分
        a[n - i - 1] = temp; // 将temp中的元素放到后半部分
    }
    
    // 五、输出结果
    for(int i = 0; i < n; i++){
        cout << a[i] << " "; // 逐个输出逆序后的数组元素
    }
    
    return 0; // 主函数正常结束
}

问题：1162 - 数组元素的删除

类型：数组元素移动

题目描述：

把一个数组的第 x 个位置的元素删除掉。

输入：

输出有三行：

第一行有一个整数 n ( n≤10 )；

第二行有 n 个整数（每个整数在1~1000之间）；

第三行有一个整数 x（1≤x≤n），为要删除的位置。

输出：

输出更新后的数组。

样例：

输入：

5
1 2 3 4 5 
3

输出：

1 2 4 5

在这里插入图片描述

1.分析问题

  1. 已知：用户将输入一个数组和一个要删除的元素的位置。
  2. 未知：删除指定位置的元素后的新数组。
  3. 关系：将指定位置之后的所有元素向前覆盖移动一位。

2.定义变量

  • n：数组的长度。
  • x:：要删除的元素的位置。
    // 二、数据定义
    int n; 
    int a[100]; 
    int x;

3.输入数据

  • 输入数组的长度。
  • 逐个输入数组元素 。
  • 输入要删除的元素的位置。
  // 三、数据输入
    cin >> n; 
    for(int i = 0; i < n; i++){
        cin >> a[i]; 
    }
    cin >> x;

4.数据计算

  • C++数组的下标从0开始，所以将输入的位置减1。
  • 将指定位置之后的元素向前覆盖移动一位。
    // 四、数据计算 - 删除指定位置的元素
    --x; 
    for(int i = x; i < n - 1; i++){
        a[i] = a[i + 1]; 
    }

5.输出结果

  • 逐个输出数组元素。
    // 五、输出结果 - 输出删除元素后的数组
    for(int i = 0; i < n - 1; i++){
        cout << a[i] << " "; 
    }

完整代码如下：

#include<iostream>
using namespace std;

int main(){
    // 一、分析问题
    // 已知：用户将输入一个数组和一个要删除的元素的位置。
    // 未知：删除指定位置的元素后的新数组。
    // 关系：将指定位置之后的所有元素向前覆盖移动一位。

    // 二、数据定义
    int n; // 数组的长度
    int a[100]; // 数组，最大长度为100
    int x; // 要删除的元素的位置

    // 三、数据输入
    cin >> n; // 输入数组的长度
    for(int i = 0; i < n; i++){
        cin >> a[i]; // 逐个输入数组元素
    }
    cin >> x; // 输入要删除的元素的位置

    // 四、数据计算 - 删除指定位置的元素
    --x; // C++数组的下标从0开始，所以将输入的位置减1
    for(int i = x; i < n - 1; i++){
        a[i] = a[i + 1]; // 将指定位置之后的元素向前覆盖移动一位
    }

    // 五、输出结果 - 输出删除元素后的数组
    for(int i = 0; i < n - 1; i++){
        cout << a[i] << " "; // 逐个输出数组元素
    }

    return 0; // 主函数正常结束
}

问题：1211 - 数组元素的插入

类型：数组元素移动

题目描述：

在一个数组的第 x 个位置插入一个新的数y。

输入：

有四行 第一行有一个整数 n (5≤n≤10）；

第二行有 n 个整数，用空格隔开；

第三行有一个整数 x，为要插入的位置；

第四行有一个整数 y，为要插入的整数。

输出：

更新后的数组。

样例：

输入：

5
7 2 3 4 5
2
9

输出：

7 9 2 3 4 5

在这里插入图片描述

1.分析问题

  1. 已知：一个数组。
  2. 未知：更新后的数组。
  3. 关系：在 x 个位置插入一个新的数 y。

2.定义变量

  • n 是数组的原始长度。
  • a[100] 是用于存储数组元素的数组，最大长度为100。
  • x 是要插入新元素的位置。
  • y 是要插入的新元素。
	//二、数据定义 
	int n,a[100],x,y;

3.输入数据

  • 首先读取数组的长度n。
  • 接着读取n个数组元素并存储在a中。
  • 然后读取插入位置x和新值y。
	//三、数据输入 
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cin>>x;
	cin>>y;

4.数据计算

  • 将插入位置x减1，因为数组下标是从0开始的。
  • 从数组的末尾开始，将每个元素向后移动一位，直到到达位置x。
  • 在位置x处放置新值y。
	//四、数据计算 
	--x;
	for(int i=n;i>=x;i--){
		a[i]=a[i-1];
	}
	a[x]=y;

5.输出结果

  • 打印出更新后的数组，包括新插入的元素。
	//五、输出结果 
	for(int i=0;i<n+1;i++){
		cout<<a[i]<<" ";
	}

完整代码如下：

#include<iostream> // 引入标准输入输出流库
using namespace std; // 使用std命名空间，避免每次调用输入输出函数时都加上std::

int main(){
    // 一、分析问题
    // 已知：一个数组
    // 未知：更新后的数组
    // 关系：在 x 个位置插入一个新的数 y

    // 二、数据定义
    int n, a[100]; // 定义一个整型变量n和一个最多有100个元素的整型数组a
    int x, y;      // 定义插入的位置x和新元素y

    // 三、数据输入
    cin >> n;      // 输入数组的长度
    for(int i = 0; i < n; i++){ // 循环读取数组的元素
        cin >> a[i];            // 读取第i个元素并存入数组a
    }
    cin >> x;                   // 输入插入的位置
    cin >> y;                   // 输入要插入的元素

    // 四、数据计算
    --x;                        // 由于数组索引从0开始，所以插入位置需要减1
    for(int i = n; i >= x; i--){ // 从数组的末尾开始，将所有元素向后移动一位
        a[i] = a[i-1];          // 将第i-1个元素复制到第i个位置
    }
    a[x] = y;                   // 在位置x处插入新元素y

    // 五、输出结果
    for(int i = 0; i <= n; i++){ // 注意这里使用<=n，因为数组现在多了一个元素
        cout << a[i] << " ";    // 输出数组中的每一个元素
    }
    return 0;                   // 主函数结束，返回0表示程序正常结束
}

问题：1161. 元素插入有序数组

类型：数组元素移动

题目描述：

给你一个整数 n 和一个数列(数列个数不超过 1000 )，这个数列保证从小到大排列，现要求将这个整数 n 插入到数列中，使新的数列仍然从小到大排列。

输入：

第一行一个整数 n 表示等待插入的数 ；

第二行一个整数 m 表示数列中数的个数；

第三行 m 个整数（空格隔开）。

输出：

一行整数：新的数列（空格隔开）。

样例：

输入：

2
4
1 3 4 5

输出：

1 2 3 4 5

在这里插入图片描述

1.分析问题

  1. 已知：一个整数 n 和一个m大小有序数列。
  2. 未知：新的数列（在原数列中插入n后）。
  3. 关系: 整数 n 插入到数列，数列仍然从小到大排列。

2.定义变量

  • n：待插入的整数。
  • m：数组的原始长度。
  • a[1010]：一个大小为1010的数组，用来存储原始的数组元素和即将插入的整数。
  • idx：插入点的索引，初始化为0。
    int n, m, a[1010], idx = 0;

3.输入数据

  • 读取待插入的整数n和数组的原始长度m。
    cin >> n;
    cin >> m;
  • 首先读取数组的元素，然后检查每个元素是否小于n。如果是，则更新idx为当前元素的下一个位置的索引，这样idx最终将指向第一个大于或等于n的元素的位置，或者在所有元素都小于n的情况下，指向数组的末尾。
    for(int i = 0; i < m; i++){
        cin >> a[i];
        if(a[i] < n){
            idx = i + 1;
        }
    }

4.数据计算

  • 将数组中从idx开始的所有元素向后移动一个位置，为插入n腾出空间。然后在idx位置插入n。
    for(int i = m; i > idx; i--){
        a[i] = a[i-1];
    }
    a[idx] = n;

5.输出结果

  • 输出更新后的数组，包括新插入的元素n。
    for(int i = 0; i <= m; i++){
        cout << a[i] << " ";
    }

完整代码如下：

#include<bits/stdc++.h> // 引入C++标准库中的所有头文件
using namespace std; // 使用标准命名空间

int main(){
    // 一、分析问题
    // 已知：一个整数 n 和一个m大小有序数列。
    // 未知：新的数列（在原数列中插入n后）。
    // 关系: 整数 n 插入到数列，数列仍然从小到大排列。

    // 二、定义变量（已知、未知、关系）
    int n, m, a[1010]; // 定义整数n，数列长度m，和最多可包含1010个元素的数组a
    int idx = 0;       // 定义idx作为插入点的索引

    // 三、输入已知
    cin >> n;          // 输入要插入的整数n
    cin >> m;          // 输入数列的长度m
    for(int i = 0; i < m; i++){
        cin >> a[i];   // 输入数列的每个元素
        if(a[i] < n){  // 检查当前元素是否小于n
            idx = i + 1; // 如果是，更新插入点的索引
        }
    }

    // 四、根据关系计算
    for(int i = m; i > idx; i--){ // 从数列的末尾开始，将所有元素向后移动一位，直到idx
        a[i] = a[i-1];            // 将第i-1个元素复制到第i个位置
    }
    a[idx] = n;                  // 在找到的插入点idx处插入n

    // 五、输出未知
    for(int i = 0; i <= m; i++){ // 输出更新后的数列
        cout << a[i] << " ";     // 注意：这里i <= m是因为数组大小增加了1
    }

    return 0;                    // 正常退出程序
}

问题：1159. 数组元素的移动

类型：数组元素移动

题目描述：

数组元素的移动，把数组的第 x 个位置的元素先保存起来，然后把 x+1 到 n 的元素，依次往前移一位，最后原来的第 x 个位置的元素放在最后。

输入：

有 3 行

第一行有一个整数 n (n≤10 )；

第二行有 n 个整数；

第三行有一个整数 x 。

输出：

移动后的数组。

样例：

输入：

8
1 2 3 4 5 6 7 8
1

输出：

2 3 4 5 6 7 8 1

在这里插入图片描述

1.分析问题

  1. 已知：一个n大小的数组，x坐标。
  2. 未知：移动后的数组。
  3. 关系: 把数组的第 x 个位置的元素先保存起来，然后把 x+1 到 n 的元素，依次往前移一位，最后原来的第 x 个位置的元素放在最后。

2.定义变量

  • n：数组的长度。
  • a[20]：数组，用于存储n个整数。
  • x：需要移动的元素的索引位置。
	//二、定义变量（已知、未知、关系） 
	int n,a[20],x;

3.输入数据

  • 首先读取数组的长度n。
  • 然后读取n个数组元素。
  • 最后读取要移动的元素的索引x。
	//三、输入已知
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cin>>x;

4.数据计算

  • 将x减1，因为数组索引是从0开始的。
  • 保存第x个位置的元素到临时变量t中。
  • 从x开始，将x+1到n-1的每个元素向前移动一位，覆盖原来的位置。
  • 将原先的第x个元素（保存在t中）放到数组的末尾。
	//四、根据关系计算
	--x;
	int t=a[x];
	for(int i=x;i<n-1;i++){
		a[i]=a[i+1];
	}
	a[n-1]=t;

5.输出结果

  • 打印更新后的数组。
	//五、输出未知 
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}

完整代码如下：

#include<bits/stdc++.h> // 包含C++标准库中的所有头文件
using namespace std; // 使用std命名空间中的所有元素

int main(){
    // 一、分析问题
    // 已知：一个大小为n的数组和一个坐标x。
    // 未知：移动元素后的数组。
    // 关系：将数组的第x个位置的元素移到数组的末尾，同时保持其他元素的相对顺序不变。

    // 二、定义变量
    int n; // 数组的长度
    int a[20]; // 数组，最多可容纳20个整数
    int x; // 需要移动的元素的索引位置

    // 三、输入已知数据
    cin >> n; // 输入数组的长度
    for(int i = 0; i < n; i++){
        cin >> a[i]; // 输入数组的每个元素
    }
    cin >> x; // 输入要移动的元素的索引位置

    // 四、根据关系计算
    --x; // 调整x为基于0的索引
    int t = a[x]; // 保存要移动的元素
    for(int i = x; i < n - 1; i++){ // 移动元素
        a[i] = a[i + 1]; // 将后面的元素移动到当前位置
    }
    a[n - 1] = t; // 将原先的元素放到数组的末尾

    // 五、输出未知数据
    for(int i = 0; i < n; i++){
        cout << a[i] << " "; // 输出更新后的数组
    }

    return 0; // 返回0，表示程序正常结束
}

三、总结

今天的学习重点是掌握数组元素的逆序、删除和插入操作。我们了解了不同场景下选择合适方法的重要性，以及如何在C++中高效地实现这些操作。

我们通过以下关键点总结今日所学：

  1. 逆序可以通过对称交换数组元素来实现。
  2. 删除元素可以通过覆盖法，即移动后续元素来模拟。
  3. 插入元素需要先移动数组中相应位置的元素，为新元素腾出空间。

四、感谢

如若本文对您的学习或工作有所启发和帮助，恳请您给予宝贵的支持——轻轻一点，为文章点赞；若觉得内容值得分享给更多朋友，欢迎转发扩散；若认为此篇内容具有长期参考价值，敬请收藏以便随时查阅。

每一次您的点赞、分享与收藏，都是对我持续创作和分享的热情鼓励，也是推动我不断提供更多高质量内容的动力源泉。期待我们在下一篇文章中再次相遇，共同攀登知识的高峰！

在这里插入图片描述

标签：NOI,int,元素,C++,插入,数组,数据结构,输入,逆序
From： https://blog.csdn.net/qq_39180358/article/details/140486180

相关文章

  • UE5蓝图 离线实时语音转文字插件 教程 c/c++插件 毫秒级响应 比http更节约资源
    UE5蓝图实现离线实时语音转文字插件教程如何用UE5蓝图实现离线实时语音转文字，实时接收麦克风音频并且快速的转换成文字。那么我来分享一下ez2txt这个插件。bilibili使用教程效果展示：蓝图：只要启动麦克风就可以了，其他的繁琐步骤插件都封装好了。参数说明Rule1_m......
  • C++智能指针
    文章目录RAIIauto_ptrunique_ptrshare_ptrshared_ptr的线程安全问题shared_ptr循环引用weak_ptrRAIIRAII（ResourceAcquisitionIsInitialization）是一种利用对象生命周期来控制程序资源（如内存、文件句柄、网络连接、互斥量等等）的简单技术。在对象构造时获取资源，接......
  • 学懂C++（四十四）：C++ 自定义内存管理的深入解析：内存池与自定义分配器
    目录1.内存池（MemoryPool）概念模型特点核心点实现适用场景经典示例实现代码解析2.自定义分配器（CustomAllocators）概念模型特点核心点实现适用场景经典示例实现代码解析高级自定义分配器示例代码解析总结        C++作为一种高性能编程语言，在......
  • c++关键字
    关键字作用：关键字是C++中预先保留的单词（标识符）在定义变量或者常量时候，不要用关键字C++关键字如下：关键字1.asmasm(指令字符串)：允许在C++程序中嵌入汇编代码。2.autoauto（自动，automatic）是存储类型标识符，表明变量"自动"具有本地范围，块范围的变量声明（如for循环体内的......
  • 【C++】初识C++模板与STL
    C++语法相关知识点可以通过点击以下链接进行学习一起加油！命名空间缺省参数与函数重载C++相关特性类和对象-上篇类和对象-中篇类和对象-下篇日期类C/C++内存管理本章将简单分享C++模板与STL相关知识，与之相关更多知识将留到下次更详细地来分享给大家......
  • vscode 编译c++项目如何配置
    配置c_cpp_properties.json文件主要用于辅助vscode智能代码提示、预定义编译宏定义示例如下：{"configurations":[{"name":"Win32","includePath":["${workspaceFolder}/**",......
  • 微软常用运行库合集|dll报错必装，Visual C++ 下载安装
    前言MicrosoftVisualC++Redistributable（简称MSVC，VB/VC，系统运行库）是Windows操作系统应用程序的基础类型库组件。此版VisualC++运行库组件合集（微软常用运行库合集）由国内封装爱好者@Dreamcast打包而成，整合VisualC++组件安装包运行库所有版本，提供图形安装界面，可自选更新V......
  • 算法与数据结构——内存与缓存
    内存与缓存数组和链表两种数据结构分别代表了“连续存储”和“分散存储”两种物理结构。实际上，物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能。计算机存储设备计算机中包括三种类型的存储设备：硬盘（harddisk）、内存（random-accessmemory，RAM）、......
  • C++学习随笔——简单的单例设计模式实例
    点击查看代码#include<iostream>classSingleton{private://私有化构造函数，防止外部实例化Singleton(){std::cout<<"SingletonInstanceCreated!"<<std::endl;}//删除拷贝构造函数和赋值运算符，防止拷贝实例Singleton(constSin......
  • ROS机器人入门系列（二）实现HelloWorld(c++/python)
    一、实现流程1、创建工作空间2、创建功能包3、编辑源文件4、编辑配置文件5、编译并执行其中，c++和python的差异仅体现在3，4两部，其他流程基本一致。二、创建工作空间和创建功能包的实现2.1 创建工作空间并初始化(1）创建工作空间mkdir-p自定义工作空间名称/src这里......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99