Transcript Arrays

• Text Book: M. T. Goodrich and R. Tamassia, "Data Structures
and Algorithms in Java," 4th edition, 2006, Wiley & Sons, Inc., ISBN
978-0471738848.
Basic Definitions
• Data Structures:
A data structure is a systematic way of
organizing and accessing data. Or, It’s the
logical relationship between data elements.
• Types of Data Structures:
- Linear D.S., such as arrays, stacks, queues.
- Non-linear D.S., such as tree.
• Arrays:
An array is a numbered (indexed) collection of
variables, all of the same type.
• Storage Structure:
It is the physical (actual) representation of data
elements in storage (memory).
• Types of Storage Structures:
1- Sequential S.S.
(Suitable for storage of static D.S. such as
arrays)
2- Linked S.S.
(Suitable for storage of dynamic D.S.)
Object Oriented Approach
One of the main ideas of the objectoriented approach is that: data should
be presented as being encapsulated
with methods (functions) that access
and modify data.
ADT (Abstract Data Type):
It is a mathematical model of a data structure that specifies
the following:
- the Type of data stored,
- the Operations performed (supported) on
them, and
- the Types of Parameters of these operations.
An ADT is modeled in Java by a class.
Abstraction:
An ADT specifies what each operation does, but not how
it does it.
• Classes:
A class defines the data being stored and operations supported
by the objects.
• Objects:
An object is an instance of the class.
Objects in Java: store data and provide methods for accessing
and modifying this data.
• Interfaces:
An interface is simply a list of method declarations, where
each method has an empty body.
Unlike an interface, classes specify how the operations are
performed in the body of each method.
• Algorithm
An algorithm is a step-by-step procedure for performing
some task in a finite amount of time.
• Pseudo Code
An algorithm is written (expressed) in a mixture of Natural
languages and High-level programming languages, this is
called pseudo code.
• Program
A program is the implementation (translation) of an algorithm
in some high-level programming language.
1.5. Arrays
• Array: is a numbered collection of
•
•
variables, all of the same type of data, or
it’s a set of indexed variables.
Arrays are special kinds of objects, so we
can use new operator to create a new
instance of an array.
Cells: each variable or cell in an array has
an index, which uniquely refers to the value
stored in that cell. Cells of an array are
numbered 0, 1, 2, …. etc.
Use of Arrays:
• We use arrays to store a numbered group of related
•
•
objects.
Example 1: To store top ten scores of a game.
Instead of using a different single variable to store
each score, we use a single object to store all group of
scores, and each score will be referred to using and
index, or subscript.
Example 2: To store medical information system of
patients currently assigned to beds in a certain
hospital. Instead of using 200 different variables, we
use one group and refer to each patient’s information
by an index.
Arrays: Declaration
• An array stores multiple values of the same
type.
• If the type is a primitive type, each element
contains one value of the declared type.
boolean[] flags; //declare flags as a Boolean array
(object)
Here, no memory space is allocated for storing object
flags.
flags is a name (or reference) to an array of integers.
Memory Allocation for Arrays
flags = new boolean[20]; // Allocates an array flags in
memory
flags = new boolean[10]; // now flags is reference to
another array
int[] grades = new int[12]; // declare variable grades; create
an array; make grades a
reference of this array
int grades2[];
// a less readable format
Arrays: Elements
• Refer to particular element in the array by position
number (called index)
int[] grades = new int[12];
grades[2] = 10;
• The index starts from 0; thus the index value must be
•
between 0 to N-1, where N is the length of the array
For example, for the preceding array grades, it can be
indexed only using the numbers 0 to 11
Array: An Array of Values
int[] grades = new int[12];
grades[0] = -45;
…
grades[11] = -78;
grades
position number (index or
subscript) of the element
within array grades
A 12-element array of values.
grades[ 0 ]
-45
grades[ 1 ]
6
grades[ 2 ]
0
grades[ 3 ]
72
grades[ 4 ]
1543
grades[ 5 ]
-89
grades[ 6 ]
0
grades[ 7 ]
62
grades[ 8]
-3
grades[ 9 ]
1
grades[ 10 ]
6453
grades[ 11 ]
-78
Arrays: Declaration
• An array can also store multiple objects: each
element of the array is a reference to an object
of the declared type
Month[] months;
months = new Month[12];
String[] codes = new String[26];
Array: An Array of Objects
Month[] months;
months = new Month[12];
for (int i = 0; i < 12; i++)
months[i] = new Month(i+1,2005);
months
position number (index
or subscript) of the
element within array
months
A 12-element array of Month objects
months[ 0 ]
ref to obj 0
months[ 1 ]
ref to obj 1
months[ 2 ]
ref to obj 2
months[ 3 ]
ref to obj 3
months[ 4 ]
ref to obj 4
months[ 5 ]
ref to obj 5
months[ 6 ]
ref to obj 6
months[ 7 ]
ref to obj 7
months[ 8]
ref to obj 8
months[ 9 ]
ref to obj 9
months[ 10 ]
ref to obj 10
months[ 11 ]
ref to obj 11
Shortcut: Array Initializer List
• An initializer list can be used to instantiate and initialize an
•
array in one step
The values are delimited by braces and separated by commas
– allocate space for the array – number of elements in initializer
list determines the size of array
– elements in array are initialized with the values in the initializer
list
• The new operator is not used
Examples:
int[] units = {147, 323, 89, 933, 540};
char[] letterGrades = {'A', 'B', 'C', 'D', 'F'};
String[] wordList = {“cs112“, “computer", “elevision"};
Month[] longMonths = {new Month(1, 2005), new Month(3, 2005),
new Month(5, 2005), new Month(7, 2005), new Month(8, 2005),
new Month(10, 2005), new Month(12, 2005) };
Shortcut: Enumerate Array Elements
• There is a special for statement to
enumerate array elements:
Example:
int[] primes = {2, 3, 5, 7, 11};
for (int i : primes)
System.out.println ( i + “ “);
Arrays as Objects
• In Java, an array is considered as an
object
Implication:
– has attributes: e.g., the length attribute.
– parameter passing will be the same as object.
– Array name is a reference to the place of
memory in which the array is stored.
Array: length
• Each array has a public constant called length
that stores the size of the array
– once an array is created, it has a fixed size
– we will see ArrayList, a dynamic array next class.
• It is referenced using the array name (just like
•
any other object):
grades.length
Note that length holds the number of elements,
not the largest index, e.g.
for (int index=0; index < grades.length; index++)
grades[index] = scan.nextInt();
21
Arrays as Parameters
• An entire array can be passed to a method as a
parameter:
– like any other object, the reference to the array is passed,
making the formal and actual parameters aliases of each
other.
– changing an array element in the method changes the
original.
• An array element can be passed to a method as well,
and follow the parameter passing rules of that
element's type
Calling a Method: Array Reference
• Each time a method is called, the actual arguments in the invocation
are copied into the formal arguments
– if a value type, then it is the value that is copied
– if a reference type, then it is the reference that is copied
• The formal argument and the actual argument are different variables,
with different memory locations.
int[] array = {1, 2, 3};
doubleArray( array );
static void doubleArray (int[] array)
array
12
42
63
array
{
for (int i = 0; i < array.length; i++) i
array[i] *= 2;
array = new int[ ] {2, 4, 6, 8};
}
2
4
6
8
Example: Using the Elements
of an Array as Counters
• Use array elements to keep track of number of
occurrences of different values
– create an array with size of the number of possible
values
– each element of the array keeps track of the number
of occurrences of one value
– when a possibility occurs, increase the array element
by one
• may need to map from value to index
Example: Using the Elements
of an Array as Counters
• Read a sequence of integers between 1 to 10 until user
inputs 0; keep track of number of occurrences of 1 to
10:
int[] counters = new int[10];
int num;
while ( (num=scan.nextInt()) != 0)
counters[num-1]++;
• Count the number of lower-case characters in a line:
int[] counters = new int[26];
String line = scan.nextLine();
for (int i = 0; i < line.length(); i++) {
char ch = line.charAt(i);
if (‘a’ <= ch && ch <= ‘z’)
counters[ch-’a’]++;
Cloning an Array
• double[ ] a;
• double[ ] b;
a = new double[10]; // Allocates an array flags in memory
b = a;
// here both a and b refer to the same array
b[3] = 5;
// this is equivalent to setting a[3] to 5
•
If instead, we want to create an exact copy of the array, a ,
and assign the array variable b to this copy of array a, we
write:
b = a.clone();
// copies all cells of a into a new array and
assigns b to point to that array
b[3] = 5;
// the new copied array will have its cell at
index 3 assigned the value 5, but the cell
a[3] doesn’t change
Array Initialization
• Arrays of Basic Types (primitive
data types) are initialized to
zeros.
• Arrays of Objects are initialized to
null references.
Out of Bounds Error
• An attempt to access an array element
indexed by a number outside the range 0
and a.lenght – 1, such a reference is said
to be out-of-bounds error condition
(exception).
3.1. Using Arrays
• Arrays can be used to store high score
entries for a video game.
• In this case, we use an array of objects,
each contains two fields: score and name.
• Initially, this array stores only null entries
(references).
• As users this game, we fill array cells with
references to new objects.
Methods for Updating Arrays
• We will have to define methods for updating
entries of arrays.
1. Insertion
One of the most common updates we might
need to apply to arrays is to add a new game
entry.
add(e): Inserts game entry e into the collection of high
scores. If the array is full, e is added only if its score is
higher than the lowest score in the set, and in this case, e
replaces the entry with the lowest score.
The main challenge in insertion is to make
room for e. see code fragment 3.3.
2. Deletion
We must define a method that lets us remove a game
entry from the array. This means to delete a reference
to a game entry object from array entries.
remove(e):
Removes and returns the entry e at
index i in the array. If index i is outside the bounds of
array entries, this method throws an exception,
otherwise, object at index i will be removed, and all
following objects will be “moved over” to fill the empty
cell.
We start from index i and move all references at
indices higher than i one cell to left, code 3.4.
3. Sorting an Array
Here, we start with an array of objects
that are out of order and we need to put
them in order, which is known as the
sorting problem.
• Simple Insertion Sort Algorithm
Algorithm InsertioSort(A):
Input: An array A of n comparable elements.
Output: The array A with elements rearranged in
ascending order
for i ← 1 to n-1 do
Insert A[i] at its proper location in A[0], A[1], …, A[i-1]
High-level description of Insertion Sort Algorithm
34
Detail of Insertion Sort
Algorithm InsertioSort(A):
Input: An array A of n comparable elements.
Output: The array A with elements rearranged in
ascending order
for i ← 1 to n-1 do
cur ← A[i]
j ← i-1
while j ≥ 0 and A[j] > cur do
A[j+1] ← A[j]
j ← j-1
A[j+1] ← cur {cur is now the right place}
Intermediate-level description of InsertionSort Algorithm
Some Simple Methods of java.util.Arrays
equals(A, B): Returns true if and only if the array A and the
array B are equal.
• they have the same number of elements
• every corresponding pair of elements in the two arrays are equal.
fill(A,x): Stores element x into every cell of array A.
sort(A): Sorts the array A using the natural ordering of its
elements.
toString(A): Returns a String representation of the array A.
For example, the following string would be returned by the method
toString called on an array of integers A = [4,5,2,3,5,7,10]:
[4, 5, 2, 3, 5, 7, 10]
36
Simple Cryptography with Strings and
Character Arrays
new String(A) create an object of class String from
a character array A
For example, the string we would construct from
the array A = [a, c, a, t] is acat.
S.toCharArray() create a character array
representation of S
For example, if we call toCharArray on the string
adog, we would get the array B = [a, d, o, g].
37
Two-Dimensional Arrays
• A one-dimensional array stores a simple list of values.
• A two-dimensional array can be thought of as a table of values,
with rows and columns.
• A two-dimensional array element is referenced using two
index values , say i and j. The first index usually refers to a
row number and the second to a column number.
• To be precise, a two-dimensional array in Java is an array of
arrays, that is an array with each of its cells being another
array.
• Array is sometimes also called a matrix
38
Two-Dimensional Arrays
Column 0
Column 1
Column 2
Column 3
Row 0
a[0][0]
a[0][1]
a[0][2]
a[0][3]
Row 1
a[1][0]
a[1][1]
a[1][2]
a[1][3]
Row 2
a[2][0]
a [2][1] a[2][2]
a[2][3]
Column index (or subscript)
Row index (or subscript)
Array name
A rectangle two-dimensional array with three rows and four columns.
Two-dimensional Arrays: Initializer
• An initializer list can be used to create and set
up a two-dimensional array.
• Each element in the list is itself an initializer
list.
• Each array dimension has its own length
constant.
40
Initializer: Example
public class Test2DArray
{
public static void main(String[] args)
{
int[][] days = { {1, 2, 3, 4},
{5, 6, 7},
{8, 9},
{0} };
for (int i = 0; i < days.length; i++)
{
for (int j = 0; j < days[i].length; j++)
System.out.print( days[i][j] );
System.out.println ();
}
}
}
2D arrays: Declaration
• In Java, we declare a 2D array as follows:
•
int[][] Y = new int[8][10]
– 2D array having 8 rows and 10 columns.
– That is, Y is an array of length 8 such that each element of Y is an
array of length 10 of integers.
42
Tic-Tac-Toe
• tic-tac-toe is a game played in a three-by-three board.
• Two players—X and O—alternate in placing their respective marks in the
cells of this board, starting with player X. If either player succeeds in getting
three of his or her marks in a row, column, or diagonal, then that player wins.
• 1 indicating an X, and −1 indicating O.
• This encoding allows us to have a simple way of testing if a given board
configuration is a win for X or O, namely, if the values of a row, column, or
diagonal add up to −3 or 3.
43
Multidimensional Arrays
• An array can have as many dimensions as
•
•
•
needed, creating a multidimensional array.
Each dimension subdivides the previous one
into the specified number of elements.
Each array dimension has its own length
constant.
Because each dimension is an array of array
references, the arrays within one dimension
could be of different lengths.
44