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

T Naughton, NUIM
Back to CS210 home

Laboratory Sheet 5

The set In this lab you will design an array-based set in much the same way as in lectures we designed an array-based stack and queue. Answer problem 5.1.

Problem 5.1 Write pseudocode for the methods of an array-based MyLittleSet class for integers. Note: a set is a collection of objects, without any particular order, and without repeated elements. The class should have at least the following public methods:

• MyLittleSet(int arraySize) - constructor, set the size of the local set,
• boolean isEmpty() - return true if local set is empty, otherwise false,
• boolean isFull() - return true if local set is full, otherwise false,
• void clear() - removes all elements from the local set,
• int cardinality() - returns the number of elements in the local set,
• void add(MyLittleSet newSet) - adds to the local set all elements specified in newSet,
• void add(int newElement) - adds a single element to the local set,
• void remove(MyLittleSet newSet) - remove from the local set all elements that appear in newSet,
• int [] extractElements() - returns a newly created array of appropriate size containing the elements of the local set (useful if another object wishes to get access to this set's elements),
• boolean isElementOf(int testElement) - return true if testElement is in the local set, otherwise false,
• void print() - print the elements of the local set to the screen,
• MyLittleSet intersection(MyLittleSet inputSet) - return a new set that is the intersection of the local set and inputSet, do not change either set in the process,
• MyLittleSet union(MyLittleSet inputSet) - return a new set that is the union of the local set and inputSet, do not change either set in the process,
• MyLittleSet setSubtraction(MyLittleSet inputSet) - return a new set that contains all the elements from the local set that are not in inputSet, do not change either set in the process,

Part of the problem here is trying to figure out what data members you need, so don't ask the demonstrators! If you have trouble with basic programming, get practice with the self-help exercises. To get you started, your class will need a private data member for the array reference,

int a[]; // reference to the array that holds elements of the set

and your constructor will have the following pseudocode,

MyLittleSet(int arraySize) {
  /* Constructor. Set the set size to that determined by
  ** the user. Initialise the set to empty.
  */

  if (arraySize >= 0) {
    a = new int[arraySize];
  } else {
    a = new int[0]; // if invalid arraysize
  }

  clear(); // initialise the set to empty
}