Transcript The Array Data Structure

Java the UML Way
http://www.tisip.no/JavaTheUmlWay/
Arrays of Primitive Data Types
The array data structure
Copying an array
The Month class
Sorting
Array as argument
Searching
The java.util.Arrays class
Two-dimensional arrays
More than two dimensions
versjon 2002-04-17
page 2-4
page 5-7
page 8
page 9-12
page 13
page 14-15
page 16
page 17-18
page 19-21
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9
Why Do We Need the Array Data Structure?
•
•
•
•
•
A data structure is a collection of
data that is stored in the internal
memory under one name.
An object is a data structure.
An array is a data structure where
all data belong to the same data
type.
Example: The precipitation data for
every day in a month.
How to declare the instance
variables?
private String monthName;
private int precipitation1;
private int precipitation2;
private int precipitation3;
private int precipitation4;
.....
private int precipitation31;
Month
monthName: String
precipitation[28..31]: int
getMaximum
getNoOfDryDays
getAverage
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 2
The Array Data Structure
• We declare an array:
– int[] march = new int[31];
length
int[ ] march = new int[31];
10 10 20
5
0
0
1
0
[0] [1] [2] [3] ............. [27] [28] [29] [30]
march
index
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 3
Using an Array
•
Every element is accessed by indexing:
– march[0] = 20;
– march[15] = 30;
– int sum = march[0] + march[1] + march[2];
•
•
•
•
The length of the array is given by the expression march.length.
First element has index no. 0, last element no. (length-1).
An invalid index throws an ArrayIndexOutOfBoundsException.
We should check an index value before using it:
– if (index >= 0 && index < march.length) number = march[index];
•
Summing up all precipitation in March:
int sumMars = 0;
for (int i = 0; i < march.length; i++) sumMars += march[i];
•
An array may be initialized in the declaration:
– int[] oneWeek = {4, 5, 6, 7, 1, 2, 3}; // the length becomes 7
•
If we do not initialize the array, all elements are automatically initialized to 0.
Solve all problems, page 244
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 4
Copying an Array
• What about using the assignment operator?
array1
array2
1
7
4
14
6
-6
int[] array1 = {1, 4, 6, -2};
int[] array2 = {7, 14, -6, 0};
-2
0
array1
array2
1
4
6
-2
7
14
-6
0
After the statement:
array2 = array1;
• This doesn't work…we get two references to the same array.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 5
An Array Has to be Copied Element by Element
Before copying:
Copying each element:
for (int i = 0; i < array1.length; i++) {
array1[i] = array2[i];
int[] array1 = {1, 4, 6, -2};
int[] array2 = {7, 14, -6, 0};
}
After copying:
array1
array2
1
7
4
14
6
-6
-2
array1
7 14
array2
7
-6
0
0
14
-6
0
Solve problem 1 page 246.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 6
System.arraycopy() may be Used for Copying Arrays
array1
1
4
6
-2
array2
7
14
-6
0
int[] array1 = {1, 4, 6, -2};
int[] array2 = {7, 14, -6, 0};
[0] [1] [2] [3]
After the statement:
System.arraycopy(array1, 1, array2, 2, 2);
array1
1
4
6
-2
array2
7
14
4
6
[0] [1] [2] [3]
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 7
The Month Class
Month
monthName: String
precipitation[28..31]: int
Show program listing 9.1 page 248-251.
getMaximum
getNoOfDryDays
getAverage
Solve problems 1 and 2, page 251.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 8
Sorting
• Examples:
– ranking the participants in a competition
– sorting names in a telephone directory
– ranking cities according to the price of local services.
• Distinguish between ascending sorts and descending sorts
• Assumptions:
– There is room in the internal memory for the whole array which will be
sorted
– The data belong to a primitive data type—in other words, numbers or
characters (the numeric characters ‘0’–‘9’ and the letters ‘a’–‘z’)
• A lot of different sorting algorithms.
• We'll look at ”Sorting by selection”.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 9
Sorting by Selection
before we begin
after first turn
for (start = 0; start < array.length; start++) {
find the index for the smallest element in
the interval [start, array.length - 1]
replace smallest element with the element
in the start position
}
ready
3
4 -5 13 10
0
8 -2
-5 4
3 13 10
0
8 -2
-5 -2
3 13 10
0
8
4
-5 -2
0 13 10
3
8
4
-5 -2
0 3 10
13
8
4
-5 -2
0 3 4
13
8
10
-5 -2
0 3 4
8
13
10
-5 -2
0 3 4
8
10
13
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 10
The sortIntegerArray() Method – a Class Method
package myLibrary;
public class Sort {
public static void sortIntegerArray(int[] array) {
for (int start = 0; start < array.length; start++) {
int smallestToNow = start;
for (int i = start + 1; i < array.length; i++) {
if (array[i] < array[smallestToNow]) smallestToNow = i;
}
int help = array[smallestToNow];
array[smallestToNow] = array[start];
array[start] = help;
}
}
/* This class consists of two more methods, see chapter 10. */
}
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 11
Using the sortIntegerArray() Method
import myLibrary.*;
class TestSort {
public static void main(String[] args) {
int[] test = {3, 4, -5, 13, 10, 0, 8, -2, 22, 15, 11, 9, 17};
Sort.sortIntegerArray(test);
System.out.println("Sorted array: ");
for (int i = 0; i < test.length; i++) System.out.print(test[i] + " ");
System.out.println();
}
}
If we want to sort decimal numerals,
we have to write a sorting method
where the parameter is of the double[] type
and the help variable is of the double type.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 12
Array as Argument
• The array name is a reference
• An array as argument means that we pass a reference to the method,
and the method works with the same array elements as the client:
testclient
Method invocation:
Sort.sortIntegerArray(test);
What’s happening behind
the scenes:
int[] arraysortIntegerArray = testclient
3
4
-5 13 ........
arraysortIntegerArray
Solve problem 3, page 254.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 13
Searching
• Searching in an array means finding the element or elements that
satisfy specific criteria.
• For example, we indicate a value and go to find the index number for
the element or elements that have this value.
• We also have to consider the possibility that this value may not be
found at all.
• Sometimes it’s enough to find one occurrence of the value; at other
times we have to find all occurrences.
• In program listing 9.1 there are two search examples:
– getNoOfDryDays()
– getDaysMax()
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 14
How to Program Searching?
• An example: Find the index for a day on which there was a specific
amount of precipitation:
public int getDay(int value) {
for (int i = 0; i < precipitation.length; i++) {
if (precipitation[i] == value) return i;
// value found
}
Check the index before it is used!
return -1; // value not found
(we use the fact that Java uses
}
• If we are not going to return the value:
short-circuit evaluation when
evaulating boolean expressions)
int dayNo = 0;
while (dayNo < precipitation.length && precipitation[dayNo] != value) dayNo++;
if (dayNo < precipitation.length) {
...do what should be done if the value is found...
} else {
...do what should be done if the value is not found..
}
Solve problem 1, page 256.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 15
The java.util.Arrays Class
•
•
•
•
Offers class methods for sorting and searching
Throws exceptions, see the online API-documentation
In the method heads below, datatype is any primitive data type
Sorting
– static void sort(datatype[] array)
– static void sort(datatype[] array, int fromIndex, int toIndex)
• Searching, the array is already sorted
– static int binarySearch(datatype[] array, datatype searchValue)
• Filling the whole array or a part of it:
– static void fill(datatype[] array, datatype value)
– static void fill(datatype[] array, int fromIndex, int toIndex, datatype value)
• Comparing arrays (true is returned if they have the same length and the
same contents)
– static boolean equals(datatype[] array1, datatype[] array2)
Solve problem 2 page 258.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 16
A Need for a Two-Dimensional Array
• Sales data for every day for one year (52 weeks, 5 days per week) can
be presented in the following manner:
day 0 day 1 day 2 day 3 day 4
week 0
week 1
week 2
week 3
week 4
week 5
......
week 51
100
230
120
200
200
210
150
160
180
210
300
400
300
450
Problem: Which services should an object
that holds this information, offer its clients?
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 17
A Two-Dimensional Array
int[ ][ ] sales = new int[4][5]; // 4 weeks, 5 days a week
sales[0]
sales[1]
sales[2]
sales[3]
0
100
230
120
300
1
200
200
210
310
2
150
160
180
250
3
210
300
400
240
4
300
450
120
200
sales[1][3]
sales[3][4]
•
•
•
A two-dimensional array has lines and columns
Every line is itself a one-dimensional array with names as follows:
sales[0], sales[1], sales[2], sales[3].
Examples:
–
–
–
sales[1][3] = 400;
int salget = sales[0][4];
int sum = sales[3][0] + sales[3][1];
Show program listing 9.3, pp. 260-262.
Solve problems 1 and 2, pp. 264-265.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 18
More Than Two Dimensions
Want sales data per salesperson:
sales[0][0][0]
week no
0
1
2
3
day no
0 1 2 3 4
200 200 450 200 600
320 450 240 220 760
180100
200200
160150
300210
450300
140 200 160 300 450
210230
210200
180160
400300
120450
150 210 180 400 120
310120
310210
250180
240400
200120
110 310 250 240 200
300 310 250 240 200
salesperson no 0
salesperson no 1
salesperson no 2
sales[2][2][4]
int[][][] sales = new int[3][4][5]
noOfSalespersons
noOfWeeks noOfDays
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 19
How to Handle the Three-Dimensional Array
•
How much has the salesperson with the index salespersonNo sold in the week
with index weekNo?
int sum = 0;
for (int i = 0; i < sales[salespersonNo][weekNo].length; i++) {
sum += sales[salespersonNo][weekNo][i];
}
•
How much has the salesperson with the index salespersonNo sold in total?
int sum = 0;
for (int weekNo = 0; weekNo < sales[salespersonNo].length; weekNo++) {
for (int dayNo = 0; dayNo < sales[salespersonNo][weekNo].length; dayNo++) {
sum += sales[salespersonNo][weekNo][dayNo];
}
}
•
What is the total sales?
int sum = 0;
for (int salespersonNo = 0; salespersonNo < sales.length; salespersonNo++) {
for (int weekNo = 0; weekNo < sales[salespersonNo].length; weekNo++) {
for (int dayNo = 0; dayNo < sales[salespersonNo][weekNo].length; dayNo++) {
sum += sales[salespersonNo][weekNo][dayNo];
}
}
}
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 20
Multidimensional Arrays aren’t Used Very Much in
Object-Oriented Programming
statistics
•
•
1995
1996
1997
January
January
January
February
February
February
March
March
March
December
December
December
Instead we make arrays of objects, where each object contains an array with
additional information directly linked to the array.
Multidimensional arrays are useful if we need to handle data in multiple
dimensions.
Only to be used in connection with the book "Java the UML Way", by Else Lervik and Vegard B. Havdal.
ISBN 0-470-84386-1, John Wiley & Sons Ltd 2002
The Research Foundation TISIP, http://tisip.no/engelsk/
Chapter 9, page 21