Set ADT

Background [see http://en.wikipedia.org/wiki/Set_(mathematics) ]:

In mathematics, a set is a collection of distinct elements (say integer numbers). For example, A={2, 5, 7} and B={3, 5, 8, 10} are two different sets. There are several basic operations for constructing new sets from given two sets, but let's just consider three basic ones:

C = union(A,B); ---> C = A union B={2, 3, 5, 7, 8, 10}
C = intersection(A,B); ---> C = A intersection B= {5}
C = difference(A,B); ---> C = A differenceB = {2, 7} also aka. complement

What to do:

You are asked to develop a set library (using two different representations: array and link list). So you will have setArrayImp.c and setLinkedListImp.c Then implement a driver program that gets two sets and one of the above operation as a command to apply, then it prints the resulting set...

Developing set library:

For interface, create an interface file set.h which contains boiler plate and the followings:

typedef int setElementT; typedef struct setCDT *setADT;

setADT setNew(); /* create a new empty set */
void setFree(setADT S); /* free the space allocated for the set S */

int setInsertElementSorted(setADT S, setElementT E);
/* if not successful, return 0; otherwise, return the number of elements in the set (including the element just inserted). Also note that the elements might be given in different orders, but your function should always keep the set in a sorted manner after each insertion */

setADT setUnion(setADT A, setADT B);
setADT setIntersection(setADT A, setADT B);
setADT setDifference(setADT A, setADT B);
int setCardinality(setADT S); /* return the number of elements in S */
void setPrint(setADT S, char *name); /* print elements of S, A = {2, 5, 7} */

For implementation, you will be asked to have two different implementations: setArrayImp.c and setLinkedListImp.c

• First implement set library as setArrayImp.c which uses a constant size array to store set elements (suppose max set size is 100).
• Second implement this library as setLinkedListImp.c which uses a dynamic single linked list to store set elements.

Develop a driver.c program and compile it with two different imp of set library

1.Create two sets called A and B.
2.Ask user to enter positive integers for set A (end input when user enters -1)
3.Ask user to enter positive integers for set B (end input when user enters -1)
4.In a loop
4.1.Ask user to enter a command:
4.2If Q is entered, quit from this loop.
4.3If U, I, or D is entered, compute set C as union, intersection, or difference.
setPrint(A, "A"); setPrint(A, "B"); setPrint(C, "C");
print the number of elements in C
setFree(C);
5.free A and B

Compile/execute driver.c with setArrayImp.c as well as setListImp.c

Here is a Makefile for you:

all: driver-array driver-list

setArrayImp.o: setArrayImp.c set.h gcc -c setArrayImp.c

setLinkedList.o: setLinkedListImp.c set.h gcc -c setLinkedList.c

driver.o: driver.c set.h gcc -c driver.c

driver-array: driver.o setArrayImp.o
gcc driver.o setArrayImp.o -o driver-array

driver-list: driver.o setLinkedListImp.o
gcc driver.o setLinkedListImp.o -o driver-list