You are asked to give a dynamic implementation of the ADT set having the following functions:

• void toempty(SET *S)
• int empty(SET S)
• int find(int x, SET S)
• void add(int x, SET *S)
• void removeS(int x, SET *S)
• void intersect(SET S1, SET S2, SET *R)
• void unionS(SET S1, SET S2, SET *R)
• void complement(SET S, SET *R)
• void display(SET S)

#include <stdio.h>
#include <stdlib.h>
#define N 100

typedef struct 
{
	int nbr;
	void *elts;
} SET;


typedef struct cell 
{
	int info;
	struct cell *next;
} *PTR;

PTR cell(int i, PTR s) 
{
	PTR res = malloc(sizeof(struct cell));
	if (res == NULL) 
	{
		fprintf(stderr, "Impossible to allocate in memory");
		exit(-1);
	}
	res->info = i;
	res->next = s;
	return res;
}

void toempty(SET *e) 
{
	e->elts = NULL;
}

int empty(SET e) 
{
	return e.elts == NULL;
}

int find(int x, SET e) 
{
	PTR p = e.elts;
	while (p != NULL && p->info != x)
		p = p->next;
	return p != NULL && p->info == x;
}

void add(int x, SET *e) 
{
	if ( ! find(x, *e))
		e->elts = cell(x, e->elts);
}

void removeS(int x, SET *e) 
{
	PTR p, pr;
     
	p = e->elts;
	while (p != NULL && p->info != x) 
	{
		pr = p;
		p = p->next;
	}
	if (p != NULL && p->info == x) 
	{
		if (p != e->elts)
			pr->next = p->next;
		else
			e->elts = p->next;
		free(p);
	}
}   

void intersect(SET e1, SET e2, SET *r) 
{
	PTR p;
    
	r->elts = NULL;
	for (p = e1.elts; p != NULL; p = p->next)
		if (find(p->info, e2))
			r->elts = cell(p->info, r->elts);
}

void unionS(SET e1, SET e2, SET *r) 
{
	PTR p;
    
	r->elts = NULL;
	for (p = e1.elts; p != NULL; p = p->next)
		r->elts = cell(p->info, r->elts);
	for (p = e2.elts; p != NULL; p = p->next)
		add(p->info, r);
}

void complement(SET e, SET *r) 
{
	PTR p;
	int i;
    
	r->elts = NULL;
	for (i = 0; i < N; i++) 
		if ( ! find(i, e))
			r->elts = cell(i, r->elts);
}

void display(SET e) 
{
	PTR p;
    
	printf("[ ");
	for (p = e.elts; p != NULL; p = p->next)
		printf("%d ", p->info); 
	printf("]");
}


int main() 
{
	SET a, b, c;
	int i;
    
	toempty(&a);
	for (i = 0; i < 32; i += 2)
		add(i, &a);
	for (i = 30; i >= 0; i -= 3)
		add(i, &a);
	printf("  a : "); 
	display(a); 
	printf("\n");
    
	toempty(&b);
	printf("a empty? %s\n", empty(a) ? "yes" : "no");    
	printf("b empty? %s\n", empty(b) ? "yes" : "no");
	for (i = 0; i < 32; i += 5)
		add(i, &b);
	printf("  b : "); 
	display(b); 
	printf("\n");
    
	complement(b, &c);
	printf(" ~b : "); 
	display(c); 
	printf("\n");
    
	intersect(a, b, &c);
	printf("a.b : "); 
	display(c); 
	printf("\n");
    
	unionS(a, b, &c);
	printf("a+b : "); 
	display(c); 
	printf("\n");
  
	for (i = 0; i < 32; i += 3)
		removeS(i, &c);
	printf("c : "); 
	display(c); 
	printf("\n");
    
	return 0;
}