数组与线性结构
数组
数组是存放一组同类型元素最简单的方式：一整块连续内存把它们一个挨一个地排好，就像一排编号为 0、1、2…… 的相同邮箱。因为每个元素大小相同又紧挨着，计算机可以直接跳到第 i 个元素——它的地址就是这块内存的起始位置加上 i 乘以单个元素的大小，既不用查找，也不用逐个走过前面的元素。
这一点就是数组的看家本领：读写 array[i] 都是 O(1) 时间，无论数组多大、i 落在哪里。代价则体现在别处。数组的大小通常在创建时就固定了，想扩容就得另开一块新内存再把数据全部拷过去；在中间插入或删除元素，则要把后面的所有元素整体挪动来保持连续，最坏情况是 O(n)。
几乎所有其他结构都建立在数组之上——字符串、动态数组、栈、队列、哈希表和堆底层都用到数组。当你需要按下标快速访问、又大致知道有多少元素时，朴素的数组很难被超越。
int a[5] = {10, 20, 30, 40, 50};
// index: 0 1 2 3 4
// +----+----+----+----+----+
// | 10 | 20 | 30 | 40 | 50 |
// +----+----+----+----+----+
int x = a[3]; // O(1): jump straight to slot 3 -> 40
a[1] = 99; // O(1) write
// inserting before index 1 would shift 20,30,40,50 right: O(n)按下标访问是 O(1)；其布局就是一整块扁平内存。
大多数语言的数组从 0 开始计数，所以长度为 n 的数组下标是 0 到 n-1。越界读取是经典而危险的错误。
又称
另见