数组：为什么很多编程语言中数组都从0开始编号？
数组：为什么很多编程语言中数组都从0开始编号？
1. 数组的定义
数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。
2. 什么是 线性表 ？
线性表就是数据排成像一条线一样的结构。每个线性表的数据最多只有前和后两个方向。
数组、链表、队列、栈等都是线性表结构。
image
3. 什么是 非线性表 ？
在非线性表中，数据不是简单的前后关系。
二叉树、堆、图等都是非线性表。
image
4. 什么叫是 连续的内存空间 ？
数组中每个元素的存储地址都是相邻的。
image
因为数组是在一段连续的内存空间，存储相同类型的数据，使得数组具有一个非常nb的特性：随机访问。
5. 什么是 随机访问 ？
只要给我 下标 我就能直接根据索引获得元素值。
计算机会给每个内存单元分配一个地址，计算机通过地址访问内存中的数据。当计算机需要访问数组中的某个元素时，会先通过下面的寻址公式计算出该元素存储的内存地址：
image
这样主要有了下标，就可以直接访问到该元素，因为数组支持 随机访问，才使得 数组适合查找。
数组查找的时间复杂度要根据所使用的算法来计算。
- 正常的 for 循环直接判断是否相等来查找，那么复杂度就为：○(n)
- 对一个已经排好序的数组，使用二分查找，那么复杂度就为：○(㏒n)
- 还有一种表述方式：数组根据下标随机访问的时间复杂度为 ○(1)
注：访问和查找是两回事，访问只是取出值就可以了，查找是要判断有没有，在哪里。
6. 低效的 插入 和 删除
数组为了保持内存数据的连续性（就是元素要一个挨着一个，无间隙），会导致 插入、删除 这两个操作比较低效。
为什么？
image
image
7. 如何优化呢？
优化插入
image
优化删除
为了避免在插入或删除时，数据被多次迁移（插入一个，就迁移一堆），我们可以先记录下要删除的数据（每次执行删除时，并没有真正的删除数据，而是给数据一个状态，记录标识其不可用，属于已删除状态）。当数组没有更多空间存储数据时，再一次性触发真正的删除操作，此举可大大减少删除操作导致的数据迁移。
8. 数组的越界问题
分析下面这段 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;
}
我还没有好好系统的学习过 c ，所以对上段代码不是很了解，不过在看懂下面文字后也明白了大致意思：在 c 语言中，对数组越界的界定与处理是交给程序员来做的。
image
9. 容器能否完全代替数组
对于 Java 程序员经常用到的 ArrayList 来说，其最大的优势就是 可以将很多数组操作的细节封装起来。 例如数组的插入、删除时的迁移过程。而且，ArrayList 还支持动态扩容。
如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小，这样可以省去很多次 内存申请 和 数据迁移 的过程。
那么合适时候数组会好一些呢？
- 因为 ArrayList 无法存储基本数据类型，只能存储包装类型，此时就涉及到 自动装箱/拆箱 的过程，如果特别关注性能，或者想使用基本数据类型，此时可以使用数组。
- 如果数据大小事先已知，并且对数据的操作非常简单，可以直接使用数组。
- 一般情况下，在处理多维数据时，使用多维数组会比 ArrayList<ArrayList> 更直观。
对于业务开发而言，直接使用容器就够了，完全不会影响系统的性能。
10. 为什么很多编程语言中数组都从0开始编号？
根据第 4、5 小节的示例，如果用 a 来表示数组的首地址，那么 a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就表示偏移 k 个 type_size 的位置：
a[k]_address = base_address + k * type_size
但是如果数组从 1 开始计算，我们计算元素 a[k] 的内存地址就会变为：
a[k]_address = base_address + (k-1)*type_size
image
