菜鸟笔记
提升您的技术认知

数组

阅读 : 165

数组概念

数组(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开始编号。