Home

Federica EU

1/12

Salvatore Cuomo » 20.Esercizi Strutture dati di tipo astratto

Le liste

Definizione

La Lista Lineare é una struttura estremamente flessibile, il numero dei nodi componenti può essere modificato dinamicamente.

La Lista si può identificare con un elenco, di cui è possibile variare sia la lunghezza che l’ordine.

Nella lista lineare l’ordinamento logico dei nodi non necessariamente corrisponde a quello fisico.

Ogni nodo della struttura è una coppia:

( informazione, puntatore )

Il primo elemento contiene l’informazione
Il secondo contiene l’indirizzo del nodo successivo secondo l’ordinamento logico

Liste 1.

Le liste

Fisicamente una lista è una successione di nodi che occupano in memoria posizioni generiche.

L’accesso ad un nodo può avvenire solo per scansione dell’intera lista, poiché non può essere noto a priori il suo indirizzo.

Si osservi ad esempio che in un array, invece, ogni componente è accessibile direttamente perché identificato univocamente all’indice.

L’accesso al primo nodo della lista avviene attraverso un puntatore p0. L’ultimo nodo ha un simbolo speciale, nel campo indirizzo, di solito lo zero, per indicare la fine della lista.

Liste 2.

Definizione di una lista in C

Una lista può essere definita attraverso una struttura di tipo nodo come segue;

typedef struct nodo *nod_punt; struct nodo{

real data; nod_punt next;

}

Per creare un nodo bisogna allocare memoria attaverso l’utilizzo di funzioni create allo scopo.

nod_punt crea_nodo(real valore){ nod_punt new_punt; new_punt=(nod_punt)malloc(sizeof(struct nodo)); If (new_punt != NULL){

new_punt->data = valore; new_punt->next = NULL;

}

return new_punt; }

Rimozione di un nodo da una lista in C

In figura viene mostrata una procedura per la rimozione di un nodo da una lista. Per eliminare un nodo un nodo bisogna allocare memoria attraverso l’utilizzo di funzioni create allo scopo.

nod_punt elimina_nodo(nod_punt pnt); { If (pnt != NULL) { pnt = pnt->next; } return pnt; }

Si osservi che:

Nel caso della cancellazione si può utilizzare una variabile found per indicare se l’elemento cercato è presente nel nodo puntato da curr.
Nel caso dell’inserimento, il nodo da inserire andrà tra i nodi puntati da prev e da curr.

Esempio 1

In figura viene mostrata l’ eliminazione del nodo contenente “B” LIST2 in una lista di alfanumerici. Viene modificato solo il valore del puntatore del primo nodo. Si osservi che Il nodo contenente “B” non viene eliminato fisicamente.

Procedura Pascal

Esempio 2

In figura viene mostrata l’inserimento di un nodo al secondo posto di LIST: lista lineare di reali. Sono modificati i valori dei puntatori del primo nodoche adesso punterà al nodo inserito e di quest’ultimo che conterrà il vecchio indirizzo del primo nodo.

Schema Lista.

Esercitazione

La pila: funzioni principali

La funzione int size(TipoStack *s), ritorna la lunghezza della pila.

La funzione void destroy(TipoStack *s), distrugge la la memoria allocata per la pila

La funzione void deleteElement(TipoStack *s, tipoElemento data), elimina un elemento della pila medinante la definizione delle operazioni ammesse per una pila: inserimento e prelievo dei dati solo dalla cima (top) della struttura