数组

介绍

​ 数组是一种基本的数据结构，它用于存储固定大小的同类型元素集合。数组的特点包括：

数组的特点

• 线性结构

​ 数组是一种线性数据结构，因为其元素在内存中是连续存储的。每个元素都可以用过一个索引(或下标)来访问，这个索引表示了元素在数组中的位置。

• 固定大小

​ 数组的大小必须在定义的时候指定，并且在运行时无法改变，这意味着数组一旦创建，其容量九四固定的。

• 元素类型一致c

​ 由于数组中的元素在内容中是连续存储的，可以通过索引实现常数时间(O(1))的随机方法问。这意味着我们可以直接访问任何位置的元素，而不需要遍历其他元素。

• 内存分配

​ 数组通常是在栈上分配内存(对于局部数组)，或者在堆上分配内存(对于动态数组)。栈上的数组在作用域结束时会自动释放，而在堆上分配的数组需要手动释放。

• 空间效率

​ 由于数组的元素在内存空格键中是连续存储的，所以数组具有良好的空间局部性，这有助于提高缓存的效率和系统的性能。

• 数组的常见操作
  • 访问元素：通过索引直接访问
  • 遍历：通过循环遍历数组的所有元素
  • 修改元素：通过索引修改数组中某个位置的值
  • 初始化：在声明时进行初始化，或者在之后通过循环或其他方式进行初始化。

数组的优缺点

优点：

• 高效的随机访问：可以在常数时间内访问任何位置的元素
• 简单的实现：实现简单，易于理解和使用

缺点：

• 固定大小：
• 插入和删除：
• 内存管理：

数组和其他数据结构的比较

• 与链表比较：链表的插入和删除操作更高效（O(1)），但随机访问的时间复杂度是O(n)，而数组提供常数时间的随机访问。
• 与哈希表比较：哈希表提供更高效的查找操作，但没有数组的顺序性和索引访问优势。
• 与树结构比较：树结构提供了有序数据存储和高效的插入/删除操作，但数组提供更简洁的实现和更好的内存局部性。

静态数组与动态数组的详细讲解

在 C++ 中，数组分为静态数组和动态数组。静态数组在编译时分配内存，大小固定；而动态数组在运行时分配内存，大小可以动态调整。下面我们分别讨论一维、二维和三维数组的静态和动态实现。

一、静态数组

1. 一维数组

声明与初始化

• 声明：类型 数组名[数组大小];
• 初始化：可以在声明时初始化，例如 int arr[5] = {1, 2, 3, 4, 5};

#include <iostream>int main() {int arr[5] = {1, 2, 3, 4, 5}; // 声明并初始化一个静态一维数组for (int i = 0; i < 5; i++) {std::cout << arr[i] << " ";}return 0;
}

运行结果：

注意事项

• 数组大小必须在编译时确定。
• 数组元素在内存中是连续存储的。
• 如果不完全初始化，未被显式初始化的元素会自动被初始化为零。

特点

• 简单且高效，内存分配和释放由编译器自动管理。
• 适用于数组大小固定且编译时已知的场景。

2. 二维数组

声明与初始化

• 声明：类型 数组名[行数][列数];
• 初始化：可以在声明时初始化，例如 int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};

#include <iostream>int main() {int arr[2][3] = {{1, 2, 3}, {4, 5, 6}}; // 声明并初始化一个静态二维数组for (int i = 0; i < 2; i++) {for (int j = 0; j < 3; j++) {std::cout << arr[i][j] << " ";}std::cout << std::endl;}return 0;
}

运行结果：

注意事项

• 与一维数组类似，数组大小在编译时确定。
• 存储方式是行优先，即按行连续存储。

特点

• 适用于需要矩阵或表格形式存储数据的场景。

3. 三维数组

声明与初始化

• 声明：类型 数组名[深度][行数][列数];
• 初始化：可以在声明时初始化，例如 int arr[2][2][3] = {{{1, 2, 3}, {4, 5, 6}}, {{7, 8, 9}, {10, 11, 12}}};

#include <iostream>int main() {int arr[2][2][3] = {{{1, 2, 3}, {4, 5, 6}},{{7, 8, 9}, {10, 11, 12}}}; // 声明并初始化一个静态三维数组for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {for (int k = 0; k < 3; k++) {std::cout << arr[i][j][k] << " ";}std::cout << std::endl;}std::cout << std::endl;}return 0;
}

运行结果：

注意事项

• 与二维数组类似，三维数组也是按行优先存储。
• 需要更多内存，因此可能在栈上占用较大空间。

特点

• 适用于需要处理多维数据的场景，例如图像处理或物理模拟。

二、动态数组

1. 一维数组

声明与初始化

• 动态数组使用指针进行管理，常用 new 操作符来动态分配内存。
• 声明：类型* 数组名 = new 类型[数组大小];

#include <iostream>int main() {int n = 5;int* arr = new int[n]; // 声明并动态分配一个一维数组for (int i = 0; i < n; i++) {arr[i] = i + 1;}for (int i = 0; i < n; i++) {std::cout << arr[i] << " ";}delete[] arr; // 释放动态分配的内存return 0;
}

运行结果：

注意事项

• 必须使用 delete[] 释放动态分配的内存，否则会导致内存泄漏。
• 数组大小可以在运行时确定。

特点

• 灵活，可在运行时根据需要调整大小。
• 适用于需要动态调整数组大小的场景。

2. 二维数组

声明与初始化

• 声明：类型** 数组名 = new 类型*[行数]; 然后为每一行分配列的内存。

#include <iostream>int main() {int rows = 2, cols = 3;int** arr = new int*[rows]; // 声明并动态分配一个二维数组for (int i = 0; i < rows; i++) {arr[i] = new int[cols];}// 初始化int count = 1;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {arr[i][j] = count++;}}// 打印数组for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {std::cout << arr[i][j] << " ";}std::cout << std::endl;}// 释放内存for (int i = 0; i < rows; i++) {delete[] arr[i];}delete[] arr;return 0;
}

运行结果：

注意事项

• 必须为每一行单独分配和释放内存。
• 处理较大的二维数组时，要小心内存泄漏。

特点

• 动态调整行列数，适用于运行时需要动态改变矩阵大小的场景。

3. 三维数组

声明与初始化

• 声明：类型*** 数组名 = new 类型**[深度]; 然后为每个“面”分配二维数组的内存。

#include <iostream>int main() {int depth = 2, rows = 2, cols = 3;int*** arr = new int**[depth]; // 声明并动态分配一个三维数组for (int i = 0; i < depth; i++) {arr[i] = new int*[rows];for (int j = 0; j < rows; j++) {arr[i][j] = new int[cols];}}// 初始化int count = 1;for (int i = 0; i < depth; i++) {for (int j = 0; j < rows; j++) {for (int k = 0; k < cols; k++) {arr[i][j][k] = count++;}}}// 打印数组for (int i = 0; i < depth; i++) {for (int j = 0; j < rows; j++) {for (int k = 0; k < cols; k++) {std::cout << arr[i][j][k] << " ";}std::cout << std::endl;}std::cout << std::endl;}// 释放内存for (int i = 0; i < depth; i++) {for (int j = 0; j < rows; j++) {delete[] arr[i][j];}delete[] arr[i];}delete[] arr;return 0;
}

运行结果：

注意事项

• 三维数组需要更多的内存管理操作。
• 可能导致复杂的内存泄漏问题，需要小心处理内存释放。

特点

• 适用于需要多维度数据处理的场景，尤其是需要在运行时动态调整每个维度大小的情况。

总结

• 静态数组 简单、高效，但受限于编译时的固定大小，适合处理大小已知且固定的数据集。
• 动态数组 提供了更大的灵活性，能够在运行时分配和释放内存，适合处理大小不确定或需要动态调整的场景。

静态数组适合于内存占用较小、大小固定的场景，而动态数组更适合内存管理要求严格或者需要处理大数据的应用。