CPSC 170 Lab 10: Linked Structures and the Set ADT 

As usual, create a lab10 subdirectory for today's lab, open this document in Firefox, and start emacs.

Introduction to Linked Structures

  1. File TestList.java contains a simple program that uses the LinearNode class to create a 3-element linked list. Save these files to your directory, then compile and run TestList to see what it does.

    Now print out TestList.java and study the code. There are seven lines marked with numbers (//**** 1 ****, etc). For each of these lines, draw a diagram like those in Chapter 4 of the text showing front and temp and everything they refer to. Your diagrams should show the structures after the line executes. Draw the diagrams on the TestList printout.

  2. Of course, it's silly to have separate code each time you put something on the front of the list. Modify TestList so that it reads a positive integer N from the user and uses a loop to create a list that holds the integers from N to 1. Add a node to the front of the list each time, as in the example, so the numbers will still be backwards in the list.

  3. Notice that when we print the list, we are using a method called printList(front). This displays the entire list from the front until the end of the list.   Traversing the structure like this is a common operation - but we don't always want to move across the entire structure.  (Think back to our class discussions about searching or finding the nth entry).   To help us do this more generally, we can rely on an Iterator.   An iterator object allows us to keep track of the current location in the structure, and get the next available element (if there is one).   If you think about it, you have been using iterators since the early days of CS 120!   Where?

  4. A Scanner implements the iterator interface - if you think of the input as a structure, you can ask the Scanner if there is more input (hasNext) and you can ask it to give you the next one (next).

  5. Suppose that  you wanted to add nodes to the end of a list, not the beginning. There are two standard strategies for this.
Print copies of  TestList1 and TestList2 for submission. (you do not need to reprint TestList - hand in the one with your drawings).

An Array Based Set Implementation

Files SetADT.java, ArraySet.java and ArrayIterator.java contain the code presented in Chapter 3 of Lewis and Chase. TestSet.java contains a simple program that illustrates some of the set operations, and Sentences.java contains a skeleton of a program that uses sets to make random sentences. Save these files to your directory.
  1. Open TestSet.java and study it to understand how it works. Then compile and run it. Particularly note how the iterators are used to print the sets in table form. Could this be done using just the ArraySet toString method instead of using iterators? Explain how or why not using comments at the top of TestSet.java.

  2. Add an intersection method to SetADT.java and ArraySet.java.  Like with the union method, this method should take a SetADT as a parameter and return a SetADT.     Then modify the TestSet program so that after it prints the union of the two sets it prints their intersection (neatly labeled, of course).

  3. The equals method in the ArraySet class in the text is unnecessarily complicated. The code given would be needed if sets could contain duplicates, but they can't. For two sets to be equal, they must be the same size and every element in one set must be in the other set.  

  4. Open Sentences.java. Fill in the code as indicated by the comments so that the program sets up three sets of strings to hold subjects, verbs, and objects respectively. After it reads values for the sets (this code is already in place), it should do the following:

  5. Use iterators to print the elements of each set.

  6. Use removeRandom on each set to make random sentences, each of which uses a different randomly chosen subject, verb, and object. Repeat this until the sets are empty.
Compile and run your program to make sure it works. To facilitate testing, you can use redirection to take input from file words.dat -- just save the file to your directory and run your program as java Sentences < words.dat

Print copies of  ArraySet, TestSet and Sentences to hand in.