Esercitazioni Anno Accademico 2004-05 (RobertoNavigli)

Di seguito sono riportati gli argomenti delle esercitazioni del corso. Cliccando sui collegamenti ipertestuali è possibile accedere al codice sorgente di tutti gli esercizi svolti a lezione, più qualcun altro che non abbiamo avuto il tempo di vedere insieme (determinazione di uno heap, visita in-order iterativa, ecc.). Molti dei file contenenti esercizi fanno uso dei file .h che dichiarano i prototipi dei vari tipi di dato (liste, pile, code, alberi), che devono quindi trovarsi nella medesima cartella, per la compilazione. Per il linking (eseguito a seguito della compilazione) è necessario invece avere a disposizione i file oggetto (.o o .obj) delle funzioni di gestione delle strutture utilizzati dai vari file .c. Più semplicemente, se si usa gcc, è possibile compilare un file x.c che dipende da un altro file y.c con il comando:

• gcc x.c y.c

Ad esempio, l'esercizio sul bilanciamento delle parentesi fa uso delle funzioni sulle pile, implementate mediante liste. Per compilarlo è sufficiente digitare:

• gcc parentesi.c pila2.c list.c

Lezione del 18/3/2005

• Lettura del contenuto di primo livello di file e cartelle; Lettura ricorsiva

Lezione del 1/4/2005

• Richiami sui puntatori
• Confronto tra stringhe
• Il tipo lista:
  • Definizione del tipo di dato e prototipi
  • Inserimento, cancellazione, lista vuota, ricerca, stampa

Lezione del 15/4/2005

• Il tipo hash:
  • Hash a indirizzamento lineare aperto
  • Hash concatenati

Lezione del 22/4/2005

• Il tipo pila:
  • Implementazione mediante array (prototipi, operazioni push, pop, top)
  • Implementazione mediante liste (definizione del tipo di dato e prototipi, operazioni push, pop, top)
    • Bilanciamento di parentesi
    • Trasferimento da una pila all'altra mantenendo l'ordinamento (versione iterativa, versione ricorsiva)
• Il tipo coda:
  • Implementazione mediante liste (definizione del tipo di dato, operazioni add, remove, top)
    • Inversione dell'ordine degli elementi in una pila mediante l'uso di una coda

Lezione del 29/4/2005

• Ricorsione:
  • Ricerca ricorsiva di un carattere all'interno di una stringa
  • Numeri di Fibonacci (confronto della versione ricorsiva con la versione iterativa)
• Albero binari: esercizi
  • Visita in-order, pre-order, post-order
  • Visita per livelli
  • Valore massimo dei nodi di un albero
  • Ricerca di un valore in un albero
  • Profondità di un albero
  • Numero nodi di un sottoalbero

Lezione del 13/5/2005

• Ricorsione: esercizi
  • Sostituzione di ciascun elemento x di una lista con la somma degli elementi della sottolista con testa x
  • Inversione ricorsiva di una lista
  • Lista come prefisso di un'altra lista
  • Restituzione della coda di una lista avente come prefisso un'altra lista
  • Creazione della lista degli elementi pari e della lista degli elementi dispari di una lista in input
• Albero binari: esercizi
  • Bilanciamento
  • Somma dei valori nel cammino da ciascun nodo alla radice
  • Altezza minimale di un albero
  • Creazione della lista dei nodi di livello k
  • Alberi completi
  • Numero di nodi in un albero con k discendenti

Lezione del 20/5/2005

• Ricorsione: Fusione di due liste ordinate
• Alberi n-ari:
  • Definizione del tipo di dato
  • Rappresentazione mediante alberi binari
  • Conversione da alberi n-ari ad alberi binari
  • Conversione da alberi binari ad alberi n-ari

Lezione del 27/5/2005

• Ricorsione:
  • Intersezione di due liste ordinate
  • Verifica dell'esistenza di un cammino da (x, y) a (x', y') in un labirinto a matrice
• Mutura ricorsione:
  • Somma degli elementi dispari di una lista e sottrazione degli elementi pari
  • Inserimento in una lista dei nodi di altezza pari in un albero
• Liste circolari:
  • Conteggio degli elementi di una lista circolare
  • Inserimento di un nuovo elemento in una lista circolare
• Alberi binari di ricerca:
  • Ricerca di una chiave
  • Verifica della proprietà di ricerca
• Alberi binari: Valore minimo e massimo nel percorso dalla radice alla foglia

-- RobertoNavigli - 28 May 2005