1.4 Arrays
Show Arrays in Java.Making an array in a Java program involves three distinct steps:
We refer to an array element by putting its index in square brackets after the array name: the code a[i]refers to element iof array a[]. For example, the following code makes an array of n numbers of type double, all initialized to 0: 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.
Shuffling and sampling.Now we describe some useful algorithms for rearranging the elements in an array.
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: 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.
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. Exercises
Creative Exercises
Web Exercises
|