数组和数据结构的关系（数据结构学习2--数组）
数组和数据结构的关系（数据结构学习2--数组）来自数据结构与算法之美05数组和线性表对立的就是非线性表，比如二叉树、堆、图等，它们不仅仅是简单的前后关系，如下图所示：这里指出了数组的三个特点：首先，线性表就是数据排成一条线一样的结构，每个线性表最多只有前后两个方向，线性表结构如下图所示，数组、链表、队列和栈都属于这种结构。来自数据结构与算法之美05数组
数据结构学习系列第二篇--数组
数组数组是一个最基础而且常见的数据结构，几乎每种编程语言都有。
如何实现随机访问数组的定义：
数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
这里指出了数组的三个特点：
- 线性表(Linear List)
- 连续的内存空间
- 存储相同类型数据
首先，线性表就是数据排成一条线一样的结构，每个线性表最多只有前后两个方向，线性表结构如下图所示，数组、链表、队列和栈都属于这种结构。
来自数据结构与算法之美05数组
和线性表对立的就是非线性表，比如二叉树、堆、图等，它们不仅仅是简单的前后关系，如下图所示：
来自数据结构与算法之美05数组
接着就是需要连续内存空间和保存相同类型的数据。这两个特点让数组有一个非常好的特性：随机访问。也就是根据下标访问数组的时间复杂度是 O(1) ，但问题就是插入和删除需要 O(n)，因为需要进行大量的数据移动操作。
那么数组是如何实现随机访问的操作的呢？
首先，给定一个长度为 10 的 int 类型的数组 a[10] ，计算机会分配一块存储空间，这里假设就是 1000~1039 ，其中内存块的首地址是 base_address=1000，如下图所示
来自数据结构与算法之美05数组
计算机给每个内存单元分配一个地址，然后通过地址访问内存中的数据。因此，这里如果需要随机访问数组的某个元素，同样也是根据地址访问，也就是首先需要找到该元素存储所在的地址，寻址公式如下所示：
a[i]_address=base_address i*data_type_size
data_type_size 表示数组每个元素的大小，这里 int 类型是 4 个字节。
注意，对于数组来说，它支持随机访问，根据下标随机访问的时间复杂度是 O(1) ，但查找时间复杂度并非是 O(1) 因为即便排好序的数值，通过二分查找，时间复杂度是 O(logn) 。
低效的插入和删除数组的插入和删除操作由于其内存数据的连续性问题，这两个操作会非常低效，那么为什么会导致低效，有哪些改进方法呢？
插入操作假设数组长度是 n ，现在需要将一个数据插入到数组的第 k 位置，如果需要执行这样的操作，需要将第 k 到 n 位置上的元素都按顺序往后移动一位。这个操作的时间复杂度是多少呢？
最好的情况，就是末尾插入元素，这样不需要移动，O(1) 复杂度；最坏的情况，数组开头就插入元素，那么就是 O(n) 的时间复杂度。平均情况时间复杂度则如下所示，每个位置插入元素概率是相同的：
当然，如果数组是有序的，就需要按照上述做法移动元素。如果数组无序呢，一个快速的方法就是仅移动目标位置的元素，即第 k 个位置的元素放到数组末尾，然后插入元素即可，这样时间复杂度就是 O(1)。
一个简单的例子如下图所示，数组有 5 个元素：a b c d e，现在希望在第三个位置插入新元素 x，此时可以直接将 c 放到末尾，即 a[5] = a[2]，然后 a[2]=x，即可完成操作。
来自数据结构与算法之美05数组
这种特殊的处理技巧，可以在特定场景下(比如数组无序)将插入元素的时间复杂度降到 O(1)。
删除操作和插入数据类似，删除第 k 个位置元素，同样需要将后续的元素往前移动。
- 最好的情况是删除末尾数据，O(1)；
- 最坏就是删除开头的元素，O(n)；
- 平均情况时间复杂度也是 O(n)。
同样在某些特定场景下，并不需要时刻追求数组中数组的连续性，可以将多次删除操作集中在一起进行操作。
如下图所示是一个长度为 10 的数组，存储了 8 个元素，`现在是需要依次删除前三个元素，a，b，c。如果每次删除操作都将所有元素往前移动，那么后续的 5 个元素总共需要移动 3 次，为了避免这个情况，我们可以先记录被删除的数据，每次操作仅仅记录那个位置的元素被删除。当数组没有空间存储数据时，再进行一次真正的删除操作，这样可以避免删除操作导致的数据搬移。
来自数据结构与算法之美05数组
这个做法其实就是 Java 中 JVM 标记清除垃圾回收算法的核心思想。
所以，我们对于数据结构和算法的学习，不应该只是死记硬背，而是需要了解它背后的思想和处理技巧，明白为什么需要这种数据结构和这种算法。
数组的越界问题首先来看一段 C 语言的代码，如下所示：
intmain(intargc char*argv[]){
inti=0;
intarr[3]={0};
for(;i<=3;i ){
arr[i]=0;
printf("helloworld\n")
}
return0;
}
这段代码的问题就是打印结果的时候，因为循环结束条件问题，会无限打印 "hello world"，给定的数组长度是 3， 但是循环结束条件是 i<=3 ，而 a[3] 其实就是访问越界了。
但是，在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。也就是说，a[3] 也是可以访问的，但是会定位到非数组所在的内存上，而这个地址正好是存储变量 i 的内存地址，也就是 a[3]=0 就相当于 i=0 ，最终导致代码的无限循环。
数组越界在 C 语言中是一种未决行为，没有规定这种情况编译器应该如何处理，所以通常会出现各种奇怪的逻辑错误。
不过，其他编程语言并不会将数组越界的工作丢给程序员来做，它们会有做越界的检查。
数组索引从0开始的原因大多数的编程语言中，数组，或者说数据结构，索引都是从 0 开始，而不是从 1 开始。
首先，从数组存储的内存模型上看，索引，或者说“下标”最确切的定义应该是偏移(offset)。
前面介绍了数组的寻址公式：
a[i]_address=base_address i*data_type_size
如果数组是从 1 开始计数，那么寻址公式就会为：
a[i]_address=base_address (i-1)*data_type_size
对比两个公式，可以知道每次访问数组元素，从 1 开始计数的方式会多一次减法运算，相当于让 CPU 多一次减法指令，但随即访问数组元素应该是非常基础的操作，需要尽可能高效，因此，为了减少一次减法操作，数组采用从 0 开始计数，而非从 1 开始。
其次，主要是 C 语言设计者用 0 开始计数，后续的编程语言，如 Java 等都效仿了 C 语言，这也是方便 C 语言程序员学习其他语言的学习成本。当然，像 Python 还支持负数下标。
参考
极客时间的数据结构与算法之美课程
