INTRODUCTION:

Programs often need a way to work with large amounts of data without declaring thousands of scalar variables. In this lesson we explain the terms data structure and algorithm, and then introduce you to a very important data structure, the array. With each new data structure comes the complementary algorithms to manipulate the data it stores. This combination of data structures and algorithms provide the powerful tools needed to solve computer science problems.

The key topics for this lesson are:

A. Data Structures and Algorithms
B. Example of an Array
C. Array Declarations and Memory Allocation
D. Applications of Arrays
E. Passing Arrays as Parameters
F. Arrays and Algorithms

VOCABULARY:

DATA STRUCTURE
TRAVERSAL
SEQUENTIAL
INDEX

ALGORITHM
ARRAY
RANDOM ACCESS

DISCUSSION:

A. Data Structures and Algorithms

1. A scalar type is a simple data type which holds one value at a time. The data types int, double, char, and boolean are important and useful, but limited.

2. A data structure is a collection of scalar data types which are all referenced or accessed through one identifier.

3. Data structures can be created to store information about any real-world situation:
a. Your high school transcript is a collection of grades.
b. The English paper you wrote on a word processor is stored as a collection of characters, punctuation, and formatting codes.
c. Your name, address, and phone number can be stored as a collection of strings.

4. After defining a data structure, algorithms will be needed to solve the specific problems associated with such a data structure.

5. One example of a data structure is an array. An array will store a list of values.

6. An algorithm is a sequence of programmed steps which solves a specific problem.

7. The fundamental algorithms which apply to an array data structure are: insertion, deletion, traversal, searching, and sorting.

B. Example of an Array

1. The following program will introduce you to some of the syntax and usage of the array class in Java:

Program 17-1

 public class ArrayExample
{
  public static void main (String[] args)
  {
    int[] A = new int[6];  //  an array of 6 integers
    int loop;

    for (loop = 0; loop < 6; loop++)
      A[loop] = loop * loop;
    System.out.println("The contents of array A are:");
    System.out.println();
    for (loop = 0; loop < 6; loop++)
      System.out.print("  " + A[loop]);
    System.out.println();
  }
}

Run output:

The contents of array A are:

  0  1  4  9  16  25

2. An array is a linear data structure composed of adjacent memory locations each holding values of the same type.

3. The variable A is an array, a group of 6 related scalar values. There are six locations in this array referenced by index positions 0 to 5. It might seem odd to begin a list at position 0 instead of position 1.

4. The variable "loop" is used in a for loop to reference index positions 0 through 5. The square of each index position is stored in the memory location occupied by each cell of the array. The syntax for accessing a memory location of an array requires the use of square brackets [].

5. The square brackets [] are collectively an operator in Java. They are similar to the parentheses as they have the highest level of precedence compared to all other operators.

C. Array Declarations and Memory Allocation

1.Array declarations look like this:

type[] arrayName;

This tells the compiler that arrayName will be used as the name of an array containing type. However, the actual array is not constructed by this declaration. Often an array is declared and constructed in one statetment like this:

type[] arrayName = new type[length];

This tells the compiler that arrayName will be used as the name of an array containing type, and constructs an array object containing length number of slots.

2. An array is an object, and like any other object in Java is constructed out of main storage as the program is running. The array constructor uses different syntax than most object constructors; type[length] names the type of data in each slot and the number of slots. For example:

int[] list = new int[6];
double[] data = new double[1000];
char[] line = new char[80];

Once an array has been constructed, the number of slots it has does not change.

3. The size of an array can be defined by using a final value.

final int MAX = 200;
int[] numb = new int[MAX];

4. When an array is declared, enough memory is allocated to set up the full size of the array. For example, the array of int as described above, int[] list = new int[6], will require 24 bytes of memory (4 bytes per cell).

D. Application of Arrays

1. Suppose we have a text file of integer data (votes.txt) which contains all the votes cast in an election. This election happened to have three candidates and the values in the integer file range from 1-3.

Program 17-2

import apcslib.*;

public class Votes
{
  public static void main (String[] args)
  {
    TextReader inFile = new TextReader(fileName);
      
    int vote, total = 0, loop;
   
    // sized to 4 boxes, initialized to 0's
    int[] data = new int[4];

    vote = inFile.readlnInt();
    while (!inFile.eof())
    {
      data[vote]++;
      total++;
      vote = inFile.readlnInt();
    }
    System.out.println("Total # of votes = " + total);
    for (loop = 1; loop <= 3; loop++)
      System.out.println("Votes for #" + loop +
                         " = " + data[loop]);

  }
}

a. The array data consists of four cells, each holding an integer amount. The first cell, data[0], is allocated but not used in this problem. We could have stored the information for candidate 1 in position 0, candidate 2 in position 1, and so forth, but the code is easier to follow if we can use a direct correspondence.

b. The value of vote is used to increment the appropriate cell of the array by +1.

2. A second example counts the occurrence of each alphabet letter in a text file.

Program 17-3

import apcslib.*;

public class CountLetters
{
  public static void main (String[] args)
  {
    TextReader inFile = new TextReader("sample.txt");
   
   // use positions 1..26 to count letters
   int[] letters = new int[27];
   char c1;
   int loop, total = 0;

   c1 = inFile.readChar();
   while (!inFile.eof())
   {
      if ('A' <= c1 && c1 <= 'Z')  // if c1 is upper case
         c1 = (char)(c1 + 32);     // change c1 to lower case
      if ('a' <= c1 && c1 <= 'z')  // if we have a letter...
      {
         letters[c1 - 96]++;  // if c1 == 'a', 97-96 = 1, etc.
         total++;
      }
      c1 = inFile.readChar();
   }
   System.out.println("Count letters");
   System.out.println();
   c1 = 'a';
   for (loop = 1; loop <= 26; loop++)
   {
      System.out.println(c1 + " : " + letters[loop]);
      c1++;
   }
   System.out.println();
   System.out.println("Total letters = " + total);
  }
}

a. Each character in the text file is read into c1. If c1 is an uppercase letter it is converted to its lowercase counterpart.
b. If the character is a letter, the ASCII value of the letter is adjusted to fit the range from 1-26. For example, if c1 == 'a', the program solves 97 - 96 = 1. Then the appropriate cell of the array is incremented by one.
c. Again, position 0 in the array is not used to make the data processing easier.

E. Passing Arrays as Parameters

1. The program in Handout, H.A.17.2, will provide examples of passing arrays as parameters. Notice that a global integer constant of 6 is used to size the array in this program.

2. The main method declares an array named data. The array is initialized with the values 0..5 inside main method.

3. The parameters of the squareList and printList methods are references to an array object. Any local reference to array list inside function squareList or printList is an alias for the array data inside of the main method. Notice that after the call of squareList, the values stored in array data in function main method have been permanently changed.

4. When rotateList method is called, the copy method of the ArrayOps class is invoked and the local array listCopy is created as a copy of the array data in main method.

5. The rotateList method rotates the values one cell to the right, with the last value moved to the front of the list. A call to printList is made inside the rotateList method just before leaving the method. After returning to main method, notice that the array data is unchanged.

F. Arrays and Algorithms

1. Insertion is a standard problem that must be solved for all data structures. Suppose an array had 10 values and an 11th value was to be added. We are assuming the array can store at least 11 values.

a. If we could place the new value at the end, there would be no problem.
b. But if the new value must be inserted at the beginning of the list in position 0, the other 10 values must be moved one cell down the list.

2. Deletion of a value creates an empty cell that probably must be dealt with. The most likely solution after deleting a value, is to move all values which are to the right of the empty spot one cell to the left.

3. A traversal of an array consists of visiting every cell location, probably in order. The visit could involve printing out the array, initializing the array, finding the largest or smallest value in the array, etc.

4. Sorting an array means to organize values in either ascending or descending order. These algorithms will be covered in depth in future lessons.

5. Searching an array means to find a specific value in the array. There are several standard algorithms for searching an array. These will be covered in future lessons.

SUMMARY/ REVIEW:

Arrays are tremendously useful data structures and you will have many opportunities (lots of labs!) to program with them. After spending a few days working with single dimension arrays, we will move on to multi-dimensional arrays.