数据结构-数组

数组是使用最广泛的基础数据结构。数组是存放在连续内存空间上的相同类型数据的集合，可以方便的通过数字索引的方式获取到索引所对应的数据。需要注意的是数组的索引都是从0开始计算的。下图就是长度为3的字符数组的例子。

内存地址	1001	1002	1003
数组元素	‘a’	‘b’	‘c’
数组索引	0	1	2

假设一个数组，其元素按照值的固定顺序排序(升序或降序)，那么这种数组被称为有序数组。在实际的算法使用中常常会对数组先进行排序，然后在进行处理。

使用数组(Java)

下面介绍如何使用数组。

定义

Java中的数组声明很简单:

// 定义时初始化
int[] array = new int[]{0,0,0};
// 通过长度定义, 元素会被初始化为默认值
// int的默认值是0
int[] array = new int[3];

数组长度

数组提供了一个length参数，可以获取数组的长度。注意一旦创建数组的长度就不能再变化，只能通过重建新的数组扩容。

int[] array = new int[3];
int arrayLength = array.length;
assert arrayLength == 3

getter & setter

数组的一个最大特点是：可以进行随机访问。即数组可以根据下标，直接定位到某一个元素存放的位置。

int[] array = new int[3];
array[0] = 1; 
array[1] = 2;
array[2] = 3;  
int head = array[0];
assert head == 1

查找

数组的查找和删除就稍微麻烦一点。对于查找，需要遍历数组，将目标值和每个元素对比。

int search(int[] arr,int target) {
    for (int i = 0; i < arr.length; i++) {
       if(arr[i] == target){
        return i;
       }
    }
    throw new IllegalArgumentException("not found");
}

删除

对于删除，如果不知道索引的情况下，删除需要遍历数组，如果知道索引，可以通过指定索引设置 null的方式删除(基类数组通过设置默认值的方式删除)。

int[] array = new int[3];
array[0] = 1;  
// -1 是默认值
array[0] = -1;
String[] strs = new String[3];
strs[0] = null;

多维数组

上面介绍的数组只有一个维度，称为一维数组，其数据元素也是单下标变量。但是在实际问题中，很多信息是二维或者是多维的，一维数组已经满足不了我们的需求，所以就有了多维数组。

chars	0	1	2
0	‘a’	‘b’	‘c’
1	‘d’	‘e’	‘f’

二维数组是一个由 m 行 n 列数据元素构成的特殊结构，其本质上是以数组作为数据元素的数组，即 「数组的数组」。二维数组的第一维度表示行，第二维度表示列。例如上面的二维数组:

assert chars[0][1] == 'b'

可以将二维数组看做是一个矩阵，并处理矩阵的相关问题，比如转置矩阵、矩阵相加、矩阵相乘等等。