数据结构 - 数组
数组（Array）是最基础、也是最常用的数据结构之一。
数组是一组类型相同、在内存中连续存放的元素集合。
数组的定义与内存布局
在 C 语言中，数组声明后会在内存中分配一块连续的空间，每个元素可以通过下标直接访问。
上图展示了一个包含 5 个 int 元素的数组在内存中的布局。假设起始地址为 0x1000，每个 int 占 4 字节，则：
- arr[0] 位于地址 0x1000
- arr[1] 位于地址 0x1004（0x1000 + 4）
- arr[i] 位于地址 0x1000 + i × 4
正是由于这种连续存储的特性，数组可以通过 起始地址 + 偏移量 的方式在 O(1) 时间内访问任意元素。
一维数组
实例
#include <stdio.h>
int main() {
/* 声明并初始化一个一维数组 */
int arr[5] = {10, 20, 30, 40, 50};
/* 遍历访问每个元素 */
printf("数组元素: ");
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* 输出: 数组元素: 10 20 30 40 50 */
/* 通过索引直接访问，时间复杂度 O(1) */
printf("arr[2] = %d\n", arr[2]); /* 输出: 30 */
return 0;
}
int main() {
/* 声明并初始化一个一维数组 */
int arr[5] = {10, 20, 30, 40, 50};
/* 遍历访问每个元素 */
printf("数组元素: ");
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* 输出: 数组元素: 10 20 30 40 50 */
/* 通过索引直接访问，时间复杂度 O(1) */
printf("arr[2] = %d\n", arr[2]); /* 输出: 30 */
return 0;
}
多维数组
C 语言支持多维数组，最常见的是二维数组，常用于表示矩阵等表格数据。
二维数组在内存中仍然是按行连续存储的（行优先存储），只是通过行列下标的计算将其映射为二维视图。
实例
#include <stdio.h>
int main() {
/* 声明 3 行 4 列的二维数组 */
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
/* 遍历二维数组：外层循环遍历行，内层循环遍历列 */
printf("二维数组 (3×4 矩阵):\n");
for (int i = 0; i < 3; i++) { /* i 为行索引 */
for (int j = 0; j < 4; j++) { /* j 为列索引 */
printf("%2d ", matrix[i][j]);
}
printf("\n");
}
/* 访问特定元素：matrix[行][列] */
printf("matrix[1][2] = %d\n", matrix[1][2]); /* 输出: 7 */
return 0;
}
int main() {
/* 声明 3 行 4 列的二维数组 */
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
/* 遍历二维数组：外层循环遍历行，内层循环遍历列 */
printf("二维数组 (3×4 矩阵):\n");
for (int i = 0; i < 3; i++) { /* i 为行索引 */
for (int j = 0; j < 4; j++) { /* j 为列索引 */
printf("%2d ", matrix[i][j]);
}
printf("\n");
}
/* 访问特定元素：matrix[行][列] */
printf("matrix[1][2] = %d\n", matrix[1][2]); /* 输出: 7 */
return 0;
}
二维数组的内存地址计算公式：
元素地址 = 起始地址 + (i × 列数 + j) × sizeof(元素类型)。其中 i 为行索引，j 为列索引。
数组的基本操作
上图展示了数组插入和删除操作的核心步骤：插入时需要将目标位置之后的元素依次后移以腾出空间；删除时需要将目标位置之后的元素依次前移以填补空缺。
遍历
实例
#include <stdio.h>
/* 遍历并打印数组所有元素
时间复杂度：O(n)，n 为数组长度 */
void traverse(int arr[], int n) {
printf("遍历结果: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {15, 28, 43, 56, 71};
int n = sizeof(arr) / sizeof(arr[0]); /* 计算数组长度 */
traverse(arr, n);
return 0;
}
/* 遍历并打印数组所有元素
时间复杂度：O(n)，n 为数组长度 */
void traverse(int arr[], int n) {
printf("遍历结果: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {15, 28, 43, 56, 71};
int n = sizeof(arr) / sizeof(arr[0]); /* 计算数组长度 */
traverse(arr, n);
return 0;
}
插入
实例
#include <stdio.h>
/* 在数组的指定位置插入元素
参数：arr 数组, n 当前元素个数, pos 插入位置(0-based),
value 插入值, capacity 数组总容量
时间复杂度：O(n)，最坏情况需要移动 n 个元素
返回值：插入后的元素个数，容量不足返回 -1 */
int insert(int arr[], int n, int pos, int value, int capacity) {
if (n >= capacity) {
printf("数组已满，无法插入\n");
return -1;
}
if (pos < 0 || pos > n) {
printf("插入位置无效\n");
return -1;
}
/* 从后向前，将 pos 及之后的元素依次后移一位 */
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = value; /* 在新位置写入数据 */
return n + 1; /* 元素个数加 1 */
}
int main() {
int arr[10] = {10, 20, 30, 40}; /* 容量为 10，当前有 4 个元素 */
int n = 4;
printf("插入前: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 输出: 插入前: 10 20 30 40 */
n = insert(arr, n, 2, 25, 10); /* 在索引 2 处插入 25 */
printf("插入后: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 输出: 插入后: 10 20 25 30 40 */
return 0;
}
/* 在数组的指定位置插入元素
参数：arr 数组, n 当前元素个数, pos 插入位置(0-based),
value 插入值, capacity 数组总容量
时间复杂度：O(n)，最坏情况需要移动 n 个元素
返回值：插入后的元素个数，容量不足返回 -1 */
int insert(int arr[], int n, int pos, int value, int capacity) {
if (n >= capacity) {
printf("数组已满，无法插入\n");
return -1;
}
if (pos < 0 || pos > n) {
printf("插入位置无效\n");
return -1;
}
/* 从后向前，将 pos 及之后的元素依次后移一位 */
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = value; /* 在新位置写入数据 */
return n + 1; /* 元素个数加 1 */
}
int main() {
int arr[10] = {10, 20, 30, 40}; /* 容量为 10，当前有 4 个元素 */
int n = 4;
printf("插入前: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 输出: 插入前: 10 20 30 40 */
n = insert(arr, n, 2, 25, 10); /* 在索引 2 处插入 25 */
printf("插入后: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 输出: 插入后: 10 20 25 30 40 */
return 0;
}
删除
实例
#include <stdio.h>
/* 删除数组指定位置的元素
参数：arr 数组, n 当前元素个数, pos 删除位置(0-based)
时间复杂度：O(n)，最坏情况需要移动 n 个元素
返回值：删除后的元素个数 */
int delete(int arr[], int n, int pos) {
if (n <= 0) {
printf("数组为空，无法删除\n");
return 0;
}
if (pos < 0 || pos >= n) {
printf("删除位置无效\n");
return n;
}
/* 从前向后，将 pos 之后的元素依次前移一位 */
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
return n - 1; /* 元素个数减 1 */
}
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5;
printf("删除前: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 输出: 删除前: 10 20 30 40 50 */
n = delete(arr, n, 2); /* 删除索引 2 的元素 (30) */
printf("删除后: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 输出: 删除后: 10 20 40 50 */
return 0;
}
/* 删除数组指定位置的元素
参数：arr 数组, n 当前元素个数, pos 删除位置(0-based)
时间复杂度：O(n)，最坏情况需要移动 n 个元素
返回值：删除后的元素个数 */
int delete(int arr[], int n, int pos) {
if (n <= 0) {
printf("数组为空，无法删除\n");
return 0;
}
if (pos < 0 || pos >= n) {
printf("删除位置无效\n");
return n;
}
/* 从前向后，将 pos 之后的元素依次前移一位 */
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
return n - 1; /* 元素个数减 1 */
}
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5;
printf("删除前: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 输出: 删除前: 10 20 30 40 50 */
n = delete(arr, n, 2); /* 删除索引 2 的元素 (30) */
printf("删除后: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* 输出: 删除后: 10 20 40 50 */
return 0;
}
查找
在一个无序数组中查找目标值，最直接的方法是遍历整个数组逐一比较，这称为线性查找。
实例
#include <stdio.h>
/* 线性查找：在数组中搜索目标值
时间复杂度：O(n)，最坏情况需要遍历整个数组
返回值：目标元素的索引，未找到返回 -1 */
int search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; /* 找到，返回索引 */
}
}
return -1; /* 未找到 */
}
int main() {
int arr[] = {43, 17, 89, 25, 61};
int n = 5;
int idx = search(arr, n, 89);
if (idx != -1) {
printf("找到目标值 89，索引为 %d\n", idx); /* 输出: 找到目标值 89，索引为 2 */
} else {
printf("未找到目标值\n");
}
return 0;
}
/* 线性查找：在数组中搜索目标值
时间复杂度：O(n)，最坏情况需要遍历整个数组
返回值：目标元素的索引，未找到返回 -1 */
int search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; /* 找到，返回索引 */
}
}
return -1; /* 未找到 */
}
int main() {
int arr[] = {43, 17, 89, 25, 61};
int n = 5;
int idx = search(arr, n, 89);
if (idx != -1) {
printf("找到目标值 89，索引为 %d\n", idx); /* 输出: 找到目标值 89，索引为 2 */
} else {
printf("未找到目标值\n");
}
return 0;
}
数组的优缺点
| 优点 | 说明 |
|---|---|
| O(1) 随机访问 | 通过下标可以在常数时间内访问任意元素，这是数组最大的优势 |
| 内存连续 | 连续存储有利于 CPU 缓存命中（空间局部性），提升访问效率 |
| 实现简单 | 语法直观，是大多数编程语言的原生支持类型 |
| 缺点 | 说明 |
|---|---|
| 大小固定 | C 语言中的静态数组在编译时就确定了大小，无法动态扩容 |
| 插入/删除慢 | 在数组中间插入或删除元素时，需要移动大量元素，时间复杂度 O(n) |
| 空间浪费 | 如果声明的数组过大而实际使用较少，会造成内存浪费 |
正是这些局限性，催生了下一章将要学习的更加灵活的动态结构——链表。
操作复杂度总结
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 按索引访问 | O(1) | 直接计算地址 |
| 在末尾插入 | O(1) | 不需要移动元素 |
| 在头部/中间插入 | O(n) | 需要移动后续元素 |
| 删除末尾元素 | O(1) | 不需要移动元素 |
| 删除头部/中间元素 | O(n) | 需要移动后续元素 |
| 线性查找 | O(n) | 逐个比较 |
| 二分查找（有序数组） | O(log n) | 要求数组已排序 |