Appunti di Strutture Dati

Appunti di Strutture Dati

Questa pagina presenta un ristretto vademecum di nozioni utili per il corso d’Informatica di Strutture Dati. È possibile trovarne una possibile implementazione in questo repository.

Tipi di dati astratti (ADT)

I tipi di dati astratti sono il risultato del paradigma dell’astrazione applicato al design di strutture dati. È altresì un modello matematico di una struttura dati che specifica il tipo di dati contenuti, le operazioni possibili su questi e i parametri delle operazioni. Un ADT specifica cosa fa ogni operazione, ma non come. In Java possono essere espressi attraverso le interfacce.

Stack

Uno stack è una collezione di oggetti che sono inseriti e rimossi seguendo il principio last-in, first-out (LIFO) e supporta le seguenti operazioni:

  • push(x): inserisce l’elemento x;
  • pop(): cancella e restituisce l’ultimo elemento inserito;
  • top(): restituisce l’ultimo elemento inserito;
  • size(): restituisce il numero di elementi;
  • isEmpty(): restituisce true o false a seconda che sia vuoto o meno.

Queue

Una coda è una collezione di oggetti che sono inseriti e rimossi seguendo il principio first-in, first-out (FIFO) e supporta le seguenti operazioni

  • enqueue(x): inserisce l’elemento x alla fine della coda;
  • dequeue(): cancella e restituisce l’elemento all’inizio della coda;
  • front(): restituisce l’elemento all’inizio della coda;
  • size(): restituisce il numero di elementi;
  • isEmpty(): restituisce true o false a seconda che sia vuota o meno.

Deque

La coda double-ended, o deque, è più generale dello stack e della queue, permettendo operazioni all’inizio e alla fine della coda e supporta le seguenti operazioni:

  • addFirst(x): inserisce l’elemento x all’inizio;
  • addLast(x): inserisce l’elemento x alla fine;
  • removeFirst(): cancella e restituisce il primo elemento;
  • removeLast(): cancella e restituisce l’ultimo elemento;
  • getFirst(): restituisce il primo elemento;
  • getLast(): restituisce l’ultimo elemento;
  • size(): restituisce il numero di elementi;
  • isEmpty(): restituisce true o false a seconda che sia vuota o meno.

Notazione postfissa

La notazione postfissa è un metodo non ambiguo per la scrittura di espressioni aritmetiche senza l’utilizzo delle parentesi. Sia (exp₁ op exp₂) una normale espressione in notazione infissa, la versione postfissa è pexp₁ pexp₂ op.

Per esempio ((5 + 2) * (8 - 3)) / 4 corrisponde a 5 2 + 8 3 - * 4 /

List

Una lista è una rappresentazione di una sequenza lineare di elementi e ogni locazione è definita da un index che va da zero al numero di elementi nella lista meno uno.

Un Array List utilizza un semplice array per l’implementazione, e supporta le seguenti operazioni:

  • get(i): restituisce l’elemento di indice i;
  • set(i, x): restituisce e rimpiazza l’elemento di indice i con l’elemento x;
  • remove(i): cancella e restituisce l’elemento di indice i;
  • size(): restituisce il numero di elementi;
  • isEmpty(): restituisce true o false a seconda che sia vuoto o meno.

Una Node List utilizza il tipo di dato astratto Position con dei puntatori alla posizione precedente e successiva e supporta le seguenti operazioni:

  • first(): restituisce la posizione del primo elemento;
  • last(): restituisce la posizione dell’ultimo elemento;
  • prev(p): restituisce la posizione dell’elemento che precede la posizione p;
  • next(p): restituisce la posizione dell’elemento che segue la posizione p;
  • addBefore(p, x): inserisce l’elemento x nella posizione che precede p e ne restituisce la posizione;
  • addAfter(p, x): inserisce l’elemento x nella posizione che segue p e ne restituisce la posizione;
  • addLast(x): inserisce l’elemento x alla fine;
  • addFirst(x): inserisce l’elemento x all’inizio;
  • addLast(x): inserisce l’elemento x alla fine;
  • remove(p): cancella e restituisce l’elemento in posizione p;
  • set(p, x): sostituisce con x l’elemento in posizione p, restituendolo in output;
  • size(): restituisce il numero di elementi;
  • isEmpty(): restituisce true o false a seconda che sia vuoto o meno.

Sequence fornisce le funzionalità di ambedue queste implementazioni, oltre alle seguenti operazioni, attraverso l’uso di due metodi ponte, atIndex(i) e indexOf(p):

  • getFirst(): restituisce il primo elemento;
  • getLast(): restituisce l’ultimo elemento;
  • removeFirst(): cancella e restituisce il primo elemento;
  • removeLast(): cancella e restituisce l’ultimo elemento.

Iterator

Iterator è un design pattern software che astrae il processo di scansione attraverso una sequenza di elementi, uno alla volta, supportando i seguenti metodi:

  • next(): restituisce il prossimo elemento;
  • hasNext(): testa se ci sono altri elementi.

Priority Queue

Una priority queue è una collezione di elementi con priorità che permette l’inserimento di elementi in modo arbitrario e la rimozione dell’elemento che ha priorità maggiore. Quando un elemento viene aggiunto alla coda a priorità, l’utente designa la sua priorità fornendo una chiave associata. I metodi principali sono:

  • insert(k, v): inserisce e restituisce l’entry (k, v);
  • removeMin(): restituisce e rimuove l’entry con chiave più piccola;

Tree

Un albero è una struttura dati astratta non lineare tra le più importanti nella computazione che conserva gli elementi in maniera gerarchica. Ad eccezione del top element, detto root, ogni elemento in un albero ha un genitore e zero o più figli.

Formalmente un albero T è un insieme di nodi contenenti gli elementi e tali nodi hanno una relazione padre-figlio che soddisfa le seguenti proprietà:

  • Se T non è vuoto, ha un nodo speciale, chiamato radice di T, ha non ha genitori.
  • Ogni nodo v di T diverso dalla radice ha un unico nodo genitore w; ogni nodo che ha w come genitore è detto figlio di w.

Due nodi figli dello stesso genitore sono detti sibling (fratelli). Un nodo v è esterno se non ha figli. Un nodo v è interno se ha uno o più figli. I nodi esterni sono anche chiamati foglie.

Un nodo u è antenato di un nodo v se u = v oppure u è antenato del genitore di v. Un nodo v è discendente di un nodo u se u è un antenato di v. La profondità di un nodo è data dal numero di antenati del nodo meno il nodo stesso.

L’altezza di un nodo è zero se è una foglia; altrimenti uno più l’altezza massima tra i figli del nodo. Il sottoalbero di T con radice al nodo v è l’albero che consiste di tutti i discendenti di v in T (incluso v), si scrive Tw.

Un arco di un albero T è una coppia di nodi (u,v) tale che u è genitore di v, o viceversa. Un cammino di T è una sequenza di nodi tali che ogni due nodi consecutivi nella sequenza formano un arco.

Un albero è ordinato se c’è un ordine lineare tra i figli di ogni nodo.

I metodi del TDA Tree sono:

  • size();
  • isEmpty();
  • iterator(): restituisce un iteratore di tutti gli elementi contenuti nei nodi dell’albero;
  • positions(): restituisce una collezione iterabile delle posizioni di tutti gli elementi dell’albero;
  • root(): restituisce la posizione della radice;
  • parent(p): restituisce la posizione del genitore del nodo in posizione p;
  • children(p): restituisce una collezione iterabile delle posizioni dei figli del nodo in posizione p;
  • isInternal(p): testa se il nodo in p è interno;
  • isExternal(p): testa se il nodo in p è esterno;
  • isRoot(p): testa se il nodo in p è la radice;
  • replace(p, e): rimpiazza l’elemento del nodo in p con e, restituendo il vecchio elemento.

Binary Tree

Un albero binario è un albero ordinato con le seguenti proprietà:

  • Ogni nodo ha al più due figli.
  • Ogni nodo figlio è segnato come figlio sinistro o figlio destro.
  • Il figlio sinistro precede il figlio destro nell’ordine dei figli del nodo.

Un sottoalbero con radice che è figlia sinistra o destra di un nodo v è chiamato rispettivamente sottoalbero sinistro o sottoalbero destro di v. Un albero binario è proprio, ovvero completo, se ogni nodo ha o zero o due figli.

Oltre ai metodi di Tree, vi sono operazioni addizionali:

  • left(p): restituisce la posizione del figlio sinistro del nodo in p;
  • right(p): restituisce la posizione del figlio destro del nodo in p;
  • hasLeft(p): restituisce true se il nodo in p ha figlio sinistro;
  • hasRight(p): restituisce true se il nodo in p ha figlio destro;

Heap

Una migliore implementazione della priority queue è data usando una struttura dati chiamata binary heap. Questa permette l’inserimento e la rimozione in tempo logaritmico, attraverso l’utilizzo di un albero binario.

Un heap è quindi un albero binario T che soddisfa due proprietà:

  • Heap-Order: in un heap T, per ogni posizione p diversa dalla radice, la chiave conservata in p è maggiore o uguale della chiave conservata nel genitore di p.
  • Albero binario completo: un heap T con altezza h è un albero binario completo se tutti i livelli 0, 1, 2, …, h-1 di T hanno il massimo numero di nodi possibile.

Oltre ai metodi del TDA Binary Tree, supporta i seguenti:

  • add(e): inserisce una foglia, al primo nodo che ha meno di due figli, che contiene l’elemento e, restituendone la posizione;
  • remove(): rimuove l’ultimo nodo dell’albero restituendone l’elemento;

Adaptable Priority Queue

Una coda a priorità adattabile, estende la struttura dati astratta della coda a priorità, fornendo funzionalità aggiuntive, quali la rimozione, il rimpiazzo delle chiavi e dei valori in maniera efficiente. Per far ciò utilizza un meccanismo per accedere direttamente ad un’entrata della coda: Locator, estende Entry e aggiunge un campo che tiene traccia del posto dove si trova tale entrata nella struttura dati usata per implementare la coda. Questo TDA estende il TDA Priority Queue con le seguenti operazioni:

  • remove(e): rimuove e restituisce l’entry e;
  • replaceValue(e, v): rimpiazza con v il valore dell’entry e, restituendo il vecchio valore;
  • replaceKey(e, k): rimpiazza con k la chiave dell’entry e, restituendo la vecchia chiave;

Map

Una mappa è una struttura dati astratta progettata per archiviare e recuperare in modo efficiente dei valori in base ad un’unica chiave che li identifica. Praticamente, una mappa archivia coppie di key-value (k, v), chiamate entries, dove k è la chiave e v il valore corrispondente. Le chiavi devono essere uniche.

Le mappe sono anche conosciute come array associativi, perché la chiave ha funzione simile all’index, tuttavia tale chiave può anche non essere numerica.

Questo TDA supporta le seguenti operazioni:

  • size();
  • isEmpty();
  • get(k): restituisce l’entry con chiave k, se esiste;
  • put(k, v): Se non esiste entry con chiave uguale a k, aggiunge l’entry (k, v) non restituendo nulla, altrimenti rimpiazza con v il valore della entry esistente, restituendo il vecchio valore;
  • remove(k): rimuove e restituisce l’entry con chiave k, se esiste;
  • keys(): restituisce una collezione iterabile delle chiavi;
  • values(): restituisce una collezione iterabile dei valori associati alle chiavi;
  • entries(): restituisce una collezione iterabile delle entries.

Dictionary

Il tipo di dato astratto dictionary è molto simile all’ADT Map, tuttavia sono permessi più elementi con la stessa chiave.

Annovera tra le sue operazioni:

  • size();
  • isEmpty();
  • find(k): restituisce l’entry con chiave k, se esiste;
  • findAll(k): restituisce una collezione iterabile di tutte le entry con chiave k;
  • entries(): restituisce una collezione iterabile delle entries.
  • insert(k, v): inserisce e restituisce l’entrata (k, v).
  • remove(e): rimuove e restituisce l’entrata e, se appartiene al dizionario.

Hash Table

Una tabella hash è una struttura dati usata per mettere in corrispondenza una chiave con un valore. Attraverso una tabella hash è possibile implementare TDA associativi come Map, Dictionary e Set, mediante un array.

Nelle tabelle hash, invece di scorrere le entrate e confrontare le chiavi, si cerca di accedere agli elementi nella tabella in modo diretto trasformando le chiavi in indirizzi della tabella.

Una tabella hash, per un dato tipo di chiavi, consiste di una funzione hash e un array chiamato bucket. Una funziona hash mappa un insieme di chiavi in un intervallo prefissato di interi e h(x) è chiamato valore hash di x. Comunque, tale computazione avviene in due fasi: mappatura di della chiave k in un intero chiamato hash code, mappatura dell’hash code in un intero nel range della capacità del bucket mediante una funzione di compressione.

Metodi per la computazione dell Hash Code

Tale computazione deve evitare quanto più possibile le collisioni.

  • Cast ad intero;
  • Somma delle parti;
  • Hash Code Polinomiale: sia a ≠ 0 e a ≠ 1, p(a) = k₀aᵐ⁻¹ + k₁aᵐ⁻² + ... + kₘ₋₂a + kₘ₋₁. Ogni componente della m-upla dà un contributo che dipende sia dal suo valore che dalla sua posizione.

Funzione di compressione

Siano i l’hash code di k ed N la capacità del bucket.

  • Metodo della divisione: |i| mod N;
  • Metodo MAD (multiply, add and divide): |ai + b| mod N, con a e b costanti intere scelte a caso tali che a > 0, b ≥ 0, a mod N ≠ 0 ed N è primo.

Schemi di risoluzione di una collisione

Quali siano i metodi utilizzati per la computazione dell’hash code e per la compressione, c’è comunque il rischio che si verifichi una collisione, ovvero due chiavi che generano lo stesso valore hash. Per gestire questa situazione si può utilizzare una di queste due strategie:

  • Separate Chaining: le entrate che hanno generato la collisione vengono memorizzate in una sequenza;
  • Open addressing: una delle entrate che hanno generato la collisione viene sistemata in un’altra cella tella tabella.

Binary Search Tree

Un albero di ricerca binario è un albero binario che memorizza in ciascun nodo una chiave in modo tale che se u, v e w sono tre nodi interni tale che u si trova nel sottoalbero sinistro di v e w si trova nel sotto albero destro di v, allora: key(u) ≤ key(v) ≤ key(w), ovvero è definita una relazione di ordine totale sulle chiavi.

Una visita preorder di un albero T, visita prima la radice e poi i sottoalberi radicati nei suoi figli, seguendo l’ordine dei figli, se c’è un ordine. Una visita inorder, di un albero di ricerca binario visita le chiavi in ordine non decrescente. Una visita postorder in un certo senso è l’opposto della visita preorder, perché visita prima i sottoalberi radicati nei figli della radice, seguendone l’ordine, e poi la radice stessa.

Set

Un insieme è una collezione di elementi non ordinata, senza duplicati. Un multiset, oppure bag è simile al set, ma consente la presenza di duplicati. Una multimap è simile ad una map, perché associa delle chiavi ai valori, tuttavia, la stessa chiave può avere più valori. Supporta, oltre ai metodi generici size() e isEmpty(), le seguenti operazioni:

  • union(B): invocato su A, rimpiazza A con l’unione di A e B;
  • intersect(B): invocato su A, rimpiazza A con l’intersezione di A e B;
  • subtract(B): invocato su A, rimpiazza A con la differenza di A e B;

Template method

Per rendere più efficienti le operazioni insiemistiche è utile definire una relazione d’ordine totale sugli elementi dell’insieme, così da poter utilizzare un algoritmo generico di merge.

Nello specifico, l’algoritmo generico di merge, utilizza i metodi ausiliari bothAreEqual, aIsLess e bIsLess, e le operazioni di intersection, union e subtract riscrivono alcuni di questi:

  • Intersection: riscrive il metodo bothAreEqual poiché l’intersezione ha bisogno di sapere quali elementi appaiono in entrambi gli insiemi;
  • Union: copia ogni elemento, ignorando eventuali duplicati, quindi riscrive tutti e tre i metodi ausiliari;
  • Subtract riscrive il metodo aIsLess, poiché ha bisogno solo degli elementi che appaiono in A e non in B.

Partition

Una partizione è una collezione di insiemi S₁, S₂, ..., Sₖ a due a due disgiunti, ovvero ∀ i ≠ j Sᵢ ∩ Sⱼ = ∅.

Per un implementazione efficiente, ad ogni elemento possiamo associare l’insieme a cui appartiene. Quindi avremo una mappa che ha come voci le coppie elemento-insieme.

Quando si esegue un’unione, spostiamo sempre gli elementi dall’insieme più piccolo a quello più grande, in modo da avere l’euristica dell’unione pesata.

Per la rimozione di un insieme da rimuovere, invece di cercare la posizione di tale insieme, è utile inserire nella classe che implementa Set una variabile che tenga traccia di questa posizione.

Il TDA Partition supporta i seguenti metodi:

  • makeSet(x): crea l’insieme contenente il singolo elemento x e lo aggiunge alla partizione;
  • union(A, B): aggiunge alla partizione l’insieme unione di A e B, distruggendoli;
  • find(x): restituisce l’insieme che contiene l’elemento x;

Graph

Un grafo è un modo di rappresentare relazioni che esistono tra coppie di oggetti. È composto da un insieme di oggetti, chiamati vertici, e da una collezione di collegamenti tra tali vertici, chiamati archi.

Gli archi di un grafo possono essere direzionati e non, quindi se in un grafo tutti gli archi sono direzionati, tale grafo è direzionato, se invece tutti gli archi sono non direzionati, tale grafo è non direzionato. I grafi misti contengono sia archi direzionati che non direzionati.

  • Arco direzionato: (u, v), coppia ordinata di vertici, u è l’origine, v è la destinazione.
  • Arco non direzionato: (u, v), coppia non ordinata di vertici.

I vertici collegati da un arco sono chiamati estremità dell’arco. Se un arco è diretto, la sua prima estremità è l’origine e l’altra è la destinazione. Due vertici u e v sono adiacenti se esiste un arco (u, v). Un arco incide un vertice se tale vertice è sua estremità. Gli archi uscenti di un vertice sono quegli archi diretti la cui origine è il vertice stesso. Gli archi entranti di un vertice sono quegli archi diretti la cui destinazione è il vertice stesso. Il grado di un vertice è il numero di archi che incidono sul vertice stesso. Un autociclo è un arco che ha entrambe le estremità uguali ad uno stesso vertice.

Un percorso è una sequenza che comincia e finisce con un vertice, in cui si alternano vertici e archi e ciascun arco è situato tra le sue estremità. Un percorso semplice è un percorso in cui tutti i vertici e tutti gli archi sono distinti. Un ciclo è un percorso che inizia e finisce nello stesso vertice. Un ciclo semplice è un ciclo in cui tutti i vertici sono distinti ad eccezione del primo e dell’ultimo. Un percorso diretto è un percorso in cui ogni arco è diretto ed è preceduto dalla sua origine e seguito dalla sua destinazione. Un ciclo diretto è un percorso diretto che comincia e termina nello stesso vertice.

Metodi supportati

  • numVertices(): restituisce il numero di vertici;
  • numEdges(): restituisce il numero di archi;
  • endVertices(e): restituisce un array con le estremità di e;
  • opposite(v, e): restituisce il vertice incidente su e opposto a v;
  • areAdjacent(v, w): restituisce true se i vertici v e w sono adiacenti;
  • incidentEdges(v): restituisce una collezione iterabile degli archi incidenti su v;
  • vertices(): restituisce una collezione iterabile dei vertici;
  • edges(): restituisce una collezione iterabile degli archi;
  • replace(v, x): sostituisce l’elemento nel vertice v con x e restituisce il vecchio elemento;
  • replace(e, x): sostituisce l’elemento nell’arco e con x e restituisce il vecchio elemento;
  • insertVertex(x): inserisce e restituisce un vertice che memorizza x;
  • insertEdge(v, w, x): inserisce e restituisce un arco (v, w) che memorizza x;
  • removeVertex(v): cancella il vertice v e i suoi archi incidenti restituendone l’elemento;
  • removeEdge(e): cancella l’arco e restituendone l’elemento;

Traversal

Formalmente, un traversal è una procedura sistematica per l’esplorazione di un grafo esaminando tutti i vertici e gli archi. È efficiente se visita tutti i vertici e gli archi in tempo proporzionale al loro numero, quindi lineare.

Depth-First Search

DFS è un algoritmo di traversal. Comincia in un vertice s di G, quindi si considera un arco incidente nel vertice corrente e se tale arco di porta in un vertice che è già visitato, lo si ignora; altrimenti, il nuovo vertice diventa quello corrente e si marca come visitato. Se si raggiunge un vicolo cieco, si torna indietro e si provano gli archi non ancora visitati. Il processo termina quando il backtracking ci riporta al vertice iniziale s.

Dijkstra’s Algorithm

Si tratta di un algoritmo che accresce iterativamente una nuvola di vertici intorno ad s, vertice iniziale, in ordine della distanza da s. Quindi, ad ogni iterazione, il prossimo vertice scelto è il vertice esterno alla nuvola che è più vicino a s. L’algoritmo termina quando non ci sono più vertici esterni alla nuvola e a questo punto avremo il percorso più breve da s a tutti i vertici di G raggiungibili da s.

Kruskal’s Algorithm

Si tratta di un algoritmo per la costruzione del minimum spanning tree. Inizialmente ogni vertice ha il proprio cluster. L’algoritmo quindi considera un arco alla volta, ordinati per peso crescente. Se un arco e collega vertici in due cluster differenti, allora e viene aggiunto all’insieme degli archi del minimum spanning tree, e i due alberi vengono uniti con l’aggiunta di e. Se, invece, e collega due vertici nello stesso cluster, allora viene scartato. Appena l’algoritmo ha aggiungo abbastanza archi per formare lo spanning tree, termina e restituisce quest’albero che sarà il minimo albero ricoprente.