文章目录
前言
在继续我们的C++数据结构学习之旅中,今天我们深入探讨了一维数组的元素移动,这是全国青少年信息学奥林匹克竞赛(NOI)准备过程中的一个重要环节。上一讲我们讨论了数组的基础操作,包括创建、访问、修改和遍历,以及如何在数组中查找特定的元素。今天,我们进一步拓展了知识面,学习了如何通过逆序、删除和插入操作来动态调整数组中的元素位置,这是解决复杂算法问题和优化数据结构管理的关键技能。
在这一讲中,我们不仅讲解了理论概念,还通过具体的例题演示了如何在C++中实现这些操作。我们从逆序数组开始,介绍了两种方法:一种是通过逆序遍历来“假装”逆序,适用于仅需输出逆序数组的情况;另一种是真正的逆序,通过交换数组元素来实现。随后,我们探讨了数组元素的删除,同样提供了两种方法:一种是通过“忽略”特定位置的元素来模拟删除,适用于仅需输出修改后的数组的情况;另一种是通过覆盖元素来真正实现删除。最后,我们讲解了数组元素的插入,通过移动数组元素为新元素腾出空间,再将新元素置入。
欢迎关注本专栏《C++从零基础到信奥赛入门级(CSP-J)》
学习路线:C++从入门到NOI学习路线
学习大纲:C++全国青少年信息学奥林匹克竞赛(NOI)入门级-大纲
一、概念
1.导入
上一讲中,我们在学习了数组创建、访问、修改、遍历的基础上解决了数组找数(在给定的数组中寻找特定元素、满足一定条件的元素或执行某种操作的问题。)的问题。
今天我们将要通过“逆序”、“删除”和“插入”的操作来解决数组元素移动的问题。
2.元素移动
2.1 逆序
在数组问题中,常常会要求你将数组逆序后输出,或者需要在逆序后进行其他操作,面对这种问题,我们应该如何解决呢?
- 方法一:假逆序
不进行逆序操作,而是逆序遍历数组输出。以“骗样例”的方式,通过oj的检查。
该方法只适合输出逆序数组的问题,如果还有其他操作就得学会方法二。
- 方法二:真逆序
逆序,无非就是让前面的元素挪到后面去。
因此我们可以将将前面的元素和后面的元素进行交换即可。
当然,肯定要对称才行。例如第一元素和最后一个元素交换,第二个元素和倒数第二个元素交换。由此也能看出交换的次数是数组长度的一半。
具体怎么做请看后面的例题《1009. 数组逆序》。
2.2 删除
首先需要知道的是,我们学习的静态数组并没有直接进行删除的方法,而是通过一系列的操作,模拟删除的效果。
- 方法一:假删除
和我们假逆序的方法一是一样的,以“骗样例”的方式,通过oj的检查。
具体操作是:不删除,输出数组所有元素,如果遇到下标为x(i==x),则不输出!
该方法一样只适合输出数组元素的问题,如果还有其他操作就得学会方法二。
- 方法二:真删除
在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.分析问题
- 已知:用户将输入m个整数。
- 未知:需要逆序输出这些整数。
- 关系:通过交换数组元素的位置实现逆序。
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.分析问题
- 已知:用户将输入一个数组和一个要删除的元素的位置。
- 未知:删除指定位置的元素后的新数组。
- 关系:将指定位置之后的所有元素向前覆盖移动一位。
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.分析问题
- 已知:一个数组。
- 未知:更新后的数组。
- 关系:在 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.分析问题
- 已知:一个整数 n 和一个m大小有序数列。
- 未知:新的数列(在原数列中插入n后)。
- 关系: 整数 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.分析问题
- 已知:一个n大小的数组,x坐标。
- 未知:移动后的数组。
- 关系: 把数组的第 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++中高效地实现这些操作。
我们通过以下关键点总结今日所学:
- 逆序可以通过对称交换数组元素来实现。
- 删除元素可以通过覆盖法,即移动后续元素来模拟。
- 插入元素需要先移动数组中相应位置的元素,为新元素腾出空间。
四、感谢
如若本文对您的学习或工作有所启发和帮助,恳请您给予宝贵的支持——轻轻一点,为文章点赞;若觉得内容值得分享给更多朋友,欢迎转发扩散;若认为此篇内容具有长期参考价值,敬请收藏以便随时查阅。
每一次您的点赞、分享与收藏,都是对我持续创作和分享的热情鼓励,也是推动我不断提供更多高质量内容的动力源泉。期待我们在下一篇文章中再次相遇,共同攀登知识的高峰!
标签:NOI,int,元素,C++,插入,数组,数据结构,输入,逆序 From: https://blog.csdn.net/qq_39180358/article/details/140486180