Multi-Dimensional Arrays
Site: | Saylor Academy |
Course: | CS101: Introduction to Computer Science I |
Book: | Multi-Dimensional Arrays |
Printed by: | Guest user |
Date: | Wednesday, October 30, 2024, 3:17 PM |
Description
We can expand the whole idea of arrays to multiple dimensions, beyond one or two dimensions. Read these sections to see how this is done.
Multidimensional Arrays
Java doesn’t limit arrays to just two dimensions. For example, suppose we decide to extend our rainfall survey to cover a ten-year period. For each year we now need a two-dimensional array. This results in a three dimensional array consisting of an array of years, each of which contains an array of months, each of which contains an array of days:
final int NYEARS = 10; final int NMONTHS = 13; final int NDAYS = 32; double rainfall [][][] = new double [NYEARS][NMONTHS][NDAYS];
Following the design convention of not using the 0 month and 0 days, we end up with a 10 ⇥ 13 ⇥ 32 array. Note the use of final variables to represent the size of each dimension of the array. This helps to make the program more readable.
In Figure 9.23, each year of the rainfall data is represented as a separate page. On each page, there is a two-dimensional table that consists of 12 rows (1 per month) and 31 columns (1 per day).
Figure 9.23: Three-dimensional data might be viewed as a collection of pages, each of which contains a two-dimensional table
As you might expect, algorithms for processing each element in a threedimensional table would require a three-level nested loop. For example, the following algorithm would be used to initialize all elements of our three-dimensional rainfall array:
Note again the proper use of the length attribute for each of the three dimensions of the array. In the outer loop, rainfall.length, we’re referring to the number of years. In the middle loop, rainfall[year].length, we’re referring to number of months
within a given year. In the inner loop, rainfall[year][month].length, we’re referring to the number of days within a month.
If we added a fourth dimension to our array and wanted to extend this algorithm to initialize it, we would simply embed the three-level loop within another for loop that would iterate over each city.
Source: R. Morelli and R. Walde, Trinity College
This work
is licensed under a Creative Commons Attribution 4.0 License.
Array Initializers
It is possible to use an initializer with a multidimensional array. For instance, the following examples create several small arrays and initialize
their elements:
The first of these declarations creates a 2 ⇥ 3 array of integers. The second
example creates a 2 ⇥ 2 array of characters, and the third example creates
an array of double consisting of three rows, each of which has a different
number of elements. The first row contains three elements, the second
contains two elements, and the last row contains four elements. As this
last example shows, the rows in a multidimensional array don't all have
to have the same length.
Using initializers, as in these examples, is feasible only for relatively
small arrays. To see why, just imagine what the initializer expression
would be for our three-dimensional rainfall array. It would require
4,160 = 10 ⇥ 13 ⇥ 32 zeroes, separated by commas!
Object-Orientated Design: Polymorphic Sorting
One limitation of the sort routines developed so far is that they only
work on one particular type of data. If you've written an insertion
sort to sort ints, you can't use it to sort doubles. What would be
far more desirable is a polymorphic sort method—that is, one method
that could sort any kind of data. This is easily done by making use of
Java wrapper classes, such as Integer and Double, together with the
java.lang.Comparable interface, which is specially designed for this
purpose.
The java.lang.Comparable interface consists of the compareTo()
method:
By implementing compareTo(), a class can impose an order on its objects. The Comparable interface is implemented by all of Java's wrapper
classes—that is, by Integer, Double, Float, Long, and so on (Fig. 9.24).
As we saw in Chapter 8, Java interfaces allow us to create a form of multiple inheritance. For example, as Figure 9.24 shows, an Integer is both an
Object and a Comparable. One implication of this is that an Integer
can be used in any method that takes either an Object parameter or a
Comparable parameter.
The compareTo() method takes an Object parameter and returns an
int. It is meant to be invoked as o1.compareTo(o2), where o1 and o2
are objects of the same type. Classes that implement compareTo() must
abide by the following rules for its return value:
In other words, if o1 < o2, then o1.compareTo(o2) will return a negative integer. If o1 > o2, then o1.compareTo(o2) will return a positive integer. And if o1 and o2 are equal, then o1.compareTo(o2) will
return 0.
For a class that implements Comparable, we can use the compareTo()
method to help sort its elements. For example, the following revised
version of insertionSort() method can be used to sort any array of
Comparable objects—that is, any array of objects whose class implements Comparable:
In this version, the parameter is an array of Comparable. Thus, we can
pass it any array whose elements implement Comparable, including an
array of Integer or Float, and so on. Then, to compare elements of a
Comparable array, we use the compareTo() method:
Note that our algorithm no longer refers to ints, as in the original insertion sort. Indeed, it doesn't mention the specific type—Integer,
Float, or whatever—of the objects that it is sorting. It refers only to
Comparables. Therefore, we can use this method to sort any type
of object, as long as the object's class implements the Comparable
interface. Thus, by using Comparable, we have a more general
insertionSort() method, one that can sort any one-dimensional array
of Comparables.
The TestSort class (Figs. 9.25 and 9.26) provides an example of how to use the polymorphic sort() method.
It contains three methods: The sort() method that we just described;
a polymorphic print() method, which can be used to print the values of any array of Comparable; and a main() method. The main()
method creates arrays of Integer and Float and then uses the polymorphic sort() method to sort them. Note how the print() method
uses the polymorphic toString() method to print the elements of a
Comparable array.
This example of polymorphic sorting illustrates once again the great
power of inheritance and polymorphism in object-oriented programming.
The Integer and Float classes use class inheritance to inherit features
from the Object class, and they use interface implementation to inherit
the compareTo() method from the Comparable class. By implementing versions of the toString() and compareTo() methods that are appropriate for these wrapper classes, Java makes it easier to use Integer
and Float objects in a variety of contexts. Taken together, inheritance and polymorphism enable us to design very general and extensible algorithms. In this example, we defined a sort() method that can sort an
array containing any kind of object as long as the object implements the
Comparable interface.
The java.util.Arrays.sort() Method
While sorting algorithms provide a good way to introduce the concepts
of array processing, real-world programmers never write their own sort
algorithms. Instead they use library methods, which have been written and optimized by programming experts. Moreover, library sort routines use sort algorithms that are much more efficient than the ones we’ve
discussed.
The java.util.Arrays class contains a polymorphic sort method
that is very simple to use. For example, here’s how we would use it to sort
the two arrays declared in the TestSort program:
That’s all there is to it! Obviously, learning how to use Java’s class and
method library, saves real-word programmers lots of effort.
SELF-STUDY EXERCISES
EXERCISE 9.20 Add a definition of a compareTo() method to the LetterFreq class so that it implements the Comparable interface. The method should define one object to be less than another object if its freq instance variable is less.
EXERCISE 9.21 Add a definition of a sort() method that can be added to the definition of the AnalyzeFreq class. Make it so the array in the class can be sorted into ascending order using the ordering of LetterFreq defined in the previous exercise. Use the java.util.Arrays.sort() method.
EXERCISE 9.22 Rewrite the main() of the AnalyzeFreq class to
make use of the sort() method of the previous exercise.
From the Java Library: java.uti
The java.util.Vector class implements an array of objects that can grow in size as needed. One limitation of regular arrays is that their lengths remain fixed. Once the array is full – once every element is used – you can't allocate additional
elements.
The Vector class contains methods for storing and retrieving objects, and for accessing objects by their index position within the Vector (Fig. 9.27).
Vector |
+ Vector() |
+ Vcclor(in size : int) |
+ addElcment(in o :Object) |
+ ckmcntAt(in index : int) :Object |
+ inscrtElcmentAt(in o :Object, in x : int) |
+ indcxOf(in et :Object) : int |
+ IastlndcxOf(in o :Object) :int |
+ rcmoveElementAt(in index : int) |
+ sizc( ) : int |
Vector Figure 9.27: The java.util.Vecto
One use for a Vector would be when a program needs to store input from the user or a file without knowing in advance how many items there are. Using a Vector is less efficient than an array in terms of processing speed, but it gives you the flexibility
of growing the data structure to meet the storage requirements.
As an illustration of this idea, the program in Figure 9.28 creates a random number of integers and then stores them in a Vector. The Vector, which is declared and instantiated in main(), is initially empty. Integers from 0 to the
random bound are then inserted into the Vector. In this case, insertions are done with the addElement() method, which causes the Vector object to insert the element at the next available location, increasing its size, if
necessary.
Once all the integers have been inserted, the printVector() method is called. Note that it uses the size() method to determine how many elements the Vector contains. This is similar to using the length()
method to determine the number of characters in a String.
Finally, note that a Vector stores objects. It cannot be used to store primitive data values. You cannot store an int in a Vector. Therefore, we need to use the Integer wrapper class to convert ints into Integers
before they can be inserted into the Vector. Because you can't just print an Integer, or any other Object, the toString() method is used to print the string representation of the object.
By defining Vector to store Objects, Java's designers have made it as general as possible and, therefore, as widely useful as possible.
JAVA EFFECTIVE DESIGN Generality. Defining a data collection, such as an array or a Vector, in terms of the Object class makes it capable of storing and processing any type of value, including values of primitive data types. This is because the Object class is the root of the Java class hierarchy. |
---|