Aniello Murano » 8.Esercitazione di laboratorio su Liste Puntate Semplici

Operazioni sulle liste

Nella precedente lezione abbiamo visto l’implementazione delle seguenti operazioni su liste

• Inizializzazione
• Inserimento in coda
• Verifica lista vuota
• Stampa lista

Oggi implementeremo inoltre le seguenti operazioni

• Ricerca elemento
• Inserimento elemento
• Cancellazione di un elemento

Esercizio I: Ricerca di un elemento

Sia L una lista definita da

struct lista {int val; struct lista *next;} L;

Scrivere in linguaggio C una funzione ricorsiva che preso in input L e un intero el, verifichi se esiste una occorrenza di el nella lista

Idea per la soluzione dell’esercizio:

Scorrere in avanti la lista in chiamate ricorsive e

• Se L=NULL, ritornare 0
• se L_val=el, ritornare 1

altrimenti, ritornare il risultato della chiamata ricorsiva su L->next

Esercizio II: Rimozione di un elemento

Sia L una lista definita da

struct lista {int val; struct lista *next;} L;

Scrivere in linguaggio C una funzione ricorsiva che preso in input L e un intero el, rimuova una ricorrenza di el dalla lista (se ne esiste una).

Idea per la soluzione dell’esercizio:

Scorrere in avanti la lista in chiamate ricorsive e

• se L=NULL, ritornare L
• se L_val=el, settare L=L_next e ritornare L
• altrimenti, associare a L_next il risultato della chiamata ricorsiva su L_ next e al ritorno dalla chiamata ricorsiva restituire L.

Esercizio III: Aggiunta di un elemento

Sia L una lista definita da

struct lista {int val; struct lista *next;} L;

Scrivere in linguaggio C una funzione ricorsiva che preso in input L, la modifichi in modo tale che ogni numero dispari sia seguito dal suo successore pari.

Idea per la soluzione dell’esercizio:

• Dapprima scorrere la lista fino alla coda conchiamate ricorsive
• Condizione di uscita: Se L=NULL, ritornare L

Al ritorno dalle chiamate ricorsive:

• Se L_val è disapri aggiungere un nuovo nodo tra L e L->next. Attenzione qui a sistemare tutti i collegamenti!!!

Ritornare la lista L.

Esercizio completo (da consegnare)

Si implementi in linguaggio C un menù di scelta multipla per la gestione “con funzioni ricorsive” di tutte le operazioni viste in precedenza. Dunque il menù permettere le seguenti operazioni:

• Creazione di una lista a puntatori (con il comando struct) e successivo riempimento della lista con n elementi dati in input
• Stampa della lista
• Ricerca di un elemento,
• inserimento (in coda o dopo un elemento specifico)
• rimozione della prima occorrenza di un elemento dato in input
• Ricerca e stampa del massimo e del minimo della lista

L’esercizio completo va consegnato via mail al tutor entro 5 giorni lavorativi.