Esercitazione 1
Esercizio 1: alberi binari ordinati
Scrivere un programma C che realizzi degli alberi binari ordinati di interi. Gli alberi binari ordinati sono tali che il valore memorizzato in un nodo è minore o uguale di tutti quelli memorizzati nel sottoalbero destro e maggiore o uguale di tutti quelli memorizzati nel sottoalbero sinistro.
Definire il tipo nodo che rappresenta il nodo generico dell'albero in modo opportuno. Si richiede di implementare almeno:
inserisci() che permette di inserire un nuovo intero nell'albero
cancella() che permette di cancellare un intero (se presente)
cerca() che permette di stabilire se un intero e' presente nell'albero
stampa() che stampa in modo ordinato tutti i valori di un albero
main() che effettua un opportuno testing delle funzioni implementate
Esercizio 2: compilazione separata e makefile
Suddividere il programma C relativo all'esercizio 1 in piu' file in modo che:
Sviluppare inoltre un opportuno makefile che contenga almeno i seguenti target:
all che permette di ricreare l'eseguibile di test
test test che esegue il test e confronta l'output con l'output atteso segnalando opportuni errori
cleanall che elimina i file di core e gli oggetti della compilazione.
Esercizio 3: map e reduce su alberi ordinati
Si considerino gli alberi ordinati degli esercizi 1 e 2: si realizzino due funzioni map_albero e reduce_albero:
La map_albero applica una funzione f (di tipo int (*f)(int))a tutti gli interi sull'albero sostituendo ogni intero x con f(x).
La reduce_albero 'somma' tutti gli interi nell'albero con l'operatore associativo (*f), di tipo int (*f)(int,int)
Definire inoltre un opportuno main di test ed estendere il makefile (ove necessario).