数组定义
一组线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
关键词解释
- 线性表：每个线性表上的数据最多只有前和后两个方向。
除了数组，链表、队列、栈都是线性表结构
联想到非线性表：数据之间并不是简单的前后关系。
如，二叉树、堆、图等
- 连续的内存空间和相同类型的数据
正因为有了这两个限制，才使得数组有了随机访问的特性；
也正是因为这两个限制，使得数组的删除、插入操作效率很低。
如何实现根据下标随机访问数组元素？
计算机会给每个内存单元分配一个地址，再通过地址来访问内存中的数据。
而计算机通过寻址公式来计算元素存储的内存地址：
//a[i]的地址就是从首地址偏移i*data_type_size的位置
a[i] = base_address + i * data_type_size
base_address: 内存块的首地址
data_type_size：数中每个元素的大小；根据存储的数据类型而定，如int型，该值为4
为什么数组要从0开始编号，而不是从1开始呢？
若数组从1开始计数，那么上面的公式就变成
a[i] = base_address + (i-1) * data_type_size
修改后，每次随机访问数组元素都多了一次减法运算，对于CPU就多了一次减法指令。
两个操作
数组的插入操作
- 效率低的原因：将某个数据插入到数组中的第
i个位置。为了给新来的元素腾出这个位置，需要移动后面的i~n个元素，复杂度为O(n); - 改进方法：当数组是无序的，简单的方法就是将原来第
i个位置上的元素放到数组最后，然后将新来的元素放到第i个位置。复杂度为O(1);
数组的删除操作
与插入操作类似，若删除第i个位置的元素，需要搬移后面的i~n个元素，才能保证内存的连续性。
- 复杂度：若删除开头元素，最坏复杂度为
O(n)；若删除数组末尾元素，最好复杂度为O(1)；平均复杂度为O(n)。 - 改进方法：不要求数组中数据的连续性，就可将多次删除操作集中在一起执行。
每次删除元素时，并不真正搬移元素，而是记录下数据已被删除。当数组没有更多空间存储数据时，再执行一次真正的删除操作（做数据元素的搬移工作）
数组的访问越界问题
分析以下一段代码：
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0};
for(; i<=3; i++){
arr[i] = 0;
printf("hello world\n");
}
return 0;
}
问题
不是只打印三行“hello world”；而是无限打印
原因
数组大小为3，a[0]，a[1]，a[2]，而我们的代码 for 循环的结束条件错写为了i<=3 而非 i<3，所以当 i=3 时，数组 a[3] 访问越界。
根据我们前面讲的数组寻址公式，a[3] 也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量 i 的内存地址，那么 a[3]=0 就相当于 i=0，所以就会导致代码无限循环。
注：例子中死循环的问题跟编译器分配内存和字节对齐有关。数组3个元素，加上一个变量i。4个整数刚好能满足8字节对齐，所以i的地址恰好跟在a[2]后面，导致死循环。如果数组本身有4个元素，则这里不会出现死循环。因为编译器64位操作系统下，默认会进行8字节对齐，变量i的地址就不会紧跟在数组后面了。
Key
1 . 常会问的一个面试题：数组和链表的区别？
正确表述：链表适合插入、删除操作，时间复杂度为O(1)；数组适合随机访问数组元素(而不应该说查找)，根据下标随机访问的时间复杂度为O(1)。
明确的点：数组是适合查找，但查找的时间复杂度不为O(1)。即便是排好序的数组，用二分查找，时间复杂度也是O(nlogn)。
2 . 数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。
在这种情况下，一般都会出现莫名其妙的逻辑错误，就像上面举的那个例子，debug的难度非常的大。而且，很多计算机病毒也正是利用到了代码中的数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码的时候一定要警惕数组越界。
3 . 二维、多维数组如何寻址？
行优先
int a[d1][d2][d3];
int *p0 = &a[0][0][0];
int *p = &a[i][j][k];
int idx = i * (d2*d3) + j * d3 + k
ASSERT( p0 + idx == p);