Appunti Informatica

Inizializzazione:

• L'uso di un doppio puntatore che contiene l'indirizzo del puntatore ad una variabile della lista. Durante l'inizializzazione della lista collegata con puntatori, si assegna NULL al puntatore alla testa della lista.

Visita:

•• Ricerca:

Inserimento in testa:

La funzione pre_insert() deve modificare l'indirizzo del primo elemento della lista, allora deve conoscere l'indirizzo del puntatore che contiene l'indirizzo del primo elemento della lista. Il modo in cui viene modificato l'indirizzo del primo elemento della lista per il relativo inserimento in testa è illustrato e descritto come segue:

Vale la pena di soffermarsi ad osservare cosa avverrebbe se, anziché l'indirizzo del puntatore al primo elemento della lista, venisse passato l'indirizzo del primo elemento della lista illustrando il relativo errato inserimento in testa: la funzione WRONG pre_insert alloca un elemento della lista su una copia

a puntare il primo puntatore che contiene il valore NULL. Su questo puntatore viene effettuata la malloc() e viene attestato il nuovo elemento.

se la lista è vuota, il puntatore da modificare è quello che contiene l'indirizzo del primo elemento (come nel caso di un inserimento in testa). In generale, per effettuare tale operazione, la funzione ha quindi bisogno di conoscere l'indirizzo del puntatore alla testa della lista.

Rappresentazione di un inserimento in coda nel caso in cui la lista sia non vuota:

• INSERIMENTO IN ORDINE:

In generale non esiste modo di evitare il doppio puntatore a meno di fare ricorso al valore di ritorno della funzione. Questo conduce ad una implementazione che lascia al chiamante la responsabilità di aggiornare il puntatore di testa della lista:

In generale, lasciare al chiamante la responsabilità di aggiornamento sul valore di testa della lista aumenta l'accoppiamento tra funzioni rendendone più

L'elemento di coda su cui effettuare l'inserimento. Così facendo, il numero complessivo di elementi visitati nel corso della operazione di copia dell'intera lista è pari a c, dove c è il costo di esecuzione dell'operazione:

Per ridurre la complessità al tempo lineare è sufficiente che la funzione clone() mantenga un puntatore all'ultimo puntatore della lista clonata per passarlo alla funzione suf_insert() come origine dalla quale avviare la scansione:

Si evita dunque l'esecuzione del corpo del ciclo while nella funzione suf_insert() e il numero di elementi visitati risulta: 23/5

Iterazione e ricorsione.

La lista in forma collegata con puntatori offre una naturale occasione per discutere il meccanismo della ricorsione.

Definizione ricorsiva = fa riferimento a sé stessa, in modo diretto o per il tramite di ulteriori definizioni intermedie. Questo può avvenire nella definizione della struttura di un dato o nella

Definizione di una funzione. Ricorsione nei dati. La definizione della struttura struct list che rappresenta un elemento di una lista è ricorsiva perché include al suo interno il campo next_ptr che è un puntatore ad una struttura che è ancora del tipo struct list:

Nell'uso della ricorsione esistono alcune limitazioni. Primariamente devono essere note le dimensioni e i formati di ciascuno dei campi che compaiono nella definizione. Non risulta possibile includere nella definizione di una struttura un campo che sia esso stesso una struttura di formato non ancora definito. Come caso particolare, non è neppure legale il caso della definizione di una struttura che contiene un campo uguale a sé stesso poiché ciò risulterebbe in una allocazione di spazio non limitata:

La definizione di una struttura può invece contenere il puntatore ad una struttura non ancora definita (i.e., la cui definizione compare nel seguito del codice).

Rappresentazione del puntatore ha infatti la dimensione e il formato di un generico indirizzo, indipendente dal formato del tipo del particolare dato puntato. Questo è ad esempio il caso dell'indirizzo next_ptr che compare in modo ricorsivo all'interno della definizione di struct list:

Ricorsione nelle funzioni. La definizione di una funzione f() è ricorsiva quando essa delega parte della sua operazione ad una ulteriore istanza di f() stessa. Questo può avvenire in modo:

• diretto, quando il corpo di f() contiene un riferimento a f() stessa;
• indiretto, quando il corpo di f() contiene un riferimento a una funzione che, a sua volta, in modo diretto o indiretto fa riferimento a f().

La ricorsione si applica in modo naturale nell'esecuzione di una operazione applicata a un insieme di dati, come potrebbe essere quello di una operazione su una lista.

Nel caso di un insieme di dati, una forma ricorsiva si ottiene in modo naturale attribuendo alla

La responsabilità di trattare un singolo dato e delegando ad una sua ulteriore istanza il trattamento di tutti gli altri. Così facendo, le successive istanze nidificate ricevono la responsabilità di trattare un insieme di dati di dimensione strettamente decrescente fino a ridurre il problema al trattamento di un unico dato. Una condizione di guardia arresta la nidificazione delle chiamate quando l'insieme dei dati da trattare è esaurito.

Un semplice esempio è applicabile all'operazione di visita degli elementi di una lista collegata con puntatori. Visita in forma ricorsiva:

void visit_r(Lista* lista) {
    if (lista != NULL) {
        // stampa il valore corrente
        printf("%d ", lista->valore);
        
        // chiama ricorsivamente la funzione su quello successivo
        visit_r(lista->successivo);
    }
}

Dovendo stampare una sequenza di valori, visit_r() ne stampa uno e delega ad una ulteriore istanza di visit_r() stessa di stampare gli elementi a partire dal successivo di quello già stampato. La guardia dell'if determina la nidificazione quando l'operazione di visita viene invocata su una lista vuota.

Lo stesso paradigma è applicabile alle altre funzioni di manipolazione dei dati, come ad esempio la ricerca, l'ordinamento o la modifica. In ogni caso, l'utilizzo di una funzione ricorsiva permette di suddividere il problema in sottoproblemi più semplici da risolvere, fino a raggiungere il caso base in cui il problema è risolto in modo diretto.

operazioni che coinvolgono gli elementi di una lista collegata con puntatori, fatta eccezione per le operazioni di inizializzazione e inserimento in testa che coinvolgono un unico elemento.

• Ricerca in forma ricorsiva:
• Inserimento in coda in forma ricorsiva:
• Inserimento in ordine in forma ricorsiva:

Osservazioni sugli schemi ricorsivi e iterativi. Complessità spaziale e temporale.

In generale, lo schema ricorsivo incorre in un maggiore costo in termini di spazio di memoria e tempo di esecuzione, dovuto al diverso carico sullo stack di sistema rispetto allo schema iterativo. Tale fattore di costo aggiuntivo è la tipica ragione per cui soluzioni ricorsive non sono adatte a implementare operazioni che incidono significativamente sulla prestazione di un sistema.

ESEMPIO. Si consideri la forma iterativa e quella ricorsiva della visita degli elementi di una lista collegata con puntatori:

Al di là di considerazioni circa la naturalezza e l'eleganza delle diverse soluzioni,

è importante rimarcare come lo schema ricorsivo incorra in un maggiore costo in termini di spazio di memoria e tempo di esecuzione, dovuto al diverso carico sullo stack di sistema. Nello schema ricorsivo, l'esecuzione della visita comporta la nidificazione di un numero di istanze della funzione visit_r() pari alla lunghezza della lista. Per ogni istanza, sullo stack viene copiato l'indirizzo di ritorno della funzione e il valore dei parametri attuali; se ce ne fossero, sarebbero allocate anche le eventuali variabili locali dichiarate nel corpo della funzione.

Adattamento alla struttura dei dati. ➢ Gli schemi ricorsivi hanno talvolta una maggiore capacità di adattarsi alla struttura dei dati. Questo è la tipica ragione per cui, in molti casi, pur a costo di una minore efficienza di esecuzione, uno schema ricorsivo può risultare migliore.

In uno schema ricorsivo, l'effetto di invertire l'ordine di visita degli elementi si ottiene postponendo,

alladistribuzione del controllo mediante la chiamata ricorsiva, l'operazione printf() sul dato corrente:Ottenere lo stesso effetto in uno schema iterativo è più complesso. In questo caso, la soluzione migliore è quella di copiare i valori su una lista di appoggio che inverte la relazione di successione e poi scandire la lista di appoggio. La lista invertita si genera scandendo la lista originale e inserendo in testa alla lista di appoggio:

Rispetto allo schema ricorsivo emerge il fatto che la lista di appoggio richiede uno spazio di memoria proporzionale alla dimensione della lista. Tuttavia, si osserva che anche la soluzione ricorsiva incorre nella stessa occupazione di memoria: in quel caso gli elementi visitati e non ancora stampati a video sono memorizzati come parametri formali sullo stack di sistema; quando la ricorsione raggiunge la sua massima nidificazione, sullo stack sono copiati gli indirizzi di tutti i nodi della lista. L'implementazione ricorsiva

haperò il pregio di rendere trasparente al programmatore la memorizzazione delle variabili int