Transcript Week8

CS1101: Programming Methodology
http://www.comp.nus.edu.sg/~cs1101/
Week 8: Strings and Arrays
 Previous lecture:
 Chapter 7: Defining Your Own Classes – Part 2
 This week:
 Chapter 9: Characters and Strings
 Chapter 10: Arrays and Collections
 Next week:
 Chapter 10: Arrays and Collections (cont’d)
 Chapter 8: Exceptions
© CS1101 (AY2009-2010 Semester 1)
Week8 - 2
Chapter 9 Characters and Strings

Let’ go over Thomas Wu’s slides now…
© CS1101 (AY2009-2010 Semester 1)
Week8 - 3
Quizzes



Are 'A' and "A" the same thing? Why?
Can char be used in a switch statement? How about
a String object?
Show the results, or if it is illegal, how to correct it.
(ASCII value of 'a' is 97.)
1.
2.
3.
4.
5.
+
System.out.println('a' + "xyz");
System.out.println('a' + 123);
System.out.println('a' + 'b');
if ("a" < "b") ...
if ("abc" < "xx") ...
© CS1101 (AY2009-2010 Semester 1)
Week8 - 4
Do not overuse String

Some students like to use String to solve numerical
problems, because there are so many methods
available for String.





For example, given an integer, extract its individual digits.
No good: convert the integer to a string, use substring to extract
the individual characters, then convert each character to a digit.
Better: use division (/) and modulo (%), like what we did for
Matriculation check code.
Manipulating strings can use up a lot of space, due to
its immutability.
Strings are special. There are two ways to create a
String object: with or without using ‘new’ statement.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 5
Two ways of creating String objects
We can do this
because String
objects are
immutable.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 6
String: Effect of Immutability

Example 1:
String s = "abc";
s = s + "def";


A new string "abcdef" is created for s in the second
statement. (Hence, it uses more memory. What happens to
the memory space that stores "abc"?)
Example 2:
String s1 = "abc";
String s2 = "abc";
s1 = "xyz";


String s2 still refers to "abc". (Imagine the horror if this is not
so!)
Hence, String objects behave differently from other
objects or arrays.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 7
Exercise: Counting “the” (1/2)




Write a program Ch9CountThe.java to count the
number of times user entered the word “the”.
The program ends when the user enters an empty
string.
The word “the” may be entered with leading or/and
trailing spaces, and it may contain uppercase or
lowercase letter.
(This question is the same as question 1 in Week 9’s
discussion.)
© CS1101 (AY2009-2010 Semester 1)
Week8 - 8
Exercise: Counting “the” (2/2)

A sample run:


User’s inputs are shown in blue
Space is denoted by the  character
Enter a string:
Enter a string:
Enter a string:
Enter a string:
Enter a string:
Enter a string:
Number of times

tHe
quick

THE
thE
"the" appears: 3
Look up the String API page for appropriate String
methods to use.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 9
Take-home lab assignment #4


It has been released more than a week ago.
Deadline is Monday, 12 October 2009,
23:59hr.
Any questions?
© CS1101 (AY2009-2010 Semester 1)
Week8 - 10
Motivation (1/3)

Task: Find the minimum value of 3 integers
int min;
if ( (value1 <= value2) && (value1 <= value3) )
min = value1;
else if ( (value2 <= value1) && (value2 <= value3) )
min = value2;
else if ( (value3 <= value1) && (value3 <= value2) )
min = value3;

What if the list is big?

Code will be longer – the logical expression in each ‘if’
statement will be longer and more complex.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 11
Motivation (2/3)

Consider this algorithm
int min = value1;
if (value2 < min)
min = value2;
if (value3 < min)
min = value3;

What if the list is big?

Code will still be longer, but if we make use of the regular
pattern and the array structure for the data, we can ‘roll’ the
if statements into a loop.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 12
Motivation (3/3)

Using the array structure
int min = value[0];
if (value[1] < min)
min = value[1];
if (value[2] < min)
min = value[2];

Rolling into a loop using array subscript/index:
int min = value[0];
for (int k = 1; k < 3; k++) {
if (value[k] < min)
min = value[k];
}

The above code can be easily modified for a bigger
list.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 13
Chapter 10 Arrays and Collections
(1/2)

In computer science, we deal with very large amount
of data




Eg: 3000 integers, 265 days, 1 million real numbers.
Do you want to create so many variables in your program?
If the data are homogeneous (of the same type), we
can organise them into a single collection (we
normally call it a list).
Array is an implementation of a list. It is an indexed
collection of homogeneous data.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 14
Chapter 10 Arrays and Collections
(2/2)



We will cover up to one-dimensional arrays today,
and continue from two-dimensional arrays next week.
The syntax for array is very simple, yet learning it
allows us to solve many interesting problems.
Let’ go over Thomas Wu’s slides now…
© CS1101 (AY2009-2010 Semester 1)
Week8 - 15
Array Declaration Syntax
 Array declaration syntax:
<element-type>[] <array-variable>;
Example: double[] values;
 Alternative syntax:
<element-type> <array-variable>[];
Example: double values[];
 I prefer the first one, it’s more readable and
meaningful. The second form is more
commonly used by C/C++ programmers.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 16
Basic Terminology
 An array is a form of ordered list.
 A list is composed of elements.
 List is homogeneous – elements are of the



same base type.
Elements in a list have a common name.
The list as a whole is referenced through the
common name.
Elements are referenced by subscripting
(indexing) the common name.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 17
Java Array Features
 Subscripts/indices are denoted as expressions within




square brackets [ ]
Size of array (number of elements) can be specified
at run time
Index type is integer and index range must be 0 … n1 where n is the array size
Automatic bounds checking
Array is an object

Has features common to all other objects
© CS1101 (AY2009-2010 Semester 1)
Week8 - 18
Common mistake: length() vs length

Do not mix up the two

The length of a String object str is obtained by
calling the String method length()


Example: str.length()
The length (size) of an array arr is stored in its
data member length

Example: arr.length
© CS1101 (AY2009-2010 Semester 1)
Week8 - 19
Classic Array Problems
 Compute statistics (sum, mean, standard




deviation, etc.) of the values in an numeric
array.
Find the maximum (or minimum) value in an
array.
Search for a value in an array.
Sort the values in an array.
Others
© CS1101 (AY2009-2010 Semester 1)
Week8 - 20
Loading an Array
 Before we solve a problem involving array, we need
to first load values into the array!
 If you know the values before-hand, use array
element initialization
 Eg: int[] numbers = { 3, 7, -12, 8, 7 };
 Slide 9 of Chapter 10
 If not, you need to read the values from the user
 Use a loop to read in the values
 Slides 6-7 and 16 of Chapter 10
 (If the array is large, the amount of data will be huge.
We may need a file to store the data. We will learn
how to read data from a file some other time.)
© CS1101 (AY2009-2010 Semester 1)
Week8 - 21
Exercise 1: Summing an Array
 Write a program SumArray.java to compute the sum
of all the values in an array containing type double
values. Display the sum in 3 decimal places.
 Let’s do it into 2 phases: load the array with values
first, then compute the sum. (Instead of accumulating
the sum as we load the array.)
Size of array: 10
Enter 10 values: 5.1 16 3.2 1.8 -4 12.3 8 3.3 -2 9.1
The sum is 52.800
 Download SumArray.java from course website,
“Resources – Lectures” page.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 22
Exercise 2: Finding Maximum
 Write a program FindMax.java to find the largest
value in an integer array. (Assume there is at least
one element in the array.)
Size of array: 5
Enter 5 values: 10 -20 43 79 8
The largest value is 79
 Take home exercise: What if you want to report the
index of the largest value, instead of the value itself?
(This problem is not well-defined! Why?)
Size of array: 5
Enter 5 values: 10 -20 43 79 8
The largest value is at index 3
© CS1101 (AY2009-2010 Semester 1)
Week8 - 23
Very Common Mistake #1

Array Index Out of Range

Beware of ArrayIndexOutOfBoundsException.
public static void main(String[] args) {
int numbers = new int[10];
. . .
for (int i=1; i<=numbers.length; i++)
System.out.println(numbers[i]);
}
© CS1101 (AY2009-2010 Semester 1)
Week8 - 24
Modular Programming Revisit


“Modularize” SumArray.java and
FindMax.java so that the computation of sum
or maximum is performed in a method.
Call your new programs
SumArrayModular.java and
FindMaxModular.java.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 25
Exercise 3: Coin Change



Download the file Ch3CoinChange.java from
the course website, “Resources – Lectures”.
Rewrite it using an array of coin
denominations (int[] coins). Name your
program Ch10CoinChange.java.
Modularize your program by writing a method
computeCoins().


What is its return type?
Does it have any argument(s)? If so, what is/are
the type(s) of its argument(s)?
© CS1101 (AY2009-2010 Semester 1)
Week8 - 26
Exercise 4: Array of Points (Take-home)
(1/2)



Write a program Ch10PointArray.java to
create an array of Point objects, and find out
which point in the array is furthest from the
origin.
If there are more than one such furthest point,
output the smallest index among them.
You may assume that the array contains at
least one point.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 27
Exercise 4: Array of Points (Take-home)
(2/2)

Sample output:
Enter number of points: 5
Enter coordinates for point #0: -2 -2
Enter coordinates for point #1: 1 4
Enter coordinates for point #2: 4 -3
Enter coordinates for point #3: 0 5
Enter coordinates for point #4: -1 1
The furthest point is at index 2
© CS1101 (AY2009-2010 Semester 1)
Week8 - 28
Very Common Mistake #2 (1/2)


When you have an array of objects, it’s very
common to forget to instantiate the array’s
objects.
Programmers often instantiate the array itself
and then think they’re done – that leads to
java.lang.NullPointerException.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 29
Very Common Mistake #2 (2/2)
Point[] array = new Point[3];
array
for (int i=0; i<array.length; i++) {
array[i].setLocation(1,2);
null
null
}
null
There are no objects referred to by
array[0], array[1], and array[2]!
Corrected code:
array
x
01
y
02
Point[] array = new Point[3];
for (int i=0; i<array.length; i++) {
array[i] = new Point();
x
01
y
02
array[i].setLocation(1,2);
}
© CS1101 (AY2009-2010 Semester 1)
x
01
y
02
Week8 - 30
Method main() (1/2)


Now that we have learned array, let’s check out the
main() method.
Usual header for main() method:
public static void main(String[] args)


args is an array of String objects.
Download Ch10MainDemo.java:
public class Ch10MainDemo {
public static void main(String[] args) {
for (int i=0; i<args.length; i++)
System.out.println("args[" + i + "]: " + args[i]);
}
}
© CS1101 (AY2009-2010 Semester 1)
Week8 - 31
Method main() (2/2)

This allows user to specify command line
arguments when executing the program.
java Ch10MainDemo 10 ABC-D hello "Ice cream"

Output:
args[0]:
args[1]:
args[2]:
args[3]:
© CS1101 (AY2009-2010 Semester 1)
10
ABC-D
hello
Ice cream
Week8 - 32
Summary for Today

Characters and Strings



More String methods
Patterns (regular expressions)
Arrays



Syntax of one-dimensional array
Creating and using an array
Passing array into a method
© CS1101 (AY2009-2010 Semester 1)
Week8 - 33
Announcements/Things-to-do (1/2)

Complete the following


Take-home lab #4


Ch10PointArray.java
Deadline: 12 October 2009, Monday, 23:59hr
To prepare for next lecture



We will continue with 2-dimensional arrays and
ArrayList next week.
Read Chapters 10 and 8 and their PowerPoint
files before you come for lecture.
We will skip Map for Chapter 10, and Assertions
for Chapter 8.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 34
Announcements/Things-to-do (2/2)

Sit-in Lab #2





To be conducted during this week’s discussion
session.
Please be punctual.
Make-up lab will only be allowed if you miss the lab
with valid reason and proof.
Topics tested include everything up to Chapter 7.
Sit-in lab #2 constitute 5% of your final grade.
© CS1101 (AY2009-2010 Semester 1)
Week8 - 35
End of File
© CS1101 (AY2009-2010 Semester 1)
Week8 - 36