数据结构-数组
本文介绍数据结构中的数组,包括数组的随机访问特性、插入删除的效率分析,以及为何数组下标从 0 开始

# 数据结构-数组

# 随机访问

  1. 数组是一种线性表数据结构,用一组连续的内存空间,来存储同一类型的数据
    • 线性表:数据排成线一样的结构,最多只有前和后两个方向
    • 数据、栈、队列、链表都是线性表结构
    • 堆、图、二叉树等数据之间不具有简单前后关系的结构,所以是非线性表结构
  2. 随机访问
    • 在连续的地址空间存相同类型的数据。这两个限制使数组具有随机访问的特性,但是在插入、删除时,为了保证数据连续性,需要做大量的数据搬移操作,影响性能
    • 随机访问时间复杂度为 O(1)
  3. 如何实现通过下标访问数据

例如,int[] a = new int[10]申请长度为10的数组,首地址为1000,连续内存空间为1000~1039

每个int类型占4个字节,每个内存地址上可以存入1个字节。所以知道首地址便可以推出后续其他地址

计算公式:a[i]_address = base_address + i * data_type_size

# 低效的插入删除

  1. 插入
    • 在数组中插入数据,需要移位操作
    • 平均时间复杂度为 O(n),最好 O(1),最坏 O(n)
    • 如果不要求数组有序,只当作存储数据的集合,可以直接把第 k 位移到尾部,然后插入第 k 位
  2. 删除
    • 在数组中删除数据,需要移位操作
    • 平均时间复杂度为 O(n),最好 O(1),最坏 O(n)
    • 为了避免连续删除造成连续搬移,可以将触发删除操作的数据记下来,待空间不够时,集中进行搬移

# 为何从 0 开始编号

  1. 从数组的内存模型来看,“下标“最准确的定义应该为”偏移“,a[0] 为偏移为 0 的位置,即首地址,计算 a[i] 的地址需要:a[i]_address = base_address + i * data_type_size,从 1 开始编号需要多做一次减法运算
  2. 历史原因:C 语言设计者用 0 开始标记数组下标,后来的高级语言沿用了此习惯
Comment here, be cool~

Copyright © 2020 CadeCode

Theme 2zh powered by VuePress

本页访问次数 0

Loading