Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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.

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.

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

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.

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
Codice_C_1

Codice_C_1

Codice_C_2

Codice_C_2


La Pila versione dinamica

Esempio

Nel seguito si implementa un programma in Linguaggio C per la gestione delle pile utilizzando elementi di una LISTA dinamica.

La definizione di un elemento della PILA avviene mediante una dichiarazione del tipo:

struct ele{

int data;
struct ele *next; };

Mentre lo Stack si definisce come:

typedef struct{

int count;
elem *top;

}stack;

La Pila versione dinamica cont

Esempio

  • Il programma principale ha inizio con l’inizializzazione.
  • Della strutturaa stack mediante le direttive: vedi figure.
Codice_C_3

Codice_C_3

Codice_C_4

Codice_C_4


La Pila versione dinamica cont

Esempio
Il programma principale è strutturato in diversi moduli che di seguito verranno analizzati.

  • La funzione void show(stack vstack), mostra gli elementi nello stack.
  • La funzione void push(stack * vstack), inserisce gli elementi nello stack
  • La funzione void pop(stack * vstack), elimina un elemento dallo Stack.
Codice_C_5
Codice_C_6

La Pila versione dinamica cont

Esempio

Il programma principale è strutturato in diversi moduli che di seguito verranno analizzati.

  • La funzione void delete(stack * vstack), cancella elementi dallo stack liberando memoria.
  • La funzione void top(stack vstack), restituisce la cima dello Stack.
  • La funzione void isempty(stack vstack), verifica se lo Stack è vuoto.
Codice_C_7

Codice_C_7

Codice_C_8

Codice_C_8


La Pila versione dinamica cont

Esempio

Il programma principale è strutturato in diversi moduli che di seguito verranno analizzati.

  • La funzione void isfull(stack vstack), verifica se lo Stack è pieno.
  • La funzione void size(stack vstack), restituisce la dimensione dello Stack.
Codice_C_9

Codice_C_9


I materiali di supporto della lezione

Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition.

Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238--243.

salvatore-cuomo-4608-20-esercizi.zip

Nick Parlante, LinkedListBasics

Nick Parlante, LinkedListProblems

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion