数组教学讲义（文本图示版）
1. 数组简介
1.1 数组定义
数组（Array）：一种线性表数据结构，利用一段连续的内存空间，存储一组相同类型的数据。
简而言之，「数组」 是线性表顺序存储结构的典型代表。
以整数数组为例，其存储方式如下图所示：
内存地址（低 → 高）
┌────┬────┬────┬────┬────┬────┐
│ 0 │ 5 │ 2 │ 3 │ 7 │ 1 │ ... (数组元素)
└────┴────┴────┴────┴────┴────┘
↑
首地址
每个元素占相同字节，连续排列
如上图，假设数组包含 个元素，每个元素都有唯一的下标索引，范围从 到 。每个下标对应一个数据元素。
可以看出，数组在计算机中本质上是一段连续的内存区域。每个元素都占用相同大小的存储单元，这些单元都有自己的内存地址，并且在物理内存中是依次排列的。
我们可以从两个角度理解数组的定义：
- 线性表：线性表是一种数据元素顺序排列、类型相同的数据结构，每个元素最多只有前驱和后继两个相邻元素。数组正是线性表的一种典型实现，此外，栈、队列、链表等也属于线性表结构。
- 连续的内存空间：线性表有「顺序存储」和「链式存储」两种方式。顺序存储结构要求内存空间连续，相邻元素在物理内存中紧挨着。数组采用的正是顺序存储结构，且所有元素类型一致。
综合这两个角度，数组可以看作是采用「顺序存储结构」实现的「线性表」。
1.2 如何随机访问数据元素
数组最显著的特点是：支持随机访问。也就是说，可以通过下标直接定位并访问任意一个元素。
那么，计算机是如何实现通过下标高效访问数组元素的呢？
实际上，数组在内存中被分配为一段连续的空间，第一个元素的地址称为 「首地址」。每个元素都有唯一的下标和对应的内存地址。计算机在访问数组元素时，会利用下标通过 「寻址公式」 快速计算出目标元素的内存地址，从而实现高效访问。
寻址公式为：下标 的元素地址 = 首地址 + × 单个元素占用的字节数
1.3 多维数组
前面介绍的是只有一个维度的数组，称为一维数组，其每个数据元素都通过单一的下标进行访问。但在实际应用中，许多数据具有二维或多维结构，一维数组已无法满足需求，因此引入了多维数组的概念。
以二维数组为例，其结构如下图所示：
行\列 列0 列1 列2 列3
行0 [0] [1] [2] [3]
行1 [4] [5] [6] [7]
行2 [8] [9] [10] [11]
内存中行优先存储（C++默认）：
[0][1][2][3][4][5][6][7][8][9][10][11]
二维数组由 行 列的数据元素组成，本质上可以理解为「数组的数组」，即每个元素本身也是一个数组。第一维表示行，第二维表示列。在内存中，二维数组通常采用行优先或列优先的存储方式。
二维数组常被视为矩阵，可以用于处理如矩阵转置、矩阵加法、矩阵乘法等相关问题。在本讲义中，我们将二维数组/二维向量统一命名为 matrix。
1.4 不同编程语言中数组的实现
C++ 提供了两种主要的数组形式：
- 传统静态数组：大小固定，在编译时确定，分配在栈或全局数据区。
std::vector（向量动态数组）：标准库中的动态数组，大小可变，分配在堆上，支持更安全、方便的操作。
一维数组的定义
// 传统一维静态数组
int arr[1000000]; // 定义大小为 1000000 的整型数组
int arr2[5] = {1, 2, 3, 4, 5}; // 定义并初始化
// 向量动态数组(vector<int>)
vector<int> vec; // 空向量
vector<int> vec2 = {1, 2, 3, 4, 5}; // 列表初始化
vector<int> vec3(10, 0); // 10 个元素，初始值均为 0
二维数组的定义
// 传统二维静态数组
int matrix[3][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}};
// 二维向量动态数组(vector<vector<int>>)
vector<vector<int>> matrix(3, vector<int>(4, 0)); // 3 行 4 列，全 0
// 不规则二维向量（类似于 Java 的 jagged array）
vector<vector<int>> matrix;
matrix.push_back({1, 2, 3});
matrix.push_back({4, 5});
matrix.push_back({6, 7, 8, 9});
2. 数组的基本操作
数组的基本操作主要包括增、删、改、查四类。以下每种操作均给出两种 C++ 实现：
- 方法一：使用传统静态数组
int arr[MAXN]+ 维护当前长度n，数据通过cin读入。 - 方法二：使用向量动态数组
vector<int>。
注意：一维数组的操作中，向量动态数组统一使用
vector<int>类型；二维操作中使用vector<vector<int>>并命名为matrix。
2.1 访问元素
访问数组中第 个元素：
- 首先检查下标 是否在合法范围内，即 ，超出该范围属于非法访问。
- 如果下标合法，则可直接通过下标获取对应元素的值。
- 如果下标不合法，则抛出异常或返回特殊值。
方法一：传统静态数组(int arr[MAXN])
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000; // 最大容量
int arr[MAXN]; // 传统数组
int n = 0; // 当前实际元素个数
// 获取指定下标元素（返回是否成功，值通过引用传出）
bool getElement(int index, int& value) {
if (0 <= index && index < n) {
value = arr[index];
return true;
}
return false;
}
int main() {
// 输入数组长度和元素
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 示例输入: 7 0 5 2 3 7 1 6
int idx, val;
cin >> idx; // 要访问的下标，例如 3
if (getElement(idx, val)) {
cout << val << endl;
} else {
cout << "下标越界" << endl;
}
return 0;
}
方法二：向量动态数组(vector)
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> vec = {0, 5, 2, 3, 7, 1, 6};
int index = 3;
if (index >= 0 && index < vec.size()) {
cout << vec[index] << endl; // 输出 3
} else {
cout << "下标越界" << endl;
}
return 0;
}
「访问数组元素」的时间复杂度为 。
2.2 查找元素
查找数组中元素值为 的位置：
- 遍历数组，将目标值 与每个元素进行比较。
- 找到匹配元素时返回其下标。
- 遍历完未找到时返回特殊值（如 ）。
方法一：传统静态数组(int arr[MAXN])
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int arr[MAXN];
int n = 0;
int findElement(int val) {
for (int i = 0; i < n; i++) {
if (arr[i] == val) return i;
}
return -1;
}
int main() {
// 输入数组长度和元素
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 示例输入: 7 0 5 2 3 7 1 6
int target;
cin >> target; // 要查找的值，例如 5 或 9
cout << findElement(target) << endl;
return 0;
}
方法二：向量动态数组(vector)
#include <bits/stdc++.h>
using namespace std;
int findElement(const vector<int>& vec, int val) {
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == val) return i;
}
return -1;
}
int main() {
vector<int> vec = {0, 5, 2, 3, 7, 1, 6};
cout << findElement(vec, 5) << endl; // 1
cout << findElement(vec, 9) << endl; // -1
return 0;
}
线性查找的时间复杂度为 。
2.3 插入元素
在数组第 个位置插入值 ：
- 检查 是否在 范围内。
- 扩展数组长度，为新元素腾出空间。
- 将 及其后的元素整体向后移动一位。
- 在 位置插入 。
插入过程示意图（假设原数组为 [0,5,2,3,7,1,6]，在 index=2 插入 4）：
初始： [0, 5, 2, 3, 7, 1, 6]
↓ 插入位置 index=2
步骤1： 扩展长度，末尾占位 [0,5,2,3,7,1,6,_]
步骤2： 后移元素：从后往前将 index 及之后的元素右移
[0,5,_,2,3,7,1,6] (注意 2 被覆盖前先移走)
步骤3： 插入 4: [0,5,4,2,3,7,1,6]
方法一：传统静态数组(int arr[MAXN])
传统数组大小固定，需要预先分配足够空间（如 MAXN），并手动维护长度
n。插入时移动元素，最后长度加一。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int arr[MAXN];
int n = 0;
bool insertElement(int index, int val) {
if (index < 0 || index > n) return false; // 无效位置
if (n >= MAXN) return false; // 空间不足
// 将 index 及之后的元素后移
for (int i = n; i > index; i--) {
arr[i] = arr[i - 1];
}
arr[index] = val;
n++;
return true;
}
int main() {
// 输入数组长度和元素
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 示例输入: 7 0 5 2 3 7 1 6
int idx, val;
cin >> idx >> val; // 插入位置和值，例如 2 4
bool ok = insertElement(idx, val);
cout << "插入结果: " << (ok ? "True" : "False") << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
方法二：向量动态数组(vector)
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> vec = {0, 5, 2, 3, 7, 1, 6};
int index = 2, val = 4;
if (index >= 0 && index <= vec.size()) {
vec.insert(vec.begin() + index, val);
cout << "插入结果: True" << endl;
} else {
cout << "插入结果: False" << endl;
}
for (int x : vec) cout << x << " "; // 0 5 4 2 3 7 1 6
cout << endl;
return 0;
}
插入操作的时间复杂度为 。
2.4 改变元素
将数组中第 个元素值改为 ：
- 检查 是否在 范围内。
- 将第 个元素值赋值为 。
改变元素示意图（将 index=2 的元素改为 4）：
原数组： [0, 5, 2, 3, 7, 1, 6]
↓
新数组： [0, 5, 4, 3, 7, 1, 6]
方法一：传统静态数组(int arr[MAXN])
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int arr[MAXN];
int n = 0;
bool changeElement(int index, int val) {
if (0 <= index && index < n) {
arr[index] = val;
return true;
}
return false;
}
int main() {
// 输入数组长度和元素
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 示例输入: 7 0 5 2 3 7 1 6
int idx, val;
cin >> idx >> val; // 修改位置和新值，例如 2 4
bool ok = changeElement(idx, val);
cout << "修改结果: " << (ok ? "True" : "False") << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
方法二：向量动态数组(vector)
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> vec = {0, 5, 2, 3, 7, 1, 6};
int index = 2, val = 4;
if (index >= 0 && index < vec.size()) {
vec[index] = val;
cout << "修改结果: True" << endl;
} else {
cout << "修改结果: False" << endl;
}
for (int x : vec) cout << x << " "; // 0 5 4 3 7 1 6
cout << endl;
return 0;
}
「改变元素」的时间复杂度为 。
2.5 删除元素
删除数组中第 个位置的元素：
- 检查下标 是否在合法范围内，即 。
- 将 位置及其后的元素整体向前移动一位。
- 删除最后一个元素（或更新数组长度）。
删除过程示意图（删除 index=2 的元素）：
原数组： [0, 5, 2, 3, 7, 1, 6]
↓ 删除
前移后： [0, 5, 3, 7, 1, 6]
方法一：传统静态数组(int arr[MAXN])
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int arr[MAXN];
int n = 0;
bool deleteElement(int index) {
if (index < 0 || index >= n) return false;
// 将 index+1 及之后的元素前移
for (int i = index; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
n--;
return true;
}
int main() {
// 输入数组长度和元素
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 示例输入: 7 0 5 2 3 7 1 6
int idx;
cin >> idx; // 要删除的下标，例如 2
bool ok = deleteElement(idx);
cout << "删除结果: " << (ok ? "True" : "False") << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
方法二：向量动态数组(vector)
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> vec = {0, 5, 2, 3, 7, 1, 6};
int index = 2;
if (index >= 0 && index < vec.size()) {
vec.erase(vec.begin() + index);
cout << "删除结果: True" << endl;
} else {
cout << "删除结果: False" << endl;
}
for (int x : vec) cout << x << " "; // 0 5 3 7 1 6
cout << endl;
return 0;
}
删除操作的时间复杂度为 。
3. 总结
数组是一种基础且重要的数据结构，采用连续的内存空间来存储同类型的数据。其最大优势在于支持随机访问，可以通过下标高效地定位和访问任意元素。
| 操作 | 传统静态数组 (int arr[N]) |
向量动态数组 (vector<int>) |
时间复杂度 |
|---|---|---|---|
| 访问 | arr[i]（需手动检查边界） |
vec[i] 或 vec.at(i) |
O(1) |
| 修改 | arr[i] = val |
vec[i] = val |
|
| 查找 | 线性遍历 | O(n) | |
| 插入 | 手动移动元素，维护长度 n |
vec.insert() |
|
| 删除 | vec.erase() |
||
推荐：在竞赛和工程开发中，若无特殊限制，应优先使用
vector<int>（向量动态数组），它更安全、方便，且提供了丰富的成员函数。
4. 练习题目
参考资料
- 【文章】数据结构中的数组和不同语言中数组的区别 - CSDN 博客
- 【文章】数组理论基础 - 代码随想录
- 【文章】C++ vector 用法详解
- 【书籍】数据结构教程 第 2 版 - 唐发根 著
- 【书籍】数据结构与算法 C++ 描述 - Mark Allen Weiss 著
