数据结构-数组

随机访问

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 开始标记数组下标，后来的高级语言沿用了此习惯