数组概念
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据, 并且不支持动态扩容。
线性表
线性表就是数据排成一条线一样的数据结构,每个线性表最多只有前后两个方向,数组,链表丶队列丶栈等都是线性表数据结构。
非线性表
非线性表就是数据不规则,与线性表是相对立的,比如二叉树丶堆丶等,在非线性表中,数据之间并不是简单的前后关系。
数组随机访问
公式
address[i] = base_address + i * data_type_size
address[i] : 下标 i 的地址值。
base_address: 数组的首地址。
data_type_size: 数组中每个元素的大小,也就是数据类型大小(字节),例如int是4个字节。
数组的增加和删除
数组 (Array) 在增删查这三个动作中,查询是高效的,但是增和删是低效的,查询高效是因为数组支持随机访问,时间复杂度是 O(1) ,这里就不多赘述了,但是在增加和删除的动作中,因为会涉及数据搬移,所以时间复杂度是 O(n) ,下面来详细讲解。
低效的"插入"和"删除"
int[] info = new int[6];
插入
数组 info 是一个一维数组,其内容是 33,44,66,77,88 现在需要在下标 2 的位置插入 55 ,将其变成33 44 55 66 77 88的数组,这其中涉及将下标 2 到下标 4 的之间进行数据进行搬移,完成后在下标 2 的位置插入 55 , 其复杂度是 O(n), 但如果是在最后进行插入的话其复杂度是 O(1)。
删除
还拿数组 info 来举例,数组删除前其内容是 33,44,00,55,66,77 现在进行删除操作,删除下标为 2 内容,这其中涉及将下标 3 到 5 的内容向前搬移,其操作的时间复杂度是 O(n) ,如果是是删除最后一位且后面没有内容,则其时间复杂度是O(1) 。
因插入和删除操作会涉及到数据搬移,所以说他是低效的。
问题:为何数组要从0开始编号,而不是1开始呢?
从数组的模型上来看的话,"下标"确切的定义应该是"偏移(offset)".也就是说,如果用a来表示数组的话,a[0]就表示偏移为0的位置,也就是首地址,a[i]就表示偏移为i个type_size的位置,所以计算a[i]的内存地址只需要使用下面的这个公式即可:
a[i]_address = base_address + i * type_size
如果是从1开始编号的话,那么计算数组元素a[i]的内存地址就成了:
a[i]_address = base_address + (i-1) * type_size
对于当中的参数的含义,base_address:数组的首地址,正如文章开头画的图表示的事1000,k表示的则是数组的下标,type_size则表示数组存储的数据的大小,如果存储的是一个int型的数据,那么就是4字节。
对比上面两个公式,并结合文章开头说话的图验证一下,可以发现,从1开始编号,每次随机访问数组元素都多了一次减法运算,对于CPU来说的话,那就是多了一次减法指令。
数组作为非常基础的数据结构,通过下标随机访问数组元素有事非常基础的编程操作,效率的优化就要尽可能的做大极致。所以为了减少一次减法操作,数组选择了从0开始编号,而不是从1开始编号。