Unità C1

Estendere i linguaggi:i tipi di dato astratti

Obiettivi

• Conoscere le principali strutture dati esistenti

• Conoscere ed essere in grado di implementare le operazioni definite sulle strutture dati

• Saper scegliere la struttura dati più adatta alla soluzione di un problema

Insiemi dinamici

• Caratteristica di un insieme dinamico: il numero e la disposizione degli elementi che lo compongono può variare nel corso della sua esistenza

• Elementi dell’insieme: alcuni tipi di insiemi dinamici sono composti da elementi formati da informazioni che li identificano chiave e da dati satellite.

• La chiave è un campo (o un insieme di campi) che consente di identificare in modo univoco un elemento.

• I dati satellite sono le informazioni memorizzate nell’elemento.

Chiavi e dati satelliti

• Un esempio: gestione degli studenti della scuola.

• Ogni singolo elemento rappresenta uno studente.

• La chiave può essere per esempio il numero del libretto scolastico (o il codice fiscale)

• I dati satellite sono tutti i dati che vengono memorizzati per ogni studente: – Cognome

– Nome

– Indirizzo

– Classe frequentata

– …

Chiavi e chiavi artificiali

• Non sempre è possibile individuare una chiave di identificazione degli elementi

• In molti casi si definisce una “chiave artificiale” (es il codice fiscale, il numero di libretto o in alcuni casi un ID (numero intero progressivo assegnato nel momento in cui un elemento viene inserito nell’insieme).

• La chiave può essere utilizzata per ordinare gli elementi in modo crescente o decrescente.

Puntatori

• I puntatori nei linguaggi di programmazione consentono di recuperare un dato conoscendo l’indirizzo di memoria in cui è memorizzato.

• Un puntatore è una variabile contenente un indirizzo di una cella di memoria.

• Un puntatore, quindi, è una variabile che, anziché contenere un valore numerico o una stringa di testo, mantiene l’indirizzo di memoria in cui è memorizzata l’informazione.

Operazioni sugli insiemi

• Le operazioni che si possono effettuare sugli insiemi dinamici si suddividono in:– operazioni di interrogazione

operazioni di sola lettura per recuperare informazioni dall’insieme

– operazioni di modificaconsentono di inserire, cancellare e riordinare gli elementi dell’insieme cambiandone il numero e/o la disposizione

Le principali operazioni

Strutture dati

• Per gestire un insieme dinamico di elementi occorre implementarlo mediante una struttura dati.

• Una struttura dati è composta da nodi, ciascuno dei quali contiene un elemento dell’insieme ed eventuali altre informazioni (puntatori) che servono per la gestione della struttura.

Tipi di strutture dati

• Le strutture dati possono essere suddivise in due grandi famiglie: – lineari

l’insieme degli elementi è organizzato in modo sequenziale.

– non linearinon prevedono che un elemento sia seguito esclusivamente da un altro elemento (Esempio la struttura ad albero del filesystem )

Le strutture fisiche dei dati

• Per implementare le strutture dati, si devono utilizzare le strutture fisiche fornite dai linguaggi che possono avere dimensione statica o dinamica.

• Un array, per esempio, è una struttura di memorizzazione dalla dimensione statica.

• Strutture fisiche dalla dimensione dinamica si possono implementare grazie all’uso dei puntatori.

Strutture dati lineari

• Una struttura dati si dice lineare se i suoi elementi sono organizzati in modo sequenziale, ovvero se logicamente gli stessi sono posizionati uno dopo l’altro.– Pila– Coda– Lista

Pila (stack)

• La pila è una struttura dati di tipo LIFO che garantisce che l’ultimo elemento depositato nella pila sia il primo a essere servito.

• LIFO (Last-In First-Out, “l’ultimo arrivato è il primo ad essere servito”)

• Esempio pila di piatti, pila di libri, di monete

Operazioni sulla pila

• push– consente di inserire un nuovo elemento in testa alla

pila• pop

– permette di estrarre il primo elemento in cima alla pila

• top– consente di leggere il primo elemento in cima alla

pila senza estrarlo da essa• vuota

– restituisce true se la pila è vuota, false in caso contrario

Coda

• La coda è una struttura dati di tipo FIFO che garantisce che il primo elemento inserito sia il primo a essere servito.

• FIFO (First-In First-Out), il primo elemento a entrare è anche il primo a uscire

Operazioni sulla coda

• Le tipiche operazioni che si possono effettuare su una coda sono le seguenti:– enqueue (accodare)

consente di accodare un elemento alla coda

– dequeue (togliere dalla coda)consente invece di eliminare l’elemento che da più tempo è presente nella coda

Lista concatenata

• La lista concatenata è una collezione ordinata di elementi, ciascuno dei quali è concatenato al successivo mediante un riferimento che indica dove andare a prendere il successivo elemento.

• In una lista concatenata non è possibile accedere in modo diretto a un elemento, bensì è necessario scorrere tutti gli elementi fino a raggiungere quello cercato.

• Ogni elemento della lista è contenuto in un nodo, in cui è presente anche un puntatore all’elemento successivo.

• L’ultimo elemento della lista avrà il puntatore nullo, mentre il puntatore al primo nodo si conserva in una variabile opportuna.

Operazioni sulla lista

• Le operazioni principali che si possono effettuare su una lista sono:– inserimento– ricerca– cancellazione

• Esempio di cancellazione:

Strutture dati non lineari

• Una struttura dati non lineare è composta da nodi posti in base a uno schema non sequenziale.

• Nelle strutture dati lineari, se ci troviamo posizionati su un nodo, possiamo decidere al più di andare sul nodo successivo come nelle liste concatenate, o sul nodo precedente come nelle liste concatenate bidirezionali.

• Nelle strutture dati non lineari, invece, partendo da un nodo abbiamo la possibilità di spostarci in più direzioni.

• Una struttura dati di questo genere assomiglia maggiormente a una rete di nodi anziché a una sequenza.

Un esempio: albero genealogico

Strutture non lineari: grafo

• Un grafo è una struttura dati non lineare composta da nodi e archi che li connettono.

• Esistono due principali categorie di grafi:– grafi orientati;– grafi non orientati.

Grafo orientato

• In un grafo orientato i nodi sono detti vertici e gli archi spigoli.

• Gli spigoli che connettono i vertici tra loro hanno una direzione e per definirla si utilizza una freccia.

• In un grafo orientato è possibile avere cappi.

• Un cappio è uno spigolo che inizia e termina sullo stesso vertice.

• Uno spigolo che esce da un vertice A o che entra in un vertice B si dice, rispettivamente, incidente da A o incidente a B.

• Il numero di spigoli uscenti da un vertice si chiama grado uscente.

• Il numero di spigoli entranti in un vertice si chiama invece grado entrante.

• Il grado di un vertice è il suo grado entrante più il suo grado uscente.

Grado, cammino

• In un grafo (orientato e non) il percorso per andare da un nodo a un altro è chiamato cammino e la sua lunghezza è pari al numero di archi attraversati.

• Un cammino si dice semplice se tutti i nodi della sequenza sono distinti tra loro.

• In un grafo orientato non è detto che esista un cammino per andare da un nodo a un altro, in quanto il percorso è condizionato dalla direzione degli spigoli.

• Se da un nodo A è possibile andare a un nodo B, si dice anche che B è raggiungibile da A tramite un determinato cammino c.

• Il grado di un vertice di un grafo non orientato è semplicemente il numero di archi incidenti su di esso.

• Un grafo non orientato si dice connesso se ogni coppia di nodi è collegata con un cammino.

• Un grafo non orientato, connesso e aciclico è detto albero libero, o più semplicemente un albero.

Albero

• Un albero è un grafo non orientato, connesso e aciclico.

• La rappresentazione grafica è simile a un albero con la radice in alto e le foglie in basso

• Un albero è una struttura dati gerarchica composta da nodi padri e nodi figli collegati da archi (rami).

• Un nodo figlio è correlato a uno e un solo nodo padre.

• Il nodo radice è il nodo da cui parte la struttura ad albero e che non possiede un nodo padre.

• Un nodo foglia non possiede nodi figli.• La profondità di un nodo è la distanza tra esso

ed il nodo radice.• La profondità maggiore tra tutti i nodi

dell’albero è l’altezza dell’albero.• Il grado di un nodo è il numero di figli che esso

possiede.

Albero (altre caratteristiche)

• Un antenato di un nodo x di un albero è qualunque nodo y che si trovi sull’unico cammino che porta dalla radice a x

• x è un discendente di y• Se i nodi di un albero

possono avere al massimo n figli, si parla di alberi n-ari

• Un albero si dice completo se i nodi foglia hanno tutti la stessa altezza e ogni altro nodo ha il grado pari al grado massimo.

Albero binario

• Un albero binario è un albero i cui nodi possono avere al più due nodi figli, denominati figlio destro e figlio sinistro.

• Un albero binario può essere definito anche in modo ricorsivo:– non contiene alcun nodo;– oppure contiene un nodo radice, un albero binario

detto sottoalbero sinistro (eventualmente vuoto) e un albero binario chiamato sottoalbero destro (eventualmente vuoto).

• Negli alberi binari esistono 3 tipi di ricerca:– PreOrdine

visita prima il nodo padre, poi il sottoalbero sinistro e infine quello destro

– PostOrdine visita prima il sottoalbero sinistro, poi quello destro e infine il nodo padre

– InOrdine visita prima il sottoalbero sinistro, poi il nodo padre e infine il sottoalbero destro.