C Set ADT

Implement Set ADT using different data structures

The sample code provided with this project implements a set ADT for linked lists. It also compiles stub code for implementations based on three other data structures which you need to provide.

Each of these should use the same interface defined in the header file set.h which is used for the provided linked list implementation:

typedef struct set set_t;
/* initialise a new set data structure */
set_t *set_create(void);
/* free the set data structure */
void set_destroy(set_t *set);
/* insert a value into the set, return 1 if new, 0 if repeat */
int set_insert(set_t *set, int val);
/* remove a value from the set, return 1 if removed, 0 if missing */
int set_delete(set_t *set, int val);
/* search for a value, return 1 if present, 0 if absent */
int set_search(set_t *set, int val);

Implement these functions for the set ADT using the following data structures in their respective files:

• set array.c - using an array.
• set btree.c - using a binary tree.
• set hash.c - using a hash table with separate chaining (linked lists)

Notes:

• All of your three implementations of the set ADT should give exactly the same output as the provided linked list implementaion given the same input data.
• A reminder that a key characteristic of the set ADT is that order is not important and there are no repeated values.
• The implementation details are up to you, but you must implement your own data structures and algorithms. You cannot use library functions such as qsort() for your implementations.
• All submissions should be in ANSI C (using the C99 standard), and should compile without warnings with the -W -Wall flags. Marks will be given to good coding style and commenting. If you develop on your own personal computers remember to periodically make sure your code compiles and runs correctly on the university machines, as waiting until right before submission to test this could go badly.
• Your code must have a maximum line width of 79 characters so they can be printed on A4 paper without line wrapping.
• You may alter the provided code if you wish, such as the provided main.c and util.c|h, however the output for the key set ADT operations (create, insert, delete, search) must not be changed.
• Additional operations to the set ADT may be added if you wish to help with your own testing as long as they do not affect the main operations required. For example, set print is provided for the linked list implementation; you may implement your own for the other data structures however this is optional.

Analysis Report

You also need to provide a brief report on the different structures you have used with emphasis on theoretical and practical analysis of their performance. Your report should discuss the advantages and disadvantages of each approach as well as any design decisions you made (sorting algorithms, hash functions, table sizes, etc.)

Your report should include an empirical analysis of the performance of the algorithms for insertion, deletion and searching under a range of different sized data sets, and you should briefly discuss the merits of each implementation under different conditions.

Notes:

• Your report must be submitted in PDF format
• As an example of different conditions to test, consider a static set - which has a building phase where all data is inserted then afterwards only searching is allowed - compared to a dynamic set which allows insertions and deletions at any time.
• It is up to you to choose how you wish to measure the performance of your algorithms empirically. The sample code provided defines a flag -p for a profile mode that you can use to do whatever you wish. You are also free to define alternative flags as long as it does not affect the default operation of the code.

Details

Provided with this project is the code to implement a set ADT using a singly linked list in a program called set llist, the usage of which is provided when the file is run without options (printed below):

Usage: set_llist [OPTIONS]... [FILES]...
Implements a basic set ADT for integers, performing the
operations defined in FILES.
Options:
-q quiet mode (no output from operations)
-v vetbose mode (default, output from operations)
-p profile mode (unimplemented, can do what you want)
File Format:
Data files consist of command lines: a character and a number.
I < number > insert < number > in the set
D < number > delete < number > from the set
S < number > search for < number > in the set
Multiple files can be specified and they will run sequentially.
Example:
set_llist insert_list.txt search_list.txt

Operations to the set ADT are provided in the input files, which are text files providing lists of commands in the format:

< char > < number >

where < char > denotes the command to be performed on the set ADT:

• I - insert (add) a new element into the set if not already present
• D - delete (remove) an element from the set if present
• S - search (query), output whether the element is present in the set

For each command, output is generated (when the program is not run in quiet mode) listing the operator and value requested and whether the value was already in the set. For example, the following input file to the program...

I 315
I 782
I 315
S 315
S 882
D 315
D 882
S 315

...generates this output:

insert: 315 new
insert: 782 new
insert: 315 repeat
search: 315 present
search: 882 absent
delete: 315 removed
delete: 882 missing
search: 315 absent