E.13 Wrap-Up
This appendix began our introduction to data structures, exploring the use of arrays to store data in and retrieve data from lists and tables of values. The appendix examples demonstrated how to declare an array, initialize an array and refer to individual elements of an array. The appendix introduced the enhanced for statement to iterate through arrays. We used exception handling to test for ArrayIndexOutOfBoundsExceptions that occur when a program attempts to access an array element outside the bounds of an array. We also illustrated how to pass arrays to methods and how to declare and manipulate multidimensional arrays.
We introduced the ArrayList<T> generic collection, which provides all the functionality and performance of arrays, along with other useful capabilities such as dynamic resizing. We used the add methods to add new items to the end of an ArrayList and to insert items in an ArrayList. The remove method was used to remove the first occurrence of a specified item, and an overloaded version of remove was used to remove an item at a specified index. We used the size method to obtain number of items in the ArrayList.
We continue our coverage of data structures in Appendix J. Appendix J introduces the Java Collections Framework, which uses generics to allow you to specify the exact types of objects that a particular data structure will store. Appendix J also introduces Java’s other predefined data structures. The Collections API provides class Arrays, which contains utility methods for array manipulation. Appendix J uses several static methods of class Arrays to perform such manipulations as sorting and searching the data in an array.
We’ve now introduced the basic concepts of classes, objects, control statements, methods, arrays and collections. In Appendix F, we take a deeper look at classes and objects.
Self-Review Exercises
E.1 Fill in the blank(s) in each of the following statements:
a) Lists and tables of values can be stored in __________.
b) An array is a group of __________ (called elements or components) containing values that all have the same ___________.
c) The __________ allows you to iterate through the elements in an array without using a counter.
d) The number used to refer to a particular array element is called the element’s __________.
e) An array that uses two indices is referred to as a(n) __________array.
f) Use the enhanced for statement __________ to walk through double array numbers.
g) Command-line arguments are stored in __________.
E.2 Determine whether each of the following is true or false. If false, explain why.
a) An array can store many different types of values.
b) An array index should normally be of type float.
c) An individual array element that’s passed to a method and modified in that method will contain the modified value when the called method completes execution.
E.3 Perform the following tasks for an array called fractions:
a) Declare a constant ARRAY_SIZE that’s initialized to 10.
b) Declare an array with ARRAY_SIZE elements of type double, and initialize the elements to 0.
c) Refer to array element 4.
d) Assign the value 1.667 to array element 9.
e) Assign the value 3.333 to array element 6.
f) Sum all the elements of the array, using a for statement. Declare the integer variable x as a control variable for the loop.
E.4 Perform the following tasks for an array called table:
a) Declare and create the array as an integer array that has three rows and three columns. Assume that the constant ARRAY_SIZE has been declared to be 3.
b) How many elements does the array contain?
c) Use a for statement to initialize each element of the array to the sum of its indices. Assume that the integer variables x and y are declared as control variables.
E.5 Find and correct the error in each of the following program segments:
a)
final int ARRAY_SIZE = 5;
ARRAY_SIZE = 10;
b)
Assume int[] b = new int[ 10 ];
for ( int i = 0; i <= b.length; i++ )
b[ i ] = 1;
c)
Assume int[][] a = { { 1, 2 }, { 3, 4 } };
a[ 1, 1 ] = 5;
Answers to Self-Review Exercises
a) arrays.
b) variables, type.
c) enhanced for statement.
d) index (or subscript or position number).
e) two-dimensional.
f) for ( double d : numbers ).
g) an array of Strings, called args by convention.
a) False. An array can store only values of the same type.
b) False. An array index must be an integer or an integer expression.
c) For individual primitive-type elements of an array: False. A called method receives and manipulates a copy of the value of such an element, so modifications do not affect the original value. If the reference of an array is passed to a method, however, modifications to the array elements made in the called method are indeed reflected in the original. For individual elements of a reference type: True. A called method receives a copy of the reference of such an element, and changes to the referenced object will be reflected in the original array element.
a) final int ARRAY_SIZE = 10;
b) double [] fractions = new double [ ARRAY_SIZE ];
c) fractions[ 4 ]
d) fractions[ 9 ] = 1.667;
e) fractions[ 6 ] = 3.333;
f)
double total = 0.0;
for ( int x = 0; x < fractions.length; x++ )
total += fractions[ x ];
a) int [][] table = new int [ARRAY_SIZE ][ ARRAY_SIZE ];
b) Nine.
c)
for ( int x = 0; x < table.length; x++ )
for ( int y = 0; y < table[ x ].length; y++ )
table[ x ][ y ] = x + y;
a) Error: Assigning a value to a constant after it has been initialized.
Correction: Assign the correct value to the constant in a final int ARRAY_SIZE declaration or declare another variable.
b) Error: Referencing an array element outside the bounds of the array (b[10]).
Correction: Change the <= operator to <.
c) Error: Array indexing is performed incorrectly.
Correction: Change the statement to a[ 1 ][ 1 ] = 5;.
a) One-dimensional array p contains four elements. The names of those elements are __________, __________, __________ and __________.
b) Naming an array, stating its type and specifying the number of dimensions in the array is called __________ the array.
c) In a two-dimensional array, the first index identifies the __________ of an element and the second index identifies the ___________ of an element.
d) An m-by-n array contains __________ rows, __________ columns and __________ elements.
e) The name of the element in row 3 and column 5 of array d is __________.
E.7 Determine whether each of the following is true or false. If false, explain why.
a) To refer to a particular location or element within an array, we specify the name of the array and the value of the particular element.
b) An array declaration reserves space for the array.
c) To indicate that 100 locations should be reserved for integer array p, you write the declaration
p[ 100 ];
d) An application that initializes the elements of a 15-element array to zero must contain at least one for statement.
e) An application that totals the elements of a two-dimensional array must contain nested for statements.
E.8 Consider a two-by-three integer array t.
a) Write a statement that declares and creates t.
b) How many rows does t have?
c) How many columns does t have?
d) How many elements does t have?
e) Write access expressions for all the elements in row 1 of t.
f) Write access expressions for all the elements in column 2 of t.
g) Write a single statement that sets the element of t in row 0 and column 1 to zero.
h) Write individual statements to initialize each element of t to zero.
i) Write a nested for statement that initializes each element of t to zero.
j) Write a nested for statement that inputs the values for the elements of t from the user.
k) Write a series of statements that determines and displays the smallest value in t.
l) Write a single printf statement that displays the elements of the first row of t.
m) Write a statement that totals the elements of the third column of t. Do not use repetition.
n) Write a series of statements that displays the contents of t in tabular format. List the column indices as headings across the top, and list the row indices at the left of each row.
E.9 (Duplicate Elimination) Use a one-dimensional array to solve the following problem: Write an application that inputs five numbers, each between 10 and 100, inclusive. As each number is read, display it only if it’s not a duplicate of a number already read. Provide for the “worst case,” in which all five numbers are different. Use the smallest possible array to solve this problem. Display the complete set of unique values input after the user enters each new value.
E.10 Label the elements of three-by-five two-dimensional array sales to indicate the order in which they’re set to zero by the following program segment:
for ( int row = 0; row < sales.length; row++ )
{
for ( int col = 0; col < sales[ row ].length; col++ )
{
sales[ row ][ col ] = 0;
}
}
E.11 (Sieve of Eratosthenes) A prime number is any integer greater than 1 that’s evenly divisible only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It operates as follows:
a) Create a primitive-type boolean array with all elements initialized to true. Array elements with prime indices will remain true. All other array elements will eventually be set to false.
b) Starting with array index 2, determine whether a given element is true. If so, loop through the remainder of the array and set to false every element whose index is a multiple of the index for the element with value true. Then continue the process with the next element with value true. For array index 2, all elements beyond element 2 in the array that have indices which are multiples of 2 (indices 4, 6, 8, 10, etc.) will be set to false; for array index 3, all elements beyond element 3 in the array that have indices which are multiples of 3 (indices 6, 9, 12, 15, etc.) will be set to false; and so on.
When this process completes, the array elements that are still true indicate that the index is a prime number. These indices can be displayed. Write an application that uses an array of 1000 elements to determine and display the prime numbers between 2 and 999. Ignore array elements 0 and 1.
E.12 (Fibonacci Series) The Fibonacci series
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
begins with the terms 0 and 1 and has the property that each succeeding term is the sum of the two preceding terms.
a) Write a method fibonacci( n ) that calculates the nth Fibonacci number. Incorporate this method into an application that enables the user to enter the value of n.
b) Determine the largest Fibonacci number that can be displayed on your system.
c) Modify the application you wrote in part (a) to use double instead of int to calculate and return Fibonacci numbers, and use this modified application to repeat part (b).