Pile e code PDF

Pile e code Corso di Algoritmi e strutture dati Corso di Laurea in Informatica Docenti: Ugo de’Liguoro, András Horváth Algoritmi e strutture dati, Ugo de’Liguor...

Pile e code Corso di Algoritmi e strutture dati Corso di Laurea in Informatica Docenti: Ugo de’Liguoro, András Horváth Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 1/ 33  Indice 1. Tipo di dato astratto (abstract data type, ADT) 2. Pile (stack) 3. Code Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 2/ 33  Sommario Obiettivo: I introdurre il concetto del tipo di dato astratto (abtrasct data type, ADT) I specificare pile e code come ADT e definire due diverse implementazioni Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 3/ 33  1. Tipi di dati I i linguaggi di programmazione tipati forniscono tipi predefiniti Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 33  1. Tipi di dati I i linguaggi di programmazione tipati forniscono tipi predefiniti I ogni tipo di dato è associato con un insieme di valori e operatori: Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 33  1. Tipi di dati I i linguaggi di programmazione tipati forniscono tipi predefiniti I ogni tipo di dato è associato con un insieme di valori e operatori: I unsigned int: 0, 1, 2,... con operazioni +, −,... Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 33  1. Tipi di dati I i linguaggi di programmazione tipati forniscono tipi predefiniti I ogni tipo di dato è associato con un insieme di valori e operatori: I unsigned int: 0, 1, 2,... con operazioni +, −,... I boolean: T , F con operazioni ¬, ∧,... Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 33  1. Tipi di dati I i linguaggi di programmazione tipati forniscono tipi predefiniti I ogni tipo di dato è associato con un insieme di valori e operatori: I unsigned int: 0, 1, 2,... con operazioni +, −,... I boolean: T , F con operazioni ¬, ∧,... I ogni operatore funzione secondo certe regole Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 33  1. Tipi di dati I i linguaggi di programmazione tipati forniscono tipi predefiniti I ogni tipo di dato è associato con un insieme di valori e operatori: I unsigned int: 0, 1, 2,... con operazioni +, −,... I boolean: T , F con operazioni ¬, ∧,... I ogni operatore funzione secondo certe regole I quando usiamo i tipi forniti dal linguaggio non ci chiediamo come vengono effettuate le operazioni Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 33  1. Tipi di dati I i linguaggi di programmazione tipati forniscono tipi predefiniti I ogni tipo di dato è associato con un insieme di valori e operatori: I unsigned int: 0, 1, 2,... con operazioni +, −,... I boolean: T , F con operazioni ¬, ∧,... I ogni operatore funzione secondo certe regole I quando usiamo i tipi forniti dal linguaggio non ci chiediamo come vengono effettuate le operazioni I si possono introdurre nuovi tipi di dati e implementare operazione per i nuovi tipi Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un tipo di dato è astratto se è descritto prescindendo dalla sua concreta implementazione Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un tipo di dato è astratto se è descritto prescindendo dalla sua concreta implementazione I tale descrizione riguarda Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un tipo di dato è astratto se è descritto prescindendo dalla sua concreta implementazione I tale descrizione riguarda I la collezione di dati: a partire da quali tipi di dati si costruisce una struttura del nuovo tipo (ma non come la si costruisce!) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un tipo di dato è astratto se è descritto prescindendo dalla sua concreta implementazione I tale descrizione riguarda I la collezione di dati: a partire da quali tipi di dati si costruisce una struttura del nuovo tipo (ma non come la si costruisce!) I le operazioni: che cosa devono fare le operazioni definite sul nuovo tipo (ma non come lo devono fare!) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un tipo di dato è astratto se è descritto prescindendo dalla sua concreta implementazione I tale descrizione riguarda I la collezione di dati: a partire da quali tipi di dati si costruisce una struttura del nuovo tipo (ma non come la si costruisce!) I le operazioni: che cosa devono fare le operazioni definite sul nuovo tipo (ma non come lo devono fare!) I complessità: eventualmente dei vincoli di complessità su tali operazioni Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un tipo di dato è astratto se è descritto prescindendo dalla sua concreta implementazione I tale descrizione riguarda I la collezione di dati: a partire da quali tipi di dati si costruisce una struttura del nuovo tipo (ma non come la si costruisce!) I le operazioni: che cosa devono fare le operazioni definite sul nuovo tipo (ma non come lo devono fare!) I complessità: eventualmente dei vincoli di complessità su tali operazioni I la descrizione delle operazioni con le pre- e postcondizioni è una sorta di assiomatizzazione del tipo Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un’implementazione concreta di un ADT è Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 6/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un’implementazione concreta di un ADT è I una struttura dati con cui memorizzare la collezione di dati Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 6/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un’implementazione concreta di un ADT è I una struttura dati con cui memorizzare la collezione di dati I ed una collezione di procedure con cui realizzare le operazioni Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 6/ 33  1. Tipo di dato astratto (abstract data type, ADT) I un’implementazione concreta di un ADT è I una struttura dati con cui memorizzare la collezione di dati I ed una collezione di procedure con cui realizzare le operazioni I la relazione fra tipo astratto e struttura concreta è analoga a quella fra problema algoritmico e algoritmo. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 6/ 33  2. Pile (stack) In una pila i dati vengono estratti in ordine inverso rispetto a quello in cui sono stati inseriti. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 7/ 33  2. Pile (stack) In una pila i dati vengono estratti in ordine inverso rispetto a quello in cui sono stati inseriti. Terminologia: I push: inserire un elemento nella pila Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 7/ 33  2. Pile (stack) In una pila i dati vengono estratti in ordine inverso rispetto a quello in cui sono stati inseriti. Terminologia: I push: inserire un elemento nella pila I pop: estrarre un elemento dalla pila Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 7/ 33  2. Pile (stack) In una pila i dati vengono estratti in ordine inverso rispetto a quello in cui sono stati inseriti. Terminologia: I push: inserire un elemento nella pila I pop: estrarre un elemento dalla pila I top: restituisce l’elemento in cima Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 7/ 33  2. Pile (stack) Operazioni: Pila: I push(3) I push(5) I push(9) I pop() I pop() I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) I push(5) I push(9) I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) I push(5) I push(9) 5 I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) I push(5) 9 I push(9) 5 I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) I push(5) I push(9) 5 I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) I push(5) I push(9) I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) I push(5) I push(9) 1 I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) I push(5) 8 I push(9) 1 I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) 2 I push(5) 8 I push(9) 1 I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) I push(5) 8 I push(9) 1 I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pile (stack) Operazioni: Pila: I push(3) 6 I push(5) 8 I push(9) 1 I pop() I pop() 3 I push(1) I push(8) I push(2) I pop() I push(6) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 33  2. Pila come ADT I collezione dati: elementi di qualunque tipo T di dati Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 9/ 33  2. Pila come ADT I collezione dati: elementi di qualunque tipo T di dati I operazioni: I void P USH(Stack S, T t) I T P OP(Stack S) I T TOP(Stack S) I bool E MPTY(Stack S) I int S IZE(Stack S) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 9/ 33  2. Pila come ADT I assiomi: Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 33  2. Pila come ADT I assiomi: I S IZE(S), E MPTY(S) e P USH(S, t) sono sempre definiti I P OP(S) e TOP(S) sono definiti se e solo se E MPTY(S) restituisce falso Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 33  2. Pila come ADT I assiomi: I S IZE(S), E MPTY(S) e P USH(S, t) sono sempre definiti I P OP(S) e TOP(S) sono definiti se e solo se E MPTY(S) restituisce falso I E MPTY(S), S IZE(S) e TOP(S) non modificano la pila S Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 33  2. Pila come ADT I assiomi: I S IZE(S), E MPTY(S) e P USH(S, t) sono sempre definiti I P OP(S) e TOP(S) sono definiti se e solo se E MPTY(S) restituisce falso I E MPTY(S), S IZE(S) e TOP(S) non modificano la pila S I E MPTY(S) restituisce vero se e solo se S IZE(S) restituisce 0 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 33  2. Pila come ADT I assiomi: I S IZE(S), E MPTY(S) e P USH(S, t) sono sempre definiti I P OP(S) e TOP(S) sono definiti se e solo se E MPTY(S) restituisce falso I E MPTY(S), S IZE(S) e TOP(S) non modificano la pila S I E MPTY(S) restituisce vero se e solo se S IZE(S) restituisce 0 I la sequenza P USH(S, t);P OP(S) restituisce t e non modifica la pila S Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 33  2. Pila come ADT I assiomi: I S IZE(S), E MPTY(S) e P USH(S, t) sono sempre definiti I P OP(S) e TOP(S) sono definiti se e solo se E MPTY(S) restituisce falso I E MPTY(S), S IZE(S) e TOP(S) non modificano la pila S I E MPTY(S) restituisce vero se e solo se S IZE(S) restituisce 0 I la sequenza P USH(S, t);P OP(S) restituisce t e non modifica la pila S I la sequenza P USH(S, t);TOP(S) restituisce t Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 33  2. Pila come ADT I assiomi: I S IZE(S), E MPTY(S) e P USH(S, t) sono sempre definiti I P OP(S) e TOP(S) sono definiti se e solo se E MPTY(S) restituisce falso I E MPTY(S), S IZE(S) e TOP(S) non modificano la pila S I E MPTY(S) restituisce vero se e solo se S IZE(S) restituisce 0 I la sequenza P USH(S, t);P OP(S) restituisce t e non modifica la pila S I la sequenza P USH(S, t);TOP(S) restituisce t I P USH(S, t) incrementa S IZE(S) di 1 I P OP(S) decrementa S IZE(S) di 1 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 33  2. Implementazione concreta con array I usiamo un array statico di M celle per definire un’implementazione concreta del ADT pila 1 N M Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 11/ 33  2. Implementazione concreta con array I usiamo un array statico di M celle per definire un’implementazione concreta del ADT pila 1 N M I grazie al meccanismo LIFO (Last In First Out) conviene fare così: Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 11/ 33  2. Implementazione concreta con array I usiamo un array statico di M celle per definire un’implementazione concreta del ADT pila 1 N M I grazie al meccanismo LIFO (Last In First Out) conviene fare così: I gli elementi presenti nella pila occupano sempre le prime posizioni dell’array I quando ci sono N elementi, il prossimo elemento da estrarre è nella posizione N Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 11/ 33  2. Implementazione concreta con array I usiamo un array statico di M celle per definire un’implementazione concreta del ADT pila 1 N M I grazie al meccanismo LIFO (Last In First Out) conviene fare così: I gli elementi presenti nella pila occupano sempre le prime posizioni dell’array I quando ci sono N elementi, il prossimo elemento da estrarre è nella posizione N I la scelta della struttura dati concreta “aggiunge un assioma”: I P USH(S, t) è definito se solo se S IZE(S)< M Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 11/ 33  2. Implementazione concreta con array P USH(S, t) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array P USH(S, t) if S.N 6= S.M then S.N ← S.N + 1 S[N] ← t else erroroverflow Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array S IZE(S) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array S IZE(S) return S.N Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array E MPTY(S) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array E MPTY(S) if S.N == 0 then return true return false Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array TOP(S) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array TOP(S) if S.N == 0 then errorunderflow else return S[S.N] Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array P OP(S) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array P OP(S) if S.N == 0 then errorunderflow else S.N ← S.N − 1 return S[S.N + 1] Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: 3 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: 3 5 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: 3 5 9 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: 3 5 9 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: 3 5 9 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: 3 5 1 9 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: 3 5 1 8 9 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: 3 5 1 8 9 2 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array Operazioni: I push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop() Pila: 3 5 1 8 9 2 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 33  2. Implementazione concreta con array I l’array darebbe la possibilità di inserimenti e estrazioni in una posizione qualsiasi Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 14/ 33  2. Implementazione concreta con array I l’array darebbe la possibilità di inserimenti e estrazioni in una posizione qualsiasi I ma se il programmatore ha deciso di utilizzare l’ADT pila allora può interagire con la pila solo seconda la specifica del ADT Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 14/ 33  2. Implementazione concreta con array I l’array darebbe la possibilità di inserimenti e estrazioni in una posizione qualsiasi I ma se il programmatore ha deciso di utilizzare l’ADT pila allora può interagire con la pila solo seconda la specifica del ADT I l’implementazione concreta e la struttura dati I sono nascosti dietro una interfaccia Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 14/ 33  2. Implementazione concreta con array I l’array darebbe la possibilità di inserimenti e estrazioni in una posizione qualsiasi I ma se il programmatore ha deciso di utilizzare l’ADT pila allora può interagire con la pila solo seconda la specifica del ADT I l’implementazione concreta e la struttura dati I sono nascosti dietro una interfaccia I e possono essere modificate senza fare modifiche a programmi che usano l’ADT Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 14/ 33  2. Implementazione concreta con lista Utilizziamo una lista per realizzare la pila: Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 15/ 33  2. Implementazione concreta con lista Utilizziamo una lista per realizzare la pila: I quale tipo di lista conviene utilizzare: doppiamente concatenate, circolari? Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 15/ 33  2. Implementazione concreta con lista Utilizziamo una lista per realizzare la pila: I quale tipo di lista conviene utilizzare: doppiamente concatenate, circolari? I conviene una lista semplice ma con sentinella per non dover fare controlli S.sen / key next Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 15/ 33  2. Implementazione concreta con lista Utilizziamo una lista per realizzare la pila: I quale tipo di lista conviene utilizzare: doppiamente concatenate, circolari? I conviene una lista semplice ma con sentinella per non dover fare controlli S.sen / key next I conviene tener conto del numero di elementi che sarà denotato con S.N Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 15/ 33  2. Implementazione concreta con lista P USH(S, t) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Implementazione concreta con lista P USH(S, t) S.N ← S.N + 1 t.next ← S.sen.next S.sen.next ← t Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Implementazione concreta con lista S IZE(S) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Implementazione concreta con lista S IZE(S) return S.N Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Implementazione concreta con lista E MPTY(S) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Implementazione concreta con lista E MPTY(S) if S.N == 0 then return true return false Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Implementazione concreta con lista TOP(S) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Implementazione concreta con lista TOP(S) if S.N == 0 then errorunderflow else return S.sen.next Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Implementazione concreta con lista P OP(S) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Implementazione concreta con lista P OP(S) if S.N == 0 then errorunderflow else S.N ← S.N − 1 t ← S.sen.next S.sen.next ← S.sen.next.next return t Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 33  2. Confronto delle due implementazioni I complessità temporale delle operazioni? Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 17/ 33  2. Confronto delle due implementazioni I complessità temporale delle operazioni? sono tutte O(1) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 17/ 33  2. Confronto delle due implementazioni I complessità temporale delle operazioni? sono tutte O(1) I complessità spaziale delle strutture? con l’array O(M) (proporzionale al numero massimo di elementi), con le liste O(N) (ma c’è l’overhead dovuto ai puntatori) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 17/ 33  2. Confronto delle due implementazioni I complessità temporale delle operazioni? sono tutte O(1) I complessità spaziale delle strutture? con l’array O(M) (proporzionale al numero massimo di elementi), con le liste O(N) (ma c’è l’overhead dovuto ai puntatori) I con l’array bisogna stabilire a priori il numero massimo di elementi, con le liste no Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 17/ 33  2. Utilizzo della struttura dati pila I chiamate ricorsive di funzioni Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 18/ 33  2. Utilizzo della struttura dati pila I chiamate ricorsive di funzioni I visita in profondità di grafi Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 18/ 33  2. Utilizzo della struttura dati pila I chiamate ricorsive di funzioni I visita in profondità di grafi I valutazione di un’espressione in notazione postfissa Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 18/ 33  3. Code (queue) In una coda i dati vengono estratti nell’ordine in cui sono stati inseriti. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 19/ 33  3. Code (queue) In una coda i dati vengono estratti nell’ordine in cui sono stati inseriti. Terminologia: I enqueue: inserire un elemento nella coda Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 19/ 33  3. Code (queue) In una coda i dati vengono estratti nell’ordine in cui sono stati inseriti. Terminologia: I enqueue: inserire un elemento nella coda I dequeue: estrarre un elemento dalla coda Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 19/ 33  3. Code (queue) In una coda i dati vengono estratti nell’ordine in cui sono stati inseriti. Terminologia: I enqueue: inserire un elemento nella coda I dequeue: estrarre un elemento dalla coda I front: restituisce il primo elemento nella coda Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 19/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: 3 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: 5 3 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: 9 5 3 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: 9 5 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: 9 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: 1 9 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: 8 1 9 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: 2 8 1 9 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Code (queue) Operazioni: I queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue() Coda: 2 8 1 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 33  3. Coda come ADT I collezione dati: elementi di qualunque tipo T di dati Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 21/ 33  3. Coda come ADT I collezione dati: elementi di qualunque tipo T di dati I operazioni: I void E NQUEUE(Queue Q, T t) I T D EQUEUE(Queue Q) I T F RONT(Queue Q) I bool E MPTY(Queue Q) I int S IZE(Queue Q) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 21/ 33  3. Coda come ADT I assiomi: Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 33  3. Coda come ADT I assiomi: I S IZE(Q), E MPTY(Q) e E NQUEUE(Q, t) sono sempre definiti I D EQUEUE(Q) e F RONT(Q) sono definiti se e solo se E MPTY(Q) restituisce falso Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 33  3. Coda come ADT I assiomi: I S IZE(Q), E MPTY(Q) e E NQUEUE(Q, t) sono sempre definiti I D EQUEUE(Q) e F RONT(Q) sono definiti se e solo se E MPTY(Q) restituisce falso I E MPTY(Q), S IZE(Q) e F RONT(Q) non modificano la coda Q Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 33  3. Coda come ADT I assiomi: I S IZE(Q), E MPTY(Q) e E NQUEUE(Q, t) sono sempre definiti I D EQUEUE(Q) e F RONT(Q) sono definiti se e solo se E MPTY(Q) restituisce falso I E MPTY(Q), S IZE(Q) e F RONT(Q) non modificano la coda Q I E MPTY(Q) restituisce vero se e solo se S IZE(Q) restituisce 0 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 33  3. Coda come ADT I assiomi: I S IZE(Q), E MPTY(Q) e E NQUEUE(Q, t) sono sempre definiti I D EQUEUE(Q) e F RONT(Q) sono definiti se e solo se E MPTY(Q) restituisce falso I E MPTY(Q), S IZE(Q) e F RONT(Q) non modificano la coda Q I E MPTY(Q) restituisce vero se e solo se S IZE(Q) restituisce 0 I se S IZE(Q)= N e viene effettuata E NQUEUE(Q, t), allora dopo N esecuzione di D EQUEUE(Q) abbiamo F RONT(Q)= t Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 33  3. Coda come ADT I assiomi: I S IZE(Q), E MPTY(Q) e E NQUEUE(Q, t) sono sempre definiti I D EQUEUE(Q) e F RONT(Q) sono definiti se e solo se E MPTY(Q) restituisce falso I E MPTY(Q), S IZE(Q) e F RONT(Q) non modificano la coda Q I E MPTY(Q) restituisce vero se e solo se S IZE(Q) restituisce 0 I se S IZE(Q)= N e viene effettuata E NQUEUE(Q, t), allora dopo N esecuzione di D EQUEUE(Q) abbiamo F RONT(Q)= t I se F RONT(Q)= t allora D EQUEUE(Q) estrae t dalla coda Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 33  3. Coda come ADT I assiomi: I S IZE(Q), E MPTY(Q) e E NQUEUE(Q, t) sono sempre definiti I D EQUEUE(Q) e F RONT(Q) sono definiti se e solo se E MPTY(Q) restituisce falso I E MPTY(Q), S IZE(Q) e F RONT(Q) non modificano la coda Q I E MPTY(Q) restituisce vero se e solo se S IZE(Q) restituisce 0 I se S IZE(Q)= N e viene effettuata E NQUEUE(Q, t), allora dopo N esecuzione di D EQUEUE(Q) abbiamo F RONT(Q)= t I se F RONT(Q)= t allora D EQUEUE(Q) estrae t dalla coda I E NQUEUE(Q, t) incrementa S IZE(Q) di 1 I D EQUEUE(Q) decrementa S IZE(Q) di 1 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 33  3. Implementazione concreta con array Usiamo un array statico di M celle per definire un’implementazione: I anche in questo caso conviene tenere gli elementi nelle prime posizioni dell’array? Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 23/ 33  3. Implementazione concreta con array Usiamo un array statico di M celle per definire un’implementazione: I anche in questo caso conviene tenere gli elementi nelle prime posizioni dell’array? no! perché? Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 23/ 33  3. Implementazione concreta con array Usiamo un array statico di M celle per definire un’implementazione: I anche in questo caso conviene tenere gli elementi nelle prime posizioni dell’array? no! perché? I se l’elemento da estrarre è nella prima posizione allora D E Q UEUE(Q) richiede spostare gli elementi rimanenti I se l’elemento da estrarre è nell’ultima posizione allora E N Q UEUE(Q) richiede spostare gli elementi presenti Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 23/ 33  3. Implementazione concreta con array Usiamo un array statico di M celle per definire un’implementazione: I anche in questo caso conviene tenere gli elementi nelle prime posizioni dell’array? no! perché? I se l’elemento da estrarre è nella prima posizione allora D E Q UEUE(Q) richiede spostare gli elementi rimanenti I se l’elemento da estrarre è nell’ultima posizione allora E N Q UEUE(Q) richiede spostare gli elementi presenti I sarebbero operazioni da O(N) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 23/ 33  3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 24/ 33 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 3 tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 3 5 tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 3 5 9 tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 3 5 9 tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 3 5 9 tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 3 5 9 1 tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 3 5 9 1 8 tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 3 5 9 1 8 2 tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 3 5 9 1 8 2 tail 3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 7 3 5 9 1 8 2 tail  3. Implementazione concreta con array Useremo l’array in maniera “circolare” tenendo conto di dove si trova l’inizio (head) e la fine (tail) della coda. Operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4). Coda: head 7 3 5 4 9 1 8 2 tail Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 24/ 33  3. Implementazione concreta con array I Q.head indica la posizione da dove estrarre l’elemento successivo Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 25/ 33  3. Implementazione concreta con array I Q.head indica la posizione da dove estrarre l’elemento successivo I Q.tail indica la posizione dove inserire l’elemento successivo Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 25/ 33  3. Implementazione concreta con array I Q.head indica la posizione da dove estrarre l’elemento successivo I Q.tail indica la posizione dove inserire l’elemento successivo I come si controlla se la coda sia vuota? Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 25/ 33  3. Implementazione concreta con array I Q.head indica la posizione da dove estrarre l’elemento successivo I Q.tail indica la posizione dove inserire l’elemento successivo I come si controlla se la coda sia vuota? Q.head == Q.tail ⇐⇒ la coda è vuota Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 25/ 33  3. Implementazione concreta con array I Q.head indica la posizione da dove estrarre l’elemento successivo I Q.tail indica la posizione dove inserire l’elemento successivo I come si controlla se la coda sia vuota? Q.head == Q.tail ⇐⇒ la coda è vuota I di conseguenza possiamo gestire M − 1 elementi al massimo con un array di M celle Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 25/ 33  3. Implementazione concreta con array S IZE(Q) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 26/ 33  3. Implementazione concreta con array S IZE(Q) if Q.tail ≥ Q.head then return Q.tail − Q.head return Q.M − (Q.head − Q.tail) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 26/ 33  3. Implementazione concreta con array S IZE(Q) if Q.tail ≥ Q.head then return Q.tail − Q.head return Q.M − (Q.head − Q.tail) E MPTY(Q) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 26/ 33  3. Implementazione concreta con array S IZE(Q) if Q.tail ≥ Q.head then return Q.tail − Q.head return Q.M − (Q.head − Q.tail) E MPTY(Q) if Q.tail == Q.head then return true return false Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 26/ 33  3. Implementazione concreta con array S IZE(Q) if Q.tail ≥ Q.head then return Q.tail − Q.head return Q.M − (Q.head − Q.tail) E MPTY(Q) if Q.tail == Q.head then return true return false N EXT C ELL(Q, c) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 26/ 33  3. Implementazione concreta con array S IZE(Q) if Q.tail ≥ Q.head then return Q.tail − Q.head return Q.M − (Q.head − Q.tail) E MPTY(Q) if Q.tail == Q.head then return true return false N EXT C ELL(Q, c) if c 6= Q.M then return c + 1 return 1 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 26/ 33  3. Implementazione concreta con array E NQUEUE(Q, t) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 27/ 33  3. Implementazione concreta con array E NQUEUE(Q, t) if S IZE(Q) 6= Q.M − 1 then Q[Q.tail] ← t Q.tail ← N EXT C ELL(Q,Q.tail) else erroroverflow Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 27/ 33  3. Implementazione concreta con array E NQUEUE(Q, t) if S IZE(Q) 6= Q.M − 1 then Q[Q.tail] ← t Q.tail ← N EXT C ELL(Q,Q.tail) else erroroverflow F RONT(Q) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 27/ 33  3. Implementazione concreta con array E NQUEUE(Q, t) if S IZE(Q) 6= Q.M − 1 then Q[Q.tail] ← t Q.tail ← N EXT C ELL(Q,Q.tail) else erroroverflow F RONT(Q) if S IZE(Q)== 0 then errorunderflow else return Q[Q.head] Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 27/ 33  3. Implementazione concreta con array D EQUEUE(Q) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 28/ 33  3. Implementazione concreta con array D EQUEUE(Q) if S IZE(Q)== 0 then errorunderflow else t ← Q[Q.head] Q.head ← N EXT C ELL(Q,Q.head) return t Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 28/ 33  3. Implementazione concreta con lista Utilizziamo una lista per realizzare la coda: Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 29/ 33  3. Implementazione concreta con lista Utilizziamo una lista per realizzare la coda: I quale tipo di lista conviene utilizzare: doppiamente concatenate, circolari? Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 29/ 33  3. Implementazione concreta con lista Utilizziamo una lista per realizzare la coda: I quale tipo di lista conviene utilizzare: doppiamente concatenate, circolari? I inserimenti vengono fatti in testa, estrazioni in coda Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 29/ 33  3. Implementazione concreta con lista Utilizziamo una lista per realizzare la coda: I quale tipo di lista conviene utilizzare: doppiamente concatenate, circolari? I inserimenti vengono fatti in testa, estrazioni in coda I usiamo una lista semplice ma aggiungiamo un puntatore all’ultimo elemento della coda Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 29/ 33  3. Implementazione concreta con lista Utilizziamo una lista per realizzare la coda: I quale tipo di lista conviene utilizzare: doppiamente concatenate, circolari? I inserimenti vengono fatti in testa, estrazioni in coda I usiamo una lista semplice ma aggiungiamo un puntatore all’ultimo elemento della coda Q.head / key next Q.tail Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 29/ 33  3. Implementazione concreta con lista I Q.head indica l’elemento da estrarre Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 30/ 33  3. Implementazione concreta con lista I Q.head indica l’elemento da estrarre I Q.tail indica l’ultimo elemento inserito Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 30/ 33  3. Implementazione concreta con lista I Q.head indica l’elemento da estrarre I Q.tail indica l’ultimo elemento inserito I come si controlla se la coda sia vuota? Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 30/ 33  3. Implementazione concreta con lista I Q.head indica l’elemento da estrarre I Q.tail indica l’ultimo elemento inserito I come si controlla se la coda sia vuota? Q.head == nil ⇐⇒ la coda è vuota Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 30/ 33  3. Implementazione concreta con lista I Q.head indica l’elemento da estrarre I Q.tail indica l’ultimo elemento inserito I come si controlla se la coda sia vuota? Q.head == nil ⇐⇒ la coda è vuota I ma comunque teniamo conto del numero di elementi in Q.N Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 30/ 33  3. Implementazione concreta con lista E NQUEUE(Q, t) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista E NQUEUE(Q, t) if Q.N == 0 then Q.head ← t Q.tail ← t else Q.tail.next ← t Q.tail ← t Q.N ← Q.N + 1 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista S IZE(Q) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista S IZE(Q) return Q.N Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista E MPTY(Q) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista E MPTY(Q) if Q.N == 0 then return true return false Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista F RONT(Q) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista F RONT(Q) if Q.N == 0 then errorunderflow else return Q.head Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista D EQUEUE(Q) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista D EQUEUE(Q) if Q.N == 0 then errorunderflow else t ← Q.head Q.head ← Q.head.next Q.N ← Q.N − 1 return t Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Implementazione concreta con lista (...sentinella aiuterebbe?) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 33  3. Confronto delle due implementazioni I complessità temporale delle operazioni? Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 32/ 33  3. Confronto delle due implementazioni I complessità temporale delle operazioni? sono tutte O(1) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 32/ 33  3. Confronto delle due implementazioni I complessità temporale delle operazioni? sono tutte O(1) I complessità spaziale delle strutture? con l’array O(M) (proporzionale al numero massimo di elementi), con le liste O(N) (ma c’è l’overhead dovuto ai puntatori) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 32/ 33  3. Confronto delle due implementazioni I complessità temporale delle operazioni? sono tutte O(1) I complessità spaziale delle strutture? con l’array O(M) (proporzionale al numero massimo di elementi), con le liste O(N) (ma c’è l’overhead dovuto ai puntatori) I con l’array bisogna stabilire a priori il numero massimo di elementi, con le liste no Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 32/ 33  3. Utilizzo della struttura dati coda I buffer Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 33/ 33  3. Utilizzo della struttura dati coda I buffer I visita in ampiezza di grafi Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 33/ 33  3. Utilizzo della struttura dati coda I buffer I visita in ampiezza di grafi I simulazione Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 33/ 33