Aniello Murano » 7.Implementazioni di Liste puntate

Indice

• Liste puntate semplici: Gli elementi sono organizzati in modo sequenziale e si possono scorrere in un unico verso. La lista ha un primo elemento (testa) e un ultimo elemento (coda)
• Liste doppiamente puntate: Simili alle liste puntate semplici, ma permettono di scorrere gli elementi in entrambi i versi
• Liste puntate semplici circolari: Sono liste puntate semplici senza testa ne coda.
• Liste doppiamente puntate circolari: Liste doppiamente puntate senza testa ne coda.

Torniamo al linguaggio C

Per l’implementazione delle liste in linguaggio C, possiamo utilizzare due importanti costrutti:

• STRUTTURE
• ALLOCAZIONE DINAMICA DELLA MEMORIA

Strutture

• La variabile “biblio” può essere dichiarata anche mettendo il nome stesso dopo la parentesi graffa:
• Inoltre, è possibile pre-inizializzare i valori, alla dichiarazione, mettendo i valori (giusti nel tipo) compresi tra parentesi graffe:
  • struct libro biblio = {“Guida al C”, “Fabrizio Ciacchi”, 2003, 45.2};
• Per accedere alle variabili interne della struttura si usa l’operatore “.”
  • Esempio: Per assegnare alla variabile interna prezzo il valore 50 usiamo biblio.prezzo = 50;

Nuovi tipi di dato

• Come per ogni altro tipo di dato, anche con “t_libro” si possono creare degli array:
  • t_libro raccolta[5000];
• Nel caso di array, per accedere ad un variabile interna, si utilizza l’indice insieme all’operatore punto (.)
  • Esempio: Per assegnare il prezzo 50 al libro con indice 10 usiamo raccolta[10].prezzo = 50;

Allocazione dinamica della memoria

A differenza di altri linguaggi, all’occorrenza il C permette di assegnare la giusta quantità di memoria alle variabili del programma.

Le funzioni utilizzate per gestire dinamicamente la memoria delle variabili sono principalmente:

• malloc() e calloc(), adibite all’allocazione della memoria;
• free() che serve per liberare la memoria allocata,
• realloc(), che permette la modifica di uno spazio di memoria precedentemente allocato.

Infine, un comando particolarmente utile è sizeof, che restituisce la dimensione del tipo di dato da allocare.

Queste funzioni sono incluse nella libreria malloc.h,

Esempio di allocazione dinamica

Rischi della gestione dinamica della memoria

Produzione di “garbage”:

• quando la memoria allocata dinamicamente resta logicamente inaccessibile, perché si sono persi i riferimenti:
• Esempio:
  • P=malloc(sizeof(TipoDato));
  • P=Q;

Riferimenti “dangling”(fluttuanti):

• quando si creano riferimenti a zone di memoria logicamente inesistenti
• Esempio:
  • P=Q; free(Q);
• l’istruzione free libera l’area di memoria ma non provoca un assegnamento automatico di NULL al puntatore Q, per cui P e Q si riferiscono perciò a celle di memoria non più esistenti

Operazioni sulle liste

Le operazioni che agiscono su un a lista rappresentano gli operatori elementari che agiscono sulle variabili di tipo lista

Corrispondono a dei sottoprogrammi (funzioni)

Alcune operazioni modificano la lista

Operazioni tipiche:

• Inizializzazione – modifica la lista
• Inserimento in testa – modifica la lista
• Inserimento in coda – modifica la lista
• Inserimento all’interno – modifica la lista
• Verifica lista vuota – non modifica la lista
• Ricerca elemento – non modifica la lista
• Stampa lista – non modifica la lista

Funzione crea_lista()

La funzione crea_lista() crea due puntatori ad elemento, uno di nome p (punta al primo elemento) e l’altro di nome punt (permette di scorrere la lista);

Funzione crea_lista()

Esempio di funzionamento di crea_lista

A questo punto inserendo il valore 12 per prima cosa viene creato un altro oggetto della lista, identificato con punt -> next,

poi “punt”, il puntatore ausiliario, viene fatto puntare, non più al secondo elemento, bensì al terzo, all’atto pratico “punt” diventa il puntatore dell’oggetto da lui puntato (cioè, punt = punt -> next;).

Quindi viene inserito il campo informazione dell’elemento tramite l’input da tastiera dell’utente; in questo caso viene inserito il valore 12;

Alla fine, punt punta al valore NULL che identifica la fine della lista.

Ricorsione su liste

La ricorsione risulta particolarmente utile sulle liste collegate. Questo è dovuto al fatto che le liste si possono definire in modo ricorsivo:

Una lista è la lista vuota, oppure un elemento seguito da un’altra lista.

In altre parole, una variabile di tipo lista L può valere NULL (che rappresenta la lista vuota), oppure può essere un puntatore a una struttura che contiene un dato più un altro puntatore. Possiamo quindi dire che la struttura è composta da un elemento e da un puntatore, che rappresenta un’altra lista.

Ricorsione su liste

La lista si ottiene guardando la struttura puntata e poi seguendo i puntatori fino a NULL.

Sia L una lista definita da

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

Una funzione ricorsiva su L avrà come argomento L, e al suo interno una chiamata ricorsiva a cui si passa L_next.

Queste funzioni normalmente operano su L_val (il primo elemento della lista), e poi agiscono sul resto della lista solo attraverso la chiamata ricorsiva.

Esercizio

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, raddoppi tutti gli elementi dispari della lista