[数据结构与算法]Java学习之路07---阵列

架构图

创建阵列

作为参考数据类型的一员，阵列(array)在java中其实就是一个物件，因此后续处理阵列时需要将物件的概念套用上，对于学过C/C++的人可能需要一点思想上的转换

首先我们来看看在java当中，是如何创建一个阵列的。java宣告时可将[]置于变数名前方或后方，但为了与C/C++做出区别，官方推荐将[]放到变数前方:

int[] arr1; // 推荐

int arr2[]; // 也可以

不过宣告完阵列变数arr以后，阵列事实上并不真正存在

对于一个阵列来说，他具备一个物件的特性，也就代表目前的arr只是一个阵列物件的参考名而已。这个阶段编译器只知道这个整数阵列可能会指向一个阵列物件，所以在宣告阵列变数后还需要使用new在Heap当中生成一个真正的整数阵列，然后再指定给arr

下面几种方法均可以生成一个阵列物件:

/* 方法1 */
int[] arr1;
arr1 = new int[10];

/* 方法2 */
int[] arr2 = new int[10];

/* 方法3 */
int[] arr3 = new int[]{1,2,3,4,5,6,7,8,9,10}; 

/* 方法4 */
int[] arr3 = {1,2,3,4,5,6,7,8,9,10}; // 可以省略掉 int[]

初始化需要注意的几个问题

• 阵列一旦建立，长度就固定了，若需要更改只能重新建立一个长度更长的阵列
• 数据类型为必填项
• 若是使用直接赋值法(例如方法3、4)可以忽略阵列长度
• 在java当中所有阵列都是动态分配的

阵列初始值
使用new建立阵列后，有别于其他变数类型，每个阵列元素都会自动分配一个预设值(物件特性)

• 对于引用资料类型或任何物件(ex. String或一个阵列物件) → null
• 对于byte/short/int/long → 0
• 对于float/double → 0.0
• 对于字元 → null字元\u0000
• 对于布林 → false

越界
当阵列index小于0或者等于或大于当前阵列长度时就会发生越界，例如我们故意将index自增到与阵列常相等(a.length为阵列长度)

class Main {
    public static void main(String[] args){
		int[] arr = {1,2,3,4,5,6,7};

		for(int i=0; i<=arr.length; i++){
			System.out.println("arr["+i+"] = " + arr[i]); // i=7时发生异常
		}
	}
}

输出结果:

arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
arr[5] = 6
arr[6] = 7
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 7 out of bounds for length 7
        at Main.main(Main.java:15)

我们可以看到程式抛出例外资讯ArrayIndexOutOfBoundsException。不像C/C++一样，编译器不会事先检查阵列是否越界，而是在执行过程中处理意外(Runtime Exception)

有几种方法可以解决例外的产生，分别是撰写例外处理程式或者使用For-each loop迴圈

使用例外处理
我们把越界问题调整一下，将上述程式的起始值设定成-1，终值设定为<=arr.length+1，产生三次越界。与此同时我们也已经知道越界异常退跳出ArrayIndexOutOfBoundsException，所以可以利用try catch去捕捉这个异常:

class Main {
    public static void main(String[] args){
		int[] arr = {1,2,3,4,5,6,7};

		for(int i=-1; i<=arr.length+1; i++){
			try {
				System.out.println("arr["+i+"] = " + arr[i]);
			} catch(ArrayIndexOutOfBoundsException e){ // 捕捉越界例外发生
				System.out.println("发生越界!"); // 通知例外发生
				continue; // 直接进入下一次循环
			}
		}
	}
}

输出结果:

发生越界!
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
arr[5] = 6
arr[6] = 7
发生越界!
发生越界!

如此一来程式执行时发生越界问题时能够即时通报，并继续运行值到跳出迴圈。下一小节将会继续探讨避免越界例外发生的另一个解决方法: For-each loop

For-each loop

For-each loop又称为增强型for迴圈，它是java迴圈的一种语法糖，具备以下几种好处:

1. 书写较为简洁
2. 方便遍历搜寻
3. 避免越界例外产生

不过若是有特殊需求，例如指定index范围或是程式逻辑涉及到阵列index时还是建议使用原本的for loop迴圈。基本的增强型for迴圈逻辑结构如下所示:

class Main {
    public static void main(String[] args){
		int[] arr = {1,2,3,4,5,0,0,0};

		for(int n:arr){
			System.out.println(n);	
		}
	}
}

输出结果:

1
2
3
4
5
0
0
0

增强型for迴圈会自动判断阵列的长度，并将阵列元素赋值给区域变数(n)，直到所有阵列元素接访问为止。所以上述程式码其实相当于:

class Main {
    public static void main(String[] args){
		int[] arr1 = {1,2,3,4,5,0,0,0};
		int[] arr2 = arr1
		int len = arr2.length;

		for(int i=0; i<len; i++){ // 有效避免越界发生
			int n = arr2[i];
			System.out.println(n);	
		}
	}
}

多维阵列

二维阵列

二维阵列其实是一种特殊的一维阵列，差别在于二维阵列的变数参考名参考一个阵列物件，该阵列物件的元素是一个阵列的参考名。举例来说:

int[][] arr;
arr = new int[4][3]{{1,2,3},{4,5,6},{7,8,9},{10,11,12}};

上述程式码的架构可以表示成下图，差别在于一个物件的阵列元素是阵列参考，一个是整数值:

其实你可以把int[]看成一种类别，随便假设它是一个新的变数类型mytype好了，因此我们其实可以把二维阵列看成mytype[]阵列，而arr就是指向这个阵列物件的参考名

如同我们在一维阵列的创建时介绍的一样，二维阵列也支援多种不同的宣告与动态分配格式:

int[][] arr1;
float arr2[][];
double []arr3[];

arr1 = new int[3][3];
arr2 = new float[3][3];
arr3 = new double[3][3];

/* Direct Method of Declaration */
long[][] num = {{1,2,3},{4,5,6},{7,8,9}};
long[][] num1 = {{78,98},{65,75,63},{98}};

需要特别注意多维阵列在宣告的时候最少需要填上row:

int[][]arr = new int[2][]; // row不能省略
arr[0] = new int[]{1,2,3};
arr[1] = new int[]{4,5,6};

错误创建方式如下:

char[][] ch = new char[][] ;
char[][] ch = new char[][5];

二维形式的增强型for迴圈

public class Main
{
	public static void main(String[] args) {
        int[][] arr = { {1,2,3}, {4,5,6}, {7,8,9}, {10,11,12}};
        
        for(int[] f: arr){
        	for(int s: f){
        		System.out.print(s + " ");
        	}
        	System.out.println();
        }
	}
}

输出结果:

1 2 3 
4 5 6 
7 8 9 
10 11 12

jagged array

其实多维阵列不一定要是方阵。举二维阵列来说，阵列物件中的参考指向的阵列长度可以不等长，这种阵列我们称之为jagged array(不规则阵列)，例如:

int[][] arr= {{78,98},{65,75,63},{98}};

int len0 = arr[0].length; // 2
int len1 = arr[1].length; // 3
int len2 = arr[2].length; // 1

创建物件时也可以分配不同长度的阵列:

class Main {
    public static void main(String[] args){
		int[][]arr = new int[2][]; // row不能省略
		arr[0] = new int[4];
		arr[1] = new int[5];

		int count = 0;
		for (int i = 0; i < arr.length; i++){
			for (int j = 0; j < arr[i].length; j++){
				arr[i][j] = count++;
			}
		}

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++){
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}
	}
}

输出结果:

0 1 2 3 
4 5 6 7 8 

另外假如一个二维方阵阵列已经被创建，那麽可以将它的改变成一个不规则阵列吗?答案当然是可以的，我们只需要将参考名参考到新的阵列物件即可:

class Main {
    public static void main(String[] args){
		int[][]arr = new int[2][];
		int []arr2 = {1,2,3,4,5,6,7,8};

		arr[0] = new int[4]; // 参考一个长度为4的阵列
		arr[1] = new int[4]; // 参考一个长度为4的阵列

        System.out.print("arr[0] before: ");
		for(int f: arr[0])
			System.out.print(f + " ");

		System.out.println();

		arr[0] = arr2; // 重新参考到arr2物件

        System.out.print("arr[0] after: ");
		for(int f: arr[0])
			System.out.print(f + " ");
	}
}

例如上述程式中，arr[0]原本参考一个长度为4并且预设值为0的阵列物件，但经过指定操作，将arr[0]参考到与arr2参考相同的物件(好拗口🤔)，这时的arr就变成一个不规则阵列

输出结果:

arr[0] before: 0 0 0 0 
arr[0] after: 1 2 3 4 5 6 7 8 

再举一个例子，我们先宣告一个二维阵列，它的row会让使用者决定，而column的长度则会依据当前index去调整，并且阵列元素的值会利用一个整数变数去累加:

import java.util.Scanner;

class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.print("input array's row: ");
        int row = sc.nextInt();
        int element = 1;
 
        int arr[][] = new int[row][];
 
        for (int i = 0; i < arr.length; i++){
            arr[i] = new int[i + 1];
        }

        for (int i = 0; i < arr.length; i++){
            for (int j = 0; j < arr[i].length; j++){
                arr[i][j] = element++;
            }
        }

        System.out.println("-------output-------");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++)
                System.out.print(arr[i][j] + " ");
            System.out.println();
        }
    }
}

输入20查看其输出结果:

input array's row: 20
-------output-------
1 
2 3 
4 5 6 
7 8 9 10 
11 12 13 14 15 
16 17 18 19 20 21 
22 23 24 25 26 27 28 
29 30 31 32 33 34 35 36 
37 38 39 40 41 42 43 44 45 
46 47 48 49 50 51 52 53 54 55 
56 57 58 59 60 61 62 63 64 65 66 
67 68 69 70 71 72 73 74 75 76 77 78 
79 80 81 82 83 84 85 86 87 88 89 90 91 
92 93 94 95 96 97 98 99 100 101 102 103 104 105 
106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 
121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 
137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 

三维阵列

三维阵列跟二维阵列类似，不过在宣告时需要增加维度，除此之外创建阵列的方法是相同的:

int[][][] arr = new int[4][3][2];

建立三维阵列时除了第一个row以外其他阵列数都可以省略，这部分只要在后续的动态分配中决定就可以了

结合之前所学，我们试着建立一个三维的不规则阵列，最后透过增强型for迴圈将值打印出来:

public class Main
{
	public static void main(String[] args) {
		int[][][] arr = new int[4][][];
		int element=0;
		
		for(int i=0; i<arr.length; i++){
		    arr[i] = new int[i+1][];
		    for(int j=0; j<arr[i].length; j++){
		        arr[i][j] = new int[j+1];
		        for(int k=0; k<arr[i][j].length; k++){
		            arr[i][j][k] = element;
		            element++;
		        }        
		    }
		}
			
		for(int [][]f:arr){
		    for(int []s:f){
			    for(int t:s){
				    System.out.print(t + " ");
			    }
		        System.out.println();
		    }
		    System.out.println("--------------");
	    }
	}
}

输出结果:

0 
--------------
1 
2 3 
--------------
4 
5 6 
7 8 9 
--------------
10 
11 12 
13 14 15 
16 17 18 19 
--------------

不建议使用三维以上阵列进行程式撰写，不易阅读加上编写困难会增加开发上的难度，可以思考有无其他资料结构可以代替

互相参考

由于阵列的物件特性，我们可以将变数参考到别的物件上，因为这种特性，阵列物件元素值的改变，是可以透过任何参考它的参考名称来产生，举例来说:

int[] arr1 = {1,2,3,4,5};
int[] arr2 = arr1;

System.out.println("arr1[2] = " + arr1[2] + ", arr2[2] = " + arr2[2]);

arr2[2] = 9;

System.out.println("arr1[2] = " + arr1[2] + ", arr2[2] = " + arr2[2]);

输出结果:

arr1[2] = 3, arr2[2] = 3
arr1[2] = 9, arr2[2] = 9

因为两个变数名称接参考同一个物件，所以当arr1改变阵列元素时，arr2[2]也会跟着发生变化，利如下图所示，因此在编写程式时需要特别注意这种关联性

複製阵列

从上述问题我们了解到，如果想要複製阵列值又想同时避免互相参考的特性，最好的办法就是再创建一个新的阵列物件，然后将阵列元素值一个一个複製过来

比如说最简单的for迴圈方式:

int[] arr1 = {1,2,3,4,5};
int[] arr2 = new int[5];

for(int i=0; i<arr1.length; i++){
	arr2[i] = arr1[i];
}

System.out.println("arr1[2] = " + arr1[2] + ", arr2[2] = " + arr2[2]);

arr2[2] = 9;

System.out.println("arr1[2] = " + arr1[2] + ", arr2[2] = " + arr2[2]);

输出结果:

arr1[2] = 3, arr2[2] = 3
arr1[2] = 3, arr2[2] = 9

会产生这种差别的原因在于arr2是参考一个不同于arr1的物件。是否使用new就是关键点，其背后逻辑如下图所示

不过其实我们可以借助System、阵列或物件提供的方法来处理阵列複製问题，不需要每次都使用for迴圈来赋值，以下介绍三种常见的阵列複製方法:

System.arraycopy()

class Main {
	public static void main(String[] args){
		int[] arr1 = {1,2,3,4,5,6,7,8,9,10};
		int[] arr2 = new int[5];

		System.arraycopy(arr1, 0, arr2, 0, arr2.length); // 複製arr1的前5个阵列元素

		for(int f:arr2){
			System.out.print(f + " ");
		}
	}
}

输出结果:

1 2 3 4 5 

参数列表:

1. 源阵列参考名
2. 源阵列起始index
3. 目标阵列参考名
4. 目标阵列起始index
5. 複製长度

Arrays.copyOf()

import java.util.Arrays; // 需要import

class Main {
    public static void main(String[] args){
        int[] arr1 = {1,2,3,4,5,6,7,8,9,10};
        int[] arr2 = Arrays.copyOf(arr1, 5); // 返回一个物件，它的长度为5，阵列元素为arr1[0]~arr1[4]
        
        for(int f:arr2){
            System.out.print(f + " ");
        }
    }
}

输出结果:

1 2 3 4 5 

参数列表:

1. 源阵列参考名
2. 複製长度

arr.clone()

class Main {
    public static void main(String[] args){
        int[] arr1 = {1,2,3,4,5,6,7,8,9,10};
        int[] arr2 = arr1.clone(); // 继承阵列物件arr1
        
        System.out.print("arr2: ");
        
        for(int f:arr2){
            System.out.print(f + " ");
        }
        
        arr2[0] = 100; // 测试是否为互相参考
        
        System.out.println();
        System.out.print("arr1: ");
        
        for(int f:arr1){
            System.out.print(f + " ");
        }
    }
}

输出结果:

arr2: 1 2 3 4 5 6 7 8 9 10 
arr1: 1 2 3 4 5 6 7 8 9 10 

如果想要更详细的说明可以参考这篇文章，裡面对阵列的複製方法有详尽的介绍