CPSC 170 Lab 9: The Set ADT and Implementations

An Array Based Set Implementation

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.

   
   
   
   
   

2. 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:
   • Use iterators to print the elements of each set.
   • 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

3. Add method intersection from the prelab to SetADT.java and ArraySet.java. Then modify the TestSet program so that after it prints the union of the two sets it prints their intersection (neatly labeled, of course).

4. Simplify method equals as described in the prelab -- the new method should be significantly simpler than the original. Run TestSet again to be sure it still works.

   Introduction to Linked Structures

5. 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.

6. 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.

7. Sometimes you want to add nodes to the end of a list, not the beginning. There are two standard strategies for this.
   • In the first strategy, you keep a variable that you might call back that points to the end of the list. Since it always points to the last node, you can use it to add a new node to the end of the list -- just make the next field of the last node point to the new node, then make back point to the new node as well (so it still points to the last node).

     Copy TestList.java into TestList1.java and use this strategy to add each node to the end of the list instead of the beginning.

     What is the big-Oh complexity of adding a node this way? Explain your answer.
     
     
     
     
     

   • In the second strategy, each time you add to the end of the list you assign a temporary pointer to the front of the list and move it along until it reaches the last node. You know when it's at the end because the next field of the last node is null. Once you find the last node, you can change its next field to point to the new node.

     Copy TestList.java into TestList2.java and use this strategy to add each node to the end of the list instead of the beginning. Note that inside your loop that adds the nodes you'll need another loop to find the end of the list each time.

     What is the big-Oh complexity of adding a node this way? Explain your answer.