Valeria Vittorini » 11.Strutture Dati Astratti

Information Hiding

• Come accennato nelle precedenti lezioni, il nascondimento delle informazioni (information hiding) consente di realizzare una astrazione sui dati nascondendo all’utente i dettagli implementativi e consentendogli di accedere ai dati solo attraverso le funzionalità pubblicate mediante l’interfaccia.
• Per poter realizzare pienamente tale tecnica è necessario però che il linguaggio di programmazione fornisca i necessari meccanismi, in modo che il compilatore possa effettuare gli opportuni controlli e verificare che l’utente non possa accedere alle informazioni “nascoste”.
• In altre parole è necessario che il linguaggio fornisca dei meccanismi di “incapsulamento”.
• Senza tali meccanismi non è possibile impedire all’utente di accedere ai dettagli implementativi del tipo di dato che un modulo sta esportando, è solo possibile che l’utente stesso si dia una disciplina di programmazione.
• Facciamo un esempio.

Esempio “Prodotto”

Nel seguente esempio il modulo “prodotto” esporta il tipo Prodotto sul quale sono fornite le funzionalità di inserimento e visualizzazione dei dati.

Il modulo utente utilizza il tipo Prodotto e accede ai campi codice, descrizione e quantità mediante le funzionalità di inserimento e visualizzazione espostate all'interfaccia del modulo, ma nulla gli vieta di accedere e manipolare direttamente i singoli campi, come infatti viene fatto modificando e visualizzando il campo quantità del prodotto p1.

Esempio “Prodotto”

Esecuzione

Definizione (ADT)

• Un tipo di dato astratto (Abstract Data Type: ADT) è una struttura dati incapsulata dalle operazioni consentite su di essa.
• In altre parole non è possibile accedere alla struttura dati (né in lettura né in scrittura) se non attraverso le operazioni definite dal progettista e dall’implementatore ed esportate mediante l’interfaccia.

Utenti e implementatori

L’utente (cliente) fa uso delle funzionalità offerte per realizzare procedure di un’applicazione o per costruire operazioni su dati più complessi
Il progettista e l’implementatore devono realizzare le astrazioni e le funzionalità previste per il dato facendo uso di un linguaggio di programmazione o appoggiandosi sulle primitive di un altro tipo di dato già disponibile.

→ Un progettista o implementatore può essere il cliente di un altro tipo di dato astratto.

Vantaggi principali

• La struttura dei dati non può venire alterata da operazioni scorrette.
• La realizzazione della struttura dei dati può essere modificata senza influenzare i moduli che ne fanno uso, cioè senza modificare il codice che utilizza la struttura dati purchè non venga modificata l’interfaccia.
• Il codice che utilizza la struttura dati è più facile da capire e correggere.

Meccanismi di incapsulamento

Al fine di poter incapsulare effettivamente una struttura dati il linguaggio di programmazione deve fornire opportuni meccanismi a supporto.

Il C++ fornisce meccanismi di incapsulamento a due diversi livelli:

• A livello di nomi (identificativi) esportati dai moduli, mediante i namespace.
• A livello dei dati, mediante le classi.

Il primo meccanismo è stato introdotto per alleviare il problema che deriva da possibili conflitti tra nomi.

il secondo meccanismo è quello che consente di realizzare tipi di dati astratti, come definiti in questa lezione.

Studieremo entrambi i meccanismi di incapsulamento più avanti in questo corso.

Strutture Dati

In questa lezione. e nella prossima. vedremo invece come realizzare alcune strutture dati classiche adottando un opportuno stile di programmazione, così come abbiamo sviluppato il tipo “Prodotto” nell’esempio.
Facendo uso dei concetti di programmazione modulare già introdotti, realizzeremo tali strutture e le funzioni che ne consentono un corretto utilizzo
L’utente – pur potendo accedere alla struttura dati – “si impegna” ad utilizzare esclusivamente le funzionalità esportate dal modulo fornitogli.

Progettazione di una struttura dati

• Prima di passare alla fase implementativa è sempre necessario svolgere una fase di progettazione della struttura dati, in particolare:
• Definizione delle funzionalità (comportamento atteso) e della interfaccia.
• Definizione di eventuali precondizioni che devono essere verificate affinchè le operazioni possano essere effettuate e/o di eventuali postcondizioni da verificare per assicurarsi che l’operazione sia stata svolta correttamente.
• Definizione della rappresentazione più opportuna per la struttura dati (nel contesto in cui deve essere utilizzata): ad esempio mediante un vettore allocato dinamicamente oppure di dimensioni note a tempo di compilazione, oppure mediante una catena a puntatori.

Strutture Dati di Base: Liste

• In questa lezione e nella prossima presenteremo quindi alcune strutture dati di base, in particolare studieremo le liste.
• Moltissime applicazioni infatti richiedono di poter rappresentare collezioni di elementi sui quali effettuare un insieme di operazioni “standard” (cioè fondamentalmente sempre le stesse).
• Tali collezioni sono spesso “elenchi” di elementi, organizzati cioè secondo un ordine lineare (in successione, dal primo all’ultimo).
• La struttura dati che più comunemente è utilizzata per rappresentare elementi organizzati linearmente è la LISTA.
• L’applicazione può richiedere che gli elementi vengano gestiti secondo una deteminata politica di accesso.

Liste: politica di accesso agli elementi

Per “politica di accesso” intendiamo le eventuali restrizioni sulle modalità di accesso agli elementi:

Sulle liste considereremo qui le seguenti:

• FIFO (First In First Out – il primo elemento ad entrare è il primo elemento ad uscire): si può accedere solo all’elemento inserito per primo nella lista. Questa è la politica di accesso della struttura dati detta CODA. Si pensi a come vengono serviti -ad esempio- gli utenti che fanno la coda ad uno sportello.
• LIFO (Last In First Out – l’ultimo elemento ad entrare è il primo elemento ad uscire): si può accedere solo all’elemento inserito per ultimo nella lista. Questa è la politica di accesso della struttura dati detta PILA. Si pensi a come viene naturale trattare una pila di piatti o di libri.
• Ordinamento: gli elementi della lista sono ordinati (ad esempio una lista di numeri ordinati in senso crescente o decrescente) e le operazioni su di essa devono quindi rispettare e mantenere l’ordinamento.

Operazioni su liste

Le operazioni che vengono generalmente effettuate su una lista – compatibilmente con la politica di accesso su di essa eventualmente definita – sono:

• Creazione della lista
• Inserimento di un elemento
• Eliminazione di un elemento
• Analisi del primo elemento
• Ricerca di un elemento
• Visita della lista
• Controllo lista piena
• Controllo lista vuota
• Distruzione della lista

Operazioni su liste

Si noti che i controlli (lista piena e lista vuota) e la Ricerca sono necessari anche alla verifica delle opportune precondizioni: non è possibile infatti inserire un elemento in una lista a capacità limitata se la lista è piena, nè è possibile eliminare un elemento se la lista è vuota. Non è possibile eliminare un elemento specifico da una lista se l’elemento in questione non è presente nella lista.
Particolarizzando l’elenco ai diversi casi di modalità di accesso qui considerate, abbiamo la tabella mostrata in figura, che specifica le funzionalità generalmente offerte sulle strutture dati classiche (la casella vuota non indica una impossibilità).
Le operazioni di creazione e distruzione si riferiscono alla eventuale allocazione dinamica della memoria necessaria e alla sua relativa deallocazione. La loro necessità dipende quindi dalla modalità di rappresentazione della struttura dati.

Figura: operazioni su liste

Realizzazione

Nella prossima lezione svilupperemo una esercitazione nella quale realizzeremo le strutture dati Pila e Coda.

La loro realizzazione verrà mostrata utilizzando le seguenti rappresentazioni:

• Vettore di dimensione nota a tempo di compilazione.
• Vettore allocato dinamicamente.

Utilizzeremo ancora un approccio modulare ipotizzando -come si è già detto- una opportuna disciplina di programmazione da parte dell’utente, rimandando l’utilizzo dei meccanismi di incapsulamento alla parte del corso dedicata alla Programmazione Orientata agli Oggetti.

In una successiva lezione verranno introdotte le liste dinamiche rappresentate mediante catene di puntatori.