Transcript Chapter 09 Student

Chapter 9 – Arrays
















Array Basics
Demo for Eclipse
Array Declaration
Array Creation
Array Initializer
Array Default Values
Array length Property
Partially Filled Arrays
Copying an Array
Histograms
Searching an Array
Sorting an Array
Selection Sort
Two-Dimensional Arrays
Arrays of Objects
For-Each Loop
1
2
Array Basics


A class stores a group of related data, and it stores the methods that operate on
that data.
An array is a limited version of a class.



Like a class, an array also stores a group of related data, but an array does not store
methods.
Another difference between an array and a class is that an array's data must all be of the
same type.
Here's a picture of an array that holds a list of phone numbers. Each of the five
boxes is called an array element and each box stores one phone number.
phoneList
8167412000
first phone number
2024561111
7852963232
8008675309
0035318842133
last phone number
3
Array Basics




A class uses dot notation to access one of its members.
On the other hand, an array uses square brackets around an index to
access one of its elements.
The rightmost column shows how to access each of the 5 elements in
the phoneList array.
Note that the index values start at 0 instead of 1 and the last index
value is one less than the number of elements in the array.
index
phoneList
how to access
each element
0
8167412000
phoneList[0]
1
2024561111
phoneList[1]
2
7852963232
phoneList[2]
3
8008675309
phoneList[3]
4
0035318842133
phoneList[4]
5 elements
Array Basics

Here's how you can change the first phone number to
2013434:
phoneList[0] = 2013434;

And here's how you can print the second phone
number:
System.out.println(phoneList[1]);
4
Array Basics
/*************************************************************
* ContactList.java
* Dean & Dean
*
* This program creates a cell phone contacts phone number
* list and prints the created list.
*************************************************************/
import java.util.Scanner;
public class ContactList
{
public static void main(String[] args)
{
Scanner stdIn = new Scanner(System.in);
long[] phoneList; // list of phone numbers
int sizeOfList;
// number of phone numbers
long phoneNum;
// an entered phone number
System.out.print(
"How many contact numbers would you like to enter? ");
sizeOfList = stdIn.nextInt();
phoneList = new long[sizeOfList];
5
Array Basics
for (int i=0; i<sizeOfList; i++)
{
System.out.print("Enter phone number: ");
phoneNum = stdIn.nextLong();
phoneList[i] = phoneNum;
} // end for
System.out.println("\nContacts List:");
for (int i=0; i<sizeOfList; i++)
{
System.out.println((i + 1) + ". " + phoneList[i]);
} // end for
} // end main
} // end class ContactList
6
Demo for Eclipse

Create a workspace and a project:






Create a program from scratch:







Open Eclipse and when prompted for a workspace, enter x:\219pgms_delme.
Select File / New / Java Project
In the project name box, enter “test”.
In the Project layout area, select “Use project folder as root for sources and class files.”
If Package Explorer is not shown, select Window / Show View / Package Explorer.
In the package explorer pane, right click on the project and select New / File.
In the New File window, select the project’s folder (test)
In the file name box, enter ContactList.java.
Copy ContactList's code from the slides into Eclipse.
Do a Project / Build Project command.
Do a Run / Run command.
Create a program by copying from an existing program:






In the package explorer tree, right click on the ContactList program and select copy.
Right click on the current project and select paste.
Change the newly pasted filename to ContactList2.java.
Review the ContactList2.java source code.
Do a Project / Build Project command.
Click the run-command triangle icon.
7
Array Declaration


An array is a variable and, as such, it must be declared
before you can use it.
Array declaration syntax:
<element-type>[] <array-variable>;

Array declaration examples:
int[] ids;
double[] workHours;
String[] names;
8
9
Array Creation



In Java, arrays are objects.
As with all objects, arrays are created/instantiated with
the new operator.
Syntax for creating and assigning an array object:
<array-variable> = new <element-type>[<array-size>];
<element-type> indicates the type of
each element in the array

Example:
long[] phoneList;
phoneList = new long[10];
array creation
<array-size> indicates the
number of elements in the array
Array Creation

It's legal to combine an array's declaration, creation,
and assignment operations. Here's an example:
long[] phoneList = new long[10];

Provide a single statement that declares, creates, and
assigns a 100-element array that stores book titles.
10
Array Initializer


An array initializer is a single statement made up of an
array declaration, creation, and {} assignment.
Array element initialization syntax:
<element-type>[] <array-name> = {<element-values-list>};

Array element initialization example:
String[] students = {"Eric", "Curtis", "John Robert"};


When an array initializer is used, the size of the array
equals the number of elements in the initialization list.
Note that with an array initializer, you create an array
object without using the new operator.
11
12
Array Default Values



An array is an object and an array's elements are the instance
variables for an array object. As such, an array's elements get
default values when the array is instantiated, the same as any
other instance variables get default values.
Here are the default values for array elements (they're also the
default values for instance variables and class variables):
Array element's type
Default value
integer
0
floating point
0.0
boolean
false
reference
null
For example, what are the default values below?
float[] gpas = new float[1000];
String[] states = new String[50];
Array length Property

Suppose you have a five-element colors array that's been
initialized like this:
String[] colors = {"blue", "gray", "lime", "teal", "yellow"};

Here's how to print such an array:
for (int i=0; i<colors.length; i++)
{
Note how an array object's length
System.out.println(colors[i]);
property gets the array's size.
}


To obtain an array's length, specify array name, dot, and then
length.
Note that length is used in two different ways:



length is a String method
length is an array property
Mnemonic acronym to help you remember when to use
parentheses with length:

ANSY (arrays no, strings yes)
13
14
Array length Property and Partially Filled Arrays
import java.util.Scanner;
public class ContactList2
{
Array length property
public static void main(String[] args) does not use ( )'s.
{
Scanner stdIn = new Scanner(System.in);
String[] phoneList = new String[100]; // phone numbers
int filledElements = 0;
// number of phone numbers
String phoneNum;
// an entered phone number
System.out.print("Enter phone number (or q to quit): ");
phoneNum = stdIn.nextLine();
String length
while (!phoneNum.equalsIgnoreCase("q") &&
method uses ( )'s.
filledElements < phoneList.length)
{
if (phoneNum.length() < 1 || phoneNum.length() > 16)
{
System.out.println("Invalid entry." +
" Must enter between 1 and 16 characters.");
}
15
Array length Property and Partially Filled Arrays
else
{
phoneList[filledElements] = phoneNum;
filledElements++;
}
System.out.print("Enter phone number (or q to quit): ");
phoneNum = stdIn.nextLine();
} // end while
System.out.println("\nContact List:");
for (int i=0; i<filledElements; i++)
{
System.out.println((i + 1) + ". " + phoneList[i]);
} // end for
} // end main
} // end class ContactList2
Partially Filled Arrays



A partially filled array is when you use some of an
array's elements, but not all.
If you have a partially filled array, you have to keep
track of the number of filled elements in the array so
you can process the filled elements differently from
the non-filled elements.
In the ContactList2 program, note how the
filledElements variable keeps track of the
number of phone numbers in the array.
16
Copying an Array


17
As with all objects and their associated reference
variables, if you assign one array reference variable to
another array reference variable, both array reference
variables then point to the same single array object.
What's the problem with that scenario? More
specifically, what's wrong with the following code if the
goal is to make a copy of arr1?
arr2 = arr1;
Copying an Array


Usually when you make a copy of an array, you'll want the copy
and the original to point to different array objects. To do that,
assign array elements one at a time.
For example, suppose you use arrays to hold a store's prices, one
array for each month's prices. And you'd like to copy January's
price array into February's price array and make a change in
February's second price. The program on the next slide does that
by assigning array elements one at a time. Here's the program's
output:
Jan
1.29
9.99
22.50
4.55
7.35
6.49
Feb
1.29
10.99
22.50
4.55
7.35
6.49
18
Copying an Array
public class ArrayCopy
{
public static void main(String[] args)
{
double[] pricesJanuary =
{1.29, 9.99, 22.50, 4.55, 7.35, 6.49};
double[] pricesFebruary = new double[pricesJanuary.length];
for (int i=0; i<pricesJanuary.length; i++)
{
pricesFebruary[i] = pricesJanuary[i];
}
pricesFebruary[1] = 10.99;
System.out.printf("%7s%7s\n", "Jan", "Feb");
for (int i=0; i<pricesJanuary.length; i++)
{
System.out.printf("%7.2f%7.2f\n",
pricesJanuary[i], pricesFebruary[i]);
}
} // end main
} // end class ArrayCopy
19
Histograms


20
A histogram is a graph that displays quantities for a
set of categories. It indicates category quantities with
bars - shorter bars equate to smaller quantities, longer
bars equate to larger quantities.
For example, the histogram on the next slide shows
the average number of deaths by age 5 per 1000 live
births.
Histograms
21
Histograms

Problem Description:


Suppose you have three coins. When you flip all three, you're
curious how likely it is you'll get zero heads, how likely it is
you'll get one head, how likely it is you'll get two heads, and
how likely it is you'll get three heads. In other words, you're
curious about the frequency distribution for the number of
heads.
Solution:


Write a main method that simulates throwing the three coins
a million times.
Print the simulation results in the form of a histogram:


For each of the four cases (zero heads, one head, etc.), print a
bar that represents the number of times the case occurred.
To mimic a bar, print a certain number of *'s where each *
represents 1% of the total number of simulation iterations.
23
Histograms

Output for the coin-flip program:
Number of times each head count occurred:
0 124685 ************
1 374759 *************************************
2 375420 **************************************
3 125136 *************

Program implementation tips:



Use a four-element frequency array to keep track of the number
of times each head-count value occurs. The frequency[0]
element holds the number of times none of the three coins lands
heads up. The frequency[1] element holds the number of times
one of the three coins lands heads up.
Each element in the frequency array is called a "bin."
After each simulation iteration, add 1 to the appropriate bin. For
example, increment the frequency[3] bin if all three of the coins
land heads up.
24
Histograms
public class CoinFlips
{
public static void main(String[] args)
{
final int NUM_OF_COINS = 3;
// number of coins that are flipped
final int NUM_OF_REPS = 1000000; // total number of repetitions
// The frequency array holds the number of times a particular number
// of heads occurred.
int[] frequency;
int heads;
// number of heads in the current group of flips
float fractionOfReps; // Number of times a particular head count occurred
// divided by total number of repetitions.
int numOfAsterisks;
// Number of asterisks in histogram for a
// particular head count.
frequency = new int[NUM_OF_COINS + 1];
for (int rep=0; rep<NUM_OF_REPS; rep++)
{
// perform a group of flips
heads = 0;
for (int i=0; i<NUM_OF_COINS; i++)
{
heads += (int) (Math.random() * 2);
}
frequency[heads]++;
// update appropriate bin
} // end for
25
26
Histograms
heads
1st
group of flips
2nd group of flips
0
0
0
1
1
012
0
2
01
1
3
0
2
3rd
group of flips
frequency
0
1
0
···
Histograms
System.out.println(
"Number of times each head count occurred:");
for (heads=0; heads<=NUM_OF_COINS; heads++)
{
System.out.print(
" " + heads + " " + frequency[heads] + " ");
fractionOfReps = (float) frequency[heads] / NUM_OF_REPS;
numOfAsterisks = Math.round(fractionOfReps * 100);
for (int i=0; i<numOfAsterisks; i++)
{
System.out.print("*");
}
System.out.println();
} // end for
} // end main
} // end class CoinFlips
27
Searching an array

Often, you'll need to determine whether an array
contains a particular value. Here's the pseudocode
algorithm for conducting a sequential search for a
particular value within a list array:
i←0
while i < number of filled elements
{
if list[i] equals the searched-for value
<do something and stop the loop>
increment i
}
28
Searching an array

Problem description:




29
Write a helper method named findStudent that searches
for an id value within an array of student id's.
The findStudent method should receive an id parameter
and return the index value of id's location within an ids array
instance variable.
If id's value is not found, then return -1.
As always, use appropriate access modifiers (public
vs. private, class method vs. instance method).
Sorting an Array


Sorting is a very common task in programming.
Examples:



Sort emails in an inbox – by date, by sender
Sort songs – by title, by author
Sort student records – by student ID
31
32
Selection Sort

There are many different sorting algorithms with varying degrees
of complexity and efficiency. Since this is your first exposure to
sorting, we'll cover a simple algorithm - the selection sort
algorithm. Here it is:
for (i0; i<list's_length; i++)
{
find the smallest value in list from list[i] down to the bottom of the list
swap the found value with list[i]
}
list (original)
list (sorted)
0
5
-3
-3
-3
-3
1
10
10
2
2
2
2
-3
5
5
5
5
3
20
20
20
20
10
4
2
2
10
10
20
Sorting an Array


You could include a sorting method in every class that
needs sorting functionality.
For example, you could include:




A studentSort method in a Students class that sorts students
by student id.
A bookSort method in a Books class that sorts books by ISBN
number.
A productSort method in a Products class that sorts products
by product id.
But suppose that you want to make a generic sorting
method that receives an array as a parameter (e.g.,
studentIds, bookISBNs, or productIds) and
sorts it.
33
Sorting an Array



To make the sorting method generic so that it can be
used by multiple classes, put the sort method in a
utility class.
A utility class is a class with general-purpose methods
that other classes can easily use. To make the
methods easy to use, use class methods (as opposed
to instance methods).
Why would it be easy for other classes to use the sort
method if the sort method is implemented as a class
method?
34
Sorting an Array

35
If you make the sort method an instance method, then you'll be
required to instantiate the sort method's enclosing class prior to
calling the sort method. For example, assuming the sort
method's enclosing class is named Sort:
Sort s = new Sort();
s.sort(studentIds);

On the other hand, if you make the sort method a class method,
then you are not required to instantiate the sort method's
enclosing class prior to calling the sort method. Instead, you
simply need to prefix the sort method call with the class name
and then a dot. For example:
Sort.sort(studentIds);

Thus, in the interest of simplicity and elegance, let's make the
sort method a class method.
Selection Sort
public class Sort
{
public static void sort(int[] list)
{
int j;
for (int i=0; i<list.length-1; i++)
{
j = indexOfNextSmallest(list, i);
swap(list, i, j);
}
} // end sort
private static int indexOfNextSmallest(int[] list, int startIndex)
{
int min = list[startIndex];
int minIndex = startIndex;
for (int i=startIndex+1; i<list.length; i++)
{
if (list[i] < min)
{
min = list[i];
minIndex = i;
}
} // end for
return minIndex;
} // end indexOfNextSmallest
36
Selection Sort
private static void swap(int[] list, int i, int j)
{
int temp;
temp = list[i];
list[i] = list[j];
list[j] = temp;
} // end swap
} // end Sort
public class SortDriver
{
public static void main(String[] args)
{
int[] studentIds = {3333, 1234, 2222, 1000};
Sort.sort(studentIds);
for (int i=0; i<studentIds.length; i++)
{
System.out.print(studentIds[i] + " ");
}
} // end main
} // end SortDriver
37
Two-Dimensional Arrays




If you have a group of related data that's organized in a table
format, consider using a two-dimensional array.
Two-dimensional arrays use the same basic syntax as onedimensional arrays except for a second pair of []'s.
The first index identifies the row and the second index identifies
the column position within a row.
For example, here's a two-row by three-column array named x:
x
column
indexes
row
indexes
how to access each element
0
1
2
0
8
-2
4
x[0][0]
x[0][1] x[0][2]
1
1
0
5
x[1][0]
x[1][1] x[1][2]
38
39
Two-Dimensional Arrays


As with one-dimensional arrays, there are two ways to
assign values into a two-dimensional array’s elements:
(1) an array initializer, and (2) assignment statements.
Here’s how you can declare the previous slide's x
array and assign values into its elements, using an
array initializer:
int[][] x = {{8,-2,4}, {1,0,5}};

initializer for a 2-row
by 3-column array
You can use the array initializer technique only if you
know the assigned values when you first declare the
array. Otherwise, you need to provide array element
assignment statements that are separate from the
array's declaration and creation.
Two-Dimensional Arrays

The following code fragment declares and creates the x array in
one statement, and assigns values to x's elements in a separate
statement (inside a nested loop).
int[][] x = new int[2][3];
Declare and create a 2-row
by 3-column array.
for (int i=0; i<x.length; i++)
{
for (int j=0; j<x[0].length; j++)
{
System.out.print(
"Enter value for row " + i + ", col " + j + ": ");
x[i][j] = stdIn.nextInt();
Assign a value to
} // end for j
the element at
} // end for i
row i column j.
40
Two-Dimensional Arrays

41
Bottom line: To loop through the rows in a two-dimensional
array, use <array-name>.length . And to loop through the
elements within a particular row, use <array-name>[0].length.
For example:
for (int i=0; i<x.length; i++)
{
for (int j=0; j<x[0].length; j++)
{
...
42
Two-Dimensional Arrays

The upcoming FlightTimes program:

Uses a two-dimensional array to store this table of flight times
between cities:
Wch
Top
KC
Col
StL


Wch
0
23
31
44
59
Top
22
0
10
27
41
KC
30
9
0
12
30
Col
42
25
11
0
14
StL
55
37
28
12
0
It takes 25 minutes
to fly from Topeka,
KS to Columbia, MO.
Contains a promptForFlightTime method that prompts
the user for a departure city and a destination city and prints
the flight time for that flight.
Contains a displayFlightTimesTable method that prints
the table.
Two-Dimensional Arrays
public class FlightTimesDriver
{
public static void main(String[] args)
{
int[][] flightTimes =
{
{0, 22, 30, 42, 55},
{23, 0, 9, 25, 37},
{31, 10, 0, 11, 28},
{44, 27, 12, 0, 12},
{59, 41, 30, 14, 0}
};
// Define terminals in the Kansas-Missouri region.
String[] cities = {"Wch", "Top", "KC", "Col", "StL"};
FlightTimes ft = new FlightTimes(flightTimes, cities);
System.out.println("\nFlight times for KansMo Airlines:\n");
ft.displayFlightTimesTable();
System.out.println();
ft.promptForFlightTime();
} // end main
} // end class FlightTimesDriver
43
Two-Dimensional Arrays
import java.util.Scanner;
public class FlightTimes
{
private int[][] flightTimes; // table of flight times
private String[] cities;
// names of cities in flightTimes table
public FlightTimes(int[][] ft, String[] c)
{
this.flightTimes = ft;
this.cities = c;
}
//********************************************
// This method prompts the user for departure and destination cities
// and prints the associated flight time.
public void promptForFlightTime()
{
Scanner stdIn = new Scanner(System.in);
int departure;
// index for departure city
int destination; // index for destination city
44
Two-Dimensional Arrays
for (int i=0; i<cities.length; i++)
{
System.out.println(i+1 + " = " + cities[i]);
}
System.out.print("Enter departure city's number: ");
departure = stdIn.nextInt() - 1;
System.out.print("Enter destination city's number: ");
destination = stdIn.nextInt() - 1;
System.out.println("Flight time = " +
flightTimes[departure][destination] + " minutes.");
} // end promptForFlightTime
//********************************************
// This method prints a table of all flight times.
<Insert displayFlightTimesTable method here.>
} // end class FlightTimes
45
47
Arrays of Objects




Suppose you need to keep track of total sales for each sales
clerk in a department store.
In the following clerks array, each array element holds a
reference for a SalesClerk object.
Each SalesClerk object holds a sales clerk's name and a totalsales value for the sales clerk.
If sales clerk Abe sells two items for $55.45 and $22.01, then
you'd like to store 77.46 for his total-sales value.
clerks
Jordan, 6.25
clerks[0]
clerks[1]
Prashuv, 58.12
clerks[2]
clerks[3]
null
Abe, 77.46
48
Arrays of Objects

Using the input shown below, how would the clerks
array get filled?
input
filledElements
Jordan
0
6.25
Prashuv
58.12
clerks
null
null
Abe
null
40
null
Jordan
-6.25
Prashuv
12.88
Arrays of Objects
import java.util.Scanner;
public class SalesClerksDriver
{
public static void main(String[] args)
{
Scanner stdIn = new Scanner(System.in);
SalesClerks clerks = new SalesClerks(2);
String name;
System.out.print("Enter clerk's name (q to quit): ");
name = stdIn.nextLine();
while (!name.equals("q"))
{
System.out.print("Enter sale amount: ");
clerks.addSale(name, stdIn.nextDouble());
stdIn.nextLine();
// flush newline
System.out.print("Enter clerk's name (q to quit): ");
name = stdIn.nextLine();
} // end while
clerks.dumpData();
} // end main
} // end SalesClerksDriver
49
Arrays of Objects
class SalesClerks
{
private SalesClerk[] clerks;
private int filledElements = 0;
// contains names and sales
// number of elements filled
//***********************************************************
public SalesClerks(int initialSize)
{
clerks = new SalesClerk[initialSize];
} // end SalesClerks constructor
//***********************************************************
//
//
//
//
Process a sale for the clerk whose name is passed in.
If the name is not already in the clerks array,
create a new object and insert a reference to it in the
next array element, doubling array length if necessary.
public void addSale(String name, double amount)
{
int clerkIndex = findClerk(name);
if (clerkIndex == -1) // add a new clerk
{
if (filledElements == clerks.length)
{
doubleLength();
}
50
Arrays of Objects
clerkIndex = filledElements;
clerks[clerkIndex] = new SalesClerk(name);
filledElements++;
} // end if
clerks[clerkIndex].adjustSales(amount);
} // end addSale
//**********************************************************
// Print all the data - sales clerk names and sales.
public void dumpData()
{
for (int i=0; i<filledElements; i++)
{
System.out.printf("%s: %6.2f\n",
clerks[i].getName(), clerks[i].getSales());
}
} // end dumpData
//**********************************************************
51
Arrays of Objects
52
// Search for the given name. If found, return the index.
// Otherwise, return -1.
The arraycopy method
copies the first argument's
array (starting at the
second argument's
position) to the third
argument's array (starting
at the fourth argument's
position). The fifth
argument specifies the
//**********************************************************
number of elements that
// Double the length of the array.
are to be copied.
private int findClerk(String name)
{
for (int i=0; i<filledElements; i++)
{
if (clerks[i].getName().equals(name))
{
return i;
}
} // end for
return -1;
} // end findClerk
private void doubleLength()
{
SalesClerk[] clerks2 = new SalesClerk[2 * clerks.length];
System.arraycopy(clerks, 0, clerks2, 0, clerks.length);
clerks = clerks2;
} // end doubleLength
} // end class SalesClerks
Arrays of Objects
public class SalesClerk
{
private String name;
private double sales = 0.0;
// sales clerk's name
// total sales for clerk
//*******************************************************
public SalesClerk(String name)
{
this.name = name;
}
//*******************************************************
public String getName()
{
return name;
}
public double getSales()
{
return sales;
}
//*******************************************************
// Adjust clerk's total sales by adding the passed-in sale.
public void adjustSales(double amount)
{
sales += amount;
}
} // end class SalesClerk
53
Arrays of Objects

Beware:


To create an array of objects, you must instantiate the array with
the new operator, and you must also instantiate each object that's
stored in the array with individual new operators.
For example, the SalesClerks constructor instantiates an array
of SalesClerk objects like this:
clerks = new SalesClerk[maxClerks];



You might think that since the above instantiation specifies
maxClerks number of SalesClerk objects, the JVM instantiates
all the SalesClerk objects.
On the contrary, the JVM only instantiates an array object and
each array element holds null.
To fill up the clerks array with SalesClerk objects, you need
to instantiate the SalesClerk objects individually.
54
For-Each Loop



55
A for-each loop is an alternative to the traditional for loop.
It’s handy when you want to iterate through all the elements in
an array and you don’t know or care where particular elements
are located.
Syntax:
for (<element-type> <element-reference> : <array-reference>)
{
...
}

When you read this, say to yourself:
“For each <element-reference> in <array-reference>,
...”
For-Each Loop

Here's a for-each loop example that prints the numbers in a
primes array:
int[] primes = {2, 3, 5, 7, 11, 13};
for (int p : primes)
{
System.out.println(p);
}

Say, “For each p in primes, print p.”

Benefits of the for-each loop (over the standard for loop):



It reduces code clutter.
It avoids the effort of index initialization (e.g., i=0), index
comparison (e.g., i<10), and index updating (e.g., i++).
It simplifies element access within the loop body by providing a
simple name for the current element (e.g., p, not primes[i]).
56
For-Each Loop

Although the for-each loop's lack of an index variable leads to
less cluttered code, the lack of an index variable can be a
drawback if there's a need for an index value within the loop.
For example, given the primes array in the earlier slide, which
type of loop (standard or for-each) should you use to print the
following?
primes[0] = 2
primes[1] = 3
...
primes[5] = 13

As a practice exercise, provide a standard for loop that prints
the above, and also provide a for-each loop that prints the
above.
57