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 !!
