-
[R1] Si scriva 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 è presente
nell’albero
- stampa()
che stampa in modo ordinato tutti i valori di un albero
- main()
che effettua un opportuno testing delle funzioni implementate
-
[R1a] Si suddivida il programma C relativo al precedente esercizio
in modo tale che
- il main() sia contenuto
in un file a parte rispetto alle altre funzioni
- siano presenti due file .c e .h per le altre funzioni
(inserisci/cancella/cerca)
Si sviluppi inoltre un opportuno
makefile
che contenga almeno i seguenti target
- all che permette di
ricreare l’eseguibile di 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
Soluzione parziale: gli header
def_albero.h e
fun_albero.h,
i programmi
fun_albero.c e
main_albero.c (tracce).
- [R1b] Si consideri infine la struttura di albero ordinato
definita negli esercizi precedenti, e si realizzino due funzioni
map_albero e
reduce_albero tali che
-
map_albero applica una funzione
fun (di tipo
int (*fun) (int))
a tutti gli interi presenti nell’albero, sostituendo ogni intero
x con
fun
- reduce_albero applica agli
interi presenti nell’albero la funzione associativa
fun2 (di tipo
int (*fun2) (int,int))
Definire inoltre un opportuno
main() di test ed estendere
il makefile
(ove necessario).
|
