## Assignment 8

In this exercise, you are asked to implement the ADT set. For simplicity, let us restrict to sets of integers. The following operations need to be implemented.

S = init();
Initialize S to the empty set.
size(S);
Return the number of elements in the set S.
T = insert(S,n);
Insert the integer n to the set S and return the modified set. If n is already present in S, then no actual insertion is done and the original set is returned.
T = delete(S,n);
Delete from the set S the integer n and return the modified set. If n was not present in S, then no actual deletion is done and the original set is returned.
T = cup(S1,S2);
Return to T the set-theoretic union of the sets S1 and S2.
T = cap(S1,S2);
Return to T the set-theoretic intersection of the sets S1 and S2.
print(S);
Print the elements of S in sorted order.

Prepare a dynamic linked list implementation for the set ADT. Keep the elements of the list in sorted order. Every insertion, deletion, cup and cap operation must output a sorted linked list.

Report the output of your program on the following main() function.

```   #include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INS_COUNT 200
#define DEL_COUNT 100

int main ()
{
int i;
set S1, S2, T;

srand((unsigned int)time(NULL));

S1 = init();
S2 = init();

for (i=0; i<INS_COUNT; ++i) S1 = insert(S1,rand()%100);
printf("After insertion the 1st set has %d elements :\n", size(S1));
print(S1); printf("\n");

for (i=0; i<INS_COUNT; ++i) S2 = insert(S2,rand()%100);
printf("After insertion the 2nd set has %d elements :\n", size(S2));
print(S2); printf("\n");

for (i=0; i<DEL_COUNT; ++i) S1 = delete(S1,rand()%100);
printf("After deletion the 1st set has %d elements :\n", size(S1));
print(S1); printf("\n");

for (i=0; i<DEL_COUNT; ++i) S2 = delete(S2,rand()%100);
printf("After deletion the 2nd set has %d elements :\n", size(S2));
print(S2); printf("\n");

T = cup(S1,S2);
printf("The union has %d elements :\n", size(T));
print(T); printf("\n");

T = cap(S1,S2);
printf("The intersection has %d elements :\n", size(T));
print(T); printf("\n");
}
```

Sample output

Here is a run of the above program with 50 insertions and 25 deletions.

```   After insertion the 1st set has 38 elements :
1  3  4  6  7 16 19 20 22 26 27 28 48 51 53 54 56 58 60 61 65 67 68 73 74
75 79 80 81 82 83 84 87 89 91 95 98 99
After insertion the 2nd set has 37 elements :
1  5 10 12 13 14 19 20 24 29 30 31 34 36 37 42 46 48 50 51 53 54 59 63 65
66 68 69 74 79 83 85 90 94 95 96 98
After deletion the 1st set has 31 elements :
1  3  7 16 19 20 22 26 27 28 51 53 56 60 61 65 67 68 73 74 75 79 80 81 82
83 84 87 89 95 99
After deletion the 2nd set has 28 elements :
1  5 10 12 13 14 19 20 24 29 30 37 42 51 53 63 65 66 68 74 79 83 85 90 94
95 96 98
The union has 48 elements :
1  3  5  7 10 12 13 14 16 19 20 22 24 26 27 28 29 30 37 42 51 53 56 60 61
63 65 66 67 68 73 74 75 79 80 81 82 83 84 85 87 89 90 94 95 96 98 99
The intersection has 11 elements :
1 19 20 51 53 65 68 74 79 83 95
```