数组的基本操作

最新推荐文章于 2025-06-04 19:21:45 发布

空与一

最新推荐文章于 2025-06-04 19:21:45 发布

阅读量634

点赞数

分类专栏： Structure Algorithm LeetCode 文章标签：数据结构 leetcode c++

本文链接：https://blog.csdn.net/Anzeron/article/details/121408717

版权

6 篇文章

订阅专栏

本文探讨了数组这一线性数据结构，包括固定数组和动态数组的特性。固定数组在初始化后不改变内存空间，而动态数组可扩容。数组操作如下标访问的时间复杂度为O(1)，但插入和删除操作在动态数组中时间复杂度较高。对于仅需要基本操作的场景，固定数组提供更好的性能。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

数组是线性数据结构。

数组分成2种类型：

固定数组：
- 初始化的时候，分配一块内存空间，之后不会重新分配内存空间
- 长度的含义是指数组容纳最多元素的数量，并且必须包含这么多的元素
动态数组：
- 初始化的时候，分配一块内存空间，之后可能重新分配空间
- 长度的含义是指当前包含元素的数量，元素数量可以小于数组最大容量，并且允许不断地新增元素
- 如果元素数量超过现有的数组容量，会重新给数组分配内存空间，并拷贝已有元素。这称之为扩容。

结合数组的结构，其最大的特点是基于下标的内存寻址操作，通过该地址访问对应的元素，其公式如下。

address(i) = base + i * data_size

下标i是相对基地址的偏移量。下标可以从0开始，那计算出来的结果就是基地址，这也是数组下标从0开始的原因。

分析上述公式，可以得到2个结论。

固定数组，基于下标的操作，其时间复杂度都是O(1)。

如果是查找指定的元素，需要遍历数组，其时间复杂度是O(n)。

动态数组的操作包含了固定数组的操作，并且其时间复杂度相同。

动态数组相对固定数组，可以进行插入和删除操作。但是这2种操作的时间复杂度较高。

分析插入元素的过程。假设数组长度为n，插入元素的下标是i，其实质是将[i,n)区间的元素向后移动一位，移动的时间复杂度是O(n)。

同理，删除元素，其实质是将[i+1,n)区间的元素向前移动一位。

考虑插入和删除的特殊情况，在末尾进行操作，则无需移动元素，其时间复杂度提高到O(1)。