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

---

[Submission site] [Lab home] [Course home]