数组是存储相同类型数据的容器，像一排连续的格子，是几乎所有算法题都会用到的基础数据结构。
6.1
数组（array）是一种线性数据结构，将相同类型的元素存储在连续的内存空间中。元素在数组中的位置称为索引（index），索引从 0 开始。
| 规则 | 合法示例 | 不合法示例 | 原因 |
|---|---|---|---|
| 只能含字母、数字、下划线 | scores, my_arr | my-arr | 含连字符 |
| 不能以数字开头 | arr2 | 2arr | 数字开头 |
| 不能与已定义变量重名 | myArr | int n=5; int n[10]; | 名字冲突 |
| 不能使用关键字 | forArr | int for[5]; | for 是关键字 |
| 1 | // 语法：类型 数组名[大小]; |
| 2 | int a[5]; // 定义可存 5 个整数的数组（未初始化） |
| 3 | |
| 4 | int b[5] = {90, 85, 78, 92, 88}; // 完整初始化 |
| 5 | int c[] = {90, 85, 78, 92, 88}; // 省略大小，自动推断为 5 |
| 6 | int d[5] = {1, 2}; // 部分初始化 → {1, 2, 0, 0, 0} |
| 7 | |
| 8 | a = b; // ❌ 错误！数组变量之间不能直接赋值 |
main() 内的局部数组存放在栈（Stack）中，栈空间默认仅 1~2 MB。数组过大会立即导致栈溢出（程序崩溃），且无任何警告，是极隐蔽的错误。main() 外部（全局变量），它会被分配到静态存储区，空间充裕。细心的话可能见过这样的写法——用一个变量（而不是像 5 这样写死的常量）来决定数组大小：
| 1 | int n; |
| 2 | cin >> n; |
| 3 | int arr[n] = {0}; // 数组大小是变量 n，而不是像 5 这样的常量 |
5，或者 const int 常量），像上面这样用一个运行时才知道值的变量 n 做数组大小，叫做变长数组（VLA，Variable Length Array），标准 C++ 里其实是不允许的。and/or、__builtin_popcount 是同一类问题——都是"编译器扩展在不同编译器上表现不一致"。vector（见后续 STL 章节）代替数组：vector<int> arr(n, 0);，效果一样能按变量 n 动态决定大小，而且是所有编译器都支持的标准写法，不用担心换个编译器就编译不过。竞赛中如果确实想用原生数组，更稳妥的办法是提前开一个足够大的固定大小数组（比如 int arr[100005];），根据题目给的数据范围上限来定，而不是直接用变量做数组大小。6.1.3
数组下标从 0 开始，最后一个元素的下标是 大小 - 1。通过 数组名[下标] 访问或修改指定位置的元素。
| 1 | int a[5] = {90, 85, 78, 92, 88}; |
| 2 | //下标： 0 1 2 3 4 |
| 3 | |
| 4 | cout << a[0]; // 输出：90（第1个元素） |
| 5 | cout << a[4]; // 输出：88（最后一个，下标 = 大小-1） |
| 6 | a[2] = 99; // 修改第3个元素 |
| 7 | |
| 8 | a[3] = {0,1,2}; // ❌ 错误！非定义时不能整体赋值 |
| 9 | |
| 10 | // 用循环遍历数组 |
| 11 | for (int i = 0; i < 5; i++) |
| 12 | cout << a[i] << " "; |
a[5]（越界）不会报错，但会读写到相邻内存，造成程序崩溃或数据错误，是极危险的隐藏 bug。始终确保下标在 [0, 大小-1] 范围内。6.1.4
数组元素在内存中紧挨着，中间没有空间。在索引 1 处插入元素 3 时，需要先将该位置及之后的所有元素依次向后移动一位，再写入新值。由于数组长度固定，插入会导致尾部元素丢失。
| 1 | int index = 1, num = 3; |
| 2 | int nums[5] = {1,2,5,4,0}; |
| 3 | |
| 4 | // 从后往前移动，腾出 index 位置 |
| 5 | for (int i = 5 - 1; i > index; i--) |
| 6 | nums[i] = nums[i - 1]; |
| 7 | |
| 8 | nums[index] = num; // 写入新值 |
nums[2]=nums[1] 先执行），会把索引2原本的值提前覆盖掉，还没来得及挪到索引3就已经丢失了。从后往前移动能保证每次覆盖之前，被覆盖位置的值已经被读取并转移走。6.1.5
删除索引 1 处的元素时，需要把该位置之后的所有元素依次向前移动一位。删除后末尾元素无意义，有效长度减 1。
| 1 | int index = 1; |
| 2 | int nums[5] = {1,3,2,5,4}; |
| 3 | |
| 4 | // 从前往后移动，覆盖 index 位置 |
| 5 | for (int i = index; i < 5 - 1; i++) |
| 6 | nums[i] = nums[i + 1]; // 后一个覆盖前一个 |
| 7 | // 末尾元素已无意义，有效长度 -1 |
6.1.6
| 1 | int a[] = {3,1,4,1,5,9,2,6}, n = 8; |
| 2 | |
| 3 | // ── 求最大值 ── |
| 4 | int maxVal = a[0]; // 以第一个元素为初始最大值 |
| 5 | for (int i = 1; i < n; i++) |
| 6 | if (a[i] > maxVal) maxVal = a[i]; |
| 7 | |
| 8 | // ── 求总和与平均值 ── |
| 9 | int sum = 0; |
| 10 | for (int i = 0; i < n; i++) sum += a[i]; |
| 11 | double avg = (double)sum / n; // 见 2.1 节：先转 double 再除 |
| 12 | |
| 13 | // ── 逆序输出 ── |
| 14 | for (int i = n-1; i >= 0; i--) cout << a[i] << " "; |
sort() 排序（需 #include <algorithm>）| 1 | #include <algorithm> |
| 2 | int a[] = {3, 1, 4, 1, 5, 9}, n = 6; |
| 3 | |
| 4 | sort(a, a + n); // 升序：1 1 3 4 5 9 |
| 5 | sort(a, a + n, greater<int>()); // 降序：9 5 4 3 1 1 |
sort(a, a + n) 中的 a 是数组首地址，a + n 是"最后一个有效元素之后"的地址（左闭右开区间），这是 C++ 标准库的通用约定，后续学习 STL 容器时会反复见到同样的写法。6.1.7
把本节内容汇总成几条最容易踩坑的规则：
a[n] 或 a[-1] 不会立刻崩溃，而是悄悄读写了相邻内存，可能过一会儿才在完全无关的地方引发诡异的错误，非常难排查。main() 或函数内部定义的数组存在栈上，空间只有 1~2 MB。定义 int a[10000000] 这种大数组作为局部变量会直接崩溃，应改为全局变量（定义在所有函数之外）。a = b、a == b 这类对数组变量整体操作的写法在 C++ 里都不合法（除非是刚定义时的初始化）。需要逐个元素用循环复制或比较。