Strutture dinamiche

3^ INFORMATICO - IIS PASCAL�DIPARTIMENTO INFORMATICA

​

​

​

​

Strutture dinamiche particolari

2

Strutture dinamiche particolari

Con struct e puntatori è possibile realizzare molte strutture dati.�Noi vedremo:

• pile
• code
• alberi binari (classe quarta)

​

E’ possibile anche costruire:

• liste bidirezionali
• grafi
• alberi n-ari
• mappa

�

Strutture dinamiche particolari - PILA

La prima struttura che vediamo è la struttura a pila (o stack)

​

caratteristiche:

• struttura LIFO (Last In First Out)�l’ultimo elemento inserito nella pila è il primo ad essere �utilizzato
• esiste una inizio della pila (head)
• operazioni previste
• push (inserisce un elemento)
• pop (estrae un elemento)
• top (visualizza l’elemento affiorante senza� eliminarlo dalla pila)�

​

Strutture dinamiche particolari - PILA

Realizzazione in C++ di una struttura che implementi il concetto di PILA

E’ comunque una struttura dinamica collegata con un elemento iniziale (come una lista)

Le operazioni previste sono già state viste nella lista

• push (inserisci un elemento all’inizio della lista)
• pop (cancella l’elemento iniziale della lista)
• top (visualizza il valore del primo elemento della lista)�

​

nullptr

head

Strutture dinamiche particolari - PILA

Operazioni

• push (inserisci un elemento all’inizio della lista)
• pop (cancella l’elemento iniziale della lista)
• top (visualizza il valore del primo elemento della lista)�

​

nullptr

head

tmp

1)

/

2)

3)

Strutture dinamiche particolari - PILA

Operazioni

• push (inserisci un elemento all’inizio della lista)
• pop (cancella l’elemento iniziale della lista)
• top (visualizza il valore del primo elemento della lista)�

​

nullptr

head

tmp

1)

/

2)

3)

Strutture dinamiche particolari - PILA

Operazioni

• push (inserisci un elemento all’inizio della lista)
• pop (cancella l’elemento iniziale della lista)
• top (visualizza il valore del primo elemento della lista)�

​

nullptr

head

2)

head

nullptr

caso lista vuota - nulla da visualizzare

caso lista non vuota - visualizzo l’info del primo nodo

ESERCIZI

9

1. Definisci una pila di stringhe e le tre funzioni push,�pop, top previste per una struttura a pila

​

• Scrivi un programma che, tramite l’utilizzo di una �struttura a pila, legga una serie di stringhe da utente�e poi le visualizzi in senso inverso.�L’utente termina l’inserimento con la stringa “STOP”�che non va considerata come valore valido�

​

​

Strutture dinamiche particolari - CODA

La seconda struttura che vediamo è la struttura a coda (o queue)

​

caratteristiche:

• struttura FIFO (First In First Out)�il primo elemento inserito nella pila è anche �il primo ad essere utilizzato
• esiste una testa della coda (head)
• operazioni previste
• enqueue (inserisce un elemento in coda)
• dequeue (estrae un elemento dalla coda)
• top (visualizza l’elemento affiorante senza eliminarlo dalla coda)�

testa

Strutture dinamiche particolari - CODA

Realizzazione in C++ di una struttura che implementi il concetto di CODA

E’ comunque una struttura dinamica collegata con un elemento iniziale (come una lista)

Le operazioni previste sono già state viste nella lista

• enqueue (inserisce un elemento in coda)
• dequeue (estrae un elemento dalla coda)
• top (visualizza l’elemento affiorante senza eliminarlo dalla coda)�

​

nullptr

testa

Strutture dinamiche particolari - CODA

Realizzazione in C++ di una struttura che implementi il concetto di CODA

E’ comunque una struttura dinamica collegata con un elemento iniziale (come una lista)

Le operazioni previste sono già state viste nella lista

• enqueue (inserisce un elemento in coda)
• dequeue (estrae un elemento dalla coda)
• top (visualizza l’elemento affiorante senza eliminarlo dalla coda)�

NOTA : � la enqueue è realizzabile con la procedura di inserimento in fondo in una lista

la dequeue è realizzabile con la procedura di estrazione dalla testa di una lista

nullptr

testa

/

Strutture dinamiche particolari - CODA

Realizzazione in C++ di una struttura che implementi il concetto di CODA

E’ comunque una struttura dinamica collegata con un elemento iniziale (come una lista)

Le operazioni previste sono già state viste nella lista

• enqueue (inserisce un elemento in coda)
• dequeue (estrae un elemento dalla coda)
• top (visualizza l’elemento affiorante senza eliminarlo dalla coda)�

​

nullptr

testa

tmp

/

Strutture dinamiche particolari - CODA

Realizzazione in C++ di una struttura che implementi il concetto di CODA

E’ comunque una struttura dinamica collegata con un elemento iniziale (come una lista)

Le operazioni previste sono già state viste nella lista

• enqueue (inserisce un elemento in coda)
• dequeue (estrae un elemento dalla coda)
• top (visualizza l’elemento affiorante senza eliminarlo dalla coda)�

​

nullptr

head

2)

head

nullptr

caso coda vuota - nulla da visualizzare

caso lista non vuota - visualizzo l’info del primo nodo

Strutture dinamiche particolari - Liste Bidirezionali

Solo un accenno alla struttura delle liste bidirezionali

Cambia la struttura del nodo: contiene anche un puntatore�al nodo precedente

Usiamo un puntatore a head (primo elemento)�e uno a tail (ultimo elemento)

​

​

​

​

​

�Più complessa ma ho accesso diretto all’ultimo elemento (e quindi inserimento sempre in O(1)) e possibilità di visualizzare la lista anche in senso inverso�Si lascia la realizzazione allo studente per esercizio

head

tail

PILE e CODE

​

​

​

Implementazione�

16

Implementazione PILA

17

Utilizzeremo la suddivisione fra files .h (intestazioni) e files .cpp (corpo dei metodi) - �NON È’ OBBLIGATORIA MA È LO STANDARD DI PROGRAMMAZIONE

​

Dividiamo il progetto in 3 files:

• main.cpp
• contiene il programma principale che userà le librerie relative alla pila
• pila.h
• contiene le intestazioni (prototipi) delle funzioni accessibili dal main
• pila.cpp
• contiene il corpo delle funzioni esplicitate in pila.h e altre funzioni utilizzate all’interno di pila.ccp ch NON vogliamo rendere pubbliche al main

​

PERCHÈ’ ?�perché se viene modificata la libreria relativa alla struttura della pila, non viene modificato il programma principale ma va soltanto ricompilato!

Implementazione PILA

18

file pila.h contiene

• il nome del tipo dato nodo che abbiamo scelto
• i prototipi delle funzioni che vogliamo implementare per modellizzare la pila
• push
• pop
• top
• isEmpty

​

Cosa sono le scritte in verde??

quando si usano i file .h è norma�usare le include guards che�hanno il compito di evitare�importazioni multiple dello stesso�file

​

Implementazione PILA

19

file pila.cpp contiene:

• la struttura del nodo
• il corpo delle funzioni che dobbiamo implementare per modellizzare la pila
• push
• pop
• top
• isEmpty
• eventuali altre funzioni�non pubblicate all’utente�come ad esempio la�funzione _count

​

​

Implementazione PILA

20

file main.cpp contiene:

• le direttive di importazione del file pila.h (che avverte il compilatore di importare pila.cpp)
• le variabili locali e globali del main
• il programma principale

​

​

​

OUTPUT

​

​

​

​

​

NOTA: Per come abbiamo implementato top, riceviamo -INT_MAX come valore per una pila vuota

Implementazione PILA

21

file main.cpp contiene:

• se proviamo a invocare la funzione _count non definita in pila.h il compilatore restituisce un errore!

​

​

​

COMPILEr OUTPUT

ESERCIZIO

22

Prova ad implementare una struttura a coda con una metodologia simile a quella appena illustrata

​

Crea un file coda.h ed il suo corrispondente coda.cpp

Definisci e implementa le seguenti funzioni:

• front() : Returns the first element of the queue if exists, -INT_MAX otherwise
• push(g) : Adds the element 'g' at the end of the queue
• pop() : Deletes the first element of the queue if exists
• isEmpty() : Returns true if queue is empty, false otherwise
• back() : Returns the last element of the queue f exists, -INT_MAX otherwise

​

Al termine inserisci nel main le istruzioni per utilizzare la coda

​

​

​

​