You are asked to give an implementation of the ADT set using an array of bits and 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)
When N> 32, we can represent a set not by a long integer, but by an array of K long integers, where K is the quotient by excess of N by 32.
We set up here a so-called paging mechanism. Since we know how to do with sets of 32 values, to manage sets of N values it suffices to see them as K packets, or pages, of 32 elements, K being the quotient by excess of N by 32.
To reach the ith element it is enough then to calculate the index of the page which concerns it (i / 32) then its rank in this page (i% 32).
Difficulty level
This exercise is mostly suitable for students
#include <stdio.h>
#include <stdlib.h>
#define N 100
#define K ((N + 31) / 32)
typedef struct
{
unsigned long tab[K];
} SET;
void toempty(SET *e)
{
int i;
for (i = 0; i < K; i++)
e->tab[i] = 0;
}
int empty(SET e)
{
int i;
for (i = 0; i < K; i++)
if (e.tab[i] != 0)
return 0;
return 1;
}
int find(int x, SET e)
{
return (e.tab[x / 32] & (1L << (x % 32))) != 0;
}
void add(int x, SET *e)
{
e->tab[x / 32] |= (1L << (x % 32));
}
void removeS(int x, SET *e)
{
e->tab[x / 32] &= ~(1L << (x % 32));
}
void intersect(SET e1, SET e2, SET *r)
{
int i;
for (i = 0; i < K; i++)
r->tab[i] = e1.tab[i] & e2.tab[i];
}
void unionS(SET e1, SET e2, SET *r)
{
int i;
for (i = 0; i < K; i++)
r->tab[i] = e1.tab[i] | e2.tab[i];
}
void complement(SET e, SET *r)
{
int i;
for (i = 0; i < K; i++)
r->tab[i] = ~e.tab[i];
}
void display(SET e)
{
int i;
printf("[ ");
for (i = 0; i < N; i++)
if (find(i, e))
printf("%d ", 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 !!
Binary tree rotations