数据结构简介

数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。

如下图所示，常见的数据结构可分为「线性数据结构」与「非线性数据结构」，具体为：「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。

Picture1.png

数组

数组（array）是一种最简单的复合数据类型，它是有序数据的集合，数组中的每个元素具有相同的数据类型，可以用一个统一的数组名和不同的下标来确定数组中唯一的元素。根据数组的维度，可以将其分为一维数组、二维数组和多维数组等。

Picture2.png

创建一维数组

声明数组

为了在程序中使用一个数组，必须声明一个引用该数组的变量，并指明整个变量可以引用的数组类型。声明一维数组的语法格式为：

1
2
3
type[] arrayName; 		//数据类型[] 数组名;
//或者
type arrayName[]; 		//数据类型 数组名[];

数组的声明有两种形式：一种是中括号”[]“跟在元素数据类型之后，另一种是中括号”[]“跟在变量名之后。

对于以上两种语法格式而言，Java 更推荐采用第一种声明格式，因为第一种格式不仅具有更好的语意，而且具有更好的可读性。其中的数据类型既可以是基本数据类型，也可以是引用数据类型。数组名可以是任意合法的变量名。声明数组就是要告诉计算机该数组中数据的类型是什么。例如：

1
2
3
4
5
6
int[] score;		//存储学生的成绩，类型是整型
double[] price;		//存储商品的价格，类型是浮点型
String[] name;		//存储商品名称，类型为字符串型

//在声明数组时不需要规定数组的长度，例如：
int score[10];		//这是错误的

分配空间

声明了数组，只是得到了一个存放数组的变量，并没有为数组元素分配内存空间，不能使用。因此要为数组分配内存空间，这样数组的每一个元素才有一个空间进行存储。

简单地说，分配空间就是要告诉计算机在内存中为它分配几个连续的位置来存储数据。在 Java 中可以使用 new 关键字来给数组分配空间。分配空间的语法格式如下：

1
arrayName = new type[size];		//数组名 = new 数据类型[数组长度]

其中，数组长度就是数组中能存放的元素个数，显然应该为大于 0 的整数，例如：

1
2
3
score = new int[10];
price = new double[30];
name = new String[20];

这里的 score 是已经声明过的 int[] 类型的变量，当然也可以在声明数组时就给它分配空间，语法格式如下：

1
type[] arrayName = new type[size];    // 数据类型[] 数组名 = new 数据类型[数组长度];

例如，声明并分配一个长度为 5 的 int 类型数组 arr，代码如下：

1
int[] arr = new int[5];

img

在图 中 arr 为数组名称，方括号“[]”中的值为数组的下标。数组通过下标来区分数组中不同的元素，并且下标是从 0 开始的。因此这里包含 5 个元素的 arr 数组最大下标为 4。

注意：一旦声明了数组的大小，就不能再修改。这里的数组长度也是必需的，不能少。

初始化一维数组

Java 语言中数组必须先初始化，然后才可以使用。所谓初始化，就是为数组的数组元素分配内存空间，并为每个数组元素赋初始值。

能不能只分配内存空间，不赋初始值呢？

不行，一旦为数组的每个数组元素分配了内存空间，每个内存空间里存储的内容就是该数组元素的值，即使这个内存空间存储的内容为空，这个空也是一个值（null）。不管以哪种方式来初始化数组，只要为数组元素分配了内存空间，数组元素就具有了初始值。初始值的获得有两种形式，一种由系统自动分配，另一种由程序员指定。

数组在初始化数组的同时，可以指定数组的大小，也可以分别初始化数组中的每一个元素。在 Java 语言中，初始化数组有以下 3 种方式。

  • 使用new指定数组大小后进行初始化
1
type[] arrayName = new int[size];

创建数组后元素是不确定的，需要对数组的元素进行赋值，其下标从0开始。

1
2
3
4
5
6
int[] number = new int[5];
number[0] = 1;
number[1] = 2;
number[2] = 3;
number[3] = 4;
number[4] = 5;

如果程序员只指定了数组的长度，那么系统将负责为这些数组元素分配初始值。指定初始值时，系统按如下规则分配初始值。

数组元素的类型是基本类型中的整数类型（byte、short、int 和 long），则数组元素的值是 0。

数组元素的类型是基本类型中的浮点类型（float、double），则数组元素的值是 0.0。

数组元素的类型是基本类型中的字符类型（char），则数组元素的值是‘\u0000’。

数组元素的类型是基本类型中的布尔类型（boolean），则数组元素的值是 false。

数组元素的类型是引用类型（类、接口和数组），则数组元素的值是 null。

  • 使用 new 指定数组元素的值

使用上述方式初始化数组时，只有在为元素赋值时才确定值。可以不使用上述方式，而是在初始化时就已经确定值。语法如下：

1
type[] arrayName = new type[]{值 1,值 2,值 3,值 4,• • •,值 n};

指定数组元素的值：

1
int[] number = new int[]{1, 2, 3, 5, 8};

上述代码的效果等价于第一种的效果。

注意：不要在进行数组初始化时，既指定数组的长度，也为每个数组元素分配初始值，这样会造成代码错误。例如下面代码：

1
int[] number = new int [5] {1,2,3,4,5};  //这样是错误的
  • 直接指定数组元素的值

在上述两种方式的语法中，type 可以省略，如果已经声明数组变量，那么直接使用这两种方式进行初始化。如果不想使用上述两种方式，那么可以不使用 new 直接指定数组元素的值。语法如下：

1
type[] arrayName = {值 1,值 2,值 3,...,值 n};

在前面例子的基础上更改代码，直接使用上述语法实现 number 数组的初始化。代码如下：

1
int[] number = {1,2,3,5,8};

使用这种方式时，数组的声明和初始化操作要同步，即不能省略数组变量的类型。如下的代码就是错误的：

1
2
int[] number;
number = {1,2,3,5,8};

获取单个元素

获取单个元素是指获取数组中的一个元素，如第一个元素或最后一个元素。获取单个元素的方法非常简单，指定元素所在数组的下标即可。语法如下：

1
arrayName[index];

其中，arrayName 表示数组变量，index 表示下标，下标为 0 表示获取第一个元素，下标为 array.length-1 表示获取最后一个元素。当指定的下标值超出数组的总长度时，会拋出 ArraylndexOutOfBoundsException 异常。

获取 number 数组中的第一个元素、最后一个元素和第六个元素，并将元素的值输出。代码如下：

1
2
3
4
int[] number = {1,2,3,5,8};
System.out.println("获取第一个元素："+number[0]);
System.out.println("获取最后一个元素："+number[number.length-1]);
System.out.println("获取第6个元素："+number[5]);

执行上述代码，输出结果如下所示：

1
2
3
//	获取第一个元素：1
//	获取最后一个元素：8
//	java.lang.ArrayIndexOutOfBoundsException: 5

创建二维数组

声明数组

在 Java 中二维数组被看作数组的数组，即二维数组为一个特殊的一维数组，其每个元素又是一个一维数组。Java 并不直接支持二维数组，但是允许定义数组元素是一维数组的一维数组，以达到同样的效果。声明二维数组的语法如下：

1
2
3
type arrayName[][];    // 数据类型 数组名[][];
//或
type[][] arrayName;    // 数据类型[][] 数组名;

其中，type 表示二维数组的类型，arrayName 表示数组名称，第一个中括号表示行，第二个中括号表示列。

下面分别声明 int 类型和 char 类型的数组，代码如下：

1
2
int[][] age;
char[][] sex;

初始化二维数组

二维数组可以初始化，和一维数组一样，可以通过 3 种方式来指定元素的初始值。这 3 种方式的语法如下：

1
2
3
type[][] arrayName = new type[][]{值 1,值 2,值 3,…,值 n};    // 在定义时初始化
type[][] arrayName = new type[size1][size2];    			// 给定空间，在赋值
type[][] arrayName = new type[size][];    					// 数组第二维长度为空，可变化

使用第一种方式声明 int 类型的二维数组，然后初始化该二维数组。代码如下：

1
int[][] temp = new int[][]{{1,2},{3,4}};

使用第二种方式声明 int 类型的二维数组，然后初始化该二维数组。代码如下：

1
int[][] temp = new int[2][2];

使用第三种方式声明 int 类型的二维数组，并且初始化数组。代码如下：

1
int[][] temp = new int[2][];

获取单个元素

在上部分使用的前 2 种方式创建并初始化了一个二行二列的 int 类型数组 temp。当需要获取二维数组中元素的值时，也可以使用下标来表示。语法如下：

1
arrayName[i-1][j-1];

其中，arrayName 表示数组名称，i 表示数组的行数，j 表示数组的列数。例如，要获取第二行第二列元素的值，应该使用 temp[1][1]来表示。这是由于数组的下标起始值为 0，因此行和列的下标需要减 1。

1
2
3
4
5
public static void main(String[] args) {
    double[][] class_score = {{10.0,99,99},{100,98,97},{100,100,99.5},{99.5,99,98.5}};
    System.out.println("第二行第二列元素的值："+class_score[1][1]);
    System.out.println("第四行第一列元素的值："+class_score[3][0]);
}

输出结果：

1
2
第二行第二列元素的值：98.0
第四行第一列元素的值：99.5

获取全部元素

在一维数组中直接使用数组的 length 属性获取数组元素的个数。而在二维数组中，直接使用 length 属性获取的是数组的行数，在指定的索引后加上 length（如 array[0].length）表示的是该行拥有多少个元素，即列数。

如果要获取二维数组中的全部元素，最简单、最常用的办法就是使用 for 语句。在一维数组全部输出时，我们使用一层 for 循环，而二维数组要想全部输出，则使用嵌套 for 循环（2 层 for 循环）。

使用 for 循环语句遍历 double 类型的 class_score 数组的元素，并输出每一行每一列元素的值。代码如下：

1
2
3
4
5
6
7
8
public static void main(String[] args) {
    double[][] class_score = { { 100, 99, 99 }, { 100, 98, 97 }, { 100, 100, 99.5 }, { 99.5, 99, 98.5 } };
    for (int i = 0; i < class_score.length; i++) { // 遍历行
        for (int j = 0; j < class_score[i].length; j++) {
            System.out.println("class_score[" + i + "][" + j + "]=" + class_score[i][j]);
        }
    }
}

上述代码使用嵌套 for 循环语句输出二维数组。在输出二维数组时，第一个 for 循环语句表示以行进行循环，第二个 for 循环语句表示以列进行循环，这样就实现了获取二维数组中每个元素的值的功能。

执行上述代码，输出结果如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
class_score[0][0]=100.0
class_score[0][1]=99.0
class_score[0][2]=99.0
class_score[1][0]=100.0
class_score[1][1]=98.0
class_score[1][2]=97.0
class_score[2][0]=100.0
class_score[2][1]=100.0
class_score[2][2]=99.5
class_score[3][0]=99.5
class_score[3][1]=99.0
class_score[3][2]=98.5

创建多维数组

除了一维数组和二维数组外，Java中还支持更多维的数组，如三维数组、四维数组和五维数组等，它们都属于多维数组。经过前面一维，二维的练习后不难发现，想要提高数组的维数，只要在声明数组时将索引与中括号再加一组即可，所以三维数组的声明为 int score[][][]，而四维数组为 int score[][][][]，以此类推。

通常也将二维数组看作是多维数组。本文以三维数组为例来介绍多维数组。

三维数组有三个层次，可以将三维数组理解为一个一维数组，其内容的每个元素都是二维数组。依此类推，可以获取任意维数的数组。

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
    String[][][] namelist = { { { "张阳", "李风", "陈飞" }, { "乐乐", "飞飞", "小曼" } },
            { { "Jack", "Kimi" }, { "Lucy", "Lily", "Rose" } }, { { "徐璐璐", "陈海" }, { "李丽丽", "陈海清" } } };
    for (int i = 0; i < namelist.length; i++) {
        for (int j = 0; j < namelist[i].length; j++) {
            for (int k = 0; k < namelist[i][j].length; k++) {
                System.out.println("namelist[" + i + "][" + j + "][" + k + "]=" + namelist[i][j][k]);
            }
        }
    }
}

执行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
namelist[0][0][0]=张阳
namelist[0][0][1]=李风
namelist[0][0][2]=陈飞
namelist[0][1][0]=乐乐
namelist[0][1][1]=飞飞
namelist[0][1][2]=小曼
namelist[1][0][0]=Jack
namelist[1][0][1]=Kimi
namelist[1][1][0]=Lucy
namelist[1][1][1]=Lily
namelist[1][1][2]=Rose
namelist[2][0][0]=徐璐璐
namelist[2][0][1]=陈海
namelist[2][1][0]=李丽丽
namelist[2][1][1]=陈海清

Arrays工具类

asList

将一个数组(变长参数的语法糖实现就是数组)转变成一个List(确切的来说是ArrayList)，注意这个List是定长的，企图添加或者删除数据都会报错（java.lang.UnsupportedOperationException）.

1
2
3
List<Integer> list = Arrays.asList(3,4,2,1,5,7,6);
System.out.println(list);
//3,4,2,1,5,7,6

但是，对于基础类型（比如byte,int,float等）千万不要想着这么实现（案例1-2，勿效仿）：

1
2
int a[] = new int[]{1,2,5,4,6,8,7,9};
List list = Arrays.asList(a);

因为List list = Arrays.asList(a);会变成List<int[]> list = Arrays.asList(a);所以遍历需要这样：

1
2
3
4
5
6
//错误
for(int[] arr:list){
    for(int i:arr){
        System.out.println(i);
    }
}

这样操作就显得非常的烦琐。因为预想List是List形式的，没想到是List<int[]>形式的。使用的时候要特别的注意一下。

1
2
3
Integer a[] = new Integer[]{1,2,5,4,6,8,7,9};
List list = Arrays.asList(a);
System.out.println(list);

sort

对数组进行排序。适合byte,char,double,float,int,long,short等基本类型，还有Object类型（实现了Comparable接口），如果提供了比较器Comparator也可以适用于泛型。

案例（基础类型，输出：[1, 1, 4, 4, 5, 6, 7, 9]）：

1
2
3
int a[] = new int[]{1,9,5,4,6,4,7,1};
Arrays.sort(a);
System.out.println(Arrays.toString(a));

案例（String类型(Object)，实现了Comparable接口，输出：[s1, s2, s3, s4]）：

1
2
3
String str[] = {"s2","s4","s1","s3"};
Arrays.sort(str);
System.out.println(Arrays.toString(str));

案例 （自定义类型，实现了Comparable接口，输出：[jj:17, zzh:18, qq:19]）：

1
2
3
4
5
Person1 persons[] = new Person1[]{
    new Person1("zzh",18),new Person1("jj",17),new Person1("qq",19)
};
Arrays.sort(persons);
System.out.println(Arrays.toString(persons));

案例（泛型，如果类型没有实现Comparable接口，可以通过Comparator实现排序）[jj:17, zzh:18, qq:19]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Person2 persons2[] = new Person2[]{
    new Person2("zzh",18),new Person2("jj",17),new Person2("qq",19)
};
Arrays.sort(persons2,new Comparator<Person2>(){

    @Override
    public int compare(Person2 o1, Person2 o2)
    {
        if(o1 == null || o2 == null)
            return 0;
        return o1.getAge()-o2.getAge();
    }

});
System.out.println(Arrays.toString(persons2));

binarySearch

通过二分查找法对已排序（譬如经过Arrays.sort排序，且按照升序进行排序。如果数组没有经过排序，那么检索结果未知）的数组进行查找。适合byte,char,double,float,int,long,short等基本类型，还有Object类型和泛型（参考sort那段）

1
2
3
4
5
6
7
8
String str[] = {"s2","s4","s1","s3"};
Arrays.sort(str);
System.out.println(Arrays.toString(str));
int ans = Arrays.binarySearch(str, "s1");
System.out.println(ans);

//[s1, s2, s3, s4]
//0

copyOf

数组拷贝，底层采用System.arrayCopy（native方法）实现。

1
2
3
4
5
6
7
String str[] = {"s2","s4","s1","s3"};
String str2[] = Arrays.copyOf(str, str.length);
System.out.println(Arrays.toString(str2));
System.out.println(str.equals(str2));

//[s2, s4, s1, s3]
//false

copyOfRange

数组拷贝，指定一定的范围，譬如（public static T[] copyOfRange(T[] original, int from, int to)）。底层采用System.arrayCopy（native方法）实现

1
2
3
4
5
String str[] = {"s2","s4","s1","s3"};
String str2[] = Arrays.copyOfRange(str,1,3);
System.out.println(Arrays.toString(str2));

//[s4, s1]

equals和deepEquals

equals：判断两个数组的每一个对应的元素是否相等（equals, 对于两个数组的元素o1和o2有o1==null ? o2==null : o1.equals(o2)）

1
2
3
4
5
6
7
8
9
10
String str1[] = {"s2","s4","s1","s3",null};
String str2[] = Arrays.copyOf(str1, str1.length);
System.out.println(Arrays.equals(str1, str2));

//true

//Arrays.equals(array1, array2)：
//检查两个数组是否包含相同数量的元素，并且两个数组中的所有相应元素对是否相等。
//array1.equals(array2)：
//将该对象与另一个对象进行比较，只有当两个对象的引用相同时才返回true `Object.equals()`

deepEquals：主要针对一个数组中的元素还是数组的情况，类似deepToString, deepHashCode如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a1[] = new int[]{1,2,3};
int a2[] = new int[]{1,3,3};
int a3[] = new int[]{4,3,2,1};
int a4[] = new int[]{1,2,3};
int a5[] = new int[]{1,3,3};
int a6[] = new int[]{4,3,2,1};
int[] a [] = new int[][]{a1,a2,a3};
int[] b [] = new int[][]{a4,a5,a6};

System.out.println(Arrays.equals(a, b));
System.out.println(Arrays.deepEquals(a, b));

//false
//true

fill

给数组赋值。填充数组之用

1
2
3
4
5
6
7
String str[] = {"s2","s4","s1","s3",null};
System.out.println(Arrays.toString(str));
Arrays.fill(str, "s5");
System.out.println(Arrays.toString(str));

//[s2, s4, s1, s3, null]
//[s5, s5, s5, s5, s5]

toString和deepToString

toString：对于一个数组int a[] = new int[]{1,9,5,4,6,4,7,1};如果按照System.out.println(a);打印企图可以打印出[1,9,5,4,6,4,7,1]，实际上只会打印出[I@3e2de41d这种。在打印数组的时候需要写成Arrays.toString(a)的形式。可参考sort的详解。
deepToString：当数组中又包含数组，那么就不能单存的利用Arrays.toString()了，请看例子。
案例：

1
2
3
4
5
6
7
8
9
int a1[] = new int[]{1,2,3};
int a2[] = new int[]{1,3,3};
int a3[] = new int[]{4,3,2,1};
int[] a [] = new int[][]{a1,a2,a3};
System.out.println(Arrays.toString(a));
System.out.println(Arrays.deepToString(a));

//[[I@1b6b7f83, [I@2e807f85, [I@76340c9c]
//[[1, 2, 3], [1, 3, 3], [4, 3, 2, 1]]

hashCode和deepHashCode

hashCode：计算一个数组的hashCode.对于一个数组Object[], hashCode方法返回的值取决于：数组中每个元素的元素oi.hashCode()的值初级计算result = 31 * result + (oi== null ? 0 : oi.hashCode());
deepHashCode: 对于一个数组Object[], deepHashCode取决于：数组中每个元素oi，如果oi还是一个数组，那么就继续深入的去获取hashCode，这段比较绕，来个例子比较形象。

1
2
3
4
5
6
7
8
9
int a1[] = new int[]{1,2,3};
int a2[] = new int[]{1,3,3};
int a3[] = new int[]{4,3,2,1};
int[] a [] = new int[][]{a1,a2,a3};
System.out.println(Arrays.hashCode(a));
System.out.println(Arrays.deepHashCode(a));

//-1683374023
//31646847