cpp_array

2025-07-03

数组基础

数组（Array）：一种线性表数据结构。它使用一组连续的内存空间，来存储一组具有相同类型的数据，是实现线性表的顺序结构存储的基础。

数组在计算机中的表示，就是一片连续的存储单元。数组中的每一个数据元素都占有一定的存储单元，每个存储单元都有自己的内存地址，并且元素之间是紧密排列的。数组是使用了顺序存储结构的线性表的一种实现方式。

数组的一个最大特点是：可以进行随机访问。数组可以根据下标，直接定位到某一个元素存放的位置。

计算机给一个数组分配了一组连续的存储空间，其中第一个元素开始的地址被称为首地址。每个数据元素都有对应的下标索引和内存地址，计算机通过地址来访问数据元素。当计算机需要访问数组的某个元素时，会通过寻址公式计算出对应元素的内存地址，然后访问地址对应的数据元素。

寻址公式如下：

\[下标 i 对应的数据元素地址 = 数据首地址 + i × 单个数据元素所占内存大小\]

很多信息是二维或者是多维的，一维数组已经满足不了我们的需求，就有了多维数组。

二维数组是一个由 m 行 n 列数据元素构成的特殊结构，其本质上是以数组作为数据元素的数组，即数组的数组。二维数组的第一维度表示行，第二维度表示列。

可以将二维数组看做是一个矩阵，并处理矩阵的相关问题，比如转置矩阵、矩阵相加、矩阵相乘等等。

C/C++ 语言中的数组最接近数组结构定义中的数组，使用的是一块存储相同类型数据的、连续的内存空间。不管是基本类型数据，还是结构体、对象，在数组中都是连续存储的。例如：

int arr[3][4] = {
    {0, 1, 2, 3},
    {4, 5, 6, 7},
    {8, 9, 10, 11}
};

Java 中的数组跟数据结构定义中的数组不太一样。Java 中的数组也是存储相同类型数据的，但所使用的内存空间却不一定是连续（多维数组中）。且如果是多维数组，其嵌套数组的长度也可以不同。例如：

int[][] arr = new int[][]{
    {1,2,3},
    {4,5},
    {6,7,8,9}
};
// 另一种写法：
int[][] arr = { {1,2,3}, {4,5}, {6,7,8,9}};

原生 Python 中没有数组的概念，是使用了类似 Java 中的 ArrayList 容器类数据结构，叫做列表。通常我们把列表来作为 Python 中的数组使用。Python 中列表存储的数据类型可以不一致，数组长度也可以不一致。例如：

arr = ['python', 'java', ['asp', 'php'], 'c']

数据结构的操作一般涉及到增、删、改、查共 4 种情况。

访问数组中第 i 个元素：

访问数组元素的操作不依赖于数组中元素个数，因此，访问数组元素的时间复杂度为 $O(1)$。

查找数组中元素值为 val 的位置:

在查找元素的操作中，如果数组无序，那么我们只能通过将 val 与数组中的数据元素逐一对比的方式进行查找，也称为线性查找。而线性查找操作依赖于数组中元素个数，因此，查找元素的时间复杂度为 $O(n)$。

插入元素操作分为两种：

在数组尾部插入值为 $val$ 的元素
在数组第 $i$ 个位置上插入值为 $val$ 的元素
在数组尾部插入值为 $val$ 的元素：
- 如果数组尾部容量不满，则直接把 $val$ 放在数组尾部的空闲位置，并更新数组的元素计数值。
- 如果数组容量满了，则插入失败。不过，Python 中的 list 列表做了其他处理，当数组容量满了，则会开辟新的空间进行插入。

在数组尾部插入元素的操作不依赖数组个数，因此，在数组尾部插入元素的时间复杂度为 $O(1)$。

在数组第 $i$ 个位置上插入值为 $val$ 的元素：
- 先检查插入下标 $i$ 是否合法，即 $0 \le i \le len(nums)$。
- 确定合法位置后，通常情况下第 $i$ 个位置上已经有数据了（除非 $i == len(nums)$），要把第 $i \sim len(nums) - 1$ 位置上的元素依次向后移动。
- 然后再在第 $i$ 个元素位置赋值为 $val$，并更新数组的元素计数值。

在数组中间位置插入元素的操作中，由于移动元素的操作次数跟元素个数有关，因此，在数组中间位置插入元素的最坏和平均时间复杂度都是 $O(n)$。

将数组中第 $i$ 个元素值改为 $val$：

改变元素的操作跟访问元素操作类似，访问操作不依赖于数组中元素个数，因此，改变元素的时间复杂度为 $O(1)$。

删除元素分为三种情况：删除数组尾部元素、删除数组第 $i$ 个位置上的元素、基于条件删除元素

删除数组尾部元素的操作，不依赖于数组中的元素个数，因此，删除数组尾部元素的时间复杂度为 $O(1)$。

删除数组第 $i$ 个位置上的元素：
- 先检查下标 $i$ 是否合法，即 $0 \le i \le len(nums) - 1$。
- 如果下标合法，则将第 $i + 1$ 个位置到第 $len(nums) - 1$ 位置上的元素依次向左移动。
- 删除后修改数组的元素计数值。

删除数组中间位置元素的操作同样涉及移动元素，而移动元素的操作次数跟元素个数有关，因此，删除数组中间位置元素的最坏和平均时间复杂度都是 $O(n)$。

这种操作一般不给定被删元素的位置，而是给出一个条件要求删除满足这个条件的（一个、多个或所有）元素。这类操作也是通过循环检查元素，查找到元素后将其删除。

基于条件删除元素的操作同样涉及移动元素，而移动元素的操作次数跟元素个数有关，因此，基于条件删除元素的最坏和平均时间复杂度都是 $O(n)$。