Università degli Studi di Milano	Polo Didattico e di Ricerca di Crema	Dipartimento di Tecnologie dell'Informazione
Home page	Teaching page

Terzo laboratorio

Consigli: cominciate a ragionare sulle strutture dati e sulle procedure del main. Faremo stretto riferimento alla corrispondente lezione del corso di Algoritmi e Strutture Dati (solo la parte sugli alberi binari), ma sarà necessario implementare anche funzioni non descritte in essa

• Il problema: Dynasty
• Esempio di input: l'albero genealogico dei Medici
• L'esempio di input in forma grafica
• Prima approssimazione: struttura generale del programma e definizione delle strutture dati
• Seconda approssimazione: interpretazione della linea di comando, procedura di creazione di un albero, accesso alla radice e verifica se l'albero è vuoto
• Terza approssimazione: caricamento delle relazioni di discendenza e costruzione di un albero fittizio, che aggiunge ogni successivo personaggio come figlio del precedente; stampa del relativo albero genealogico in in-ordine e deallocazione dell'albero al termine
• Quarta approssimazione: correzione del caricamento dei dati, in modo che l'albero venga costruito tenendo conto delle relazioni di discendenza (procedura di ricerca del padre nell'albero corrente)
• Quinta approssimazione: calcolo delle date di ascesa al trono e stampa della lista dei sovrani
• Sesta approssimazione: calcolo del numero di discendenti (e di discendenti sovrani) di ogni personaggio e stampa
• Esercizio per casa: è possibile evitare l'uso della funzione appendenodo nella costruzione dell'albero genealogico, purché si mantenga una lista dinamica degli alberi definiti sinora. Tale lista può essere visitata ad ogni nuova relazione di discendenza, per fondere fra loro sottoalberi diversi con la funzione di base costrbinalbero. Questo permette anche di gestire il caso in cui l'input fornisce simultaneamente più alberi genealogici disgiunti tra loro. Implementare la variante.

Pagina aggiornata il