Description

Project 3: Sets, Arrays, and Hash Tables
1 Introduction
In this project, you will implement a set abstract data type, first for strings and then for generic pointer types. Your interface and implementation must be kept separate. Separate source files that provide main will be provided for testing your data type.
2 AnADTforStrings
2.1 Interface
The interface to your abstract data type must provide the following operations:
• SET *createSet(int maxElts); return a pointer to a new set with a maximum capacity of maxElts
• void destroySet(SET *sp); deallocate memory associated with the set pointed to by sp
• int numElements(SET *sp); return the number of elements in the set pointed to by sp
• void addElement(SET *sp, char *elt); add elt to the set pointed to by sp
• void removeElement(SET *sp, char *elt); remove elt from the set pointed to by sp
• char *findElement(SET *sp, char *elt); if elt is present in the set pointed to by sp then return the matching element, otherwise return NULL
• char **getElements(SET *sp); allocate and return an array of elements in the set pointed to by sp
2.2 Implementation
Implement a set using a hash table of length m > 0 and linear probing to resolve collisions. Create an auxiliary function search that contains all of the search logic as you did for the previous assignment, and use search to implement the functions in your interface. The following hash function should be used:
unsigned strhash(char *s) { unsigned hash = 0;
while (*s != ’’) hash = 31 * hash + *s ++;
return hash;
}
Asinthepreviousassignment, yourimplementationshouldallocatememoryandcopythestringwhenadding, and therefore also deallocate memory when removing.
1
3 AnADTforGenericPointerTypes
Unfortunately, we need to do a little more than just replace “char *” with “void *” in our implementation. Our implementation needs to be told how to compare two elements as well as compute the hash value for an element. After all, strcmp and strhash only work on strings. Therefore, our createSet function must take extra parameters that are now pointers to these two functions:
SET *createSet(int maxElts, int (*compare)(), unsigned (*hash)());
These two functions must be stored internally as part of the set structure. Rather than calling strcmp and strhash in the function search, you will need to call the client-provided functions instead. Assuming that the pointer to the set is sp and the comparison function is stored as a member called compare:
(*sp->compare)(…);
Our new generic set ADT also does not know how to allocate or deallocate the elements it stores, so rather than calling strdup and free, it simply copies the pointers themselves. The client is responsible for managing memory. Such is the price we pay for using a generic ADT.
Once you have completely finished your set ADT for strings, copy it to the generic directory and modify it so it uses generic pointer types instead of strings. You can test it against the unique and counts programs in that directory. Note that since the interface is slightly different, you cannot test your implementation against the programs in the strings directory. Moving forward, all future ADTs we design will be generic ADTs.
4 Submission
Download the project3.tar file from the course website to get started. Call your source file table.c. Place the solution for the ADT for strings in the subdirectory strings. Complete the file report.txt containing the results requested for below. Place the solution for the ADT for generic pointer types in the subdirectory generic. Submit a tar file containing the entire project3 directory using the online submission system.
5 Grading
Your implementation will be graded in terms of correctness, clarity of implementation, and commenting and style. Your implementation must compile and run on the workstations in the lab. The algorithmic complexity of each function must be documented. Report the execution times of the test programs on each of the sample input files by using the time command. (Report the average of the “real” times of at least three runs on each input file.)
2