查看: 110|回复: 0

什么是数组?

[复制链接]
发表于 2020-2-18 10:25:53 | 显示全部楼层 |阅读模式
今天要先容的主角就是-数组,数组也是数据呈线性分列的一种数据结构。与前一节中的链表不同,在数组中,访问数据非常简朴,而添加和删除数据比较耗工夫。这和什么是数据结构那篇文章中讲到的姓名按拼音顺序分列的电话簿雷同。
数组


如上就是数组的概念图,Blue、Yellow、Red 作为数据存储在数组中,其中 a 是数组的名字,后面 [] 中的数字表现该数据是数组中的第几个数据,该数字也就是数组下标,下标从 0 开始计数,好比 Red 就是数组 a 的第 2 个数据。
那么为什么许多编程语言中的数组都从 0 开始编号的呢?先别急,可以先自己思考下,将会在文末进行解说。

从图中可以看出来,数组的数据是按顺序存储在内存的一连空间内的。

由于数据是存储在一连空间内的,所以每个数据的内存所在(在内存上的位置)都可以通过数组下标算出,我们也就可以借此直接访问目标数据,也就是随机访问

好比现在我们想要访问 Red,假如是链表的话,只能使用指针就只能从头开始查找,但在数组中,只必要指定 a[2],便能直接访问 Red。

但是,假如想在任意位置上添加或者删除数据,数组的操作就要比链表复杂多了。这里我们实行将 Green 添加到第 2 个位置上。

首先,在数组的末尾确保必要增长的存储空间。

为了给新数据 Green 腾出位置,要把已有数据一个个移开,首先把 Red 往后移。

然后把 Yellow 往后移。

最后在空出来的位置上写入 Green。

添加数据的操作就完成了。
反过来,假如想要删除 Green 呢?

首先,删掉目标数据 Green。

然后把后面的数据一个个往空位移,先把 Yellow 往前移。

接下来移动 Red。

最后再删掉多余的空间,这样一来 Green 便被删掉了。
补充

这里解说一下对数组操作所耗费的运行时间,假设数组中有 n 个数据,由于访问数据时使用的是随机访问(通过下标可计算出内存所在),所以必要的运行时间仅为恒定的 O(1)。
通过数组下标计算出内存所在的寻址公式如下:
  1. a[i]_address = base_address + i * data_type_size
复制代码
其中 base_address 为内存块的首所在,data_type_size 表现数组中每个元素的大小。
但另一方面,想要向数组中添加新数据时,必须把目标位置后面的数据一个个移开。所以,假如在数组头部添加数据,就必要 O(n) 的时间,删除操作同理。
在链表和数组中,数据都是线性地排成一列。在链表中访问数据较为复杂,添加和删除数据较为简朴;而在数组中访问数据比较简朴,添加和删除数据却比较复杂。
我们可以根据哪种操作较为频繁来决定使用哪种数据结构。

最后,让我们一起来思考下刚开始提到的问题:为什么许多编程语言中数组都从 0 开始编号?
解惑

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。假如用 a 来表现数组的首所在,a[0] 就是偏移为 0 的位置,也就是首所在,a[k] 就表现偏移 k 个 type_size 的位置,所以计算 a[k] 的内存所在只必要用这个公式:
  1. a[k]_address = base_address + k * type_size
复制代码
但是,假如数组从 1 开始计数,那我们计算数组元素 a[k] 的内存所在就会变为:
  1. a[k]_address = base_address + (k-1)*type_size
复制代码
对比两个公式,可以发现,从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。
数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是从 1 开始。
除此之外还有汗青缘故原由,C 语言设计者用 0 开始计数数组下标,之后的 Java、javascript 等高级语言都效仿了 C 语言,或者说,为了在一定程度上减少 C 语言程序员学习 Java 的学习本钱,因此继续相沿了从 0 开始计数的风俗。实际上,许多语言中数组也并不是从 0 开始计数的,好比 Matlab。甚至还有一些语言支持负数下标,好比 Python。
总结

这篇文章重要先容了数据结构中常用的数组,数组用一块一连的内存空间,来存储相同类型的一组数据,最大的特点就是支持随机访问,但插入、删除操作也因此变得比较低效,平均情况时间复杂度为 O(n)。有一种高效的查找算法是二分查找法,就是使用了数组随机访问的特性。
总得来说,数组实用于多操作多、写操作少的场景,和我们上一篇文章中的链表正好相反。
参考
《我的第一本算法书》
数据结构与算法之美

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?用户注册

x

天涯海角也要找到Ni:什么是数组?

中发现Ni: 什么是数组?
中发现Ni: 什么是数组?
中发现Ni: 什么是数组?
中发现Ni: 什么是数组?
中发现Ni: 什么是数组?
中发现Ni: 什么是数组?
相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表