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 */
/* 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:
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.
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.
-q quiet mode (no output from operations)
-v vetbose mode (default, output from operations)
-p profile mode (unimplemented, can do what you want)
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.
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:
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...
...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