重新认识数组

什么是数组

数组是一个连续内存空间，存储相同数据类型的数据结构。

数组优缺点

优点：由于连续的内存空间，且每个元素的数据类型相同，也就是每个元素的字节数相同，所以可以随件访问数组任意元素。计算公式为：a[k]_address = base_address + k * type_size。通过下标查找数组的时间复杂度为T(n) = O(1)。

缺点：不适合插入和删除，有序数组的删除和插入的时间复杂度为T(n) = O(n),无序数组的时间复杂度为T(n) = O(1)。

为什么数组的第一个下标为0

第一个下标为0时，计算数组a的下标为k的元素地址：a[k]_address = base_address + k * type_size。

第一个小标为1时，计算数组a的下标为k的元素地址：a[k]_address = base_address + （k-1） * type_size。

可以看出如果第一个小标为1时，对于 CPU 来说多了一次减法指令，数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。

二维数组在内存中的存储

上面讲了一维数组在内存中的计算公式，而一维数组在内存的数据结构很简单。

比如我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10]来举例，内存块的首地址为 base_address = 1000。

二维数组的数据结构也很简单，比如设置一个a[4][4]的数组，内存块的首地址为 base_address = 1000。

可以看出二维数组仍然是一个线性表.

二维数组的计算公式：
对于 一个m * n 的数组(i < m,j < n)，a[i][j]address = base_address + ( i * n + j) * type_size

总结

推理三维数组，四维数组同样是一个线性表