Prof. Pier Luca Lanzi

Algoritmi e Strutture DatiAlgoritmi 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

Tipi di Dati Astratti

• Sono definiti da due parti: la specifica e l’implementazione

• La specifica è il manuale d'uso, nasconde i dettagli implementativi all'utilizzatore

• L’implementazione è la realizzazione vera e propria

• EsempiNumeri reali (la specifica) – IEEE754

(l’implementazione)Grafi (la specifica) – matrici d’adiacenza

(l’implementazione)

4

Prof. Pier Luca Lanzi

Strutture Dati

• I dati sono riuniti in insiemi detti strutture di dati Sono particolari tipi di dato, caratterizzati più

dall'organizzazione dei dati più che dal tipo dei dati stessi Il tipo dei dati contenuti può essere addirittura

parametrico Esempio: un vettore di interi, un vettore di stringhe

• Una struttura di dati è composta da Un modo sistematico di organizzare i dati Un insieme di operatori che permettono di manipolare la

struttura

• Tipologie di strutture di dati: Lineari / non lineari (presenza di una sequenza) Statiche / dinamiche (variazione di dimensione,

contenuto) Omogenee / disomogenee (dati contenuti)

5

Prof. Pier Luca Lanzi

Sequenza

• Struttura di dati Dinamica e lineare Contenente elementi generici (Item), potenzialmente

anche duplicati Ordine all’interno della sequenza è importante

• Interfaccia È possibile aggiungere / togliere elementi, specificando la

posizione s = s1, s2, ..., sn

L’elemento si è in posizione posi

Esistono le posizioni (fittizie) pos0, posn+1

È possibile accedere direttamente ad alcuni elementi (testa / coda)

È possibile accedere sequenzialmente a tutti gli altri elementi

6

Prof. Pier Luca Lanzi

Operazioni su Sequenze (1) 7

Prof. Pier Luca Lanzi

Operazioni su Sequenze (2) 8

Prof. Pier Luca Lanzi

Insiemi

• Struttura dati “generale”: insieme dinamicoPuò crescere, contrarsi, cambiare contenutoOperazioni base: inserimento, cancellazione,

verifica contenimento Il tipo di insieme (= struttura) dipende dalle

operazioni

• Elementi Elemento: oggetto “puntato” da un

riferimento/puntatoreComposto da: campo chiave di identificazione,

dati satellite, campi che fanno riferimento ad altri elementi dell'insieme

9

Prof. Pier Luca Lanzi

Operazioni su Insiemi 10

Prof. Pier Luca Lanzi

Dizionari

• Il dizionario rappresenta una relazione univoca R : D → C Insieme D è il dominio (elementi detti chiavi) Insieme C è il codominio (elementi detti valori)

• Associazione chiave-valore

• Operazioni ammesse:Ottenere il valore associato ad una particolare

chiave (se presente), o nil altrimenti

Inserire una nuova associazione chiave-valore, cancellando eventuali associazioni precedenti;

Rimuovere un’associazione chiave-valore esistente

11

Prof. Pier Luca Lanzi

Operazioni su Dizionari 12

Prof. Pier Luca Lanzi

13Alberi e Grafi

• Un albero ordinato Un insieme finito di “nodi” Un nodo particolare è designato

come radice I rimanenti nodi, se esistono, sono

partizionati in insiemi ordinati e disgiunti, anch’essi alberi ordinati

• Grafi Insiemi di nodi e archi che

connettono i nodi

• Operazione tipica è la visita o ispezionecompleta di tutti i nodi

Prof. Pier Luca Lanzi

Discussione

• Le specifiche viste finora possono essere arricchite

• Operatori min() e max() nel tipo di dato Set, se esiste ordinamento totale

• Concetti di insieme e dizionario sono collegati Insieme delle chiavi/insieme dei valoriScorrere tutte le chiavi

14

Prof. Pier Luca Lanzi

Implementazione

• Alcune realizzazioni sono “naturali”Sequenza ↔ listaAlbero astratto ↔ albero basato su puntatori

• Esistono tuttavia realizzazioni alternative Insieme come vettore booleanoAlbero come vettore dei padri

• La scelta della struttura di dati ha riflessi sull’efficienza e sulle operazioni ammesseDizionario come hash table: lookup in tempo

O(1), ma niente ordinamentoDizionario come albero: lookup in tempo O(log

n), con ordinamento

15