1.2. Tipi di dati astratti
La maggior parte dei concetti introdotti nella sezione precedente vengono generalmente insegnati in un corso introduttivo di programmazione e dovrebbero esserti familiari. Solo i tipi di dati astratti possono essere nuovi, quindi discutiamo prima del loro ruolo nel processo di sviluppo del software. Per prima cosa, confrontiamo un tipo di dati astratto con il concetto familiare di procedura.
Una procedura, uno strumento di programmazione essenziale, può essere pensata come un concetto generalizzato di operatore. A differenza degli operatori integrati in un linguaggio di programmazione, che sono limitati nelle loro capacità (addizione, moltiplicazione, ecc.), utilizzando le procedure, un programmatore può creare propri operatori e applicarli ad operandi di vario tipo, non solo di base. Un esempio di tale operatore di procedura è la subroutine standard della moltiplicazione di matrici.
Un altro vantaggio delle procedure (oltre alla possibilità di creare nuove istruzioni) è che possono essere utilizzate per incapsulamento parti dell'algoritmo inserendo in una sezione separata del programma tutti gli operatori responsabili di un determinato aspetto del funzionamento del programma. Esempio di incapsulamento: utilizzo di una singola procedura per leggere l'input di qualsiasi tipo e convalidarlo. Il vantaggio dell'incapsulamento è che sappiamo quali istruzioni incapsulate devono essere modificate in caso di problemi nel funzionamento del programma. Ad esempio, se è necessario organizzare un controllo dei dati di input per valori positivi, è necessario modificare solo alcune righe di codice e sappiamo esattamente dove si trovano queste righe.
Definizione tipo astratto dati
Definiamo tipo di dati astratto(ATD) come modello matematico con un insieme di operatori definiti all'interno di questo modello. Un semplice esempio di ADT sarebbe insiemi di interi con operatori di unione, intersezione e differenza di insieme. Nel modello ADT gli operatori possono avere come operandi non solo dati definiti dall'ADT, ma anche dati di altro tipo: tipi standard del linguaggio di programmazione o quelli definiti in altri ADT. Il risultato di un'azione dell'operatore può anche essere di tipo diverso da quelli definiti nel modello ADT dato. Ma assumiamo che almeno un operando o risultato di qualsiasi operatore abbia un tipo di dati definito nel modello ADT in questione.
Due caratteristiche le procedure - generalizzazione e incapsulamento - che sono state discusse sopra, caratterizzano perfettamente i tipi di dati astratti. Un ADT può essere pensato come una generalizzazione di tipi di dati semplici (interi, numeri reali, ecc.), proprio come una procedura è una generalizzazione di semplici operatori(+, - ecc.). Un ADT incapsula i tipi di dati nel senso che la definizione del tipo e tutti gli operatori che possono essere eseguiti sui dati di quel tipo sono inseriti in una sezione del programma. Se è necessario modificare l'implementazione di un ADT, sappiamo dove trovare e cosa modificare in una piccola sezione del programma e possiamo essere sicuri che ciò non porterà a errori in nessuna parte del programma quando si lavora con questi dati genere. Inoltre, al di fuori della sezione sulla definizione degli operatori ADT, possiamo considerare i tipi ADT come tipi primari, poiché le dichiarazioni di tipo non sono formalmente correlate alla loro implementazione. Ma in questo caso possono sorgere complicazioni, poiché alcune affermazioni possono essere avviate per più di un ADT e i riferimenti a queste affermazioni devono trovarsi in sezioni di più ADT.
Per illustrare le idee di base che portano alla creazione di un ADT, si consideri la procedura greedy della sezione precedente (listato 1.3), che utilizza semplici operatori su dati del tipo astratto LIST (elenco di interi). Questi operatori devono eseguire le seguenti azioni sulla variabile newclr di tipo LIST.
1. Rendi vuoto l'elenco.
2. Selezionare il primo elemento dell'elenco e, se l'elenco è vuoto, restituire il valore nullo.
3. Selezionare l'elemento successivo dell'elenco e restituire il valore nullo, Se elemento successivo no.
4. Inserire un numero intero nell'elenco.
È possibile utilizzare diverse strutture dati con le quali eseguire efficacemente le azioni descritte. (Discuteremo in dettaglio le strutture dei dati nell'argomento 2.) Se nel Listato 1.3 sostituiamo gli operatori corrispondenti con le espressioni
MAKENULL(newcJr);
w:= PRIMO(newcJr);
w:= NEXT(nuovocfr);
INSERT(v, newclr);
allora uno dei principali aspetti (e vantaggi) dei tipi di dati astratti risulterà chiaro. È possibile implementare un tipo di dati in qualsiasi modo e i programmi che utilizzano oggetti di questo tipo non dipendono da come viene implementato il tipo: le procedure che implementano gli operatori per questo tipo di dati sono responsabili di questo.
Torna al tipo astratto Dati GRAFICI(Grafico). Gli oggetti di questo tipo richiedono operatori che eseguano le azioni seguenti.
1. Seleziona il primo vertice non dipinto.
2. Controlla se c'è un bordo tra due vertici.
3. Segna la parte superiore con un colore.
4. Selezionare il prossimo vertice non riempito.
Ovviamente, altri operatori, come inserire vertici e spigoli in un grafo o contrassegnare tutti i vertici del grafo come non riempiti, rimangono fuori dall'ambito della procedura greedy. Strutture varie i tipi di dati che supportano questo tipo di dati saranno trattati negli argomenti 6 e 7.
Va sottolineato che il numero di operatori applicati agli oggetti di questo modello matematico non è limitato. Ogni insieme di istruzioni definisce un ADT separato. Di seguito sono riportati esempi di operatori che possono essere definiti per il tipo di dati astratto SET (Set).
1. MAKENULL(A), questa procedura rende l'insieme A un insieme vuoto.
2. UNIONE(A, B, C). Questa procedura accetta due argomenti di "input", gli insiemi A e B, e assegna l'unione di questi insiemi al suo argomento di "output", l'insieme C.
3. TAGLIA (A). Questa funzione ha un argomento set A e restituisce un oggetto di tipo intero uguale al numero di elementi dell'insieme A. Il termine implementazione ADT implica quanto segue: traduzione in linguaggio di programmazione dichiarazioni di dichiarazioni che definiscono variabili di questo tipo di dati astratto, più procedure per ogni istruzione eseguita su oggetti ADT. L'attuazione dipende da strutture dati, in rappresentanza di ATD. Ogni struttura dati è costruita sulla base dei tipi di dati di base del linguaggio di programmazione utilizzato, utilizzando gli strumenti di strutturazione dati disponibili in questo linguaggio. Le strutture di array e record sono due mezzi importanti per strutturare i dati possibili in Pascal. Ad esempio, uno di possibili implementazioni la variabile S di tipo SET può essere una matrice contenente elementi dell'insieme S.
Uno dei motivi principali per definire due diversi ADT all'interno dello stesso modello è che devono essere eseguite azioni diverse sugli oggetti di questi ADT, ad es. definire gli operatori tipi diversi. Questo riepilogo copre solo alcuni dei principali modelli matematici, come la teoria degli insiemi e la teoria dei grafi, ma con varie implementazioni, alcuni ADT verranno costruiti sulla base di questi modelli vari set operatori.
Idealmente, è desiderabile scrivere programmi in un linguaggio i cui tipi di dati e operatori di base siano sufficienti per implementare un ADT. Da questo punto di vista il linguaggio Pascal non è un linguaggio molto adatto per implementare vari ADT, ma, d'altra parte, è difficile trovare un altro linguaggio di programmazione in cui sia possibile dichiarare un ADT in modo così diretto . Informazioni aggiuntive per tali linguaggi di programmazione si vedano le note bibliografiche alla fine dell'argomento.
Un tipo di dati descrive un insieme di oggetti con proprietà simili. Tutti i linguaggi di programmazione tradizionali utilizzano un insieme di tipi di dati di base (reale, intero, stringa, carattere). I tipi di dati di base sono soggetti a un insieme predefinito di operazioni. Ad esempio, il tipo di dati di base intero consente di eseguire operazioni quali addizione, sottrazione, moltiplicazione e divisione.
I linguaggi di programmazione tradizionali includono costruttori di tipi, il più comune dei quali è il costruttore di record. Ad esempio, per un record di tipo CLIENTE, è possibile definire campi dati. La voce CLIENTE sarà nuovo tipo struttura dati, che memorizzerà informazioni sul cliente, è possibile accedere direttamente a questa struttura dati facendo riferimento ai nomi dei campi. È possibile eseguire operazioni come SCRITTURA, LETTURA, CANCELLA, AGGIORNAMENTO su un record. Non è possibile definire nuove operazioni per i tipi di dati di base.
Come i tipi di dati di base, i tipi di dati astratti (ATD) descrivono molti oggetti simili. Ci sono differenze tra ATD e tipo tradizionale dati:
· le operazioni sotto ATD sono definite dall'utente;
· Gli ATD non consentono l'accesso diretto alla rappresentazione interna dei dati e alle implementazioni dei metodi.
In alcuni sistemi OO (ad esempio Smalltalk), i tipi di dati di base sono implementati come astratti.
Per creare un tipo di dati astratto, devi fornire:
il nome del tipo;
La rappresentazione di dati o variabili di istanza di un oggetto di proprietà dell'ATD; ogni variabile di istanza ha un tipo di dati, che può essere uno dei due tipo di base, o un altro ATD;
· Le operazioni ei vincoli ATD sono implementati utilizzando metodi.
La definizione ATD ricostruisce la definizione della classe. In alcuni sistemi OO, la parola chiave type viene utilizzata per distinguere tra classi e tipi quando si fa riferimento a strutture di dati e metodi di una classe e quando si fa riferimento a un insieme di istanze di oggetti, parola chiave classe. Il tipo (tipo) è un concetto più statico e la classe è principalmente correlata al runtime. La differenza tra una classe OO e un tipo OO può essere illustrata con un esempio. Supponiamo che ci sia un modello per un costruttore. Il modello è accompagnato da una descrizione della sua struttura, nonché da istruzioni per il suo utilizzo. Questo modello è la definizione del tipo. Un insieme di prodotti reali realizzati utilizzando un modello, ognuno dei quali ha un numero univoco (o OID), costituisce una classe (classe).
ATD, insieme all'ereditarietà, consente di creare oggetti complessi. Un oggetto complesso si forma combinando altri oggetti che hanno relazioni complesse tra loro. Esempio oggetto complesso possono essere trovati nei sistemi di sicurezza che utilizzano tipi diversi dati:
1. dati standard (tabulari) sul dipendente (nome completo, n. Tab., ecc.);
2. bitmap per l'archiviazione delle foto dei dipendenti;
La capacità di lavorare con un ambiente di dati così complesso con relativa facilità aumenta l'importanza dei sistemi OO nel mercato dei database di oggi.
Tipo di dati astratto Tipi di dati generali Tipo di dati astratto disposizioni generali specificazione, rappresentazione, attuazione 1
Che cosa sono i dati? Set di vari oggetti informativi, su cui determinate azioni vengono eseguite dagli operatori di programma, sono chiamati dati. I dati sono un attributo indispensabile di qualsiasi programma. Possono essere: - singoli bit; - sequenza di bit indipendenti; -numeri in diverse forme di rappresentazione; -byte e gruppi di byte indipendenti; - matrici di numeri; - liste collegate; -file separati e file system. 2
La rappresentazione universale di questa varietà di dati è difficile e poco pratica Si consiglia di suddividerli in tipi 3
Che cos'è un tipo di dati? Il tipo di dati è determinato da: – Il formato di rappresentazione nella memoria del computer secondo alcune convenzioni del linguaggio algoritmico, ma senza necessità di calcoli; - Molti valori consentiti, che può assumere una variabile o una costante appartenente al tipo selezionato; – L'insieme delle operazioni valide applicabili a questo tipo. 4
Esempi di tipi di dati Tipi interi Tipo reale tipo booleano Tipo di carattere Tipo enumerato Tipo di intervallo Puntatori 5
Tipi di interi Esistono cinque tipi di interi predefiniti: Shortint, Integer, Longint, Byte e Word. Ogni tipo denota un sottoinsieme specifico di numeri interi. Un valore di un tipo intero può essere convertito in modo esplicito in un altro tipo integrale utilizzando un cast. 6
Tipo reale Il tipo reale si riferisce a un sottoinsieme di numeri rappresentati in formato a virgola mobile con un numero fisso di cifre. Un valore a virgola mobile di solito include tre valori - m, b ed e - tali che m * b ^ e = n, dove b è sempre 2, e m ed e sono valori interi nell'intervallo di tipo reale . Questi valori di m ed e definiscono ulteriormente l'intervallo di rappresentazione e la precisione del tipo reale. Esempio: 0,143 E+22, dove m è 0,143; b=2(implicito), e=22. Ci sono cinque tipi tipi reali: reale (Real), con precisione singola (Single), con precisione doppia (Double), con precisione aumentata (Extended) e complessa (Comp). 7
Tipo booleano Esistono 4 tipi booleani predefiniti: Booleano, Byte. Bool, Parola. bool e lungo. Bollo. I valori booleani sono indicati dagli identificatori costanti integrati False e True. Le variabili booleane possono essere utilizzate per memorizzare i risultati di qualsiasi calcolo logico. Per le variabili booleane sono consentite solo 2 operazioni di confronto "="(uguale) e ""(non uguale). 8
Tipo di carattere L'insieme di valori di questo tipo sono caratteri ordinati in base al set di caratteri ASCII esteso. Queste sono le lettere ["A". . . "Z", "a". . . "z"], cifre ["0". . . "9"], segni di punteggiatura e caratteri speciali. Una variabile di questo tipo occupa un byte di memoria. nove
Tipo enumerato I tipi enumerati definiscono insiemi ordinati di valori attraverso un'enumerazione di identificatori che denotano tali valori. Gli insiemi vengono ordinati in base all'ordine in cui sono elencati gli identificatori. Tipo Settimana = (lunedì, martedì, mercoledì, giovedì, venerdì, sabato, domenica); 10
Tipo di intervallo Un tipo di intervallo è un intervallo di valori di un tipo ordinale. La definizione di un tipo di intervallo include il più piccolo e valore più alto nel sottointervallo. Digitare Intervallo = 0. . . 1000; Tale dichiarazione di tipo indica al compilatore che solo i numeri all'interno dell'intervallo specificato sono consentiti per le variabili di quel tipo. Pertanto, il programma può organizzare automaticamente i controlli per la correttezza delle operazioni di assegnazione per queste variabili. undici
Comune per i tipi di dati Ciascuno dei tipi di dati corrisponde a un insieme semplici operazioni. INTEGER-operazioni +, -, *, div, mod REAL - operazioni + , -, *, / BOOLEAN- operazioni - congiunzione (e), disgiunzione V (o), negazione (non) CHAR-operazione ORD (c) -N : (C in ASCII), CHR (I) I-esimo carattere in ASCII Con l'aumento del volume e della complessità della presentazione delle informazioni, sono necessarie forme convenienti di presentazione, archiviazione ed elaborazione. 12
La definizione di un tipo di dati astratto (ATD o tipo di dati astratto, o ADT) è un insieme di oggetti astratti che rappresentano elementi di dati e un insieme di operazioni definite su di esso che possono essere eseguite su elementi di questo insieme. 13
ADT - una generalizzazione dei tipi di dati I tipi di dati astratti (ATD) possono essere considerati un mezzo per estendere i linguaggi di programmazione. Confrontiamo un tipo di dati astratto con il concetto familiare di procedura. Una procedura può essere vista come una nozione generalizzata di operatore. Due caratteristiche delle procedure - generalizzazione e incapsulamento - caratterizzano perfettamente i tipi di dati astratti. Un ADT può essere pensato come una generalizzazione di semplici tipi di dati (interi, reali, ecc.), così come una procedura è una generalizzazione di semplici operatori (+, -, ecc.)
Vantaggi Estratto ATD le strutture dati sono per comoda conservazione e l'accesso alle informazioni. Loro forniscono interfaccia intuitiva per le tipiche operazioni sugli oggetti archiviati, nascondendo i dettagli di implementazione all'utente. Naturalmente, questo è molto conveniente e consente di ottenere una maggiore modularità del programma. 15
Esempio per controllo automatizzato temperatura nei vari ambienti di un grande edificio, un TERMOSTATO sarebbe un utile ATD. Il programma potrebbe averne molti tipo variabili TERMOSTATO corrispondente a veri e propri termostati in vari ambienti dell'edificio. Un ADT può essere descritto dal nome, dall'insieme di valori e dalle operazioni consentite proprio come qualsiasi altro tipo di dati. Descrizione per tipo TERMOSTATO: – Tipo di dati: TERMOSTATO – Campo valori: La temperatura può variare tra 0 e 50 gradi (Celsius). – Operazioni: Su, Giù, Imposta, Verifica, Sveglia. (Si possono inventare molte operazioni utili, ma troppe degradano l'astrazione) 16
Strati di astrazione Gli strati di astrazione sono come strati Software. I più alti livelli di astrazione riflettono l'idea dell'utente di risolvere il problema. livelli inferiori le astrazioni sono le possibilità di un linguaggio di programmazione. 17
Esempio di astrazione del livello utente Un architetto rappresenta una casa in termini di pareti, pavimenti, finestre, porte e così via.In questo caso, il tipo di dati è Immagine. Le porte potrebbero essere un buon tipo astratto. Tipo di dati: Disegno. Operazioni della porta: Disegna. Cancellazione della porta. Tiraggio della porta. Doppio. Porta ……. Foto. Le porte sono astratte alto livello, che riflette il punto di vista dell'utente sul problema 18
Esempio di astrazione a livello di programmatore Il programmatore può suggerire un altro livello di astrazione per questi oggetti, come un rettangolo. Tipo di dati: Rettangolo Operazioni: Disegna. Cancella rettangolo. Rettangolo Dividi. Rettangolo. Sul. Parti……. Il rettangolo è un'astrazione basso livello, poiché è più vicino all'attuazione. 19
Costruttori ADT Ogni ADT deve contenere operazioni per la costruzione di valori del suo tipo. Tali operazioni sono chiamate costruttori. I costruttori dovrebbero essere sufficienti per generare l'intero insieme di valori di questo tipo. Un ADT che soddisfa questa proprietà è chiamato completo. Un ADT incompleto è un errore di progettazione. venti
Suggerimenti per la scelta di operazioni sui tipi di dati astratti È consigliabile includere le seguenti operazioni: – operazioni di costruzione, – operazioni di verifica, – operazioni di conversione del tipo, – operazioni di I/O, – operazioni di copia, – operazioni di selezione. Cerca di mantenere il numero di transazioni al minimo. Un semplice ADT è più facile da capire. Mantieni le operazioni associate all'astrazione del tipo di tua scelta. 21
Costruttore primario Le operazioni che creano nuovi valori per un ADT, indipendentemente dal suo valore precedente, sono chiamate costruttori primari. Ogni ADT include almeno un costruttore primario: senza di esso è impossibile formare un valore iniziale. 22
Utilizzo di tipi nascosti I tipi di dati astratti sono meglio dichiarati come tipi nascosti. Ciò consente di spostare la descrizione della struttura dei dati nell'unità di implementazione, dove viene utilizzata prevalentemente. Forniscono anche un'opportunità per prevenire accesso diretto ai componenti del tipo da parte dell'importatore. Poiché un tipo nascosto viene sempre implementato con un puntatore, ci sono tre operazioni che devono essere incluse in un ADT. – Crea: un'operazione che crea un nodo della struttura corrispondente. – Distruggi - operazione per liberare la memoria del nodo tipo nascosto. – Assegna - l'operazione di copia dei campi della struttura dinamica di un nodo di tipo nascosto. 23
Qual è la specifica e l'implementazione di un tipo di dati astratto Un tipo di dati astratto è un modo per definire un concetto come una classe di oggetti con alcune proprietà e operazioni. In un linguaggio di programmazione, tale definizione è formalizzata come una costruzione sintattica speciale richiamata lingue differenti capsula, modulo, cluster, classe, pacchetto, modulo, ecc. Questa costruzione nella sua forma più avanzata contiene: una specifica del tipo di dati, che include una descrizione dell'interfaccia (nome del tipo che si sta definendo, nomi delle operazioni con indicazione dei loro profili) e una descrizione astratta delle operazioni e degli oggetti, con cui funzionano, alcuni mezzi di specificazione; un'implementazione del tipo di dati che include una descrizione specifica delle stesse operazioni e oggetti. 24
Classificazione dei tipi di dati in base al metodo di descrizione e protezione confezionato, se la descrizione del tipo di dati è raccolta in un unico luogo (in un pacchetto), ovvero i suoi oggetti e le sue operazioni sono combinati in un unico concetto; ha una definizione, che può contenere, però, solo la sua attuazione; incapsulato, se il tipo di dati è compresso, la sua definizione contiene una descrizione e un'implementazione dell'interfaccia e viene fornito anche l'incapsulamento dell'implementazione; abstract se il tipo di dati è incapsulato e la sua specifica include una dichiarazione astratta. 25
Componenti della specificazione La programmazione, come processo, inizia con l'enunciazione del problema (la sua definizione), o la specificazione del problema. Più avanti in tutto il testo vengono utilizzate delle specifiche, costituite da sei componenti: – Titolo - il nome del problema da risolvere; – Descrizione: diverse frasi che descrivono l'essenza del compito; - Entrata - descrizione dettagliata la forma prevista dei dati di input; – Output: una descrizione dettagliata della forma prevista dei dati di output; - Errori - elenco dettagliato situazioni derivanti da dati di input errati; – Esempio - un esempio di esecuzione in termini di input-output. 26
Esempio di specifica Un tipo di dati astratto STEK che implementa una struttura di dati ben nota caratterizzata dal fatto che è possibile "inserirvi" un elemento e "selezionare" da esso l'elemento posizionato più di recente. La parte della sintassi della specifica del tipo di dati STACK è genere La specifica STACK è CREATE: function () return (@); INSERT: funzione (intero; @) ritorno (@); CANCELLA: funzione (@) ritorno (@); TOP: funzione (@) ritorno (intero); VUOTO: funzione (@) ritorno(booleano); specifica finale; Qui, l'operazione CREATE produce come risultato uno stack vuoto, INSERT - uno stack con il suo elemento aggiunto al "top", DELETE - uno stack con l'elemento "top" rimosso, TOP - il valore dell'elemento "top" di lo stack, VUOTO - un segno di vuoto dello stack. Gli elementi dello stack qui possono essere solo numeri interi. 27
IMPLEMENTAZIONE DI UN TIPO DI DATO ASTRATTO L'implementazione è più conveniente utilizzando linguaggi di programmazione orientati agli oggetti come C++ o Java, dove i tipi di dati astratti sono supportati da classi.Un'implementazione di un ADT include una descrizione specifica degli oggetti del tipo in corso definito e l'attuazione delle operazioni di quel tipo. Ciò significa che gli oggetti sono descritti come dati di tipi semplici o come array, record o unioni. Inoltre, vengono utilizzati tipi di dati predefiniti o ADT definiti in precedenza. L'implementazione delle operazioni consiste nella descrizione delle subroutine che eseguono azioni necessarie con gli oggetti specificati. Ad esempio operazioni +, *, =. . ecc., ma allo stesso tempo l'attuazione stessa di queste operazioni è nascosta. 28
Lo sviluppo di modelli astratti per i dati e le modalità di elaborazione di questi dati è componente essenziale nel processo di risoluzione dei problemi utilizzando un computer. Ne vediamo esempi sia a basso livello nella programmazione quotidiana (ad esempio, quando si usano array e liste concatenate, discussi in), sia ad alto livello quando si risolvono compiti applicati(come quando si risolve il problema di connettività utilizzando la foresta di ricerca join nella "Introduzione"). Questa lezione discute i tipi di dati astratti ( abstract data type , di seguito ADT), che consentono di creare programmi utilizzando astrazioni di alto livello. I tipi di dati astratti consentono di separare le trasformazioni astratte (concettuali) eseguite dai programmi sui dati da qualsiasi rappresentazione particolare di una struttura dati e da qualsiasi implementazione particolare di un algoritmo.
Qualunque cosa sistemi informatici in base ai livelli di astrazione: alcune proprietà fisiche del silicio e di altri materiali consentono l'adozione di un modello astratto di un bit, che può assumere i valori binari 0-1; quindi, un modello astratto della macchina è costruito sulle proprietà dinamiche dei valori di un certo insieme di bit; inoltre, in base al principio di funzionamento della macchina sotto il controllo del programma su linguaggio macchina viene costruito un modello astratto del linguaggio di programmazione; e, infine, viene costruito un concetto astratto di algoritmo, che viene implementato come un programma C++. I tipi di dati astratti consentono di continuare ulteriormente questo processo e sviluppare meccanismi astratti per determinati compiti computazionali a un livello superiore rispetto a quello fornito dal sistema C++, sviluppare meccanismi astratti focalizzati su applicazioni specifiche e adatto per risolvere problemi in numerose aree applicative, nonché per creare meccanismi astratti di livello superiore che utilizzano questi costrutti di base. I tipi di dati astratti ci forniscono un insieme infinitamente espandibile di utensili per risolvere sempre più nuovi problemi.
Da un lato, l'uso di costrutti astratti libera dalle preoccupazioni circa la loro implementazione dettagliata; d'altra parte, quando prestazione programma è importante, è necessario conoscere i costi dell'esecuzione delle operazioni di base. Usiamo molte astrazioni di base integrate hardware computer e fungere da base per le istruzioni della macchina; implementare altre astrazioni nel software; e utilizzare astrazioni aggiuntive fornite dal software di sistema precedentemente scritto. I costrutti astratti di alto livello sono spesso basati su di più disegni semplici. A tutti i livelli vale lo stesso principio di base: devi trovare il massimo operazioni importanti nei programmi e la maggior parte caratteristiche importanti dati, e quindi definire con precisione sia a livello astratto che sviluppare meccanismi concreti efficaci per la loro attuazione. In questa lezione, esamineremo molti esempi dell'applicazione di questo principio.
Lo sviluppo di un nuovo livello di astrazione richiederà (1) la definizione degli oggetti astratti da manipolare e delle operazioni da eseguire su di essi; (2) rappresentare i dati in alcune strutture dati e attuare le operazioni; (3) e (soprattutto) per garantire che questi oggetti siano convenienti da usare per risolvere problemi applicati. Questi punti si applicano anche a tipi semplici dati, in modo che i meccanismi di base per supportare i tipi di dati, discussi in "Strutture di dati elementari", possano essere adattati ai nostri scopi. Tuttavia, il linguaggio C++ offre importante espansione meccanismo delle strutture, chiamato classe ( class ). Le classi sono estremamente utili per creare livelli di astrazione e sono quindi trattate come lo strumento principale utilizzato a questo scopo nel resto del libro.
Definizione 4.1. Un tipo di dati astratto (ATD) è un tipo di dati (un insieme di valori e un insieme di operazioni su quei valori) a cui si accede solo tramite un'interfaccia. Il programma che utilizza l'ADT verrà chiamato client e il programma contenente la specifica di questo tipo di dati verrà chiamato implementazione.
È la parola che rende astratto solo il tipo di dati: nel caso di un ADT, i programmi client non hanno accesso ai valori dei dati in nessun modo diverso dalle operazioni descritte nell'interfaccia. La rappresentazione di questi dati e le funzioni che implementano queste operazioni sono nell'implementazione e sono completamente separate da un'interfaccia dal client. Diciamo che un'interfaccia è opaca: il client non può vedere l'implementazione attraverso l'interfaccia.
Nei programmi C++, questa distinzione è generalmente resa un po' più chiara, poiché è più semplice creare un'interfaccia includendo presentazione dei dati, ma specificando che ai programmi client non è consentito l'accesso diretto ai dati. In altre parole, gli sviluppatori client potrebbero saperlo presentazione dei dati, ma non posso usarlo in alcun modo.
A titolo di esempio, si consideri l'interfaccia del tipo di dati per i punti (Programma 3.3) della Sezione 3.1 "Strutture di dati elementari". Questa interfaccia dichiara esplicitamente che i punti sono rappresentati come strutture costituite da una coppia di numeri in virgola mobile, indicati da xey. Questo uso dei tipi di dati è comune in grandi sistemi software: sviluppiamo un insieme di convenzioni di rappresentazione dei dati (oltre a definire un insieme di operazioni correlate) e mettiamo a disposizione queste regole attraverso un'interfaccia in modo che possano essere utilizzate dai programmi client inclusi nel grande sistema. Il tipo di dati garantisce che tutte le parti del sistema siano coerenti con la rappresentazione delle strutture di dati sottostanti a livello di sistema. Per quanto valida possa essere questa strategia, ha uno svantaggio: se è necessario cambiare presentazione dei dati, dovrai modificare tutti i programmi client. Il Programma 3.3 ci fornisce ancora un semplice esempio: uno dei motivi per lo sviluppo di questo tipo di dati è la comodità dei programmi client che lavorano con i punti e ci aspettiamo che i clienti abbiano accesso alle coordinate individuali di un punto, se necessario. Ma non possiamo passare a una diversa rappresentazione dei dati (ad esempio, coordinate polari o coordinate 3D o anche altri tipi di dati per le singole coordinate) senza modificare tutti i programmi client.
Al contrario, il Programma 4.1 contiene un'implementazione di un tipo di dati astratto che corrisponde al tipo di dati nel Programma 3.3, ma utilizza una classe di linguaggio C++ che definisce contemporaneamente sia i dati che le operazioni associate. Il programma 4.2 è programma client A che funziona con questo tipo di dati. Questi due programmi eseguono gli stessi calcoli dei programmi 3.3 e 3.8. Illustrano alcune delle principali proprietà delle classi che esamineremo ora.
Quando scriviamo una definizione come int i in un programma, diciamo al sistema di riservare un'area di memoria per i dati (onboard) digita int, a cui si accede con il nome i. Il linguaggio C++ ha il termine oggetto per tali entità. Quando una definizione come POINT p viene scritta in un programma, si dice che viene creato un oggetto della classe POINT, a cui ci si può riferire con il nome p. Nel nostro esempio, ogni oggetto contiene due elementi di dati, denominati x e y. Come per le strutture, possono essere indicate con nomi come p.a.
I membri dati xey sono chiamati membri dati della classe. La classe può anche definire funzioni membro che implementano le operazioni associate a questo tipo di dati. Ad esempio, la classe definita nel Programma 4.1 ha due funzioni membro denominate POINT e distanza .
I programmi client, come il Programma 4.2, possono chiamare le funzioni membro associate a un oggetto specificandone i nomi allo stesso modo dei nomi dei dati contenuti in alcune strutture struct. Ad esempio, l'espressione p.distance(q) calcola la distanza tra i punti p e q (la stessa distanza deve essere restituita chiamando q.distance(p) ). La funzione POINT(), la prima funzione del Programma 4.1, è una funzione membro speciale chiamata costruttore: ha lo stesso nome di una classe e viene chiamata quando è necessario creare un oggetto di quella classe.
Programma 4.1. Implementazione della classe POINT (punto)
Questa classe definisce un tipo di dati che consiste in un insieme di valori che sono "coppie di numeri in virgola mobile" (supponendo che siano interpretati come punti in un piano cartesiano), nonché due funzioni membro definite per tutte le istanze del POINT class: function POINT() , che è un costruttore che inizializza le coordinate con valori casuali da 0 a 1, e una funzione distance(POINT) che calcola la distanza da un altro punto. Rappresentazione dei datiè privato e solo le funzioni dei membri possono accedervi o modificarlo. Le stesse funzioni dei membri sono pubbliche (pubbliche) e disponibili per qualsiasi cliente. Il codice può essere salvato, ad esempio, in un file chiamato POINT .cxx.
#includere
Programma 4.2. Programma client per la classe POINT (trovare il punto più vicino)
Questa versione del programma 3.8 è un client che utilizza il POINT ADT definito nel programma 4.3. Operazione nuova crea un array di oggetti POINT (chiamando il costruttore POINT() per inizializzare ogni oggetto con valori di coordinate casuali). L'espressione a[i].distance(a[j]) chiama la funzione membro distance sull'oggetto a[i] con l'argomento a[j] .
#includere
La definizione di POINT p nel programma client comporta l'allocazione di un'area di memoria per un nuovo oggetto e quindi (utilizzando la funzione POINT()) l'assegnazione a ciascuno dei suoi due elementi di dati un valore casuale nell'intervallo da 0 a 1.
Questo stile di programmazione, a volte chiamato programmazione orientata agli oggetti, è completamente supportato dal costrutto di classe C++. Una classe può essere pensata come un'estensione del concetto di struttura, in cui non solo i dati vengono combinati, ma vengono definite le operazioni su quei dati. Possono esserci molti oggetti diversi appartenenti alla stessa classe, ma sono tutti simili in quanto i loro membri dati possono assumere lo stesso insieme di valori e lo stesso insieme di operazioni può essere eseguito su quei membri dati - in generale, sono istanze dello stesso tipo di dati. Nella programmazione orientata agli oggetti, gli oggetti sono progettati per elaborare i loro membri dati (invece di utilizzare funzioni indipendenti per elaborare i dati archiviati negli oggetti).
Stiamo esaminando l'esempio di una piccola classe sopra descritta solo per familiarizzare con le caratteristiche di base delle classi; quindi è tutt'altro che completo. Nel codice reale per la classe point, avremo molte più operazioni. Ad esempio, nel programma 4.1, non ci sono nemmeno operazioni che ti permettano di scoprire i valori delle coordinate xey. Come vedremo, aggiungere queste e altre operazioni è un compito abbastanza semplice. Nella parte 5 daremo un'occhiata più da vicino alle classi per punti e altre astrazioni geometriche come linee e poligoni.
In C++ (ma non in C), le strutture possono anche avere funzioni ad esse associate. La differenza fondamentale tra classi e strutture ha a che fare con l'accesso alle informazioni, che è caratterizzato da parole chiave.
