6.1 数 组
深入理解数据结构及如何使用它们，对程序设计有极大的帮助。除基本数据类型和字符串外，数组是Java支持的最简单的数据结构。
在Java类库的java.util包中有一套数据结构，让用户能更灵活地操纵数据。java.util包提供的数据结构的功能非常强大，具备众多的功能。这些数据结构包括接口Iterator、Map 以及下述类：ArrayList、LinkedList、HashSet、HashMap等。本章就向读者阐述各个类的作用以及如何正确使用这些类。
本章主要内容
& 数组的使用
& Java集合框架
& Collection接口及其实现
& Set接口及其实现
& List接口及其实现
& Map接口及其实现
6.1 数 组
数组是由下标与值组成的数偶的有序集合，即它的每一个元素是由一个值与一组下标所确定。数组不是一种基本数据类型，它是由数据类型组成的集合类型。数组在程序设计语言中占有很重要的地位。
数组具有以下特点：对于每组有定义的下标，总有一个相应的数值与之对应，并且这些值都是同一类型的。下标决定了元素的位置，数组中各元素之间的关系由下标体现出来，下标的个数决定了数组的维数。因为由下标所决定的位置之间的关系可以看成是一种有序的线性关系，所以说数组是有限个相同类型数据元素组成的有序序列。从这个角度看，数组是线性表的推广，它的逻辑结构实际是一种线性结构。
数组最大的缺点在于：不能改变其大小以存储更多或更少的元素。这意味着不能向已满的数组中加入新的元素。由于链表和向量都没有这种限制，因此可以用这些对象来代替数组。
6.1.1 一维数组
一维数组可以看作一个线性表，一维数组中每个元素都有一个下标以确定元素的位置，一维数组是最简单的数组。
1．一维数组的定义
一维数组的定义如下：
Type arrayName[];
其中Type既可以是Java中的简单数据类型，例如int、char等，也可以是复杂数据类型，例如Integer、String等。Java数组还可以这样声明：
Type[] arrayName;
以上两种数组定义的方法是完全等价的。数组名arrayName为一个合法的标识符，[]指明该变量是一个数组类型的变量。一个合法的数组声明如下所示：
int intArray[] 或int[] intArray;
与C和C++不同，Java在数组声明时不用在“[]”中指出数组元素的个数，即数组长度，因为Java在数组声明时并不为数组元素分配内存。为元素分配内存则要使用到new运算符，格式如下。
arrayName = new Type[arraySize];
其中，arraySize指明数组长度。例如：
intArray = new int[3];
这两部分可以合写为如下语句：
Type arrayName[] = new Type[arraySize];
以上面的例子为例，可以写成：
int intArray[] = new int[3];
2．一维数组的引用
Java数组通过下标进行引用，格式是：
arrayName[index];
其中index是数组的下标，这个下标的范围可以是从0到arraySize-1，arraySize表示数组长度。arrayName[0]表示引用数组arrayName的第1个元素，arrayName[arraySize-1]表示引用数组arrayName最后一个元素。index可以是整型的常数或者表达式，如1、i*6（i为整型）等。对于上面的例子而言，intArray的3个元素分别是intArray[0]、intArray[1]和intArray[2]。
3．一维数组的初始化
数组的初始化有两种方式：静态初始化和动态初始化。
静态初始化即在数组定义的同时对数组进行初始化，例如：
int intArray[]={1,2,3};
动态初始化数组时，简单数据类型的数组和复杂数据类型的数组稍有不同。简单数据类型的数组在分配空间后就可以通过下标对数组元素进行赋值，例如：
int intArray[] = new int[3];
intArray[0]=1;
intArray[1]=2;
intArray[2]=3;
复杂数据类型的数组需要为数据的每一个元素进行空间分配，例如：
String strArray[];
strArray =new String[3];
strArray [0]=new String("Red");
strArray [1]=new String("Green");
strArray [2]=new String("Blue");
【例6-1】下面给出一个完整的数组初始化的例子，这个例子包括对简单数据类型数组的初始化和复杂数据类型数组的初始化。
public class ArrayTest{
public static void main( String args[ ] ){
int i;
int a[ ]=new int[5];
for( i=0; i<5; i++ )
a[i]=i;
for( i=a.length-1; i>=0; i-- )
System.out.println("a["+i+"] = "+a[i]);
String[] b = {"String A", "String B", "String C"};
for( i=b.length-1; i>=0; i-- )
System.out.println("b["+i+"] = "+b[i]);
}
}
这个程序的输出如下：
a[4] = 4
a[3] = 3
a[2] = 2
a[1] = 1
a[0] = 0
b[2] = String C
b[1] = String B
b[0] = String A
4．一维数组使用示例
【例6-2】本例产生Fibonacci数列的前10个数。Fibonacci数列的定义为：
F1 = F2 = 1, Fn = Fn-1 + Fn-2 (n>=3)
以下是完整的代码。
public class Fibonacci{
public static void main( String args[ ] ){
int i;
int f[ ]=new int[10];
f[0]=f[1]=1;
for( i=2; i<10; i++ )
f[i]=f[i-1]+f[i-2];
for( i=1; i<=10; i++ )
System.out.println("F["+i+"]= "+f[i-1]);
}
}
这个程序的输出如下：
F[1]= 1
F[2]= 1
F[3]= 2
F[4]= 3
F[5]= 5
F[6]= 8
F[7]= 13
F[8]= 21
F[9]= 34
F[10]= 55
6.1.2 多维数组
本小节将用二维数组来说明多维数组的使用。事实上，二维数组和更高维的数组本质上是一样的，而且三维以上的数组平时应用很少。
1．二维数组的定义
二维数组的定义如下：
Type ArrayName[][];
与一维数组一样，Type可以是简单数据类型，也可以是复杂数据类型，而且也可以这样来定义：
Type [][]ArrayName;
例如：
int intArray[][] 或int[][] intArray;
与一维数组一样，这时对数组元素也没有分配内存空间，同样要使用运算符new来分配内存，然后才可以访问每个元素。
对高维数组来说，分配内存空间时可以直接为每一维分配空间，例如：
int a[ ][ ] = new int[2][3];
也可以从最高维开始，分别为每一维分配空间，例如：
int a[ ][ ] = new int[2][ ]；
a[0] = new int[3];
a[1] = new int[3];
这一点与C和C++是不同的，在C和C++中必须一次指明每一维的长度。
2．二维数组的引用
二维数组中每个元素，其引用方式为：
arrayName[index1][index2];
其中，index1、index2为下标，可为整型常数或表达式，如a[2][3]等。同样，每一维的下标都从0开始。
3．二维数组的初始化
与一维数组类似，二维数组的初始化也可分为静态初始化和动态初始化。静态初始化在数组定义时进行初始化，例如：
int intArray[][]={{1,2},{3,4}};
则intArray[0][0]的值是1，Array[0][1]的值是2，以此类推。
动态初始化则动态分配内存，直接对元素赋值。例如：
int a[ ][ ] = new int[2][ ]；
a[0] = new int[3];
a[1] = new int[3];
a[0][0] = 1;
4．二维数组使用示例
【例6-3】下面的程序示意了如何使用二维数组。这个程序利用两个二维数组存储两个矩阵，然后对这两个矩阵进行乘法操作，结果存放在另外一个二维数组中。程序的代码如下：
public class MatrixMultiply{
public static void main( String args[ ] ){
int i,j,k;
int a[ ][ ]={{1,3,-10},{5,-7,9}};
int b[ ][ ]={ {3,5,7,-5},{3,7,-2,6},{4,2,-5,-8} };
int c[ ][ ]=new int[2][4];
for( i=0; i<2; i++ ){
for( j=0; j<4; j++ ){
c[i][j]=0;
for( k=0; k<3; k++ )
c[i][j]+=a[i][k]*b[k][j];
}
}
System.out.println("\nMatrix A:");
for( i=0; i<2; i++ ){
System.out.print("[");
for( j=0; j<3; j++ )
System.out.print(a[i][j]+" ");
System.out.println("]");
}
System.out.println("\nMatrix B:");
for( i=0; i<3; i++ ){
System.out.print("[");
for( j=0; j<4; j++ )
System.out.print(b[i][j]+" ");
System.out.println("]");
}
System.out.println("\nMatrix C:");
for( i=0; i<2; i++ ){
System.out.print("[");
for( j=0; j<4; j++ )
System.out.print(c[i][j]+" ");
System.out.println("]");
}
}
}
这个程序的输出结果如下：
Matrix A:
[1 3 -10 ]
[5 -7 9 ]
Matrix B:
[3 5 7 -5 ]
[3 7 -2 6 ]
[4 2 -5 -8 ]
Matrix C:
[-28 6 51 93 ]
[30 -6 4 -139 ]