数组

1、什么是数组？

数组（array）是一种线性表数据结构。用一组连续的内存空间，来储存一组具有相同数据类型的数据。
优点：支持随机访问，适合查找
缺点：删除、插入数据效率低
注意: 多维数组不是线性表数据结构。

2、数组如何实现根据下标随机访问数组的元素？

例：int[] a = new int[10];
计算机给数组a分配了一块连续的内存空间1000~1039。内存块的首地址是1000
当计算机需要随机访问某个元素，可以通过寻址公式，计算出该元素存储的内存地址。
a[i]_address = base_address + i * data_type_address

3、为什么数组要从0开始？

由于数据是通过寻址公式，计算出该元素的内存地址：
a[i]_address = base_address + i * data_type_address

如果数组是从1开始计数：
a[i]_address = base_address + （i - 1） * data_type_address
对于cpu来说多做了一次减法。
当然也可能是因为c语言设计者从0开始计数数组下标，减少c语言程序员学习java的学习成本，因此沿用了从0开始计数的习惯。

4、数据结构中的“数组”与编程语言中的“数组”的区别和联系

大部分的数据结构和算法书籍中，数组作为最基础的数据类型，一般这样定义：

数组这种数据结构，是存储相同数据类型的一块连续的存储空间。
解读一下这个定义的话，那就是：数组中的数据必须是相同类型的，数组中的数据必须是连续存储的。
只有这样，数组才能实现根据下标快速地（时间复杂度是O(1)）定位一个元素

我们所熟悉的编程语言中，“数组”这种数据类型，不一定符合上面的定义。
比如javascript：数组中的数据不一定连续储存的。也不一定是相同类型，甚至数组可以变长的。
var`` arr = ``new`` ``Array``(``4``,``'hello'``, ``new`` ``Date``());

二位数组：
二维数组中的数据，是先按行再按列（或者先按列后按行），依次存储在连续的存储空间中。

如果二维数组定义为a[n][m]，那a[i][j]的寻址公式为下面这样（先按行后按列存储）：

address_a[i][j] = address_base + (im+j) data_size;

先按列后按行存储：

address_a[i][j] = address_base + (i+jn) data_size;

a. C/C++中数组的实现方式

C/C++中的数组，是非常标准的数据结构中的数组，也就是连续存储相同类型的数据的一块内存空间。在C/C++中，不管是基本类型数据，比如int、long、char，还是结构体、对象，在数组中都是连续存储的。

int arr[3];arr[0] = 0;arr[1] = 1;arr[2] = 2;

struct Dog {  
    char a;  
    char b;
};
struct Dog arr[3];
// 为了节省页面，放到了一行里了
arr[0].a = '0'; 
arr[0].b = '1'; 
arr[1].a = '2'; 
arr[1].b = '3';
arr[2].a = '4';
arr[2].b = '5';

struct Dog {  
    char a;    
    char b;};
struct Dog arr[3][2];

b、 Java中数组的实现方式

Java中的数组就有点跟数据结构中数组的定义不一样了。我们还是分三种情况来分析。这三种情况分别是：基本数据类型数组、对象数组、二维数组（或多维数组）。

首先，我们先来看下基本数据类型数组，也就是说，数组中存储的是int、long、char等基本数据类型的数据。我们还是拿一段代码来举例。

int arr[] = new int[3];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;

如果我们把arr中数据在内存中的存储方式，用图画出来的话，就是下面这个样子的。注意，new申请的空间在堆上，arr存储在栈上。arr存储的是数组空间的首地址。

从图中来看，在Java中，基本数据类型数组还是符合数据结构中数组的定义的。数组中数据是相同类型的、并且存储在一片连续的内存空间中。

我们再来看下对象数组，也就是说，数组中存储的不是int、long、char这种基本类型数据了，而是对象。我们还是拿一个例子来说明。

class Person {    
    private String name;    
    public Person(String name) {    
        this.name = name;    
    }}
Person arr[] = new Person[3];
arr[0] = new Person("0");
arr[1] = new Person("1");
arr[2] = new Person("2");

从图中，你有没有发现，在Java中，对象数组的存储方式，已经跟C/C++中对象数组的存储方式，不大一样了。在Java中，对象数组中存储的是对象在内存中的地址，而非对象本身。对象本身在内存中并不是连续存储的，而是散落在各个地方的。

Java中的二维数组，跟数据结构中二维数组，有很大区别。在Java中，二维数组中的第二维，可以是不同长度的。这句话有点不好理解。我举个例子说明一下。

int arr[][] = new int[3][];
arr[0] = new int[1];
arr[1] = new int[2];
arr[2] = new int[3];

在上面的代码中，arr是一个二维数组，第一维长度是3，第二维的长度各不相同：arr[0]长度是1，arr[1]长度是2，arr[2]长度是3。如果我们把这个数组在内存中的存储方式，用图画出来的话，就是下面这个样子。

刚刚这个二维数组存储的是基本数据类型，我们再来看下，如果二维数组中存储的是对象，那又会是怎么的数据存储方式呢？我们还是拿个例子来说明。

总结一下。在Java这种编程语言中，数组这种数据类型，除了存储基本数据类型的一维数组之外，对象数组、二维数组，都跟数据结构中数组的定义，有很大区别了。

c、JavaScript中数组的实现方式

实际上，JavaScript中数组的底层实现原理，已经不是依赖数据结构中的数组了。也就是说，JavaScript中的数组只不过是名字叫数组而已，跟数据结构中数组没啥太大关系。
还提供了一种数据类型，叫做ArrayBuffer。而ArrayBuffer才符合标准的数据结构中数组的定义。它分配一片连续的内存空间，仅仅用来存储相同类型的数据。