NUIMCrest CS210 - Algorithms and Data Structures I
Department of Computer Science
National University of Ireland, Maynooth

T Naughton, NUIM
Back to CS210 home

Laboratory Sheet 6

The abstract data type (ADT) In this lab you will design and write code for abstract data types. Answer Problems 6.1 through 6.4. As always, what you do not get done in the lab should be completed in your own time. Problem 6.4 requires a level of appreciation of the issues involved in writing ADTs in Java that might not become clear to you until after our next lecture.

Abstract data types
Modular programs are easier to write, read, and modify. One would achieve modularity by breaking the functionality of your program into sections (modules) of code that perform one task (or a small number of closely related tasks) each. These sections of code could be functions, procedures, methods, or classes. In this way you and others can easily reuse your code.

Modules usually have both a specification (what it does) and an implementation (how it does it).

Information hiding:

Data abstraction:

Abstract data type:

Writing functions for ADTs

Here is a function that writes an array of ints to the screen.

void printArray(int list[]) {
  /* This function prints an array of integers.
  */
  int count; // counter

  if (list == null) {
    System.out.println("List:."); // show list is empty

  } else {
    System.out.print("List:"); // print blank list
    count = 0;
    while (count < list.length) {
      System.out.print(" " + list[count]);
      count++;
    }
    System.out.println('.');
  }
}

Download it with its tester program Lab06A.java and run it. Next we will look at how we might change the function printArray() so that it could work with arrays of any type. There are two important pieces of information that will help us to make this work:

  • All ADTs in Java are derived from the Object type. This means that if we write a function to work for type Object, it will work for all ADTs.
  • Many ADTs in Java will contain a useful method called toString() that will convert the unknown type to a String, so that we may easily write it to the screen without ever knowing what type it is.

    Here is the code (Lab06B.java) that shows the above function working for ADTs.

    Problem 6.1 Write code for an array-implementation of the well-known stack operations push(e), pop(), and isEmpty(), such that they would support Objects rather than simply ints as given in lectures.

    Problem 6.2 Write an ADT function in Java that takes an array (possibly containing multiple occurances of particular elements) and returns a new Object array with all duplicates of elements removed. When comparing array elements use the boolean equals(Object o) method that many ADTs in Java support. So, where one might have used (list[1]==list[2]) when comparing int array elements, one will use (list[1].equals(list[2])) when comparing Object array elements. This is to avoid comparing references (or addresses in memory) of objects when we mean to compare the value of objects.

    Writing your own ADTs

    The Java language specifies some built-in ADTs such as Integer and String. We, of course, could write our own. Here is a class Lab06C.java for an ADT that maintains a record of the number of brothers and sisters that a person has.

    public class Lab06C {
      /* This class maintains the number of brothers and sisters of a person.
      **
      ** Public methods:
      ** Lab06C() - default constructor, sets brothers & sisters to zero
      ** Lab06C(int b, int s) - conversion constructor, sets values
      ** Lab06C(Lab06C o) - copy constructor, sets values
      **
      ** int brothers() - number of brothers
      ** int sisters() - number of sisters
      ** int siblings() - number of brothers plus number of sisters
      ** boolean noSiblings() - returns true if no brothers or sisters
      ** String toString() - return data as a newly allocated string
      ** boolean equals(Lab06C e) - true if equal in value
      */

      private int pB; // number of brothers
      private int pS; // number of sisters

      . . .

    }

    Here is a program Lab06D.java that tests this ADT.

    Problem 6.3 Write a class in Java that specifies an ADT to store an array of Objects. The array's length will be exactly as long as the number of objects it is holding. Every time a new object is added, create a new array one larger and copy all elements to it. The constructor should create an array of length zero. Besides the default constructor and an add(Object o) method, your class should have a toString() method and a removeDuplicates() method. You should incorporate your solution from Problem 6.2. Also write a tester program.

    Problem 6.4 Write a class in Java called Lab0604 that stores an array of Lab06C objects. Besides a default constructor Lab0604() that creates an array of length zero and a copy constructor Lab0604(Lab0604 o), your class will have an add(Lab06C o) method, a totalSiblings() method, a toString() method, and its own equals() method. The totalSiblings() method should return the total number of siblings over all persons in the array. Also write a tester program.
    Note: to code the copy constructor and the equals() method you will have to gain access to the array elements within a Lab0604 object. Can you see why? One solution is to include a toArray() method. This returns a (reference to a) copy of the private array of Lab06C references and will allow one to iterate through the array elements.

    public Lab06C [] toArray() {
      /* Returns a reference to a copy of the private array
      ** of references (useful if another object wishes to get
      ** access to this object's array elements).
      */
      Lab06C tempArray[]; // reference to internal array
      int count; // array counter

      // make tempArray the same size as private array
      tempArray = new Lab06C[pArray.length];

      // copy references
      count = 0;
      while (count < pArray.length) {
        tempArray[count] = pArray[count];
        count++;
      }
      return tempArray;
    }

    End of sheet