You are asked to give a static 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)

In this version, reduce some of the complexities by keeping the elements in array sorted.


Difficulty level
This exercise is mostly suitable for students
#include <stdio.h>
#define N 100

typedef struct 
{
	int nbr;
	int tab[N];
} SET;

void toempty(SET *e) 
{
	e->nbr = 0;
}

int empty(SET e) 
{
	return e.nbr == 0;
}

int find(int x, SET e) 
{
	int i = 0;
	while (i < e.nbr && e.tab[i] < x)
		i++;
	return i < e.nbr && e.tab[i] == x;
}

void add(int x, SET *e) 
{
	int i = 0, j;
	while (i < e->nbr && e->tab[i] < x)
		i++;
	if (i < e->nbr && e->tab[i] == x)
		return;
	for (j = e->nbr - 1; j >= i; j--)
		e->tab[j + 1] = e->tab[j];
	e->nbr++;
	e->tab[i] = x;
}

void removeS(int x, SET *e) 
{
	int i = 0, j;
	while (i < e->nbr && e->tab[i] < x)
		i++;
	if (i < e->nbr && e->tab[i] == x) 
	{
		for (j = i + 1; j < e->nbr; j++)
			e->tab[j - 1] = e->tab[j];
		e->nbr--;
	}
}   

void intersect(SET e1, SET e2, SET *r) 
{
	int i = 0, j = 0, k = 0;
	while (i < e1.nbr && j < e2.nbr) 
		if (e1.tab[i] == e2.tab[j]) 
		{
			r->tab[k++] = e1.tab[i];
			i++;
			j++; 
		}
		else 
			if (e1.tab[i] < e2.tab[j])
				i++;
			else
				j++;
	r->nbr = k;
}

void unionS(SET e1, SET e2, SET *r) 
{
	int i = 0, j = 0, k = 0;
	while (i < e1.nbr && j < e2.nbr) 
		if (e1.tab[i] == e2.tab[j]) 
		{
			r->tab[k++] = e1.tab[i];
			i++;
			j++; 
		}
		else 
			if (e1.tab[i] < e2.tab[j]) 
			{
				r->tab[k++] = e1.tab[i];
				i++;
			}
			else 
			{
				r->tab[k++] = e2.tab[j];
				j++;
			}
	while (i < e1.nbr)
		r->tab[k++] = e1.tab[i++];
	while (j < e2.nbr)
		r->tab[k++] = e2.tab[j++];
	r->nbr = k;
}

void complement(SET e, SET *r) 
{
	int i, j = 0, k = 0;
    
	for (i = 0; i < e.nbr; i++) 
	{
		while (j < e.tab[i])
			r->tab[k++] = j++;
		j++;
	}
	while (j < N)
		r->tab[k++] = j++;
	r->nbr = k;
}

void display(SET e) 
{
	int i;
    
	printf("[ ");
	for (i = 0; i < e.nbr; i++)
		printf("%d ", e.tab[i]); 
	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;
} 


Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Tracing QuickSort and Heapsort