数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据

线性表和非线性表

线性表中的数据只有前后两个方向，排成一条线，常见包括，数组，链表，队列，栈等。
非线性表中的数据不是简单的前后关系，可以一对多，常见有二叉树，堆，图等。

数组为什么从0开始？

当数组下标从0开始

a[i]_address = base_address + i * data_type_size

图片来自于极客时间，数据结构与算法之美

当数组下标从1开始

因为物理存储空间是固定的，因此可以知道
a[i]_address = base_address + (i-1)*data_type_size
每次随机访问数组是，CPU都要多执行一次减法指令
数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化应该做到极致

看看下面C语言代码

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;
}

结果：会无限死循环下去
解释1:在C语言中，只要不是访问受限的内存，所有内存都可以自由访问，a[3]会被定位到不属于数组的内存，由于局部变量分配内存是在栈中从高到低分配的，所以分配地址顺序分别为i,a[2],a[1],a[0]，当i=3时，a[3]通过寻址访问的地址刚好是i的地址，a[3]=0也就是i=0，因此会无限循环下去。
解释2:（个人觉得更靠谱）和编译器有关，C语言在一般编译器里int型变量占四个字节，由于局部变量分配内存是在栈中从高到低分配的，所以分配的地址由高到低分别是i,a[2],a[1],a[0]，但由于编译器分配空间需要按8字节对齐，又因为数组此时长度为3刚好和i凑在一起满足8字节对齐，所以他们的空间是连续的，a[3]越界访问的地址刚好为i地址。dev-c++运行实例如下图

数组长度为3

数组长度为4

总结

1.数组的“下标”又称“偏移（offset）”，例如int a[] = new a[10]; a表示该数组的首地址，a[0]表示偏移量为0的地址。
2.数组在实际运用中，一定要注意越界情况，稍有不慎可能玩完。
3.最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。
······

拓展了解

1.JVM的深入了解
2.Java中的ArrayList（容器）
3.C++中的vector（动态数组，也称向量）