## CS13002 Programming and Data Structures | ## Section: 5/E, Spring 2006 |

## 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
Sto the empty set.size(S);- Return the number of elements in the set
S.T = insert(S,n);- Insert the integer
nto the setSand return the modified set. Ifnis already present inS, then no actual insertion is done and the original set is returned.T = delete(S,n);- Delete from the set
Sthe integernand return the modified set. Ifnwas not present inS, then no actual deletion is done and the original set is returned.T = cup(S1,S2);- Return to
Tthe set-theoretic union of the setsS1andS2.T = cap(S1,S2);- Return to
Tthe set-theoretic intersection of the setsS1andS2.print(S);- Print the elements of
Sin 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 outputHere 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