Appunti dell'intera parte di programmazione del corso di Algoritmi e strutture dati

ADT

Scegliere una adeguata struttura dati per: o codificare le informazioni del problema proposto (in input,

risultati intermedi e finali) o consentire la manipolazione delle informazioni (le operazioni) Le informazioni

in forma utilizzabile da un sistema di elaborazione si dicono dati e sono memorizzati in strutture dati: o

interne (memoria centrale) o esterne (memoria di massa) o statiche (dimensione decisa in stesura del

programma e fissa nel tempo) o dinamiche (dimensione decisa in fase di utilizzo e variabile nel tempo)

Tipi di dato

Classificazione o base (standard), forniti dal linguaggio o definiti dall’utente, mediante definizioni di tipo e/o

funzioni o tipi di dati astratti: netta separazione tra definizione e implementazione

Standard: Tipi scalari (numeri e caratteri): o int (signed, unsigned, long, short) o float (double, long double)

o char Tipi strutturati (composti/aggregati) o array (vettori/matrici: campi omogenei) o struct (campi

eterogenei) o typedef permette di introdurre un nuovo nome per un tipo (da ricondurre a un tipo base,

scalare o composto/aggregato)

ADT: Tipi di Dato Astratto

▪ Scopo o livello di astrazione sui dati tale da mascherare completamente l’implementazione rispetto

all’utilizzo ▪ definizione o tipo di dato (valori + operazioni) accessibile SOLO attraverso un’interfaccia.

❑ ❑

Creazione di ADT Il C non ha un meccanismo semplice ed automatico di creazione di ADT L’ADT è

❑

realizzato come modulo con una coppia di file interfaccia/implementazione Enfasi su come nascondere i

dettagli dell’implementazione al client

Quasi ADT ▪ Interfaccia o definizione del nuovo tipo con typedef o raramente si appoggia su tipi base, in

generale è un tipo composto, aggregato o contenitore (struct wrapper) o Prototipi delle funzioni ▪

Implementazione o Il client include il file header, quindi vede i dettagli interni del dato e/o del wrapper. In

pratica dato che la typedef è fatta nel .h il client vede com’è definito il dato includendo il .h.

ADT di I classe Per impedire al client di vedere i dettagli della struct: ▪ il tipo di dato viene dichiarato nel file

.h di interfaccia come struttura incompleta, o come puntatore a struct incompleta, non viene quindi

definita la struct composto, aggregato o wrapper ▪ la struct viene invece completamente definita nel file .c ▪

il client utilizza unicamente puntatori alla struttura incompleta ▪ Il puntatore è opaco e si dice handle.

Quasi ADT o ADT di I classe? Per i casi semplici di dati composti o aggregati, che non prevedano allocazione

dinamica, il quasi ADT: ▪ è un ragionevole compromesso o non nasconde completamente i dettagli interni o

non richiede allocazione dinamica ▪ costituisce una soluzione più semplice e pratica.

Vantaggi dell’ADT ▪ enfasi sull’algoritmo e non sui dati ▪ prelude al polimorfirmo ▪ Tuttavia NON si tratta di

un tipo generico, ma di una soluzione che concentra eventuali modifiche all’interno dell’ADT Sono

accettabili soluzioni ▪ quasi ADT o con tipo visibile al client (che può tuttavia ignorare la visibilità), non

necessariamente dinamico ▪ ADT di I classe o dato nascosto, ma allocazione dinamica e puntatori

De-allocare o no? La de-allocazione ha senso se c’è stata allocazione, quindi solo nei casi 2 e 4, non nei casi

1 e 3. Due casi: il client ▪ rinuncia a de-allocare (oppure chiama funzioni di de-allocazione fittizie, che non

fanno nulla) ▪ tratta diversamente i casi con allocazione e senza, diventando dipendente da Item.

Conclusione ▪ accettabili le soluzioni 1 e 3 ▪ accettabile la soluzione 2 anche se disuniforme, purché il client

sia responsabile ▪ sconsigliata la soluzione 4: o coi quasi-ADT meglio non usare troppo allocazione dinamica

o (Oppure) Se si vuole allocazione dinamica, meglio non usare i quasi-ADT

Versione ADT di I classe ▪ L’ADT di prima classe ha senso per dati «complessi», quindi per le tipologie 3 e 4

di Item basati su struct ▪ Nelle tipologie 1 e 2 la chiave è talmente semplice che una soluzione a quasi ADT è

accettabile

Conclusione ▪ ADT di I classe con ITEMnew e ITEMscan garantisce al client completa responsabilità su

allocazione/deallocazione ▪ Consigliabile per tipologia 4 (campo stringa dinamica).

L’ ADT di I classe: 1. nasconde al client i dettagli 2. permette al client di istanziare più variabili del tipo

dell’ADT Un quasi ADT viola una delle 2 regole precedenti o entrambe. I quasi ADT visti sinora (per

composti/aggregati) violavano la prima regola.

Quasi-ADT (non ADT) per collezioni Per gli ADT collezioni di dati può bastare avere a disposizione un solo

contenitore, facendone una variabile globale dell’implementazione. Scompare il tipo di dato per la

collezione (non c’è un’istruzione typedef). Sarebbe meglio chiamarlo non ADT, ma si mantiene il nome

storico di «quasi ADT».

L’ADT pila (stack) Definizione: ADT che supporta operazioni di o STACKpush: inserimento in cima o

STACKpop: preleva (e cancella) dalla cima l’oggetto inserito più di recente Terminologia: la strategia di

gestione dei dati è detta LIFO (Last In First Out)

Vettore vs. lista: vantaggi/svantaggi Spazio: ▪ vettore: spazio allocato sempre pari al massimo previsto,

vantaggioso per stack quasi pieni ▪ lista: spazio utilizzato proporzionale al numero di elementi correnti,

vantaggioso per stack che cambiano rapidamente dimensione Tempo: ▪ push e pop T(n) = O(1)

Quasi ADT vs. ADT I classe Quasi ADT ▪ implementazione mediante variabili globali (dichiarate fuori da

funzioni) e invisibili da altri file sorgenti (static) ADT di I classe ▪ una struct puntata (da handle), contenente,

come campi, la variabili globali del quasi ADT.

Implementazione con vettore o inizializzazione dello stack (STACKinit): array dinamico la cui dimensione

viene ricevuta (come parametro maxN) dal programma client o NON viene controllato il rispetto dei casi

limite (pop da stack vuoto o push in stack pieno)

Implementazione con lista Stack di elementi in lista concatenata: ▪ coda della lista: primo elemento inserito

▪ testa della lista: ultimo elemento inserito ▪ push: inserzione in testa ▪ pop: estrazione dalla testa La

dimensione dello stack è (virtualmente) illimitata. ▪ inizializzazione dello stack come lista vuota (maxN non

viene utilizzato) ▪ funzione NEW per creare (dinamicamente) un nuovo elemento ▪ NON viene controllato il

rispetto del caso limite (pop da stack vuoto)

L’ADT coda (queue) Definizione: ADT che supporta operazioni di: o enqueue/put: inserisci un elemento

(QUEUEput) o dequeue/get: preleva (e cancella) l’elemento che è stato inserito meno recentemente

(QUEUEget) Terminologia: la strategia di gestione dei dati è detta FIFO (First In First Out).

Vettore vs. lista: vantaggi/svantaggi Spazio: ▪ vettore: spazio allocato sempre pari al massimo previsto,

vantaggioso per code quasi piene ▪ lista: spazio utilizzato proporzionale al numero di elementi correnti,

◼

vantaggioso per code che cambiano rapidamente dimensione Tempo: put e get T(n) = O(1)

Quasi ADT vs. ADT I classe Quasi ADT ▪ implementazione mediante variabili globali (dichiarate fuori da

funzioni) e invisibili da altri file sorgenti (static) ADT di I classe ▪ una struct puntata (da handle), contenente,

come campi, la variabili globali del quasi ADT.

Accesso a testa e coda Servono 2 variabili head e tail: ▪ head permette di accedere all’elemento in testa,

cioè il prossimo da estrarre ▪ tail permette di accedere: o implementazione a vettore: alla locazione che

segue l’ultimo elemento in coda, cioè alla posizione della prossima inserzione o implementazione a lista:

alla posizione dell’ultimo elemento in coda. head e tail sono: ▪ indici nell’implementazione a vettore ▪

puntatori nell’implementazione a lista.

Implementazione con vettore (O(n)) ▪ put assegna alla prima cella libera, se esiste, in fondo al vettore con

complessità O(1). L’indice tail contiene il numero di elementi nella coda ▪ get da posizione fissa (head = 0),

ma comporta scalare a sinistra tutti gli elementi restanti con costo O(n)

Implementazione con vettore (O(1)): buffer circolare ▪ put assegna alla prima cella libera, se esiste, in

posizione indicata da indice tail (O(1)) ▪ get da posizione variabile (head assume valori tra 0 e N-1). Le celle

del vettore occupate da elementi si spostano per via di put e get (buffer circolare).

Implementazione con lista Coda di elementi in lista concatenata: ▪ testa della lista (head): primo elemento

inserito ▪ coda della lista (tail): ultimo elemento inserito ▪ put: inserzione in coda ▪ get: estrazione dalla

testa La dimensione della coda è (virtualmente) illimitata:

L’ADT coda a priorità Definizione: ADT che supporta operazioni di: o insert: inserisci un elemento (PQinsert)

o extract: preleva (e cancella) l’elemento a priorità massima (o minima) (PQextractmax o PQextractmin).

Terminologia: la strategia di gestione dei dati è detta priority-first.

Complessità ▪ implementazione con vettore/lista NON ordinato: o inserzione in testa alla lista o in coda al

vettore -> O(1) o estrazione/visualizzazione del massimo/minimo con scansione -> O(N) o cambio di

priorità: richiede ricerca dell’elemento con scansione -> O(N) ▪ implementazione con vettore/lista ordinato:

o inserzione ordinata nella lista o nel vettore mediante scansione -> O(N) o estrazione/visualizzazione del

massimo/minimo se memorizzato in testa alla lista o in coda al vettore con accesso diretto -> O(1) o cambio

di priorità: • lista: richiede ricerca dell’elemento mediante scansione (O(N)), eliminazione (O(1)),

reinserimento (O(N)), globalmente complessità O(N) • vettore: richiede ricerca dell’elemento mediante

ricerca dicotomica (O(logN)), eliminazione (O(N)), reinserimento (O(N)), globalmente complessità O(N)

Complessità ▪ implementazione con heap: o inserzione/estrazione del massimo/minimo con complessità

O(logN) o visualizzazione del massimo/minimo con complessità O(1) o cambio di priorità: richiede ricerca

dell’elemento (con tabella di hash complessità media O(1)), globalmente complessità O(logN).

ADT I classe coda a priorità Implementazione con liste ordinate

L’ADT Tabella di Simboli Definizione: ADT che supporta operazioni di: ▪ insert: inserisci un dato (item)

(STinsert) ▪ search: ricerca dato con certa chiave (STsearch) ▪ delete: cancella il dato con una certa chiave

(STdelete). Talora la tabella di simboli è detta dizionario. Altre operazioni: ▪ inizializzare la tabella ▪

distruggere la tabella ▪ contare il numero di dati ▪ visualizzare della tabella ▪ se sulla chiave è definita una

relazione d’ordine: ▪ ordinare la tabella ▪ selezionare la chiave di rango r (r-esima più piccola chiave)

Possibili versioni dell’ADT tabell