数组

  • A+
所属分类:算法与数据结构

数组

数组是线性表数据结构,用一组连续的内存空间,来存储一组数据类型相同的数据。

线性表即只有前后两个方向。链表、队列、栈都属于线性表。树、图都是非线性表。

特点:可以随机存取,根据数组下标,随机访问数据的时间复杂度为O(1)。

元素所在的内存地址:

a[i]_address = base_address + I * data_type_size

在插入删除数据时,最好时间复杂度为O(1),最坏和平均时间复杂度都为O(n)。在插入数据时,如果对数据没有严格的顺序,可以通过将原来的数据移到末尾,再插入新的数据的方法来降低时间复杂度。在删除数据时,可以通过多次删除合并为一次删除的方法来降低时间复杂度。

下标更准确的定义是偏移(offset)。从0开始即偏移量为0,首地址+偏移量×type_size即为元素的地址。

LTXU
  • 版权声明:本站原创文章,于2019年5月13日21:06:47,由 发表,共 344 字。
  • 转载请注明:数组 | AICSDN

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: