什么是数组？
- 数组（Array）是一种<u>线性表</u>数据结构。它用一组<u>连续的内存空间</u>，来存储一组具有相同类型的数据
- 线性表：数据排成像一条线一样的结构（数组、链表、队列、栈）
- 连续的内存空间和相同的数据类型：因为这两个限制，数组有“随机访问”的特性，但是让数组的很多操作变得低效，如 删除、插入，为了保证连续性，需要大量数据搬迁
非线性表 ：数据之间并不是简单的前后关系，如 二叉树、堆、图等
访问数组元素的原理
如 一个长度为10 的 int 类型数组
Java：int[] a = new int[10]，分配了一块连续内存空间 1000～1039（Java 的 int 的长度为 4 字节），内存首地址为 base_address=1000
Go: var a:=[10]int{1,2,3,4,5,6,7,8,9,10} ，分配一块连续内存空间 32位系统下 1000～1039，64位系统下 1000～1079 （Go 的 int 的长度是根据系统位数来决定的，32位系统是4字节，64位系统是8字节）
寻址公式：
<pre class="cm-s-default" style="color: rgb(89, 89, 89); margin: 0px; padding: 0px; background: none 0% 0% / auto repeat scroll padding-box border-box rgba(0, 0, 0, 0);">a[i]_address = base_address + i * data_type_size</pre>
data_type_size 是int类型字节大小
低效的“插入”和“删除”
插入
有序数组
- 往数组插入一个数据到 K 位置，为了给第 K 个位置腾出来给新数据，需要将第 K～N这部分的数据顺序的往后挪一位，时间复杂度为 O(n)
- 如果在末尾插入元素，不需要移动数据，时间复杂度为 O(1)
- 如果在数据开头插入元素，那所有的数据都要依次往后挪一位，所以最坏时间复杂度为O(n)
- 因为在每个位置插入元素的概率是一样的，所以平均时间复杂度为(1+2+...+n)/n=O(n)
无序数组
- 往数组插入一个数据到 K 位置，可以把 K 位置的数据搬到数组元素的最后，把新的元素直接放入到 K 位置
删除
删除第 K 个位置的数据，为了内存的连续性，需要搬移数据，不然中间会出现空洞，内存就不连续了
特殊场景下，并不一定非要追求数组中数据的连续性。如果将多次删除操作集中在一起执行，删除效率会提高
为了避免d,e,f,g,h被多次搬移，可以先记录下已经被删除的数据。每次的删除操作并不是真正的搬移数据，只是记录数据已经被删除。让数组没有更多的空间存储数据时，再出发执行一次真正的删除操作，这样就减少了删除操作导致的数据搬移。
数组越界
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时，数组a[3]访问越界
在C中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的，所以，根据数组寻址公式，a[3]也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量 i 的内存地址，那么 a[3]=0 就相当于 i=0，所以会导致代码无限循环（函数体内的局部变量存在栈上，且是连续压栈。在Linux进程的内存布局中，栈区在高地址空间，从高向低增长。变量i和arr在相邻地址，且i比arr的地址大，所以arr越界正好访问到i。当然，前提是i和arr元素同类型，否则那段代码仍是未决行为。）<u>操作系统或计算机体系结构的教材应该会讲到</u>
数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。
数组优化
- 支持动态扩容
- 事先指定数据大小
为什么大多数编程语言数组要从 0 开始编号
- 为了性能
- 如果从0开始编号， a[k]_address = base_address + k * type_size
- 如果从1开始编号， a[k]_address = base_address + (k-1) * type_size
从 1 开始编号每次随机访问对CPU来说都会多一次减法运算，数组作为非常基础的数据结构，通过下标是非常基础的操作，效率的优化得做到极致，所以为了减少一次减法操作，数组选择了从0开始编号
还有一种说法是C设计用 0 开始计数数组下标，之后的语言为了降低学习成本，所以沿用了数组下标从0开始计数。
