Concetti Chiave
- Il tipo Insieme è composto da elementi astratti di tipo Elemento e offre operazioni come inizializzazione e accesso tramite array.
- Le funzioni inizializza(), cardinalità(), confronta(), copia(), aggiungi() e ricerca() gestiscono le operazioni di base sugli insiemi.
- I prototipi delle funzioni in C includono la direzionalità dei parametri: output (O) e input (I).
- La funzione unione() crea un nuovo insieme contenente gli elementi di due insiemi senza duplicati.
- La funzione intersezione() genera un insieme con elementi comuni a due insiemi, evitando duplicati.
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.
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
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
aggiungi (&ris, &(a));
return ris;
}
Insieme set1, set2;
Insieme risultato;
…..
risultato = intersezione(&set1, &set2); // I - I
Domande da interrogazione
- Quali sono le funzioni principali per gestire un insieme di elementi astratti?
- Come si implementa l'unione di due insiemi senza duplicati?
- Qual è il ruolo della funzione confronta() nel contesto degli insiemi?
- Come si determina l'intersezione di due insiemi?
Le funzioni principali sono inizializza(), cardinalità(), confronta(), copia(), aggiungi() e ricerca().
Si inizializza un nuovo insieme, si copiano gli elementi del primo insieme e si aggiungono gli elementi del secondo insieme solo se non sono già presenti.
La funzione confronta() verifica se due elementi sono uguali, restituendo 0 se lo sono, simile a strcmp().
Si crea un nuovo insieme e si aggiungono gli elementi che sono presenti in entrambi gli insiemi originali.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
