Prototipi e implementazione di operazioni su insiemi astratti in C

Unione e intersezione di due insiemi di elementi astratti Supponiamo di disporre di un tipo Insieme composto da elementi astratti di tipo Elemento (non dovete definirlo). Ogni insieme è implementato internamente con un array e ha le seguenti caratteristiche:

· è possibile accedere ai suoi elementi e percorrerli con l’operatore [ ], con indice che parte da zero

· esiste una funzione che inizializza() l'insieme e una che restituisce la sua cardinalità() (numero di elementi)

· esiste una funzione che confronta() due elementi e dice se sono uguali (non si può usare l’operatore di uguaglianza tra interi)

· esiste una funzione che copia() in un insieme tutti gli elementi di un altro insieme (in una sola operazione)

· esiste una funzione aggiungi() che permette di aggiungere un elemento a un insieme

· esiste una funzione ricerca() che permette di determinare se un certo Elemento è presente in un Insieme.

Prototipi delle funzioni in C

1. Dichiarate in C i soli prototipi (senza implementazione!) delle funzioni inizializza(), cardinalità(), confronta(), copia(), aggiungi() e ricerca(), facendo MOLTA attenzione alla modalità di passaggio dei parametri. Indicare anche la direzionalità.

void inizializza (Insieme * set); //O

int cardinalità (const Insieme *set); //I

int confronta (const Elemento *primo, const Elemento *secondo); //I - I

/* Come strcmp() restituisce 0 se uguali, 0 se primo > secondo.

Alternativamente si poteva usare un boolean per verificare la sola (dis)uguaglianza */

void copia (Insieme * destinazione, const Insieme * sorgente); //O - I

void aggiungi (Insieme * set, const Elemento *elem); //O - I

boolean ricerca (const Insieme *set, const Elemento *elem); //I - I

//volendo poteva anche restituire un int

Sfruttando le funzioni dichiarate qui sopra, dichiarate i prototipi, scrivete il codice C che implementa le operazioni di unione() e intersezione() di due insiemi e la chiamata. Attenzione perché in un insieme NON si devono inserire elementi duplicati!

Implementazione delle operazioni di unione

unione()

Insieme unione (const Insieme *a, const Insieme *b)

{

Insieme ris;

int i;

inizializza (&ris);

copia (&ris, a)

for (i=0; i

if (ricerca (&ris, &(b)) == false) //se non c’è già lo aggiungo

aggiungi (&ris, &(b));

return ris;

}

Insieme set1, set2;

Insieme risultato;

…..

risultato = unione(&set1, &set2); // I – I

-----------------------------------------------------------------------------------------------

Implementazione delle operazioni di intersezione

intersezione()

Insieme intersezione (const Insieme *a, const Insieme *b)

{

Insieme ris;

int i;

inizializza (&ris);

for (i=0; i

if (ricerca (b, &(a)) == true) // se è presente in entrambi gli insiemi lo aggiungo

aggiungi (&ris, &(a));

return ris;

}

Insieme set1, set2;

Insieme risultato;

…..

risultato = intersezione(&set1, &set2); // I - I