Prof. Pier Luca Lanzi

Strutture Dati ElementariAlgoritmi e Calcolo Parallelo

Prof. Pier Luca Lanzi

Riferimenti

• Bertossi Alan A., Montresor Alberto. “Algoritmi e strutture di dati” (seconda edizione), CittàStudi 2010

• Stanley B. Lippman, Barbara E. Moo, Josee Lajoie“C++ Primer”, 5th Edition Addison-Wesley

2

Prof. Pier Luca Lanzi

Tipo di Dato Astratto

• Dato In un linguaggio di programmazione, un dato è

un valore che una variabile può assumere

• Tipo di dato astrattoUn modello matematico, dato da una collezione

di valori e un insieme di operazioni ammesse su questi valori

• Tipi di dati primitiviForniti direttamente dal linguaggioEsempi: int (+,-,*,/, %), boolean (!, &&, ||)

3

Prof. Pier Luca Lanzi

Liste

• Liste (List, Linked List)Una sequenza di nodi, contenenti dati arbitrari e

1-2 puntatori all'elemento successivo e/o precedente

La contiguità nella lista non implica la contiguità in memoria

• Costo operazioniTutte le operazioni hanno costo O(1)

• Realizzazione possibiliBidirezionale/MonodirezionaleCon sentinella/Senza sentinellaCircolare /Non circolare

4

Prof. Pier Luca Lanzi

Esempi di Linked Liste 5

Prof. Pier Luca Lanzi

Liste puntate (Linked List)

• Sequenza di nodi, contenenti dati (qualsiasi) arbitrari e 1-2 reference (puntatori, link) all'elemento successivo e/o precedente

• Liste puntate semplici

• Liste puntate doppie

• Liste circolari

6

Prof. Pier Luca Lanzi

Liste Puntate Semplici (Linked List)

7

Prof. Pier Luca Lanzi

Liste Puntate Semplici (Linked List)

Inserimento Cancellazione

8

Prof. Pier Luca Lanzi

Liste Puntate Semplici e Doppie (Linked List)

LIST-SEARCH(L, k)1 x ← head[L]2 while (x ≠ NIL && key[x] ≠ k)3 do x ← next[x]4 return x

Ricerca Inserimento in testa

LIST-INSERT(L, x)1 next[x] ← head[L]2 if head[L] ≠ NIL3 prev[head[L]] ← x4 head[L] ← x5 prev[x] ← NIL

9

Prof. Pier Luca Lanzi

List - Circolare, Bidirezionale, con Sentinella

10

Prof. Pier Luca Lanzi

Liste nella STL C++

• Sono implementate come liste bidirezionali

• Vantaggi Inserimento e cancellazione di un elemento sono efficienti

(Θ(1)) Spostamento di elementi nella stessa lista o fra liste è

efficiente (Θ(1)) L’iterazione sugli elementi della lista nelle due direzioni è

efficiente (Θ(n))

• Svantaggi Non permettono l’accesso diretto agli elementi della

struttura (e.g. A[i]) Ad esempio, per accedere all’elemento i di una lista

bisogna scorrerla dall’inizio fino all’elemento cercato (Θ(n))

Richiedono la memorizzazione dei collegamenti fra elementi(maggiore memoria rispetto ai vettori)

• Riferimenti http://www.cplusplus.com/reference/stl/list/

11

Prof. Pier Luca Lanzi

Liste nella STL C++

• Iteratori: begin(), end(), rbegin(), rend()

• Capacità: empty, size, max_size, resize

• Accesso agli elementi: front, back

• Modificatori: push_front, pop_front, push_back, pop_back, insert, erase, swap, clear

• Operazioni: splice, remove, remove_if, unique, merge, sort, reverse

12

Prof. Pier Luca Lanzi

Liste – Implementazione con Vettori

• E’ possibile realizzare una lista con vettori La posizione equivale all’indice nel vettore Le operazioni insert e remove hanno costo O(n) Tutte le altre operazioni hanno costo O(1)

• Problema Spesso non si conosce a priori quanta memoria serve per

memorizzare la lista Se ne alloca una certa quantità, per poi accorgersi che non è

sufficiente.

• Soluzione Si alloca un vettore di dimensione maggiore, si ricopia il

contenuto del vecchio vettore nel nuovo e si rilascia il vecchio vettore

13

Prof. Pier Luca Lanzi

Liste – Implementazione con Vettori(Espansione/Contrazione)• Espansione (due approcci)

Raddoppiare la capienza del vettore Incrementare il vettore di un fattore costante

• Contrazione E’ opportuno contrarre il vettore quando il fattore di

carico α = size/capacity diventa troppo piccolo size è il numero di elementi attualmente presenti capacity è la dimensione del vettore L’operazione richiede l’allocazione, la copia, e la

deallocazione

14

Prof. Pier Luca Lanzi

Pile/Stack

• Insieme dinamico in cui l’elemento rimosso dall’operazione di cancellazione è predeterminato: “quello che per meno tempo è rimasto nell’insieme”

• Politica “last in, first out” (LIFO)

• Operazioni previste (tutte realizzabili in O(1))

20

Prof. Pier Luca Lanzi

Stack (o Pila)

• Una pila o stack è un insieme dinamico in cui l’elemento rimosso dall’operazione di cancellazione è predeterminato: “quello che per meno tempo è rimasto nell’insieme” politica “last in, first out” (LIFO)

• Operazioni previste void push(Item) // inserisce un elemento Item pop() // rimuove l‘elemento

// in cima Item top() // legge l’item in cima

// non rimuove l'item boolean isEmpty() // true se la pila è vuota

21

Prof. Pier Luca Lanzi

Applicazione e Implementazione

• Possibili utilizzi Nei linguaggi con procedure:

gestione dei record di attivazione Nei linguaggi stack-oriented: le

operazioni elementari prendono uno-due operandi dallo stack e inseriscono il risultato nello stack

Notazione RPN: 3 4 + 7 -

• Possibili implementazioni Tramite liste bidirezionali

(puntatore all'elemento top) Tramite vettore

(dimensione limitata, overhead più basso)

22

top

Prof. Pier Luca Lanzi

Stack (Pseudocodice) 23

Prof. Pier Luca Lanzi

Stack nella STL C++

• Funzioniemptysize toppushPop

• Esempihttp://ideone.com/QUyf6https://ideone.com/zh4ho

24

Prof. Pier Luca Lanzi

Code/Queue

• Insieme dinamico in cui l’elemento rimosso dall’operazione di cancellazione è predeterminato: “quello che per più tempo è rimasto nell’insieme”

• Politica di gestione “first in, first out” (FIFO)

• Operazione previste O(1)

25

Prof. Pier Luca Lanzi

Code/Queue

• ApplicazioniNei sistemi operativi, i processi in attesa di

utilizzare una risorsa vengono gestiti tramite una coda FIFO

Visita dei grafi

• ImplementazioniListe monodirezionali: puntatore head (inizio

della coda), per estrazione; puntatore tail (fine della coda), per inserimento

Array circolari: dimensione limitata, overhead più basso

26

Prof. Pier Luca Lanzi

Coda/Queue – Implementazione con Vettori Circolari

• La “finestra” dell’array occupata dalla coda si sposta lungo l’array!

• Dettagli implementativiL'array circolare può

essere implementato con un'operazione di modulo

Bisogna prestare attenzioneai problemi di overflow(buffer pieno)

27

head+n

3

654

43

head

3 6 54 43

head

head+n

Prof. Pier Luca Lanzi

Coda/Queue – Implementazione con Vettori Circolari

28

head

3 6 54 43

head+n

3 6 54 43 12

6 54 43 12

head+n

head head+n

head

enqueue(12)

dequeue() → 3

6 54 43 12

head+n

head

15 1733

enqueue (15, 17, 33)

Prof. Pier Luca Lanzi

Coda/Queue - Pseudocodice 29

Prof. Pier Luca Lanzi

Code/Queue nella STL C++

• Funzioniemptysize front: accesso al prossimo elemento della codaback: accesso all’ultimo elementopush: inserisce un elemento in codapop: cancella il prossimo elemento

• Costuttoretemplate < class T, class Container = deque<T> > class queue;

30