7. Arrays and Vectors
To be able to use
arrays and vectors to
collect objects
To implement partially
filled arrays
To be able to pass
arrays to methods
To learn about
common array
algorithms
To build classes
containing arrays and
vectors
To learn how to use
two-dimensional
arrays
Arrays
An array is a collection
of data items of the
same type.
Every element of the
collection can be
accessed separately
by using index.
In Java, array indexing
starts from 0.
Array can be
constructed using
double[ ] data = new
double[10];
An Array Reference
and an Array
Using Arrays to Store
Data
To access the fifth
element in an array,
we use
data[4] = 35.5;
System.out.println
(“The price = ” + data
[4]);
sum = sum + data[4];
double[ ] data; // error :
not initialized
data[0] = 10.5; // assign
a value to data[0]
Bounds Error
double[ ] data = new
double[10];
// we can access data
[0], data[1], … data[9]
data[10] = 35.5; //
cause
ArrayIndexOutOfBound
sException
Size of the array:
arrayRefName.length
double[ ] data = new
double[10];
for (int i = 0; i <
data.length; i++)
if (data[i] < lowest)
lowest = data[i];
Don’t combine array
access and index
increment
x = v[i++]; => x = v[i]; i+
+;
Array Initialization
int[] primes = new int
[5];
primes[0] = 2; primes
[1] = 3; primes[2] = 5;
primes[3] = 7; primes
[4] = 11;
// better to use the
following
int[ ] primes = {2, 3, 5,
7, 11};
Copying Arrays
Reference
double[] data = new
double[10];
// … fill array
double[] prices;
prices = data; // copy
reference of array
Make a true copy of
array
double[] prices = new
double[data.length];
for (int j = 0; j <
data.length; j++)
prices[j] = data[j];
Better if we use the
static
System.arrayCopy
method
System.arrayCopy
(from, fromStart, to,
toStart, count);
System.arrayCopy
(data, 0, prices, 0,
data.length);
Partially Filled Arrays
When we need to set
the size of an array
before you know how
many elements there
are, we can make an
array that is large
enough and partially fill
it.
final int DATA_LENGTH =
1000;
double[] data = new
double[DATA_LENGTH];
then keep a variable
that tells how many
elements are actually
used
int dataSize = 0; // for
collect size of array
and increment this
variable every time
data is added to the
array
double price =
console.readDouble();
data[dataSize] = price;
dataSize++;
Remember! Not to
access the data over
the datasize
for (int j=0; j <
dataSize; j++) // not
data.length
System.out.println(data
[j]);
and not to overfill the
array
if (dataSize <
data.length) // OK
{ data[dataSize] =
price;
dataSize++;
}
else // Array is full
{ System.out.println
(“Sorry, array is full”);
}
If the array fills up, we
can create a new,
larger array; copy all
elements into the new
array; and then attach
the new array to the
old array variable.
if (dataSize >= data.length)
{ //
double[] newData = new
double[2 * data.length];
// copy data
System.arrayCopy(data,
0, newData, 0,
data.length);
//create new reference for
"new data" ่
data = newData;
}
Suppose we want to
write a program that
reads a set of prices
offered by 10 vendors
for a particular product
and then prints them,
marking the lowest
one.
public class BestPrice
{ public static void
main(String[] args)
{ final int DATA_LENGTH =
1000;
double[] data = new
double[DATA_LENGTH];
int dataSize = 0;
// read data
ConsoleReader
console = new
ConsoleReader
(System.in);
boolean done = false;
while (!done)
{ System.out.println
("Enter price, 0 to
quit:");
double price =
console.readDouble();
if (price == 0) // end of
input
done = true;
else if (dataSize <
data.length)
{ // add price to data
array
data[dataSize] = price;
dataSize++;
}
else // array is full
{ System.out.println
("Sorry, the array is
full.");
done = true;
}
}
// compute lowest
price
if (dataSize == 0)
return; // no data
double lowest = data
[0];
for (int i = 1; i <
dataSize; i++)
if (data[i] < lowest)
lowest = data[i];
// print out prices,
marking the lowest
one
for (int i = 0; i <
dataSize; i++)
{ System.out.print(data
[i]);
if (data[i] == lowest)
System.out.print(" <--
lowest price");
System.out.println();
}
}
}
Array Parameters and
Return Values
The method to
compute the average
of an array of floating-
point numbers
public static double
average(double[] data)
{ if (data.length == 0)
return 0;
double sum = 0;
for (int j = 0; j <
data.length; j++)
sum = sum + data[j];
return sum /
data.length;
}
double[] prices =
{ 10.5, 24.5, 30.5, 10.0,
50.4 };
System.out.println
(“Price average = ” +
average(prices));
Array Parameters
When an array is
passed to a method,
the array parameter
contains a copy of the
reference to the
argument array.
A method can modify
the entries of any array
that you pass to it.
The method can return
an array if the returning
result consists of a
collection of values of
the same type.
A method can return an
array
public static int[]
randomData(int length,
int n)
{ Random generator =
new Random();
int[] data = new int
[length];
for (int j = 0; j <
data.length; j++)
data[j] =
generator.nextInt(n);
return data;
}
Array Algorithms
Finding a Value: want
to know the price of
first product that has
price lower or equal
1000
double [] prices;
double targetPrice = 1000;
int j = 0;
boolean found = false;
while (j < prices.length
&& !found)
{ if (prices[j] <=
targetPrice)
found = true;
else
j++;
}
if (found)
System.out.println(“Item”
+ j + “ has a price of” +
prices[j]);
Counting: want to
know the number of
product that has price
lower or equal 1000
double [] prices;
double targetPrice = 1000;
int count = 0;
for (int j = 0; j <
prices.length; j++)
{ if (prices[j] <=
targetPrice)
count++;
}
System.out.println(count
+ “ computers.”);
Removing an Element
from an Unordered
Array
If we want to remove
an element from an
unordered array, we
simply overwrite the
element to be
removed with the last
element of the array.
However, an array
cannot be shrunk to
get rid of the last
element, so we have
to used the technique
of a partially filled
array.
Removing an Element :
Array not sorted
public class Remove1
{ public static void
main(String[] args)
{ ConsoleReader
console = new
ConsoleReader
(System.in);
String[] staff = new
String[5];
staff[0] = "Harry"; staff
[1] = "Romeo"; staff[2]
= "Dick";
staff[3] = "Juliet"; staff
[4] = "Tom";
int staffSize =
staff.length;
print(staff, staffSize);
System.out.println
("Remove which
element? (0 - 4)");
int pos =
console.readInt();
// overwrite the
removed element with
the last element
staff[pos] = staff
[staffSize - 1];
staffSize--;
print(staff, staffSize);
}
/**
Prints an array of
strings
@param s the string
array
@param sSize the
number of strings in
the array
*/
public static void print
(String[] s, int sSize)
{ for (int i = 0; i < sSize;
i++)
System.out.println(i + ":
" + s[i]);
}
}
Remove an Element
from an Ordered Array
After removing an
element, we have to
move all elements
beyond the element to
be removed by one
slot.
Removing from an
Ordered Array
public class Remove2
{ public static void
main(String[] args)
{ ...
int staffSize =
staff.length;
print(staff, staffSize);
System.out.println
("Remove which
element? (0 - 4)");
int pos =
console.readInt();
// shift all elements
above pos down
for (int i = pos; i <
staffSize - 1; i++)
staff[i] = staff[i + 1];
staffSize--;
print(staff, staffSize);
}
}
Inserting an Element
Suppose we want to
insert an element in
the middle of an array,
we must move all
elements beyond the
insertion location by
one slot.
When we insert an
element, we start
moving at the end of
an array, move that
element, then go to
the one before it. This
operation is in reverse
order from removing
operation.
public class Insert
{ public static void
main(String[] args)
{ String[] staff = new
String[6];
staff[0] = “Mary”;
staff[1] = “Ben”;
staff[2] = “Sandy”;
staff[3] = “Janet”;
staff[4] = “Peter”;
int staffSize =
staff.length - 1;
System.out.print
("Insert before which
element? (0 - 4) ");
int pos =
console.readInt();
// shift all element
after pos up by one
for (int i = staffSize; i >
pos; i--)
staff[i] = staff[i - 1];
// insert new element
into freed slot
staff[pos] = "New,
Nina";
staffSize++;
print(staff, staffSize);
}
Parallel Arrays, Arrays
of Objects
and Array as Object
Data
When we want to
analyze a data set that
contains more than
one data item, such as
a data set that contains
the names, prices, and
quality of a collection
of products.
We want to look for
products that give
good quality at low
price.
The problem with this
program is that it
contains three arrays
of the same length.
Bestdata.java
public class BestData
{ public static void
main(String[] args)
{ final int DATA_MAX =
500;
String[] name = new
String[DATA_MAX];
double[] price = new
double[DATA_MAX];
int[] score = new int
[DATA_MAX];
int Size = 0;
// read data from
console
ConsoleReader
console = new
ConsoleReader
(System.in);
Boolean done = false;
while (!done)
{ System.out.println
(“Enter name or leave
blank when done: ”);
String inLine =
console.readLine();
if (inLine == null ||
inLine.equals(“ ”))
done = true;
else if (Size < DATA_
MAX)
{ name[Size] = inLine;
System.out.println
(“Enter price: “);
inLine =
console.readLine();
price[Size] =
Double.parseDouble
(inLine);
System.out.println
(“Enter score: “);
inLine =
console.readLine();
score[Size] =
Integer.parseInt
(inLine);
Size++;
}
else
{ System.out.println
(“Sorry, the array is
full. “);
done = true;
}
}
// compute best buy
if (Size == 0) return; //
no data
double best = score[0]
/ price[0];
for (int j = 0; j < Size; j+
+)
if (score[j] / price[j] >
best)
best = score[j] / price
[j];
final int COLUMN_WIDTH
= 30;
for (int j = 0; j < Size; j+
+)
{ System.out.print
(name[j]);
int pad = COLUMN_
WIDTH - name[j].length();
for (int k = 1; k < = pad; k+
+)
System.out.print(“ “);
System.out.print(“ $” +
price[j] +“ score = “ +
score[j]);
if (score[j] / price[j] ==
best)
System.out.print(“ <--
best buy “);
System.out.println();
}
}
}
Parallel Arrays
The problem with
Bestdata.java is that it
contains three parallel
arrays namely name[j],
price[j], and score[].
We must ensure that
the arrays always have
the same length and
that each slice is filled
with values that
actually belong
together.
We can solve this
problem by turning this
concept into class.
Product.java
class Product
{
private String name;
private double price;
private int score;
public Product(String n,
double p, int s)
{ name = n;
price = p;
score = s;
}
public String getName
()
{ return name;
}
public double getPrice
()
{ return price;
}
public int getScore()
{ return score;
}
}
Bestproduct.java
public class
BestProduct
{ public static void
main(String[] args)
{ final int DATA_MAX =
500;
Product[] data = new
Product[DATA_MAX];
int Size = 0;
// read data from
console
ConsoleReader
console = new
ConsoleReader
(System.in);
Boolean done = false;
while (!done)
{ Product p =
readProduct(console);
if (p == null)
done = true;
else if (Size < DATA_
MAX)
{ data[Size] = p;
Size++;
}
else
{
System.out.println
(“Sorry, the array is
full.”);
done = true;
}
}
// compute best buy
if (Size == 0) return; //
no data
double best = data[0]
.getScore() / data[0]
.getPrice();
for (int j = 1; j < Size; j+
+)
{ double ratio = data[j]
.getScore() / data[j]
.getPrice();
if (ratio > best)
best = ratio;
}
// print out data
for (int j = 0; j < Size; j+
+)
{ printProduct(data[j]);
if (data[j].getScore() /
data[j].getPrice() ==
best)
System.out.print(“ <--
best buy “);
}
}
public static Product
readProduct
(ConsoleReader in)
{ System.out.println
(“Enter name or leave
blank when done:”);
String name =
in.readLine();
if (name == null ||
name.equals(“ “))
return null;
System.out.println
(“Enter price: “);
String inLine =
in.readLine();
double price =
Double.parseDouble
(inLine);
System.out.println
(“Enter score: “);
inLine = in.readLine();
int score =
Integer.parseInt
(inLine);
return new Product
(name, price, score);
}
public static void
printProduct(Product p)
{ final int WIDTH = 30;
System.out.print
(p.getName());
int pad = WIDTH –
p.getName().length;
for (int j = 1; j <= pad; j+
+)
System.out.print(“ “);
System.out.print(“ $” +
p.getPrice() + “ score =
“ +
p.getScore());
}
}
Example:
PolygonTest.java
Arrays as Object Data
import
java.applet.Applet;
import
java.awt.Graphics;
import
java.awt.Graphics2D;
import
java.awt.geom.Line2D;
import
java.awt.geom,Point2D
;
public class
PolygonTest extends
Applet
{ public void paint
(Graphics g)
{ Graphics2D g2 =
(Grahpics2D) g;
Polygon triangle = new
Polygon(3);
triangle.add(new
Point2D.Double(40, 40)
);
triangle.add(new
Point2D.Double(120,
160));
triangle.add( new
Point2D.Double(20,
120));
double x = 200;
double y = 200;
double r = 50;
Polygon pentagon =
new Polygon(5);
for (int j = 0; j < 5; j++)
pentagon.add(new
Point2D.Double(
x + r * Math.cos(2 *
Math.PI * j / 5),
y + r * Math.sin(2 *
Math.PI * j / 5)));
triangle.draw(g2);
pentagon.draw(g2);
}
}
// Polygon class
definition
class Polygon
{ public polygon(int n)
{ corners = new
Point2D.Double[n];
cornerCount = 0;
}
public void add
(Point2D.Double p)
{ if (cornerCount <
corners.length)
{ corners[cornerCount]
= p;
cornerCount++;
}
}
public void draw
(Graphics2D g2)
{ for (int j = 0; j <
cornerCount; j++)
{ Point2D.Double from
= corners[j];
Point2D.Double to =
corners[(j+1) %
corners.length];
g2.draw(new
Line2D.Double(from, to);
}
}
private Point2D.Double
[] corners;
private int
cornerCount;
}
Example
To generate a triangle,
we can use the
following segment of
code:
Polygon triangle = new
Polygon(3);
triangle.add(new
Point2D.Double(40,40))
;
triangle.add(new
Point2D.Double
(120,160));
triangle.add(new
Point2D.Double(20,120)
);
Another kind of
geometric shape is
called a regular
polygon which has all
sides of the same
length.
A regular n-gon with
center (x,y) and radius
r has n corners, c0, c1,
…, cn-1, where
ci = (x+r•cos(2p i/n), y
+r•sin(2p i/n))
A regular polygon can
be generated by:
Polygon pentagon =
new Polygon(5);
for (int j = 0; j < 5; j++)
pentagon.add(new
Point2D.Double(
x +r*Math.cos
(2*Math.PI*j/5),
y+r*Math.sin
(2*Math.PI*j/5)));
PolygonTest.java
import
java.applet.Applet;
import
java.awt.Graphics;
import
java.awt.Graphics2D;
import
java.awt.geom.Line2D;
import
java.awt.geom.Point2D
;
public class
PolygonTest extends
Applet
{ public void paint
(Graphics g)
{ Graphics2D g2 =
(Graphics2D) g;
Polygon triangle = new
Polygon(3);
triangle.add(new
Point2D.Double(40,40))
;
triangle.add(new
Point2D.Double
(120,160));
triangle.add(new
Point2D.Double(20,120)
);
double x = 200;
double y = 200;
double r = 50;
Polygon pentagon =
new Polygon(5);
for (int j = 0; j < 5; j++)
{ pentagon.add(new
Point2D.Double(
x+r*Math.cos
(2*Math.PI*j/5),
y+r*Math.sin
(2*Math.PI*j/5)));
}
triangle.draw(g2);
pentagon.draw(g2);
}
}
// define polygon class
class Polygon
{ public Polygon(int n)
{ corners = new
Point2D.Double[n];
cornersSize = 0;
}
public void add
(Point2D.Double p)
{ if (cornersSize <
corners.length)
{ corners[cornersSize]
= p;
cornersSize++;
}
}
public void draw
(Graphics2D g2)
{ for (int j = 0; j <
cornersSize; j++)
{ Point2D.Double from
= corners[j];
Point2D.Double to =
corners[(j+1) %
corners.length];
g2.draw(new
Line2D.Double(from,
to));
// Line2D.Double line =
new Line2D.Double
(from, to);
// g2.draw(line);
}
}
private Point2D.Double
[] corners;
private int cornersSize;
}
Vector
A Vector is a container
of objects that grows
automatically
A Vector can hold
objects of any types
Internally, the Vector
class keeps an Object
[] array.
There is no limit to the
number of elements
that we add.
We can add new
elements at the end of
the vector with the
add method.
However, vectors are
objects of a class and
not arrays so we
cannot use the []
operator to access
vector.
Instead, we use the
set method to write an
element, and the get
method to read an
element.
products.set(0, p);
Example
// Consider
BestProduct.java
Vector products = new
Vector();
boolean done = false;
while (!done)
{ Product p =
readProduct();
if (p == null) // last
product read
done = true;
else
products.add(p); // add
the object to the end
of the vector
}
Vector positions start
at 0.
The number of
elements stored in a
vector is obtained by
the size method.
int n = products.size();
To read an element
from a vector, we use
the get method:
products.get(i) is the
ith element in the
vector products.
However, because the
return type of the get
method is the class
Object, we must cast
the return value of the
get method to the
correct type.
Product p = (Product)
products.get(i);
An example of a loop
that traverses the
elements of a vector.
for (int j = 0; j <
products.size(); j++)
{ Product p = (Product)
products.get(j);
do something with p;
}
We can also insert an
object in the middle of
a vector by using v.add
(j,p) to add the object
p at position j, move
all elements by one
position, from position
j to the last element in
the vector, and
increase the size of
the vector by 1.
The call v.remove(j)
removes the element
at position j, moves all
elements after the
removed element
down by one position,
and reduce the size of
the vector of the
vector by 1.
Since numbers are not
objects in Java, we
cannot have vectors
of numbers.
To store sequence of
integers, floating-point
numbers, or boolean
values, we must use
wrapper classes.
The classes Integer,
Double, and Boolean
wrap numbers and
truth values inside
objects.
These wrapper
objects can be stored
inside vectors.
The Double class is a
number wrapper.
There is a constructor
that makes a Double
object out of a double
value:
Double d = new Double
(29.74);
Conversely, the
doubleVal method
retrieves the double
value that is stored
inside the Double
object.
double x =
d.doubleValue();
To add a number into a
vector, we first
construct a wrapper
object, then add the
object to the vector:
Vector data = new
Vector();
data.add(new Double
(29.95));
To retrieve the
number, we need to
cast the return value
of the get method to
Double, then call the
doubleValue method:
double x = ((Double)
data.get(0))
.doubleValue();
Converting Vectors to
Arrays
The advantage of
vectors is the dynamic
growth since we need
not know the final size
of the vector.
The disadvantage is
the cumbersome
access syntax.
We can convert a
vector to an array with
the copyInfo method:
// read values into a
vector
vector productVector =
new Vector();
boolean done = false;
while (!done)
{ Product p =
readProduct();
if (p == null)
done = true;
else
productVector.add(p);
}
// allocate an array of
the correct size
Product[] products =
new Product
[productVector.size()];
// copy the elements
from the vector to the
array
productVector.
copyInfo(products);
for (int j = 0; j <
products.length; j++)
do something with
products[j];
Two-Dimensional
Arrays
An arrangement
consisting of rows and
columns of values is
called a two-
dimensional array or
matrix.
To construct a 2D
array, we need to
specify how many ros
and columns we need,
for example
int[][] powers = new
int[10][8];
To access a particular
element in the matrix,
we specify two
subscripts in separate
brackets:
powers[3][4] =
Math.pow(2, 4);
Two-Dimensional
Arrays
In Java, 2D arrays are
stored as arrays of
arrays:
int[][] powers = new
int[10][8];
For example, power is
an array of 10 objects,
each of which is an int
[] array of length 8.
The number of rows is:
int nrows =
powers.length;
The number of
columns is:
int ncols = power[0]
.length;
// See example:
Table2.java
Table2.java
public class Table2
{ public static void
main(String[] agrs)
{ final int COL_WIDTH =
10;
int[][] powers = new
int[10][8];
for (int i = 0; i <
powers.length; i++)
for (int j = 0; j <
powers[i].length; j++)
powers[i][j] = (int)
Math.pow(i+1, j+1);
printTable(powers,
COL_WIDTH);
}
public static void
printTable(int[][] table,
int width)
{ for (int i = 0; i <
table.length; i++)
{ for (int j = 0; j < table
[i].length; j++)
{ System.out.print
(format(table[i][j],
width));
}
System.out.println();
}
}
public static String
format(int n, int width)
{ String nstr = “” + n;
while (nstr.length() <
width)
nstr = “ “ + nstr;
return nstr;
}
}
Friday, July 1, 2011
lesson 7-Arrays & Vectors
12:45 AM
Ravi mishra
No comments
0 comments:
Post a Comment