To this point, we've represented collections of data using data structures in which objects contain references to other objects. Traversal of these data structures is done bo following the references (for example, linked list traversal or searching a binary tree). One advantage of these pointer-based data structures is the ability to add in new items, even into the middle of the structure.
However, sometimes we know how many items will be in a data
structure when it is first created. In that case, we might just
want to set up all the references at once. For example, we
might know that we have 12 months in a year, so we'd like to
create 12 references to Month objects, and be able
to go to any month. This kind of data structure is provided by
the array, a concept built into partically all
languages, including Java.
Suppose we already have a class Month whose
constructor takes the name of the month and the number of days
in the month.
Month months[];
Month[] months;
These two are equivalent, and both mean that
months is a reference to an array
of Month references.
months = new Month[12];
This creates an array of 12 Month references. Note
that it's NOT an array of objects, but an array of references.
Having created the array, we can refer to the individual items by number. Since we created 12 month references, we can access them using the index values 0-11. For example,
months[0] = new Month("January", 31);
months[6] = new Month("July", 31);
months[0].getName() => "January"
months[6].numDays() => 31
months[5].getName() => Null pointer exception
months[12].getName() => Array index out of bounds exception
Why? Let's see what it looks like in memory.
This is a contiguous memory block of
Month references. The offsets aren't stored in
memory; they are just the "distance" from the start of the array
to each slot.
When we ask for the ith entry, Java looks in the position that is i slots down from the start of the array. If i is bigger than the size of the array, an exception occurs.
Suppose we had created all 12 month objects and initialized the month array completely. We could write a procedure to compute the number of days in a year as follows:
int daysInYear(Month[] calendar) {
int total = 0; // days up to, but not including, month i
int i = 0;
while (i < 12) {
total += calendar[i].numDays();
i++;
}
}
Each Month object could contain an array of
Day's, where each day might contain a list of
appointments:
public class Month {
Day[] days;
String name;
int daysInMonth;
public Month(String name, int daysInMonth) {
this.name = name;
this.daysInMonth = daysInMonth;
days = new Day[daysInMonth];
}
public int numDays() { return daysInMonth; }
public String getName() { return name; }
public Day getDay(int date) {
if (days[date] == null)
days[date] = new Day(name, date);
return days[date];
}
}
Sometimes, it's convenient to think of a data structure as a grid. For example, the positions on a checkerboard or the pixels on a graphics display. For this, arrays of arrays are convenient.
For example, we might create a checkerboard as an array of 8
rows, where each row contains 8 positions. We can use an
int in each position, where
int[][] checkerboard = new int[8][8];
This creates an array of arrays of int's. If we
wanted, we could also create a calendar where each array entry was
an array of Day references.
Day[][] calendar = new Day[12][];
This creates an array of 12 arrays of Day references;
the number for each month is left unspecified. Now,
calendar[0] = new Day[31];
calendar[1] = new Day[28];
...
Sometimes, it's useful to find the length of an array:
calendar.length => 12
calendar[1].length => 28
Matrices are useful in many computer applications. For example, in graphics, matrices are used to render perspective drawings of shapes in a scene.
An m × n matrix consists of m rows and n columns. For example, this is a 3×2 matrix.
We can represent a matrix as an array of m rows, where each row is an array of n numbers.
double[][] x = new double[3][2];
x[0][0] = 2;
x[0][1] = 3;
x[1][0] = 1;
...
A common operation performed on matrices is the transpose, which interchanges the rows and columns. For example,
double[][] transpose(double[][] x) {
int m = x.length;
int n = x[0].length;
double[][] y = new double[n][m];
int i = 0;
while (i < m) {
int j = 0;
while (j < n) {
y[j][i] = x[i][j];
j++;
}
i++;
}
return y;
}
This procedure uses nested loops, one loop inside another. Each loop has a loop counter, a continuation test, and a statement to be executed to modify the loop counter at the end of each iteration.
Since these kinds of loops are so typical, Java provides the
for loop, which is no more powerful than the
while loop, but is more compact.
for (int i = 0; // loop initialization
i < m; // test for continuation
i++) // statement executed at the end of each iteration
for (int j = 0; j < n; j++)
y[j][i] = x[i][j];
could replace the nested loops in the preceding example.
Given two arrays of doubles (that are the same length), we can define their dot product as the sum of the products of the corresponding entries. For example,
[2 3 1] · [7 4 0] = 2 · 7 + 3 · 4 + 1 · 0 = 26As a procedure,
double dotProduct(double[] a, double[] b) {
int result = 0;
for (int i = 0; i < a.length; i++)
result += a[i]*b[i];
return result;
}
Matrix multiplication of an m × r matrix A and an r × n matrix B is defined as the m × n matrix C such that each entry
C[i][j] = the dot product of row i of A and column j of B.For example,
To write a procedure for this, we can use the transpose and dot
product: (we assume that the number of rows of
b is the same as the number of columns of
a)
double[][] multiply(double[][] a, double[][] b) {
double[][] c = new double[a.length][b[0].length];
double[][] bt = transpose(b);
for (int i = 0; i < a.length; i++)
for (int j = 0; j < bt.length; j++)
c[i][j] = dotProduct(a[i], bt[j]);
return c;
}
Similarly, one could define procedures for other matrix
operations, such as Gaussian elimination, and put all of these
together in a Matrix class.