重新认识数组

计算机软件开发 · 2024-9-17 18:05:44

什么是数组

数组是一个一连内存空间，存储类似数据范例的数据结构。
数组优缺点

优点：由于一连的内存空间，且每个元素的数据范例类似，也就是每个元素的字节数类似，所以可以随件访问数组恣意元素。盘算公式为：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[j]address = base_address + ( i * n + j) * type_size
总结

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

重新认识数组

所属分类: 问答交流

新帖推荐: 30日

推荐作品