nikpez di nikpez
Ominide 738 punti

ADT - Esercizio

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.

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

unione()
Insieme unione (const Insieme *a, const Insieme *b)
{
Insieme ris;
int i;
inizializza (&ris);
copia (&ris, a)
for (i=0; i<cardinalità(b); 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

-----------------------------------------------------------------------------------------------
intersezione()
Insieme intersezione (const Insieme *a, const Insieme *b)
{
Insieme ris;
int i;
inizializza (&ris);
for (i=0; i<cardinalità(a); 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

Registrati via email