数据结构——数组Array

各类语言中的数组（）是对此数据结构中的数组进行了封装，并添加了各自语言的特性。

1.定义

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

1.1线性表

线性表就是数据排成像一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。
线性表结构：数组，链表，队列，栈

1.2 连续的内存空间和相同的数据类型

• 优势：因为这两个限制，才有了杀手锏的特性：随机访问。
• 劣势：让数组的很多操作变得很低效，如：在数组中插入和删除一个数据，为了保证连续性，就需要大量的数据搬移工作。

纠正错误：数组和链表的区别，很多人回答说：“链表适合插入、删除，时间复杂度为O(1)；数组适合查找，查找时间复杂度O(1)”。
实际上这种表述不准确。数组是适合查找操作，但是查找的时间复杂度并不为O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。

2.数组越界问题

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

这段代码并非是打印三行“hello world”，而是无限打印“Hello world”（32位操作系统）（64位操作系统，i<=7，无限打印）,(推荐gcc编译器运行)。

原因：

1.数组大小为3，分别为：a[0],a[1],a[2];
2.i=3时,a[3]访问越界，但是c语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的
3.a[3]会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量i 的内存地址，那么a[3]=0就相当于i = 0,所以导致代码虚线循环。
4.数组越界在C语言中是一种未决行为，并没有规定数组访问越界是编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过便宜计算得到的内存地址是可用的，那么程序就可能不会抱任何错误。

注：针对数组类型，很多语言提供了容器类，比如JAVA中ArrayList,ArrayList最大的有事就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入，删除数据时需要搬移其他数据等，另外，还支持动态扩容。