Data Structures and Intermediate Programming 
Program Assignment 4

Overview"




In this assignment, you will implement an abstract data
type Set and its two subclasses TreeSet and HashSet. The Set class is a pure abstract super class, so
you cannot create its instance. The actual set you will use in a program is an
instance of either the TreeSet or the HashSet subclass. The TreeSet subclass
implements the set abstraction using a binary search tree, while the HashSet
does it by using a hash table. The TreeSet instance has a better worst case
performance for updates. In contrast, the HashSet instance has a much better
average case performance for search. !

Problem Statement"



An abstract data type Set realizes the mathematical set,
which is a collection of items with no duplicates. A set does not have a notion
of order, unlike a list. Your task is to implement the Set type and support
basic set operations such as union and intersection. The Set type is realized
by three classes, the Set superclass and two subclasses TreeSet and HashSet.
The complete declaration for the Set superclass is provided to you. Your task
is to implement the concrete subclasses TreeSet and HashSet. You use some
variation of a binary tree structure to implement the TreeSet subclass and a
hash table for the HashSet subclass. You are not allowed to use any system
library classes such as the vector or the list when implementing the internal
data structure for the subclasses.!

Specification"



Here’s the
declaration for the Set superclass.! ! class! Set
{ public! :              

  //--------- Update Operations ----------------------------//    

!   virtual
void insert(string
item) = 0;       

!   virtual
void remove(string
item) = 0;    

  //--------- Set Operations ----------------------------//                           !   virtual
Set* set_union(Set* s2) = 0; //set
union     

!   virtual
Set* set_intersect(Set* s2) = 0; //set
intersection                           virtual
Set* set_diff(Set*
s2) = 0; //set difference     

!!

  //--------- Access Operations --------------------//                              !   virtual
vector<string
scan( ) = 0;         

  //--------- Queries ----------------------------//    

!   virtual
int size( ) = 0;                            !   virtual
bool isEmpty( ) = 0;   

   virtual bool
in(string
item) = 0; };             

Operations"
!

Please read the specification for each function very, very
carefully. !





Function


Specification




void insert(string item)


Insert an item into the
set. If the item already exists in the set, do nothing.




void remove(string item)


Delete the designated item
from the set. If the designated item is not found, do nothing.




Set* set_union(Set* s2)


Return the set union of
this set and s2. This set and s2 remain unchanged.




Set* set_intersect(Set* s2)


Return the set intersection
of this set and s2. This set and s2 remain unchanged.




Set* set_diff(Set* s2)


Return the set difference
of this set and s2. This set and s2 remain unchanged. Remove all items in s2
from this set. An item in this set but not in s2 remains in the result.




vector<string scan( );


Return the items in the set
as a vector of items. If the set is empty, then return an empty vector, i.e.,
a vector with no elements, not a NULL.




int size( );


Return the number of items
in the set.




bool isEmpty( );


Return true if the set is
empty; otherwise, return false.




bool in(string item);


Return true if the item is
in the set. Otherwise, return false.




!

!

Here’s a sample use:!

!

!                        Set * ps1 = new
TreeSet();

                         Set * ps2 = new
TreeSet();

                    Set * ps3;             




!
               


ps1-insert("Hello");




                !
               


ps1-insert("World"); ps2-insert("C++");         




                !
               


ps2-insert("Hello"); ps3 = ps1-set_union(ps2);!




Requirements"



1.  All
functions must have good performance. For example, when taking a union of two
set, you should aim for an algorithm that performs better than inserting all
elements from s1 and s2, one by one, into s3. !

2.  There
should be absolutely NO input and output statements in the functions. You may
place temporary I/O statements in a function for testing/debugging purposes
during the development, but you must remove them before the submission.!

3.  DO
NOT CHANGE the public member functions defined in the file Set.h. The instructor's test program will import
functions from your module so it is critical that the function signatures are
not changed. !

4.  DO
NOT ADD any new public member functions to the Set class. But, you may add as
many private data members and private helper functions as you wish.!

5.  Functions
you define in the program should not access any global variables, those define
outside of the class. Use of the global symbolic constants is fine.!

6.  In
your source files, include a header comment with your name, the course number,
the assignment number, and any detailed explanation of your functions as
appropriate.!

7.  Format
the program in a clean manner. Group statements into logical groups and include
a descriptive comment for each group. Group comments do not have to be verbose.
One sentence would suffice if the statements in a group are written correctly
and precisely. Include enough blank lines between logical groups.!

8.  Insert
one or more blank lines between statements as necessary to make the code more
readable and easier to follow. Do not pack statements too densely (e.g., 20
statements with no blank lines between them).! 9. Use comments judiciously. Do
not include redundant and meaningless comments.!

             

!

Starter Code"



The following source files are provided to you.!




Filename


Description




set.h


The source file for the
abstract superclass Set. Do not make any changes to the public segment of the
class declaration. The private segment, however, is under your complete
control.





prog4.cpp


This sample main program illustrates a basic interaction
with a set.




vectorset.h! vectorset.cpp


This is a partially
completed sample subclass to illustrate how the set union can be implemented
using a vector. This class is provided solely for the purpose of giving you
some idea. You do not have to do anything to this class.




!

Development Ideas"



1.   Implement
the TreeSet class using some variation of a binary search tree. Consider making
modifications to the base BST class so the set union, intersection, and
difference can be implemented efficiently.!

2.   Implement
the HashSet class using one of the hashing techniques. Again, aim for the
hashing technique that will allow you to implement the set operations
efficiently.!

!

Testing the Functions"



As always, you need to plan
effective testing methodology to verify the implementation.!

!

Submission"



Submit the source files for the
HashSet and TreeSet class—hashset.h, hashset.cpp, treeset.h,
and treeset.cpp—that fully implements the
Set class, via the Sakai course website’s Program Assignment 4 page.!
Powered by