In this section, we consider a fundamental construct(结构) known as the array. An array stores a sequence of values that are all of the same type. We want not just to store values but also to be able to quickly access each individual value. The method that we use to refer to individual values in an array is to number and then index them—if we have n values, we think of them as being numbered from 0 to n−1.
Arrays in Java.
Making an array in a Java program involves three distinct(明确的、确定的) steps:
Declare the array name.
Create the array.
Initialize the array values.
We refer to an array element by putting its index in square brackets after the array name: the code
double[] a; // declare the array
a = new double[n]; // create the array
for (int i = 0; i < n; i++) // elements are indexed from 0 to n-1
a[i] = 0.0; // initialize all elements to 0.0
Typical array-processing code.
ArrayExamples.java contains typical examples of using arrays in Java.
Programming with arrays.
Before considering more examples, we consider a number of important characteristics of programming with arrays.
Zero-based indexing. We always refer to the first element of an array a[] as a[0], the second as a[1], and so forth. It might seem more natural to you to refer to the first element as a[1], the second value as a[2], and so forth, but starting the indexing with 0 has some advantages and has emerged(出现) as the convention used in most modern programming languages.
Array length. Once we create an array, its length is fixed. You can refer to the length of an a[] in your program with the code a.length.(创建之后，长度固定)
Default array initialization. For economy(经济高效) in code, we often take advantage of Java's default array initialization convention. For example, the following statement is equivalent to the four lines of code at the top of this page:(下面的一行代码等价于前面的四行，包含了默认初始化)
double[] a = new double[n];
The default initial value is 0 for all numeric primitive types and false for type boolean.
Memory representation. When you use new to create an array, Java reserves space in memory for it (and initializes the values). This process is called memory allocation.
Bounds checking. When programming with arrays, you must be careful. It is your responsibility to use legal indices when accessing an array element.
Setting array values at compile time. When we have a small number of literal values that we want to keep in array, we can initialize it by listing the values between curly braces(花括号), separated by a comma(逗号). For example, we might use the following code in a program that processes playing cards.
String[] SUITS = {
"Clubs", "Diamonds", "Hearts", "Spades"
};
String[] RANKS = {
"2", "3", "4", "5", "6", "7", "8", "9", "10",
"Jack", "Queen", "King", "Ace"
};After creating the two arrays, we might use them to print a random card name such as Queen of Clubs, as follows.
int i = (int) (Math.random() * RANKS.length);
int j = (int) (Math.random() * SUITS.length);
System.out.println(RANKS[i] + " of " + SUITS[j]);Setting array values at run time. A more typical situation is when we wish to compute the values to be stored in an array For example, we might use the following code to initialize an array of length 52 that represents a deck(甲板) of playing cards, using the arrays RANKS[] and SUITS[] just defined.
String[] deck = new String[RANKS.length * SUITS.length];
for (int i = 0; i < RANKS.length; i++)
for (int j = 0; j < SUITS.length; j++)
deck[SUITS.length*i + j] = RANKS[i] + " of " + SUITS[j];
System.out.println(RANKS[i] + " of " + SUITS[j]);
Shuffling and sampling.
Now we describe some useful algorithms for rearranging the elements in an array.
Exchange. Frequently, we wish to exchange two values in an array. Continuing our example with playing cards, the following code exchanges the card at position i and the card at position j:(交换)
String temp = deck[i];
deck[i] = deck[j];
deck[j] = temp;Shuffling. The following code shuffles our deck of cards:(置乱)
int n = deck.length;
for (int i = 0; i < n; i++) {
int r = i + (int) (Math.random() * (n-i));
String temp = deck[r];
deck[r] = deck[i];
deck[i] = temp;
}Proceeding from left to right, we pick a random card from deck[i] through deck[n-1] (each card equally likely) and exchange it with deck[i]. This code is more sophisticated than it might seem: see the textbook for details. Deck.java contains the full code for creating and shuffling a deck of cards.
Sampling without replacement. In many situations, we want to draw a random sample from a set such that each member of the set appears at most once in the sample. Sample.java takes two command-line arguments m and n, and creates a permutation(排列) of length n whose first mentries(门道) comprise(包含) a random sample. See the textbook for details.
Precomputed values.
One simple application of arrays is to save values that you have computed, for later use. As an example, suppose that you are writing a program that performs calculations using small values of the harmonic(调和) numbers. One easy way to accomplish such a task is to save the values in an array with the following code
double[] harmonic = new double[n];
for (int i = 1; i < n; i++)
harmonic[i] = harmonic[i-1] + 1.0/i;
and then simply use the code harmonic[i] to refer to any of the values. Precomputing values in this way in an example of a space-time tradeoff: by investing in space (to save the values) we save time (since we do not need to recompute them). This method is not effective if we need values for huge n, but it is very effective if we need a huge number of values for small n.(用数组存储已经计算的值，以节省重复计算的时间)
Simplifying repetitive code.
As an example of another simple application of arrays, consider the following code fragment, which prints the name of a month given its number (1 for January, 2 for February, and so forth):
if (m == 1) System.out.println("Jan");
else if (m == 2) System.out.println("Feb");
else if (m == 3) System.out.println("Mar");
else if (m == 4) System.out.println("Apr");
else if (m == 5) System.out.println("May");
else if (m == 6) System.out.println("Jun");
else if (m == 7) System.out.println("Jul");
else if (m == 8) System.out.println("Aug");
else if (m == 9) System.out.println("Sep");
else if (m == 10) System.out.println("Oct");
else if (m == 11) System.out.println("Nov");
else if (m == 12) System.out.println("Dec");
We could also use a switch statement, but a much more compact alternative is to use an array of strings consisting of the names of each month: (和C语言一致，没有特殊的)
String[] MONTHS = {
"", "Jan", "Feb", "Mar", "Apr", "May", "Jun",
"Jul", "Aug", "Sep", "Oct", "Nov", "Dec"
};
...
System.out.println(MONTHS[m]);
This technique would be especially useful if you needed to access the name of a month by its number in several different places in your program. Note that we intentionally waste one slot in the array (element 0) to make MONTHS[1] correspond to January, as required.
Coupon collector.
Suppose that you have a shuffled deck of cards and you turn them face up(翻开朝上), one by one. How many cards do you need to turn up before you have seen one of each suit? This is an example of the famous coupon collector (优惠券收集) problem. In general, suppose that a trading card company issues trading cards with n different possible cards: how many do you have to collect before you have all n possibilities, assuming that each possibility is equally likely for each card that you collect? CouponCollector.java takes an integer command-line argument n and simulates this process. See the textbook for details. (需要多久才能收集到全部的优惠券?)
Sieve of Eratosthenes.
The prime counting function π(n) is the number of primes(素数) less than or equal to n. For example π(17) = 7 since the first seven primes are 2, 3, 5, 7, 11, 13, and 17. PrimeSieve.java takes an integer command-line argument n and computes π(n) using the Sieve of Eratosthenes. See the textbook for details. ([数]爱拉托逊斯筛法)
Two-dimensional arrays.
In many applications, a natural way to organize information is to use a table of numbers organized in a rectangle and to refer to rows and columns in the table. The mathematical abstraction corresponding to such tables is a matrix; the corresponding Java construct is a two-dimensional array.
Two-dimensional arrays in Java. To refer to the element in row i and column j of a two-dimensional array a[][], we use the notation a[i][j]; to declare a two-dimensional array, we add another pair of brackets; to create the array, we specify the number of rows followed by the number of columns after the type name (both within brackets), as follows: (定义和初始化二维数组)
double[][] a = new double[m][n];
We refer to such an array as an m-by-n array. By convention, the first dimension is the number of rows and the second dimension is the number of columns.
Default initialization. As with one-dimensional arrays, Java initializes all entries in arrays of numbers to 0 and in arrays of booleans to false. Default initialization of two-dimensional arrays is useful because it masks more code than for one-dimensional arrays. To access each of the elements in a two-dimensional array, we need nested loops:
double[][] a;
a = new double[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
a[i][j] = 0;Memory representation. Java represents a two-dimensional array as an array of arrays. A matrix with m rows and n columns is actually an array of length m, each entry of which is an array of length n. In a two-dimensional Java array, we can use the code a[i] to refer to the ith row (which is a one-dimensional array). Enables ragged arrays.（数组的数组）
Setting values at compile time. The following code initializes the 11-by-4 array a[][]:
double[][] a = {
{ 99.0, 85.0, 98.0, 0.0 },
{ 98.0, 57.0, 79.0, 0.0 },
{ 92.0, 77.0, 74.0, 0.0 },
{ 94.0, 62.0, 81.0, 0.0 },
{ 99.0, 94.0, 92.0, 0.0 },
{ 80.0, 76.5, 67.0, 0.0 },
{ 76.0, 58.5, 90.5, 0.0 },
{ 92.0, 66.0, 91.0, 0.0 },
{ 97.0, 70.5, 66.5, 0.0 },
{ 89.0, 89.5, 81.0, 0.0 },
{ 0.0, 0.0, 0.0, 0.0 }
};Ragged arrays. There is no requirement that all rows in a two-dimensional array have the same length—an array with rows of nonuniform length is known as a ragged array. The possibility of ragged arrays creates the need for more care in crafting array-processing code. For example, this code prints the contents of a ragged(参差不齐的) array: (每行可以长度不一样，演示代码：RaggedArrays.java)
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}Multidimensional arrays. The same notation extends to arrays that have any number of dimensions. For instance, we can declare and initialize a three-dimensional array with the code
double[][][] a = new double[n][n][n];
and then refer to an entry with code like a[i][j][k].
Matrix operations.
Typical applications in science and engineering involve implementing various mathematical operations with matrix operands. For example, we can add two n-by-n matrices as follows:(矩阵相加)
double[][] c = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
c[i][j] = a[i][j] + b[i][j];
}
}
Similarly, we can multiply two matrices. Each entry c[i][j] in the product of a[] and b[] is computed by taking the dot product of row i of a[] with column j of b[].(矩阵相乘)
double[][] c = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
c[i][j] += a[i][k]*b[k][j];
}
}
}
Self-avoiding walk.
SelfAvoidingWalk.java is an application of two-dimensional arrays to chemistry(化学). See textbook for details. (二维数组的应用例子：随机游走)
