【数据结构与算法】数组

一、是什么

一种用连续内存空间，存储相同类型数据的线性表数据结构

• 连续内存空间： 所以插入、删除操作低效，随机访问高效
• 线性表： 数据像一条线一样的结构，线性表上的数据最多只有前和后两个方向。数组、链表、队列、栈都属于线性表结构，而树、堆、图属于非线性表结构。

二、使用场景

• 存储数据容器
• 保存数据映射关系，方便下标取数

三、下标访问工作原理

address[i] = base_address + i * data_type_size

• address[i]： 下标i地址
• base_address： 数组首地址
• i： 即是数组下标，也是相对于首地址的偏移量
• data_type_size： 数组中每个元素的大小（数据类型的大小），例如int是4个字节

四、优劣

• 优点：
  根据下标随机访问的时间复杂度是O(1)
• 缺点：
  删除和插入操作低效
• 缺点优化：

1. 对于无序的数组（数组只是被当做存储数据的集合），要想将某个数据插入到第k个位置，为了避免大规模的数据搬移，直接将第k位的数据搬移到数组元素最后，把新元素直接放入第k个位置
2. 删除多个元素，为了避免内存空洞而产生的多次数据搬移操作，可以记下已经删除的数据，待最后触发一次真正的删除操作，减少数据搬移的次数

五、替代性技术

• 链表
• 栈
• 队列

六、延伸思考

为什么编程语言中的数组是从0开始编号

从数组存储的内存模型看，下标最确切的定义应该是偏移，对于随机访问地址公式：
address[i] = base_address + i * data_type_size，
如果数组从1开始计数，公式将变成：
address[i] = base_address + (i-1) * data_type_size,
对比这两个公式，发现从1开始编号，每次随机访问都多一次减法运算，对于CPU来说，多了一次减法指令