为什么需要数组？
我们已经学过变量，假定你的班级学生人数为 30，现在要存储每个学生的分数，你可能定义如下变量：
int xiaoming = 100;
int xiaohong = 98;
int xiaowang = 99;
……
然而，这样写比较麻烦，变量名太复杂，我们给班级学员分配一个学号，从 1 到 30，然后定义如下变量：
int a1 = 100;
int a2 = 98;
int a3 = 99;
……
然而，变量依然比较多，我们可以考虑用一个数组变量存储所有的学员分数，int a[30];
该代码执行后，计算机会在内存中开辟出一段连续的 30 个 int 类型空间。
一维数组
1.数组是由相同数据类型组成的集合
2.一个数组在内存占有一片连续的存储区域
3.数组名是存储空间的首地址
4.数组的每个元素用下标变量标识
一维数组定义
当数组中每个元素只带有一个下标时，我们称这样的数组为一维数组。
说明：
①数组名的命名规则与变量名的命名规则一致。
②常量表达式表示数组元素的个数。可以是常量和符号常量，但不能是变量。
例如：
int a[10]; //数组a 定义是合法的
int b[n]; //数组b 定义是非法的
其中，a 是一维数组的数组名，该数组有10个元素，依次表示为：a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]。需要注意的是： a[10] 不属于该数组的空间范围。当在说明部分定义了一个数组变量之后，C++ 编译程序为所定义的数组在内存空间开辟一串连续的存储单元，每个数组第一个元素的下标都是 0，因此第一个元素为第 0 个数组元素。例如：上例中的 a 数组在内存的存储如表所示：
a 数组共有 10 个元素组成，在内存中 10 个数组元素共占 10 个连续的存储单元。a 数组最小下标为 0，最大下标 9。按定义 a 数组所有元素都是整型变量。
一般数组定定义，使用 const 常量，放在全局区。一方面，题目中数组范围可能比较大，比如 ，main 函数内容为栈区，空间较小，不适合存储过大的数组，在 Dev 编译器中，会导致程序异常。
一维数组初始化
数组的初始化可以在定义时一并完成。格式：类型标识符 数组名[常量表达式]={值1，值2，…}
例如：int a[5] = {1,2,3,4,5};
说明：
（1）在初值列表中可以写出全部数组元素的值，也可以写出部分。例如，以下方式可以对数组进行初始化：int a[10] = {0,1,2,3,4}; 该方法仅对数组的前 5 个元素依次进行初始化，其余值为 0。
（2）对数组元素全部初始化为 0，可以简写为：{ }。 例如：int a[5] = { }; 将数组 a 的 5 个元素都初始化为 0。
一维数组访问和赋值
通过给出的数组名称和这个元素在数组中的位置编号（即下标），程序可以访问这个数组中的任何一个元素。
一维数组元素的访问格式：数组名[下标]
例如：若 i、j 都是 int 型变量，则 a[5]、a[i+j]、a[i++] 都是合法的元素。
说明：
（1）下标可以是任意值为整型的表达式，该表达式里可以包含变量和函数调用。访问时，下标值应在数组定义的下标值范围内。
（2）数组的精妙在于下标可以是变量，通过对下标变量值的灵活控制，达到灵活处理数组元素的目的。
（3）C++语言只能逐个引用数组元素，而不能一次引用整个数组。
（4）数组元素可以像同类型的普通变量那样使用，对其进行赋值和运算的操作，和普通变量完全相同。 例如：a[10]=34;实现了给 a[10] 赋值为 34。
数组越界
C++中并不提供数组越界检查，那么定义数组大小有什么用呢？
1.当我们定义了数组大小为 int类型 110 个元素时（int a[110]），编译器会在内存中开辟出 110 * 4 个字节的连续空间，其他数据不可以占有该内存空间。
2.一旦数组越界，比如，我们访问 a[200] 内存空间中的数据，编译器会以 a 作为首地址，向后偏移 200 * 4，将该内存中数据返回。尤其是我们向 a[200] 中写入数据时，很可能修改了程序中其他重要变量数据，进而引发程序崩溃或异常。所以，编程时，一定要注意数组越界检查。
咱先试试能不能越个界。。。
越界后→
动态创建和释放数组【选学】
通过 new 可以在堆空间开辟出一块连续的内存空间，返回值为该空间第一个元素的地址。
#include <iostream>
using namespace std;
int main(){
int* pa = new int[10];
for(int i = 0; i < 10; i++)
*(pa + i) = i;
for(int i = 0; i < 10; i++)
cout << pa[i] << " ";
delete [] pa;
pa = NULL;
return 0;
}
vector容器
在C++中，vector 是标准模板库（STL）提供的一个动态数组容器。是一个能够动态增长和缩小的数组，提供了方便的操作接口，使得在运行时能够有效地管理数组的大小。
以下是一些关于C++中vector的重要特性：
- 动态大小：
vector允许在运行时动态调整数组的大小，而不需要预先指定数组的大小。 - 自动内存管理：
vector会自动处理内存的分配和释放，避免了手动管理内存的麻烦。 - 连续存储：
vector中的元素在内存中是连续存储的，这有助于提高访问速度。 - 随机访问：
vector支持通过下标直接访问数组中的元素，具有常数时间的随机访问性能。 - 尾部插入和删除： 在
vector的尾部插入和删除元素是高效的操作，平均时间复杂度为常数时间。
#include <iostream>
#include <vector> // 向量 动态数组
using namespace std;
vector<int> v;
int main(){
for(int i = 0; i < 10; i++) v.push_back(i);
cout << v[0] << " " << v[1] << endl;
cout << v.size() << " " << v.empty() << endl;
for(int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
// 迭代器
vector<int>::iterator it = v.begin();
cout << *it << endl;
for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
cout << *it << " ";
cout << endl;
for(auto it = v.begin(); it != v.end(); it++)
cout << *it << " ";
cout << endl;
//v.erase(v.begin() + 3);
for(int x: v) cout << x << " ";
cout << endl;
v.erase(v.begin() + 1, v.begin() + 5);
for(int x: v) cout << x << " ";
cout << endl;
v.pop_back();
for(int x: v) cout << x << " ";
cout << endl;
v.insert(v.begin() + 2, 789);
for(int x: v) cout << x << " ";
cout << endl;
return 0;
}
输出：
0 1
10 0
0 1 2 3 4 5 6 7 8 9
0
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 5 6 7 8 9
0 5 6 7 8
0 5 789 6 7 8
#include <iostream>
#include <vector> // 向量 动态数组
using namespace std;
vector<int> v;
int main(){
v.assign(8, 1);
v[2] = 123;
v[3] = 456;
v[4] = 789;
for(auto x: v) cout << x << " ";
cout << endl;
v.insert(v.begin() + 5, 888);
for(auto it = v.begin(); it != v.end(); it++)
cout << *it << " ";
cout << endl;
auto p = v.begin() + 3;
cout << *p << endl;
cout << *prev(p) << endl;
cout << *next(p) << endl;
v.clear();
cout << v.size() << endl;
return 0;
}
输出：
1 1 123 456 789 1 1 1
1 1 123 456 789 888 1 1 1
456
123
789
0
sort排序
排序算法有很多，我们本节主要使用 C++ 中提供的 sort 函数进行排序。
需要引入库：#include <algorithm>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N];
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++) cout << a[i] << " ";
return 0;
}
sort 默认从小到大排序，如果从大到小排序，需要学习函数，在后面课程进行讲解，或者反向遍历将结果存储到另一个一位数组中。
自定义比较函数如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N];
bool cmp(int a, int b){
return a > b;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i++) cout << a[i] << " ";
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> v;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
v.push_back(x);
}
sort(v.begin(), v.end());
for(auto x: v) cout << x << " ";
cout << endl;
sort(v.begin(), v.end(), greater<int>());
for(auto x: v) cout << x << " ";
cout << endl;
return 0;
}
注意：vector 的 size 函数返回类型是 unsigned _int64，所以当 size() 为 0 时，再减 1，结果会是一个非常大的整数，要用 int 进行强制转换，再减 1。
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v;
cout << v.size() << endl;
cout << int(v.size()) - 1 << endl;
return 0;
}
max_element()和min_element()函数的用法
需要引入库：
#include <algorithm>max_element() 的使用方法：
- 查找一个区间内的最大元素：max_element(first, last)
- 查找一个区间内的最大元素，并使用自定义比较函数：max_element(first, last, cmp)
min_element() 的使用方法：
- 查找一个区间内的最小元素：min_element(first, last)
- 查找一个区间内的最小元素，并使用自定义比较函数：min_element(first, last, cmp)
二分查找函数
begin：迭代器或指针，指向要查找的数组区间的第一个元素
end：迭代器或指针，指向要查找的数组区间的最后一个元素的后一个位置
