APSU Notes

Home / CSCI2010 / Chapters / Chapter1 / Arrays

• Arrays
  • Topics
  • 7.1 Array Basics
    • Creating and Accessing Arrays
    • Arrays and for Loops
    • Array Details
    • The Instance Variable length
    • Arrays and for-each Loops
    • More About Array Indices
    • Starting Indexes at One
    • Initializing Arrays
  • 7.2 – Arrays in Classes and Methods
    • Arrays as Instance Variables
    • Entire Arrays as Arguments to a Method
    • Arguments for the Method main
    • Array Assignment and Equality
    • Methods that Return Arrays
  • 7.3 – Programming with Arrays and Classes
    • A Specialized List Class
    • Using the SimpleList class
    • Implementing the SimpleList class
    • The addItem Method
    • The getItemAt Method
    • Partially Filled Arrays
  • 7.4 – Sorting and Searching Arrays
    • Selection Sort
    • Selection Sort Implementation
    • Other Sorting Algorithms
    • Searching an Array
  • 7.5 – Multidimensional Arrays
    • Multidimensional Arrays
    • Multidimensional Array Basics
    • Parameters and Returned Values
    • Multidimensional Array Representation
    • Ragged Arrays
  • Chapter 7 Summary
• Powerpoint
• Quiz

Arrays

Savitch 7.1-7.5

Topics

• 7.1 – Array Basics
• 7.2 – Arrays in Classes and Methods
• 7.3 – Programming with Arrays and Classes
• 7.4 – Sorting and Searching Arrays
• 7.5 – Multidimensional Arrays

7.1 Array Basics

Creating and Accessing Arrays

• An array is a ordered collection of items of the same type.
• An array element or indexed variable is used to access an item in the array.
• An index or subscript determines which item is being accessed.

// the declaration and initialization can be on a single line
double[] temperature;        // declares variable
temperature = new double[7]; // initializes to new array object

// Assign 68 to indexed variable temperature[3]
temperature[3] = 68;

// Access the value of temperature[3] in an expression
double celsiusTemp = (temperature[3] - 32) * 5 / 9;

Arrays and for Loops

• The index used to access an array element can be any expression that evaluates to an integer value between 0 and the length minus one.
• A for loop with an index variable can be used to iterate through the items in an array.

System.out.println("Enter 7 temperatures:");
for (int index = 0; index < 7; index++)
  temperature[index] = keyboard.nextDouble();

System.out.println("The 7 temperatures are:");
for (int index = 0; index < 7; index++)
  System.out.print(temperature[index] + " ");
System.out.println();

Array Details

• In Java, an array is created as follows:

Base_Type[] Array_Name = new Base_Type[Length];

• The base type is the type of the items in the array.
• The number of items in the array is its length, size, or capacity.
• The base type can be a primitive type of a class type.
• An array element is accessed as follows:

Array_Name[Index]

• An array element acts as a variable of the base type of the array.

The Instance Variable length

• An array is a kind of object with a single public instance variable called length.

Species entry = new Species[20];
System.out.println(entry.length); // displays 20

• The length instance variable is final, so its value cannot be changed.

entry.length = 10; // Illegal!

• A for loop can use the length instance variables in its loop condition:

for (int index = 0; index < temperature.length; index++)
  temperature[index] = keyboard.nextDouble();

Arrays and for-each Loops

• A for-each loop can be used to iterate though the items in array.

// value is initially assigned temperature[0], then is assigned
// the next item in the array before each successive iteration
for (int value : temperature)
{
  if (value < average)
    System.out.println(value + " below average.");
  else if (value > average)
    System.out.println(value + " above average.");
  else // value == average
    System.out.println(value + " the average.");
}

More About Array Indices

• If an index evaluates to an integer outside of the range between zero and the array length minus one, the index is out of bounds or invalid.
• Out of bounds errors can be avoided by validating the index.

int index = 0;
int number = keyboard.nextInt();
while ((index < list.length) && (number >= 0))
{
  list[index] = number; // index is guaranteed to be in bounds
  index++;
  number = keyboard.nextInt();
}

Starting Indexes at One

• Sometimes data is numbered starting at 1 instead of 0.

// Option 1: adjust index when displaying it to the user
int [] hours = new int[NUMBER_OF_EMPLOYEES];
for (int index = 0; index < hours.length; index++) {
  System.out.println("Enter hours for employee " + (index + 1));
  hours[index] = keyboard.nextInt();
}

// Option 2: allocate an extra item and skip item at index 0
int [] hours = new int[NUMBER_OF_EMPLOYEES + 1];
for (int index = 1; index < hours.length; index++) {
  System.outprintln("Enter hours for employee " + index);
  hours[index] = keyboard.nextInt();
}

Initializing Arrays

• An array can be initialized when i is declared:

double[] reading = {3.3, 15.8, 9.7}

• The length of the array is set to the number of initial values are provided.
• If array elements are not initialize they may be initialized to the default value for the base type (e.g. 0 for ints).
• It is good practice to initialize array elements explicitly.

int [count] = new int[100];
for (int index = 0; index < 100; index++)
  count[index] = 0;

7.2 – Arrays in Classes and Methods

Arrays as Instance Variables

• An array can be used as an instance variables in a class definition:

public class Section
{
  private Course course;
  private int sectionSize;
  private Student[] roster;

  public Section(Course course, int sectionSize)
  {
    this.course = course;
    this.sectionSize = sectionSize;
    this.roster = new Student[sectionSize]; // does not create the
  }                                         // Student objects
}

• An indexed variable can be used anywhere that any other variable of the base type of the array can be used.
• For example, an indexed variables of type int can be passed as an argument to a method with a parameter of type int.

public static double getAverage(int num1, int num2)
{
  return (num1 + num2 ) / 2.0;
}

public static void main(String[] args)
{
  int[] score = {72, 81};
  double average = getAverage(score[0], score[1]);
}

Entire Arrays as Arguments to a Method

• An entire array can be used as parameter to a method.
• The length of the array is not specified by the parameter.

public static void incrementArrayBy2(double[] arr)
{
  for (int index = 0; index < arr.length; index++)
    arr[index] = arr[index] + 2;
}

public static void main(String[] args)
{
  double[] number = {5, 2, 7, 4, 9, 0};
  incrementArrayBy2(number);
  // number is now {7, 4, 9, 6, 11, 2}
}

Arguments for the Method main

• The main method takes an array of strings as an argument.

public static void main(String[] args)

• The array args is initialized to the command line arguments used when the program is launched.

java TestProgram Sally Smith

• In this example args[0] would be "Sally" and args[1] would be "Smith".

Array Assignment and Equality

• Arrays are objects, so the = and == operators behave in the same way they do with other objects.

int[] first = {8, 3, 1, 9, 2};
int[] second = {8, 3, 1, 9, 2};
// first and second reference different objects so first != second

first[2] = 5;
// second[2] still has a value of 1

second = first;
// first and second reference the same object so first == second

first[2] = 7;
// second[2] also has a value of 7

Methods that Return Arrays

• A method can return an array.

public static int[] getSquares(int size)
{
  if (value <= 0)
  {
    System.out.println("Error: can not create array of size " + size);
    System.exit(0);
  }
  int[] squares = new int[size];
  for(int index = 0; index < size; index++)
    squares[index] = index * index;
  return squares;
}

// example method call: int[] squareArr = getSquares(10);

7.3 – Programming with Arrays and Classes

A Specialized List Class

• Consider a class called SimpleList that keeps track of a list of items.
• Items are numbered from one to the maximum number of items.
• There may be fewer than the maximum number of items in the list.
• The class contains the following methods:
  • SimpleList(int maxItems)
  • void addItem(String item)
  • String getItemAt(int position)
  • boolean contains(String item)
  • int getNumItems()
• There is also a public constant called START_POSITION that is et to the initial position of 1.

Using the SimpleList class

SimpleList shoppingList = new SimpleList(5);

shoppingList.addItem("A loaf of bread");
shoppingList.addItem("A stick of butter");
shoppingList.addItem("A container of milk");

int position = shoppingList.START_POSITION;
while(position <= shoppingList.getNumItems()) {
  String next = shoppingList.getItemAt(position);
  System.out.println(next);
  position++;
}

Implementing the SimpleList class

/** A list of items */
public class SimpleList {
  public static final int START_POSITION = 1;

  private int numItems; // may be < items.length
  private String[] items;

  /** Create an empty list with a given capacity */
  public SimpleList(int maxItems) {
    items = new String[maxItems];
    numItems = 0;
  }

The addItem Method

/** Add an item to the list */
  public void addItem(String item) {
    if (!contains(item)) {
      if (numItems == items.length) { // array is full
        System.out.println("Adding item to full list!");
        System.exit();
      }
      else {
        items[numItems] = item;
        numItems++;
      }
  }

The getItemAt Method

  /** Get the item at the given position */
  public String getItemAt(int position) {
    String result = null;
    if ((1 <= position) && (position <= numItems))
      result = items[position – 1];
    return result;
  }

  /** Get the number of items in the list */
  public int getNumItems() {
    return numItems;
  }

Partially Filled Arrays

• The SimpleList class uses a partially filled array to store its items.
• The capacity of the list is determined by the length of the array.
• The actual number of items in the list is determined by the numItems instance variable.
• The list items are stored at indexes 0 though numItems - 1.
• Any items stored in the rest of the array are ignored.
• To consider a portion of an array that does not start at index 0, first and last indexes can used.

7.4 – Sorting and Searching Arrays

Selection Sort

• An array is storted if its items are arranged in some specified order.
• A sorting algorithm can be used to sort an array.
• Selection sort is a sorting algorithm that repeatedly does the following:
  1. Find the smallest item that has not yet been sorted.
  2. Swap that item with the first item that has not yet been sorted.
• Initially all of the items in the array are unsorted.
• Each time the next smallest item is swapped, it becomes part of the sorted section of the array.
• The algorithm halts when there is only one unsorted item left.
• This item is guaranteed to be the largest item in the array.

Selection Sort Implementation

public static void selectionSort(int[] anArray) {
  for (int first = 0; first < anArray.length - 1; first++) {
    int smallest = getIndexOfSmallest(first, anArray);
    swap(first, smallest, anArray);
  }
}

private static void swap(int i, int j, int[] arr) {
  int temp = arr[i]; // save the value at index i
  arr[i] = arr[j]; // copy the item at index j to index i
  arr[j] = temp; // copy saved value to index j
}

private static int getIndexOfSmallest(int start, int[] arr)
{
  // assume the smallest item is at the start index
  int min = start;
  // look for something smaller
  for (int curr = start + 1; curr < arr.length; curr++)
    if (arr[curr] < arr[min])
      min = curr; // found something smaller
  // return the index of the smallest item found
  return min;
}

Other Sorting Algorithms

• Selection Sort one of the simplest sorting algorithms, but it not the most efficient.
• The java.util package contains a class called Arrays that has more efficient method called sort.

// sort an entire array
Arrays.sort(anArray);

// sort a range of an array from first to last
Arrays.sort(anArray, first, last);

• The array must contain items that implement the Comparable interface.

Searching an Array

• A searching algorithm finds a particular item in an array,
• Sequential search is a searching algorithm that looks through each item in an array in order.

public boolean contains(String item) {
  boolean found = false;
  int index = 0;
  while(!found && (index < numItems))
     if(item.equalsIgnoreCase(items[i])) found = true;
     else index++;
  return found
}

7.5 – Multidimensional Arrays

Multidimensional Arrays

• Two-dimensional (2D) arrays are arrays that have two indexes.
• The first index represents the rows in a table and the second index represents the columns.
• The syntax for an element of a 2D array in Java is:

Array_Name[Row_Index][Column_Index]

• For example the entry at row 3 and column 2 of a 2D array called table would be table[3][2].
• An array with more than one index is called a multidimensional array.
• An array with exactly one index is called a one-dimensional (1D) array.

Multidimensional Array Basics

• A 2D array of integers with 10 rows and 6 columns can declared as follows:

int[][] table;            // declares a 2D array variable
table = new int[10][6];   // allocates a 2D array

int[][] table = new int[10][6]; // same as 2 lines above

• Nested for-loops can be used to iterate through the elements of a 2D-array in order:

for (int row = 0; row < 10; row++)   // iterates through rows
  for (int col = 0; col < 6; col++)  // iterates through columns
    table[row][col] = row * 6 + col; // initializes elements

Parameters and Returned Values

• Multidimensional arrays can be method parameters can return values.

public static double[][] copy(double[][] startArray, int size)
{
  double[][] temp = new double[size][size];
  for (int row = 0; row < size; row++)
    for (int col = 0; col < size; col++)
      temp[row][col] = startArray[row][col];
  return temp;
}

// method call:
double[][] arr1 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
double[][] arr2 = copy(arr1, 3);

Multidimensional Array Representation

• A multidimensional array is an array of arrays.
• Consider the following 2D array:

int[][] table = new int[10][6];

• table refers to an array of 10 arrays, and table.length is 10.
• table[0] refers to an array of 6 ints, and table[0].length is 6.
• We can rewrite the nested for loop to take advantage of this:

for (int row = 0; row < table.length; row++)
  for(int col = 0; col < table[row].length; col++)
    table[row][col] = row * table[row].length + col;

Ragged Arrays

• The rows of a 2D array can have different lengths.

int[][] ragged = new int[3][]; // allocate an array with 3 rows
ragged[0] = new int[5];        // first row has 5 entries
ragged[1] = new int[7];        // second row has 7 entries
ragged[2] = new int[4];        // third row has 4 entries

• A nested for loop must check the length of each row.

for (int row = 0; row < ragged.length; row++) {
  for (int col = 0; col < ragged[row].length; col++)
    System.out.print(ragged[row][col] + " ");
  System.out.println();
}

Chapter 7 Summary

• An array can be thought of as a collection of variables all of the same type.
• Arrays are objects that are created using the operator new, although the syntax is slightly different from that used when creating objects of a class.
• Array elements are numbered starting with 0 and ending with 1 less than the length of the array. If a is an array, a[i] is an indexed variable of the array. The index i must have a value greater than or equal to 0 and strictly less than a.length, the array’s length. If i has any other value when you run your program, an array index out-of-bounds error will occur, causing an error message.
• When an indexed variable is used as an argument to a method, it is treated just like any other argument whose data type is the same as the array’s base type. In particular, if the base type is a primitive type, the method cannot change the value of the indexed variable, but if the base type is a class, the method can change the state of the object at the indexed variable.
• You can pass an entire array to a method. The method can change the values of an array of primitive values or the states of objects in the array.
• A method’s return value can be an array.
• When you use only part of an array, you normally store values in an initial segment of the array and set an int variable to the number of these values. In this case, you have a partially filled array.
• An accessor method that returns an array corresponding to a private instance variable of an array type should be careful to return a copy of the array, as returning the private instance variable itself causes a privacy leak.
• The selection sort algorithm orders an array of values, such as numbers, into either increasing or decreasing order.
• Arrays can have more than one index, and so are called multidimensional. Multidimensional arrays are implemented in Java as arrays of arrays.
• A two-dimensional array can be thought of as a two-dimensional table of rows and columns. An indexed variable of such an array is an element whose row and column are indicated by its indices, where the first index designates the row, and the second index designates the column.

Powerpoint

View presentation

Quiz

Quiz 2