Transcript counts

Introduction to Computer Science
Unit 10
One Dimensional Arrays
Arrays
 An
array is a sequence of variables of
identical type
 It
is used to store large amounts of data,
without having to declare many individual
variables
[0]
[1]
[2]
[3]
[4]
[5]
[6]
counts
10- 2
Arrays
 “Arrays
bring to data what loops
bring to action—power.”
 Arrays
give us a way of defining a
structured collection of data,
without having to name each
component (as we would have to
do with individual variables)
 It
gives us an important tool for
implementing data abstraction
10- 3
Old Example
public static void main (String[ ] args) {
int
score;
int
sumOfScores = 0;
int
numberOfScores = 0;
SimpleInput sinp = new SimpleInput(System.in);
System.out.print(“Enter score (eof ends the data): ”);
score = sinp.readInt( );
int
maxOfScores = score;
int
minOfScores = score;
while ( !sinp.eof( ) ) {
numberOfScores++;
//new score
sumOfScores += score;
//update sum
if (maxOfScores < score) //new largest score
maxOfScores = score;
if (minOfScores > score) //new smallest score
minOfScores = score;
…
10- 4
That was a “streamoriented” approach to data
Once a value goes past, it’s gone—there’s only one
variable, score, that holds input data.
But suppose we want to read and average the input
stream, and echo only values that are above average. We
could:
 Read
the input stream twice, averaging the first time,
printing large numbers the second (a file-oriented
approach; not practical for human input)
 Read
and store the input values, summing them as
they’re stored. Get average at end, then echo only the
larger ones (this will use an array)
10- 5
Variables and Arrays
95
264
3
score
sumOfScores
numberOfScores
Simple variables give us a snapshot of the data.
[0]
counts
[1]
[2]
[3]
[4]
[5]
[6]
An array lets us reinspect any
part of the data stream
10- 6
A Random Access Data Structure
Arrays are a random access data
structure.
Values can be stored or retrieved
in any order we want.
[0]
[1]
[2]
[3]
[4]
[5]
[6]
counts
10- 7
Things to Notice with an Array
1. What’s the array’s name?
2. What kinds of values can it hold?
3. How many values can it hold?
4. How do we refer to individual
values in the array?
We’ll now look at each of these
answers for a Java array
10- 8
Arrays Are a Special Kind of Object
 An
array contains a fixed number
of variables of identical type
 This
fixed number is called the
array’s length
 Like
any object, an array must
first be declared, then allocated
(created)
 Remember
that an array is an
object, and this fact will help you
10- 9
Declaring an Array Variable
 Declare
a variable to be an array:
int[ ] counts;
double[ ] scores;
Time[ ] appointmentTimes;
 The
brackets tell Java that the
variable (counts, scores, or
appointmentTimes) will be an array
10- 10
Answers to some questions
 We’ve
answered questions 1 and 2
with our declarations:
1. What is the array’s name?
2. What kinds of values can it hold?
int[ ] counts;
double[ ] scores;
Time[ ] appointmentTimes;
 First
array’s name is “counts”, and it
holds values of type int, etc.
10- 11
Allocating (creating) an
Array in the Heap
We create an array using the new notation, but
with some variations
 We have to tell new how many variables will be in
the array object (use square brackets):

counts = new int[10];
scores = new double[15];
appointmentTimes = new Time[10];

In general, new type[ size ]
creates an array of length size with variables of
type type, returning an array object (in the heap);
Answer to Question 3. How many values can it
hold? (given during allocation)
10- 12
Doing it All At Once

Obviously, like with any variable (simple or
object), you can write it on one line:
int[ ] counts = new int[10];
double[ ] scores = new double[15];
Time[ ] appointmentTimes = new Time[10];

Now we have array objects sitting in the heap,
called counts (that can hold 10 ints), scores
(that can hold 15 doubles), and
appointmentTimes (that can hold 10 Time
objects)
10- 13
Creation of an Array Object
new type[ size ]

size can be any integer or integer expression:
int i = 3;
char[ ] name = new char[i];
is just as good as:
char[ ] name = new char[3];

The memory in an array is automatically
initialized for us (to 0 for numbers, false for
booleans, or null for objects, as appropriate)
10- 14
Let’s Look at counts
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
counts
•Place to hold 10 ints
•Each int is held in a separate box
•The subscript, or index, of the variables runs from 0 to 9
(the index always starts at 0)
•Arrays can contain any type of value: simple value or
(reference to) object
•Let’s deconstruct
Time[ ] appointmentTimes = new Time[10];
10- 15
If We Just Wrote:
Time[ ] appointmentTimes;
null
appointmentTimes
heap
10- 16
If We Wrote:
appointmentTimes
null
null
null
null
null
null
null
null
null
null
Time[ ] appointmentTimes = new Time[10];
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
heap
10- 17
After we fill up the appointmentTimes
array with Time objects…
Attributes:
_hour = …
_minute = …
Methods:
…
Attributes:
_hour = …
_minute = …
Methods:
…
Attributes:
_hour = …
_minute = …
Methods:
…
Attributes:
_hour = …
_minute = …
Methods:
…
Attributes:
_hour = …
_minute = …
Methods:
…
Attributes:
_hour = …
_minute = …
Methods:
…
[0]
appointmentTimes
Attributes:
_hour = …
_minute = …
Methods:
…
[1]
[2]
[3]
Attributes:
_hour = …
_minute = …
Methods:
…
Attributes:
_hour = …
_minute = …
Methods:
…
Attributes:
_hour = …
_minute = …
Methods:
…
[4]
[5]
[6]
[7]
[8]
[9]
heap
10- 18
Answer to Question 4: How do we refer
to individual values in the array?
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
counts
Use subscripts to obtain any specific variable
counts[0]
is the first variable in counts
counts[1]
is the second variable in counts
counts[9]
is the last variable in counts
counts[10]
is an error!
10- 19
They are Used Like
Regular Variables
counts[0]
counts[1]
counts[9]
These are all int variables, and can be used
anywhere any int variable (like “score” or
“sumOfScores”) is used:
counts[1] = 17;
score = counts[8];
sumOfScores = (7 * ((counts[4] + 2)/8));
10- 20
Java Checks
Array Bounds For You
counts[10]
 This does not exist, since the 10
elements in counts run from 0 to 9
 If you try and use this nonexistent
value, Java throws an
ArrayIndexOutOfBoundsException
error
 More about these kinds of errors
(exceptions) later
10- 21
public class Simple {
public static void main (String[ ] args)
{
int[ ] counts = new int[10];
SimpleInput sinp = new SimpleInput(System.in);
System.out.println(“Enter
counts[0] = sinp.readInt(
counts[1] = sinp.readInt(
counts[2] = sinp.readInt(
counts[3] = sinp.readInt(
counts[4] = sinp.readInt(
counts[5] = sinp.readInt(
counts[6] = sinp.readInt(
counts[7] = sinp.readInt(
counts[8] = sinp.readInt(
counts[9] = sinp.readInt(
ten numbers: ”);
);
);
);
);
);
Of course we
);
this with a
);
);
);
);
System.out.print(counts[9]+ “ ” +
counts[7] + “ ” + counts[6]
counts[5] + “ ” +
counts[4] + “ ” + counts[3]
counts[2] + “ ” +
counts[1] + “ ” + counts[0]
}
}
can do
loop
counts[8] + “ ” +
+ “ ” +
+ “ ” +
+ “\n”);
A Small Note on Variable Scope
 When
we write
for (int i = 0; i < 10; i++)
System.out.println( counts[i] );
the variable i exists only for the scope of
the for loop
 It cannot be reused later, unless it is
redeclared
 This is just a convenience for writing
loops
10- 23
import intro2cs.utils.*;
import java.io.*;
public class Simple {
public static void main (String[ ] args)
throws IOException
{
int[ ] counts = new int[10];
SimpleInput sinp = new SimpleInput(System.in);
System.out.println(“Enter ten numbers: ”);
for (int i = 0; i < 10; i++) {
counts[i] = sinp.readInt( );
}
for (int i = 9; i >= 0; i--) {
System.out.print(counts[i] + “ ”);
}
System.out.println();
}
}
10- 24
Using a Variable as an Index
 If
i is an integer variable, you can, for
example, write
counts[i]
to refer to one of the variables in counts

counts[2*i]
refers to counts[0] if i is 0, counts[2] if i is
1, etc.; illegal if i is outside the 0 to 4 range

counts[i/2]
refers to counts[0] if i is 0 or 1, counts[1] if
i is 2 or 3, etc.; illegal if i is outside 0 to 19
10- 25
Alternative Way to Declare and
Allocate an Array All At Once

Arrays can be initialized by giving a list of all their
elements:
int[ ] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

The declaration is on the left side of the
assignment

No explicit creation of the object is necessary;
Java handles it automatically

It must be done in a single line; this is illegal:
int[ ] primes;
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
10- 26
Let’s Use the Technique
 Method
that takes an integer and prints
out that day of the week:
final String[ ] NAME = {“”,
“Sunday”, “Monday”, “Tuesday”,
“Wednesday”, “Thursday”, “Friday”,
“Saturday”};
void printName (int day) {
System.out.print(NAME[day]);
}
10- 27
What is the Effect of the Following?
int[ ] a, b;
a = new int[10];
b = a;
 Since
arrays are objects, a and b are
references to objects (in the heap, as
expected)
 So
now a and b refer to the same array
 An
array is a mutable object; changes
made to the array are reflected in
“both” a and b
10- 28
Two Variables Pointing to Same Array Object
int[ ] a, b;
null
b
null
a
heap
10- 29
Two Variables Pointing to Same Array Object
int[ ] a, b;
a = new int[10];
null
b
0 0 0 0
0 0
0 0
0 0
[0]
[4]
[6]
[8]
[1]
[2]
[3]
[5]
[7]
[9]
heap
a
10- 30
Two Variables Pointing to Same Array Object
int[ ] a, b;
a = new int[10];
b = a;
b
0 0 0 0
0 0
0 0
0 0
[0]
[4]
[6]
[8]
[1]
[2]
[3]
[5]
[7]
[9]
heap
a
10- 31
Passing an Array as an
Argument Between Methods
public int firstMethod( ) {
int[ ] a = new int[10];
a[0] = 9;
secondMethod(a);
return a[0];
}
public void secondMethod(int[ ] b)
b[0] = 5;
}
{
a is an array object variable. b receives a copy of a,
and thus points to the same object. Changes to b are
reflected in a. firstMethod( ) therefore returns 5.
10- 32
Passing an Array as an Argument
Between Methods
public int firstMethod( ) {
int[ ] a = new int[10];
a[0] = 9;
secondMethod(a);
return a[0];
}
public void secondMethod(int[ ] b)
b[0] = 5;
}
a
{
0 0 0 0
0 0
0 0
0 0
[0]
[4]
[6]
[8]
[1]
[2]
[3]
[5]
[7]
[9]
heap
10- 33
Passing an Array as an Argument
Between Methods
public int firstMethod( ) {
int[ ] a = new int[10];
a[0] = 9;
secondMethod(a);
return a[0];
}
public void secondMethod(int[ ] b)
b[0] = 5;
}
a
{
9 0 0 0
0 0
0 0
0 0
[0]
[4]
[6]
[8]
[1]
[2]
[3]
[5]
[7]
[9]
heap
10- 34
Passing an Array as an Argument
Between Methods
public int firstMethod( ) {
int[ ] a = new int[10];
a[0] = 9;
secondMethod(a);
return a[0];
}
public void secondMethod(int[ ] b)
b[0] = 5;
}
a
{
9 0 0 0
0 0
0 0
0 0
[0]
[4]
[6]
[8]
[1]
[2]
[3]
[5]
[7]
[9]
heap
10- 35
Passing an Array as an Argument
Between Methods
public int firstMethod( ) {
int[ ] a = new int[10];
a[0] = 9;
secondMethod(a);
return a[0];
}
public void secondMethod(int[ ] b)
b[0] = 5;
}
b
a
{
9 0 0 0
0 0
0 0
0 0
[0]
[4]
[6]
[8]
[1]
[2]
[3]
[5]
[7]
[9]
heap
10- 36
Passing an Array as an Argument
Between Methods
public int firstMethod( ) {
int[ ] a = new int[10];
a[0] = 9;
secondMethod(a);
return a[0];
}
public void secondMethod(int[ ] b)
b[0] = 5;
}
b
a
{
5 0 0 0
0 0
0 0
0 0
[0]
[4]
[6]
[8]
[1]
[2]
[3]
[5]
[7]
[9]
heap
10- 37
Passing an Array as an Argument
Between Methods
public int firstMethod( ) {
int[ ] a = new int[10];
a[0] = 9;
secondMethod(a);
return a[0];
}
public void secondMethod(int[ ] b)
b[0] = 5;
}
a
{
5 0 0 0
0 0
0 0
0 0
[0]
[4]
[6]
[8]
[1]
[2]
[3]
[5]
[7]
[9]
heap
10- 38
The public Instance
Variable “length”
 Every
array object has a public instance
variable (final) called length
 It tells how many elements are in the array
 Since it is public, it can be freely accessed;
if a is an array, a.length says how many
elements it has
 Print all elements of the array counts:
for (int i = 0; i < counts.length; i++)
System.out.println( counts[i] );
10- 39
Simple Array Processing Loops
 Copy
all the elements from array b into
array a (assume they are same length):
for (int i = 0; i < a.length; i++)
a[i] = b[i];
 How
does this differ from
a = b;
10- 40
Another Example
 Initialize
the array counts to contain
the numbers 0, 10, 20, etc. up to 90:
counts 0
[0]
10 20
30 40 50 60
70 80 90
[1]
[3]
[7]
[2]
[4]
[5]
[6]
[8]
[9]
for (int i = 0; i < counts.length; i++)
counts[i] = i * 10;
10- 41
Read 10 numbers into array “counts”
and print them in reverse order (again)
import intro2cs.utils.*;
import java.io.*;
public class Simple {
public static void main (String[ ] args)
throws IOException
{
int[ ] counts = new int[10];
SimpleInput sinp = new SimpleInput(System.in);
System.out.println(“Enter ten numbers: ”);
for (int i = 0; i < 10; i++) {
counts[i] = sinp.readInt( );
}
for (int i = 0; i < 10; i++) {
System.out.print(counts[9 - i] + “ ”);
}
System.out.println();
}
}
10- 42
Another Way to Do It (again)
import intro2cs.utils.*;
import java.io.*;
public class Simple {
public static void main (String[ ] args)
throws IOException
{
int[ ] counts = new int[10];
SimpleInput sinp = new SimpleInput(System.in);
System.out.println(“Enter ten numbers: ”);
for (int i = 0; i < 10; i++) {
counts[i] = sinp.readInt( );
}
for (int i = 9; i >= 0; i--) {
System.out.print(counts[i] + “ ”);
}
System.out.println();
}
}
10- 43
An Array’s Size is Fixed
When Created
 An
array cannot grow
 Its
size is determined when it is
created
 One
simple way of dealing with this
is to make a large array and only
partially fill it
 Let’s
look at an example
10- 44
Encapsulate reading and
echoing an array in a class
 We’ll
make a class Collection, which will
include an array and methods for
handling the array
 The
client uses Collection by creating a
Collection object, passing its constructor
the (large) size of the array desired
 Let’s
look at how the client would use the
Collection class, and how the class itself
is defined
10- 45
The client to the Collection class
class MyClient {
static final int INPUT_MAX = 1000;
public static void main (String[ ] arg) {
Collection c = new Collection(INPUT_MAX);
c.readAndEcho( );
}
}
10- 46
class Collection {
private int[ ] _item;
private int _size = 0;
A wrapper class
for an array
public Collection (int number) {
_item = new int[number];
}
public void readAndEcho( ) {
SimpleInput sinp = new SimpleInput(System.in);
System.out.println(“Enter first number: ”);
int n = sinp.readInt( );
while ( !sinp.eof( ) ) {
_item[_size] = n;
_size++;
System.out.println(“Enter next number: ”);
n = sinp.readInt( );
}
System.out.println( );
for (int i = 0; i < _size; i++)
System.out.println(_item[i]);
}
}
What That Looks Like in Memory
…
array
of ints
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
Attributes:
_item = …
_size = …
Methods:
void readAndEcho ( )
c
[8]
[9]
Collection
object
heap
10- 48
Another Example
 Create
program that reads in student
name and two scores and prints average
for each student (until end-of-file):
Enter name and two exam grades: Bill
57
69
Enter name and two exam grades: Scott
94
86
Enter name and two exam grades: ^D or
^Z
10- 49
The Expected Output
Name
Bill
Scott
Average
63
90
The client program:
class MyClient {
static final int INPUT_MAX = 100;
public static void main (String[ ] arg) {
GradeBook grades = new GradeBook(INPUT_MAX);
grades.readAndAverage( );
}
}
10- 50
class GradeBook {
private String[ ] _names;
private int[ ] _exam1, _exam2;
private int _size = 0;
A wrapper class
for 3 arrays
public GradeBook (int number) {
_names = new String[number];
_exam1 = new int[number];
_exam2 = new int[number];
}
public void readAndAverage( ) {
SimpleInput sinp = new SimpleInput(System.in);
while ( true ) {
System.out.println(“Enter name and ” +
“two exam grades: ”);
_names[_size] = sinp.readString( );
if ( sinp.eof( ) ) break;
_exam1[_size] = sinp.readInt( );
_exam2[_size] = sinp.readInt( );
_size++;
}
System.out.println( );
System.out.println(“\tName\tAverage”);
for (int i = 0; i < _size; i++)
System.out.println(“\t” + _names[i] +
“\t\t” + (_exam1[i] + _exam2[i]) / 2);
}
}
What That Looks Like in Memory
…
[0]
Three arrays:
one of Strings,
two of ints
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
…
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
…
[0]
grades
[1]
[2]
[3]
[4]
[5]
Attributes:
Attributes:
_names
_names == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
_size
_size == …
…
Methods:
Methods:
void
void readAndAverage
readAndAverage (( ))
[6]
[7]
[8]
[9]
GradeBook
object
heap
10- 52
Arrays Can Contain Objects
 Arrays
can contain any kind of
data, not just integers and strings
 So
instead of building GradeBook
the way we did, let’s create a
Student class, and fill up the array
with Student objects
 Each
object includes names and
grades
10- 53
Class Student, for making
Student Objects
class Student {
can be omitted; Java will provide
private String _name;
a default constructor that does
private int _exam1, _exam2;
nothing if we left this out
public
public
public
public
public
public
public
public
}
Student ( ) { }
void setName (String s) { _name = s; }
void setExam1 (int n) { _exam1 = n; }
void setExam2 (int n) { _exam2 = n; }
String getName ( ) { return _name; }
int getExam1 ( ) { return _exam1; }
int getExam2 ( ) { return _exam2; }
int getAvg ( ) {return (_exam1+_exam2)/2; }
}
10- 54
class GradeBook {
private Student[ ] _students;
private int _size = 0;
public GradeBook (int number) {
_students = new Student[number];
}
}
A wrapper class
for an array of
objects
public void readAndAverage( ) {
SimpleInput sinp = new SimpleInput(System.in);
String nextname;
while ( true ) {
System.out.println(“Enter name and ” +
“two exam grades: ”);
nextname = sinp.readString( );
if ( sinp.eof( ) ) break;
_students[_size] = new Student( );
_students[_size].setName(nextname);
_students[_size].setExam1(sinp.readInt( ));
_students[_size].setExam2(sinp.readInt( ));
_size++;
}
System.out.println( );
System.out.println(“\tName\tAverage”);
for (int i = 0; i < _size; i++)
System.out.println( “\t” +
_students[i].getName( ) + “\t\t” +
_students[i].getAvg( ) );
}
What That Looks Like in Memory
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
Student
objects
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
[0]
[1]
[2]
[3]
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
[4]
[5]
[6]
Attributes:
Attributes:
_students
_students == …
…
_size
_size == …
…
Methods:
Methods:
void
void readAndAverage
readAndAverage (( ))
grades
Attributes:
Attributes:
_name
_name == …
…
_exam1
_exam1 == …
…
_exam2
_exam2 == …
…
Methods:
Methods:
void
void setName(String
setName(String s)
s)
String
String getName
getName (( ))
[7]
[8]
[9]
…
GradeBook
object
heap
10- 56