数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。数组的两个特点是:
- 线性表
- 连续的内存空间和相同类型的数据(随机访问)
计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:
a[i]_address = base_address + i * data_type_size
// 如果数组从 1 开始计数
a[k]_address = base_address + (k-1)*type_size
数组从
1
开始编号,是因为根据寻址公式,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。
注意:数组支持随机访问,根据下标随机访问的时间复杂度为
这点很多博客没有注明。
假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。平均情况时间复杂度为
C++
、JAVA
等语言都提供了类似数组的容器类,比如 C++
STL
中的 vector
。根据我的经验,一般情况下,推荐用容器开发,简单省事、代码易懂,底层和高性能开发用数组,毕竟容器的灵活性还是牺牲了一定性能的。