Home

Federica EU

1/25

Valeria Vittorini » 12.Esercitazione: Strutture Dati Pila e Coda

Progettazione della Struttura Dati “Pila”

La Pila è una struttura dati utilizzata per rappresentare un elenco di elementi (dello stesso tipo) gestiti secondo una logica LIFO, il comportamento atteso e le funzionalità da fornire sono pertanto quelle specificate nella precedente lezione.
Detto “Pila” il tipo pila, e T il tipo degli elementi da gestire, la progettazione dell’interfaccia è riassunta in figura.
Le operazioni sono descritte come funzioni. Ad esempio, la notazione relativa alla funzione Push: Pila x T -> Pilasignifica che per ogni coppia (p,t) dove p è una pila e t è di tipo T, Push(p,t)=p’, dove p’ appartiene al tipo Pila.

Progettazione dell'interfaccia della struttura dati Pila

Progettazione dell’interfaccia della struttura dati Pila

L’operazione Start genera una pila vuota. La sua implementazione dipende dalla rappresentazione utilizzata: nel caso in cui la struttura dati è una struttura rappresentata mediante un array allocato dinamicamente Start avrà anche il compito di allocare lo spazio necessario alla memorizzazione della struttura. Nel caso in cui ciò non sia necessario, Start ha solo il compito di inizializzare lo stato della pila.

La funzionalità relativa alla distruzione della Pila deve essere fornita se la rappresentazione utilizzata è dinamica, quindi nel caso di rappresentazione mediante array allocato dinamicamente o nel caso di rappresentazione mediante catena a puntatori. Pertanto non è riportata in questa fase di progettazione.

Si noti che nella progettazione proposta, il predicato Empty deve essere utilizzato per accertarsi che la pila non sia vuota prima di effettuare le operazioni Pop e Top. Lo stesso dicasi del predicato Full che deve essere utilizzato per accertarsi che vi sia spazio disponibile nella pila prima di effettuare una operazione di Push.

Progettazione della Struttura Dati “Coda”

La Coda è una struttura dati utilizzata per rappresentare un elenco di elementi gestiti secondo una logica FIFO, il comportamento atteso e le funzionalità da fornire sono pertanto quelle specificate nella precedente lezione.

Detto “Coda” il tipo coda, e T il tipo degli elementi da gestire, la progettazione dell’interfaccia è riassunta in figura.

Anche in questo caso le operazioni sono descritte come funzioni. Ad esempio, la notazione relativa alla funzione Append: Coda x T -> Coda significa che per ogni coppia (c,t) dove c è una coda e t è di tipo T, Append(c,t)=c’, dove c’ appartiene al tipo Coda.

Progettazione dell'interfaccia della struttura dati Coda

Progettazione dell’interfaccia della struttura dati Coda

L’operazione Start genera una coda vuota. La sua implementazione dipende dalla rappresentazione utilizzata: valgono le stesse considerazioni effettuate per la pila.

Come già per la struttura dati Pila, a funzionalità relativa alla distruzione della Coda deve essere fornita nel caso in cui la rappresentazione utilizzata è dinamica, pertanto non è riportata in questa fase di progettazione.

Si noti che nella progettazione proposta, il predicato Empty deve essere utilizzato per accertarsi che valga la precondizione “coda NON vuota” prima di effettuare le operazioni Remove e Front. Analogamente, il predicato Full deve essere utilizzato prima di effettuare una operazione di Append per accertarsi che vi sia spazio disponibile nella coda per inserire un nuovo elemento.

Rappresentazione della struttura dati

La rappresentazione utilizzata per realizzare la struttura dati è una scelta di progetto delicata perché può influenzare significativamente le prestazioni del programma a seconda del contesto in cui deve operare.
La complessità computazionale degli algoritmi non è un tema trattato in questo corso, ma faremo alcune considerazioni relative ai vantaggi/svantaggi delle diverse rappresentazioni qui considerate dopo aver introdotto le catene di puntatori.
Nel seguito di questa lezione implementiamo le strutture dati Pila e Coda basandoci su una rappresentazione mediante array. Svilupperemo le strutture dati:
- mediante array monodimensionale di dimensione fissa nota a tempo di compilazione (che con abuso di notazione nel seguito chiameremo per brevità “array statico”);
- mediante array monodimensionale di dimensione fissa allocato dinamicamente.

Pila: rappresentazione con array “statico”

La struttura dati è costituita da:
- Array monodimensionale (vettore) di dimensione massima N nota a tempo di compilazione.
- Variabile di tipo intero che mantiene la posizione nel vettore successiva a quella dell’elemento di testa, cioè a quella dell’ultimo elemento inserito. Nel seguito ci riferiremo a questa informazione come all’”indice-puntatore” alla prima posizione “libera” nel vettore.
La struttura dati deve preservare l’ordine di inserimento degli elementi
Nella prossima figura, detto p il vettore e t l’indice-puntatore, è riportato il codice che realizza la logica LIFO.

Pila - realizzazione delle funzionalità (array "statico")

Osservazioni

La funzione Start inizializza la pila ponendo t a zero. Infatti quando la pila è vuota la prima posizione disponibile nel vettore per l’inserimento è la posizione di indice zero.
La funzione Push inserisce un elemento “e” memorizzandolo nel vettore in posizione t, indice della prima posizione libera disponibile nel vettore. L’elemento inserito diviene l’elemento di testa nella pila. E’ importante che dopo l’inserimento t venga aggiornato in modo da mantenere il valore dell’indice relativo alla posizione successiva nel vettore, che è diventata la prima posizione disponibile
La funzione Pop estrae l’elemento di testa dalla pila e lo assegna alla variabile “e” (in modo che il suo valore possa essere eventualmente reso disponibile). Per effettuare l’estrazione è necessario decrementare l’indice-puntatore t in modo da accedere alla posizione dell’elemento di testa della pila. Si noti che l’elemento non viene fisicamente cancellato dal vettore (si renderebbe necessaria una operazione di compattamento) ma semplicemente verrà sovrascritto alla prossima operazione di Push, poichè l’indice-puntatore t ora segnala che la posizione è libera.
La funzione Top consente l’analisi dell’elemento affiorante, cioè assegna alla variabile “e” il valore dell’elemento di testa nella pila, rendendolo disponibile, senza modificare la pila. Si noti infatti che l’espressione t-1 serve a valutare l’indice della posizione a cui accedere nel vettore, ma non modifica t.
La funzione Empty valuta l’espressione logica t==0 che avrà valore true se la pila è vuota (l’indice puntatore dice che la prima posizione libera è la posizione di indice zero del vettore), false altrimenti.
La funzione Full valuta l’espressione logica t==N che avrà valore true se la pila è piena (l’indice puntatore vale N, ma l’ultima posizione valida nel vettore è N-1 ), false altrimenti.

Implementazione della Pila (array “statico”): struttura dati

Raffiniamo ora ulteriormente la realizzazione della struttura dati Pila fino ad ottenere una sua implementazione.
La definizione del tipo Pila può essere quella in figura.
Si noti l’uso di una struttura record per la definizione del tipo Pila. Il record consente infatti di associare al vettore usato per la memorizzazione degli elementi (il campo vettore P) il relativo indice-puntatore (il campo intero t). T è il tipo degli elementi contenuti nella Pila, N è la dimensione massima del vettore (costante intera).

Struttura Dati Pila

Implementazione della Pila (array “statico”): Interfaccia

La figura mostra il file header “Pila.h” contenente:

La dichiarazione del tipo T (è una pila di interi).
La dichiarazione della costante N.
La definizione della struttura dati Pila.
L’interfaccia esportata (come definita in fase di progettazione).

Header file "Pila.h"

Implementazione della Pila (array “statico”): definizione delle funzioni

La figura mostra il file “Pila.cpp” contenente il corpo del modulo e l’inclusione testuale del file header “Pila.h”.
Si noti che – avendo optato per l’utilizzo di un record nella definizione della struttura dati- è necessario utilizzare la notazione . (punto) per l’accesso ai singoli campi (P e t).

file di implementazione "Pila.cpp"

Utilizzo della struttura dati

In figura è mostrato un programma di prova della struttura dati appena realizzata e l’output ottenuto dalla sua esecuzione. Il modulo utente:

Importa le funzionalità esportate dal modulo Pila (#include “Pila.h”).
Definisce una o più variabili di tipo Pila ().
Utilizza su di esse le funzionalità disponibili, adottando una disciplina di programmazione secondo la quale non accede alla struttura dati se non attraverso le funzionalità messe a disposizione dall’interfaccia (ma potrebbe farlo, il compilatore non gli impedirebbe –ad esempio- di modificare il valore dell’indice puntatore in maniera incontrollata, o di modificare il vettore…).

Esempio d'uso della struttura dati Pila

Pila: rappresentazione con array allocato dinamicamente

La struttura dati è costituita da:
- Un puntatore al tipo T degli elementi (che punterà al primo elemento del vettore allocato dinamicamente)
- Una variabile intera n che serve a mantenere la dimensione del vettore
- Variabile di tipo intero che mantiene la posizione nel vettore successiva a quella dell’elemento di testa, cioè a quella dell’ultimo elemento inserito. Nel seguito ci riferiremo a questa informazione come all’“indice-puntatore” alla prima posizione “libera” nel vettore.

La definizione del tipo Pila può essere quindi quella in figura:

Struttura Dati della Pila

Implementazione della Pila (array allocato dinamicamente): Interfaccia

La figura mostra il file header “Pila.h” contenente:
- La dichiarazione del tipo T (è una pila di interi).
- La definizione della struttura dati Pila.
L’interfaccia esportata (come definita in fase di progettazione).
Si noti che l’interfaccia delle funzioni che implementano la logica LIFO non viene modificata al cambiare della rappresentazione.
E’ necessario aggiungere la funzionalità Destroy al fine di consentire all’utente di deallocare il vettore allocato dinamicamente.
Rispetto all’header precedente, le modifiche introdotte sono le seguenti:
- Non è definita la costante N (non serve più).
- La definizione della struct è modificata nella dichiarazione del campo P e nell’aggiunta della variabile n.
- La funzione Start consente all’utente di specificare la dimensione desiderata per la pila a tempo di esecuzione.
- È aggiunto il prototipo void destroy(Pila &).

Header file "Pila.h"

Implementazione della Pila (array allocato dinamicamente): definizione delle funzioni

L’implemetazione delle funzionalità che realizzano la logica LIFO resta invariata, l’unica differenza essendo la natura dinamica del vettore
La funzione Start ha ora anche il compito di inizializzare la variabile n e di allocare lo spazio in area heap per il vettore
La funzione Full effettua il controllo basandosi sulla variabile n
La funzione Destroy dealloca lo spazio allocato da Start, pone a 0 il puntatore e azzera il valore delle variabili t ed n.
NOTA IMPORTANTE: Sarebbe possibile mantenere invariata l’interfaccia della funzione Start utilizzando per la rappresentazione un array dinamico ridimensionabile. In questo caso però sarebbe necessario ridimensionare l’array ogni volta che viene effettuata una operazione di Push o di Pop.
Le funzioni Push e Pop dovrebbero invocare una funzione per il ridimensionamento del vettore ed essere quindi implementate in modo diverso (mentre la loro interfaccia continuerebbe a rimanere invariata).

file di implementazione "Pila.cpp"

Utilizzo della struttura dati

L’utilizzo da parte dell’utente della struttura dati Pila non cambia, tranne che:

nella invocazione della procedura start, alla quale va passato oltre alla variabile di tipo Pila anche un numero intero indicante la dimendione del vettore. Ad esempio: start(P1,3);
nella aggiunta della chiamata alla procedura Destroy, che deve essere invocata quando si intende che il ciclo di vita della variabile di tipo Pila venga terminato, ad esempio destroy(P1).

Coda: rappresentazione con array “statico”

Un modo semplice di realizzare una coda è rappresentarla in modo da preservare l’ordine di inserimento degli elementi, come già fatto per la pila
Tale rappresentazione rende facile l’inserimento che deve avvenire sempre in coda (cioè nella posizione successiva a quella occupata dall’ultimo elemento inserito nell’array) ma richiede che a seguito di ogni prelievo il vettore venga compattato, in modo da poter riutilizzare in coda lo spazio liberatosi in testa.

Coda: rappresentazione con array “statico” (segue)

Per rendere più efficiente e meno complicata l’operazione di prelievo è possibile adottare una gestione “circolare” degli elementi (nel rispetto della logica FIFO): il vettore viene visto come se fosse una struttura “ciclica” in cui – detta N la dimensione massima del vettore – è possibile definire:
- L’elemento successivo all’elemento di posizione N-1 come l’elemento di posizione 0.
- L’elemento precedente al’elemento di posizione 0 come l’elemento di posizione N-1.
Questo richiede di abbandonare l’idea che la posizione dell’elemento da estrarre sia sempre la posizione “zero” del vettore
Utilizziamo quindi un indice-puntatore (sia “testa”) per indicare la posizione del primo elemento della coda e un indice-puntatore (sia “coda”) per indicare la posizione di inserimento del prossimo elemento nella coda.

In figura è riportato un esempio di coda circolare.

Esempio di Coda Circolare

Con riferimento alla figura precedente: sia N=4. c e t rappresentano rispettivamente l’indice-puntatore alla posizione di inserimento e l’indice-puntatore all’elemento di testa.

Figura a) rappresenta una coda di interi contenente due elementi (5,40)
Figura b) rappresenta lo stato della coda in seguito all’inserimento di un terzo elemento (17): l’indice puntatore alla posizione di inserimento è stato spostato incrementando il suo valore di una unità.
Figura c) rappresenta lo stato della coda in seguito all’estrazione di un elemento (5), l’indice puntatore all’elemento di testa è stato spostato incrementando il suo valore di una unità. La posizione zero diviene disponibile.
Figura d) rappresenta lo stato della coda in seguito all’estrazione di un altro elemento (40). l’indice puntatore all’elemento di testa è stato spostato nuovamente incrementando il suo valore di una unità. La posizione 1 del vettore diviene disponibile.
Figura e) rappresenta lo stato della coda in seguito all’inserimento di un elemento (32). L’indice puntatore alla posizione di inserimento specificava che l’elemento doveva essere inserito in posizione 3 (figura d) . Il valore dell’indice puntatore è stato incrementato raggiungendo il valore 4. Si noti che, a questo punto, se utilizzassimo il confronto tra l’indice puntatore c ed N per stabile se un nuovo inserimento è possibile, dovremmo rinunciare ad inserire, mentre le posizioni 0 ed 1 del vettore sono ancora disponibili. Pertanto il valore della posizione deve essere calcolato “Modulo N”, cioè calcolando: c%N. Essendo coda pari a 4 il resto della divisione di c per N è 0. Il nuovo elemento deve essere inserito in posizione 0.

Esempio di Coda Circolare

Figura f) rappresenta lo stato della coda in seguito all’inserimento di un elemento in posizione c%N. Il valore dell’indice puntatore è stato incrementato, ed in questo momento vale 5. Pertanto la posizione del prossimo inserimento c%N è 1, resto della divisione intera 5 div 4.

Figura g) rappresenta lo stato della coda in seguito all’inserimento di un elemento in posizione 1 (c%N). c è stato incrementato. In questo momento gli indici puntatori alla coda ed alla testa hanno assunto lo stesso valore. Lo stesso evento si verifica però anche nel caso in cui la coda sia vuota (vedi figura m), infatti in quel caso entrambi gli indici puntatore hanno valore zero. Per cui, sia nel caso di coda vuota, sia nel caso di coda piena è verificata la condizione: testa==coda.
- Questa condizione quindi non può essere usata per stabile se la coda è piena/vuota.
- Una possibile soluzione è costituita dall’introduzione di una variabile contatore che in ogni istante sia in grado di fornire il numero degli elementi effettivamente presenti nella coda.

Figure i), l), ed m) Si noti che anche il valore della posizione dell’elemento di testa – cioè dell’indice-puntatore t- deve essere valutato “modulo N”.

NOTA: si ricorda che X%N restituisce il resto della divisione intera di X per N

Coda: rappresentazione con array “statico”

La struttura dati è costituita quindi da:

Array monodimensionale (vettore) di dimensione massima N nota a tempo di compilazione
Due variabili di tipo intero t e c:
- t mantiene la posizione del primo elemento in coda (testa);
- c mantiene la posizione in cui deve avvenire il prossimo inserimento (cioè la posizione successiva a quella dell’ultimo elemento in coda).
Una variabile di tipo intero nelem che mantiene il numero degli elementi presenti nella coda.
Una possibile rappresentazione del tipo Coda quindi può essere quella mostrata in figura.

Struttura Dati della Coda

Figura: Coda – realizzazione delle funzionalità (array “statico”)

Implementazione della Coda (array “statico”): Interfaccia

La figura mostra il file header “Coda.h” contenente:

La dichiarazione del tipo T (è una coda di interi).
La dichiarazione della costante N.
La definizione della struttura dati Coda.
L’interfaccia esportata (come definita in fase di progettazione).

Header file "Coda.h"

Implementazione della Coda (array “statico”): definizione delle funzioni

La figura mostra il file “Coda.cpp” contenente il corpo del modulo e l’inclusione testuale del file header “Coda.h”. La coda è circolare.
Si noti che – avendo optato per l’utilizzo di un record nella definizione della struttura dati- è necessario utilizzare la notazione . (punto) per l’accesso ai singoli campi (C,t,c,nelem)

Header file "Coda.h"

Utilizzo della struttura dati

In figura è mostrato un programma di prova della struttura dati appena realizzata e l’output ottenuto dalla sua esecuzione. Il modulo utente:
- Importa le funzionalità esportate dal modulo Coda (#include “Coda.h”).
- Definisce una o più variabili di tipo Coda.
- Utilizza su di esse le funzionalità disponibili, adottando una disciplina di programmazione secondo la quale non accede alla struttura dati se non attraverso le funzionalità messe a disposizione dall’interfaccia (ma potrebbe farlo, come già osservato precedentemente nell’uso della struttura dati Pila).
Nell’esempio riportato in figura il programma è stato eseguito con N pari a tre. Dopo tre inserimenti viene effettuata una cancellazione, il successivo inserimento sfrutta pertanto la disponibilità della posizione 0 del vettore grazie alla implementazione circolare. Un successivo inserimento trova invece la coda piena.

Esempio d'uso della struttura dati Coda

Coda: rappresentazione mediante array allocato dinamicamente

Le considerazioni già riportate nel caso della rappresentazione della Pila mediante vettore allocato dinamicamente sono valide allo stesso modo per la Coda.
Pertanto si lascia la definizione e la realizzazione del tipo Coda mediante array allocato dinamicamente come esercizio.