1.2. Tipuri de date abstracte
Majoritatea conceptelor introduse în secțiunea anterioară sunt de obicei predate într-un curs introductiv de programare și ar trebui să vă fie familiare. Numai tipurile de date abstracte pot fi noi, așa că să discutăm mai întâi rolul lor în procesul de dezvoltare a software-ului. Mai întâi, să comparăm un tip de date abstracte cu conceptul familiar de procedură.
O procedură, un instrument de programare esențial, poate fi gândită ca un concept generalizat de operator. Spre deosebire de operatorii încorporați ai unui limbaj de programare, care sunt limitati în capacități (adunare, înmulțire etc.), folosind proceduri, un programator poate crea proprii operatoriși aplicați-le la operanzi de diferite tipuri, nu doar la cele de bază. Un exemplu de astfel de operator-procedură este subrutina standard de multiplicare a matricei.
Un alt avantaj al procedurilor (în afară de capacitatea de a crea instrucțiuni noi) este că pot fi folosite încapsulare părți ale algoritmului prin plasarea într-o secțiune separată a programului a toți operatorii responsabili de un anumit aspect al funcționării programului. Exemplu de încapsulare: Utilizarea unei singure proceduri pentru a citi intrarea de orice tip și a o valida. Avantajul încapsulării este că știm ce instrucțiuni încapsulate trebuie schimbate în cazul unor probleme în funcționarea programului. De exemplu, dacă este necesar să organizăm o verificare a datelor de intrare pentru valori pozitive, trebuie să schimbăm doar câteva linii de cod și știm exact unde sunt situate aceste linii.
Definiție tip abstract date
Noi definim tip de date abstracte(ATD) ca model matematic cu un set de operatori definiți în cadrul acestui model. Un exemplu simplu de ADT ar fi seturi de numere întregi cu operatori de unire, intersecție și diferență de set. În modelul ADT, operatorii pot avea ca operanzi nu numai date definite de ADT, ci și date de alte tipuri: tipuri standard ale limbajului de programare sau cele definite în alte ADT-uri. Rezultatul unei acțiuni a unui operator poate fi, de asemenea, de un tip diferit de cele definite în modelul ADT dat. Dar presupunem că cel puțin un operand sau rezultat al oricărui operator are un tip de date definit în modelul ADT în cauză.
Două caracteristici procedurile - generalizare și încapsulare - care au fost discutate mai sus, caracterizează perfect tipurile de date abstracte. Un ADT poate fi gândit ca o generalizare a unor tipuri de date simple (numere întregi, numere reale etc.), la fel cum o procedură este o generalizare a operatori simpli(+, - etc.). Un ADT încapsulează tipuri de date în sensul că definiția tipului și toți operatorii care pot fi executați pe date de acel tip sunt plasați într-o secțiune a programului. Dacă este necesară modificarea implementării unui ADT, știm unde să găsim și ce să schimbăm într-o mică secțiune a programului și putem fi siguri că acest lucru nu va duce la erori nicăieri în program atunci când lucrați cu aceste date. tip. Mai mult, în afara secțiunii privind definirea operatorilor ADT, putem considera tipurile ADT ca tipuri primare, deoarece declarațiile de tip nu sunt legate formal de implementarea lor. Dar, în acest caz, pot apărea complicații, deoarece unele declarații pot fi inițiate pentru mai mult de un ADT, iar referințele la aceste declarații trebuie să fie în secțiuni ale mai multor ADT.
Pentru a ilustra ideile de bază care duc la crearea unui ADT, luați în considerare procedura lacomă din secțiunea anterioară (listarea 1.3), care utilizează operatori simpli pe date de tipul de date abstract LIST (listă de numere întregi). Acești operatori trebuie să efectueze următoarele acțiuni asupra variabilei newclr de tip LIST.
1. Faceți lista goală.
2. Selectați primul element al listei și, dacă lista este goală, returnați valoarea nul.
3. Selectați următorul element din listă și returnați valoarea nul, dacă elementul următor Nu.
4. Introduceți un număr întreg în listă.
Este posibil să utilizați diverse structuri de date cu care puteți efectua eficient acțiunile descrise. (Vom discuta structurile de date în detaliu în Subiectul 2.) Dacă în Listarea 1.3 înlocuim operatorii corespunzători cu expresii
MAKENULL(newcJr);
w:= FIRST(newcJr);
w:= NEXT(newcfr);
INSERT(v, newclr);
atunci unul dintre principalele aspecte (și avantajele) tipurilor de date abstracte va fi clar. Puteți implementa un tip de date în orice mod, iar programele care folosesc obiecte de acest tip nu depind de modul în care este implementat tipul - procedurile care implementează operatorii pentru acest tip de date sunt responsabile pentru acest lucru.
Înapoi la tipul abstract date GRAPH(Grafic). Obiectele de acest tip necesită operatori care efectuează următoarele acțiuni.
1. Selectați primul vârf nevopsit.
2. Verificați dacă există o muchie între două vârfuri.
3. Marcați partea de sus cu o culoare.
4. Selectați următorul vârf necompletat.
Evident, alți operatori, cum ar fi inserarea de vârfuri și muchii într-un grafic sau marcarea tuturor vârfurilor unui grafic ca necompletate, rămân în afara domeniului de aplicare al procedurii greedy. Structuri diverse Tipurile de date care acceptă acest tip de date vor fi tratate în subiectele 6 și 7.
Trebuie subliniat faptul că numărul de operatori aplicați obiectelor acestui model matematic nu este limitat. Fiecare set de instrucțiuni definește un ADT separat. Iată exemple de operatori care pot fi definiți pentru tipul de date abstracte SET (Set).
1. MAKENULL(A), Această procedură face din setul A un set gol.
2. UNIUNEA(A, B, C). Această procedură ia două argumente „de intrare”, seturile A și B și atribuie uniunea acestor mulțimi argumentului său „ieșire”, setul C.
3. DIMENSIUNEA(A). Această funcție are un argument set A și returnează un obiect de tip întreg egal cu numărul de elemente ale mulțimii A. Termenul implementare ADT implică următoarele: traducerea în limbajul de programare a declarațiilor care definesc variabilele acestui tip de date abstracte, plus proceduri pentru fiecare instrucțiune efectuată pe obiecte ADT. Implementarea depinde de structuri de date, reprezentând ATD. Fiecare structură de date este construită pe baza tipurilor de date de bază ale limbajului de programare utilizat, folosind instrumentele de structurare a datelor disponibile în acest limbaj. Structurile de matrice și de înregistrare sunt două mijloace importante de structurare a datelor posibile în Pascal. De exemplu, unul dintre implementari posibile variabila S de tip SET poate fi o matrice care contine elemente ale multimii S.
Unul dintre motivele principale pentru definirea a două ADT-uri diferite în cadrul aceluiași model este că trebuie efectuate acțiuni diferite asupra obiectelor acestor ADT-uri, adică. definirea operatorilor tipuri diferite. Acest rezumat acoperă doar câteva dintre principalele modele matematice, cum ar fi teoria mulțimilor și teoria grafurilor, dar cu diverse implementări, anumite ADT-uri vor fi construite pe baza acestor modele diverse seturi operatori.
În mod ideal, este de dorit să scrieți programe într-un limbaj ale cărui tipuri de date și operatori de bază sunt suficiente pentru a implementa un ADT. Din acest punct de vedere, limbajul Pascal nu este un limbaj foarte potrivit pentru implementarea diverselor ADT-uri, dar, pe de altă parte, este greu de găsit un alt limbaj de programare în care să fie posibil să se declare un ADT într-un mod atât de direct. . Informatii suplimentare pentru astfel de limbaje de programare, consultați notele bibliografice de la sfârșitul subiectului.
Un tip de date descrie un set de obiecte cu proprietăți similare. Toate limbajele de programare tradiționale folosesc un set de tipuri de date de bază (real, întreg, șir, caracter). Tipurile de date de bază sunt supuse unui set predefinit de operațiuni. De exemplu, tipul de date de bază întreg vă permite să efectuați operații precum adunarea, scăderea, înmulțirea și împărțirea.
Limbajele de programare tradiționale includ constructori de tip, dintre care cel mai comun este constructorul de înregistrări. De exemplu, pentru o înregistrare de tip CLIENT, puteți defini câmpuri de date. Intrarea CLIENT va fi tip nou structura de date, care va stoca informații despre client, puteți accesa direct această structură de date, referindu-vă la numele câmpurilor. Puteți efectua operațiuni precum SCRIERE, CITIRE, ȘTERGERE, UPDATE pe o înregistrare. Nu puteți defini operațiuni noi pentru tipurile de date de bază.
La fel ca tipurile de date de bază, tipurile de date abstracte (ATD) descriu multe obiecte similare. Există diferențe între ATD și tip tradițional date:
· operațiunile sub ATD sunt definite de utilizator;
· ATD-urile nu permit accesul direct la reprezentarea datelor interne și la implementările metodelor.
În unele sisteme OO (de exemplu, Smalltalk), tipurile de date de bază sunt implementate ca și abstracte.
Pentru a crea un tip de date abstracte, trebuie să furnizați:
numele tipului;
Reprezentarea datelor sau a variabilelor de instanță ale unui obiect deținut de ATD; fiecare variabilă de instanță are un tip de date, care poate fi fie tip de bază, sau un alt ATD;
· Operațiile și constrângerile ATD sunt implementate folosind metode.
Definiția ATD reconstruiește definiția clasei. În unele sisteme OO, cuvântul cheie type este folosit pentru a distinge între clase și tipuri atunci când se face referire la structurile de date și metodele unei clase și când se face referire la un set de instanțe de obiect, cuvânt cheie clasă. Tipul (tipul) este un concept mai static, iar clasa este legată în principal de timpul de execuție. Diferența dintre o clasă OO și un tip OO poate fi ilustrată cu un exemplu. Să presupunem că există un șablon pentru un constructor. Șablonul este însoțit de o descriere a structurii sale, precum și de instrucțiuni de utilizare. Acest șablon este definiția tipului. Un set de produse reale realizate folosind un șablon, fiecare având un număr unic (sau OID), constituie o clasă (clasă).
ATD, împreună cu moștenirea, vă permite să creați obiecte complexe. Un obiect complex se formează prin combinarea altor obiecte care se află în relații complexe între ele. Exemplu obiect complex pot fi găsite în sistemele de securitate care utilizează tipuri diferite date:
1. date standard (tabulare) despre angajat (nume complet, Tab. Nr. etc.);
2. bitmap pentru stocarea fotografiilor angajatului;
Capacitatea de a lucra cu un mediu de date atât de complex cu relativă ușurință crește importanța sistemelor OO pe piața actuală a bazelor de date.
Tip de date abstracte Tipuri de date generale Tip de date abstracte Dispoziții generale specificare, reprezentare, implementare 1
Ce sunt datele? Set de diverse obiecte informaţionale, asupra cărora anumite acțiuni sunt efectuate de către operatorii de program, se numesc date. Datele sunt un atribut indispensabil al oricărui program. Pot fi: - biţi individuali; - succesiunea de biți independenți; -numerele în diferite forme de reprezentare; -octeți și grupuri de octeți independenți; - matrice de numere; - liste legate; - fisiere separateși sisteme de fișiere. 2
Reprezentarea universală a acestei varietăți de date este dificilă și nepractică. Este recomandabil să le împărțiți în tipurile 3
Ce este un tip de date? Tipul de date este determinat de: – Formatul de reprezentare în memoria calculatorului conform anumitor convenții ale limbajului algoritmic, dar fără a fi nevoie de calcule; - Mulți valori admise, pe care o poate lua o variabilă sau constantă aparținând tipului selectat; – Setul de operațiuni valabile aplicabile acestui tip. 4
Tip de date Exemple Tipuri întregi Tip real tip boolean Tip de caractere Tip enumerat Tip interval Indicatori 5
Tipuri întregi Există cinci tipuri de întregi predefinite: Shortint, Integer, Longint, Byte și Word. Fiecare tip denotă un subset specific de numere întregi. O valoare a unui tip întreg poate fi convertită în mod explicit într-un alt tip integral folosind un cast. 6
Tip real Tipul real se referă la un subset de numere reprezentate în format virgulă mobilă cu un număr fix de cifre. O valoare în virgulă mobilă include de obicei trei valori - m, b și e - astfel încât m * b ^ e = n, unde b este întotdeauna 2, iar m și e sunt valori întregi în intervalul de tip real . Aceste valori ale lui m și e definesc în continuare domeniul de reprezentare și precizia tipului real. Exemplu: 0,143 E+22, unde m este 0,143; b=2(implicit), e=22. Există cinci tipuri tipuri reale: real (Real), cu precizie simplă (Single), cu precizie dublă (Double), cu precizie crescută (Extended) și complex (Comp). 7
Tip boolean Există 4 tipuri booleene predefinite: Boolean, Byte. Bool, Word. bool și lung. Bool. Valorile booleene sunt notate de identificatorii constanti încorporați False și True. Variabilele booleene pot fi folosite pentru a stoca rezultatele oricăror calcule logice. Pentru variabilele booleene, sunt permise doar 2 operații de comparare „="(egal) și „”(nu este egal). opt
Tipul de caractere Setul de valori de acest tip sunt caractere ordonate conform setului de caractere ASCII extins. Acestea sunt literele [„A”. . . „Z”, „a”. . . „z”], cifre [„0”. . . „9”], semne de punctuație și caractere speciale. O variabilă de acest tip ocupă un octet în memorie. nouă
Tipul enumerat Tipurile enumerate definesc seturi ordonate de valori printr-o enumerare de identificatori care denotă acele valori. Seturile sunt ordonate în funcție de ordinea în care sunt listați identificatorii. Tip Week = (luni, marți, miercuri, joi, vineri, sâmbătă, duminică); zece
Tip de interval Un tip de interval este un interval de valori dintr-un tip ordinal. Definiția unui tip de interval include cele mai mici și cea mai mare valoareîn subgamă. Interval de tip = 0. . . 1000; O astfel de declarație de tip îi spune compilatorului că numai numerele din intervalul specificat sunt permise pentru variabilele de acel tip. Astfel, programul poate organiza automat verificări pentru corectitudinea operațiunilor de atribuire pentru aceste variabile. unsprezece
Comun pentru tipurile de date Fiecare dintre tipurile de date corespunde unui set operatii simple. INTEGER-operații +, -, *, div, mod REAL - operații + , -, *, / BOOLEAN-operații - conjuncție (și), disjuncție V (sau), negație (nu) CHAR-operație ORD (c) -N : (C în ASCII), CHR (I) I-lea caracter în ASCII Pe măsură ce volumul și complexitatea reprezentării informațiilor crește, este nevoie de forme convenabile de prezentare, stocare și procesare a acesteia. 12
Definiția unui tip de date abstracte (ATD sau tip de date abstracte, sau ADT) este un set de obiecte abstracte reprezentând elemente de date și un set de operații definite pe acesta care pot fi efectuate asupra elementelor acestui set. 13
ADT - o generalizare a tipurilor de date Tipurile de date abstracte (ATD) pot fi gândite ca un mijloc de extindere a limbajelor de programare. Să comparăm un tip de date abstracte cu conceptul familiar de procedură. O procedură poate fi privită ca o noțiune generalizată a unui operator. Două trăsături caracteristice ale procedurilor - generalizarea și încapsularea - caracterizează perfect tipurile de date abstracte. Un ADT poate fi gândit ca o generalizare a unor tipuri de date simple (numere întregi, reale etc.), la fel cum o procedură este o generalizare a operatorilor simpli (+, -, etc.)
Avantaje ATD Rezumat structurile de date sunt pentru depozitare convenabilăși accesul la informații. Ei furnizeaza interfață ușor de utilizat pentru operațiuni tipice cu obiectele stocate, ascunderea detaliilor de implementare de la utilizator. Desigur, acest lucru este foarte convenabil și vă permite să obțineți o mai mare modularitate a programului. cincisprezece
Exemplu pentru control automatizat temperatura în diferitele încăperi ale unei clădiri mari, un TERMOSTAT ar fi un ATD util. Programul poate avea multe variabile de tip TERMOSTAT corespunzător termostatelor reale din diferite încăperi ale clădirii. Un ADT poate fi descris după numele său, setul de valori și operațiunile permise la fel ca orice alt tip de date. Descriere pentru tipul TERMOSTAT: – Tip de date: TERMOSTAT – Domeniu de valori: Temperatura poate varia între 0 și 50 de grade (Celsius). – Operații: Sus, Jos, Setare, Verificare, Alarmă. (Se pot veni cu multe operații utile, dar prea multe dintre ele degradează abstracția) 16
Straturi de abstractizare Straturile de abstractizare sunt ca straturi software. Cele mai înalte niveluri de abstractizare reflectă ideea utilizatorului de a rezolva problema. niveluri inferioare abstracțiile sunt posibilitățile unui limbaj de programare. 17
Exemplu de abstracție la nivel de utilizator Un arhitect reprezintă o casă în termeni de pereți, podele, ferestre, uși și așa mai departe. În acest caz, tipul de date este Imagine. Ușile ar putea fi un tip abstract bun. Tip de date: Desen. Operații la uși: Desenați. Ștergerea ușii. Tragere la ușă. Dubla. Usa ……. Imagine. Ușile sunt abstracte nivel inalt, reflectând punctul de vedere al utilizatorului asupra problemei 18
Exemplu de abstracție la nivelul programatorului Programatorul poate sugera un alt nivel de abstracție pentru aceste obiecte, cum ar fi un dreptunghi. Tip de date: Dreptunghi Operații: Desenare. Ștergere dreptunghi. Împărțire dreptunghiulară. Dreptunghi. Pe. Părți……. Dreptunghiul este o abstractizare nivel scăzut, deoarece este mai aproape de implementare. nouăsprezece
Constructori ADT Fiecare ADT trebuie să conțină operații pentru construirea de valori de tipul său. Astfel de operații se numesc constructori. Constructorii ar trebui să fie suficienți pentru a genera întregul set de valori de acest tip. Un ADT care satisface această proprietate se numește complet. Un ADT incomplet este o eroare de proiectare. douăzeci
Recomandări pentru alegerea operaţiilor de tip de date abstracte Este recomandabil să se includă următoarele operaţii: – operaţii de constructor, – operaţii de verificare, – operaţii de conversie de tip, – operaţii de I/O, – operaţii de copiere, – operaţii de selectare. Încercați să mențineți numărul de tranzacții la minimum. Un simplu ADT este mai ușor de înțeles. Păstrați operațiunile asociate cu tipul de abstractizare la alegere. 21
Constructorul primar Operațiile care creează noi valori pentru un ADT, indiferent de valoarea sa anterioară, se numesc constructori primari. Fiecare ADT include cel puțin un constructor primar: fără el, este imposibil să se formeze o valoare inițială. 22
Utilizarea tipurilor ascunse Tipurile de date abstracte sunt cel mai bine declarate ca tipuri ascunse. Acest lucru permite ca descrierea structurii de date să fie mutată în unitatea de implementare, unde este utilizată predominant. Ele oferă, de asemenea, o oportunitate de prevenire acces direct la componentele tip din partea importatorului. Deoarece un tip ascuns este întotdeauna implementat cu un pointer, există trei operații care trebuie incluse într-un ADT. – Creare - o operație care creează un nod al structurii corespunzătoare. – Distruge - operațiune pentru a elibera memoria nodului tip ascuns. – Atribuire - operația de copiere a câmpurilor structurii dinamice a unui nod de tip ascuns. 23
Care este specificația și implementarea unui tip de date abstract Un tip de date abstract este o modalitate de a defini un concept ca o clasă de obiecte cu anumite proprietăți și operații. Într-un limbaj de programare, o astfel de definiție este formalizată ca o construcție sintactică specială numită în limbi diferite capsulă, modul, cluster, clasă, pachet, formular etc. Această construcție în forma sa cea mai avansată conține: o specificație a tipului de date, care include o descriere a interfeței (numele tipului care se definește, numele operațiunilor cu indicarea profilurilor acestora) și o descriere abstractă a operațiilor și obiectelor, cu care acestea lucrează, unele mijloace de specificare; o implementare a tipului de date care include o descriere specifică a acelorași operațiuni și obiecte. 24
Clasificarea tipurilor de date în funcție de metoda de descriere și protecție ambalate, dacă descrierea tipului de date este colectată într-un singur loc (într-un singur pachet), adică obiectele și operațiunile sale sunt combinate într-un singur concept; are o definiție, care poate conține, totuși, doar implementarea ei; încapsulat, dacă tipul de date este împachetat, definiția acestuia conține o descriere a interfeței și o implementare și este furnizată și încapsularea implementării; abstract dacă tipul de date este încapsulat și specificația sa include o declarație abstractă. 25
Componentele specificației Programarea, ca proces, începe cu enunțarea problemei (definiția acesteia) sau specificarea problemei. În continuare pe tot cuprinsul textului, sunt utilizate specificații, formate din șase componente: – Titlu - denumirea problemei care se rezolvă; – Descriere – mai multe propoziții care descriu esența sarcinii; - Intrare - descriere detaliata forma dorită a datelor de intrare; – Ieșire - o descriere detaliată a formei dorite a datelor de ieșire; – Erori – lista detaliata situații care decurg din datele introduse incorecte; – Exemplu - un exemplu de execuție în termeni de intrare-ieșire. 26
Exemplu de specificație Un tip de date STEC abstract care implementează o structură de date bine-cunoscută care se caracterizează prin faptul că puteți „pune” un element în el și „selectați” din el elementul plasat cel mai recent acolo. Partea de sintaxă a specificației tipului de date STACK este tip Specificația STACK este CREATE: function () return (@); INSERT: funcție (întreg; @) return (@); DELETE: funcția (@) return (@); TOP: funcția (@) return (întreg); EMPTY: function (@) return(boolean); specificație finală; Aici, operațiunea CREATE produce ca rezultat o stivă goală, INSERT - o stivă cu elementul său adăugat la „sus”, DELETE - o stivă cu elementul „sus” eliminat, TOP - valoarea elementului „sus” de stiva, EMPTY - un semn de golire a stivei. Elementele stivei de aici pot fi doar numere întregi. 27
IMPLEMENTAREA UNUI TIP DE DATE ABSTRACTE Implementarea se face mai convenabil folosind limbaje de programare orientate pe obiecte, cum ar fi C++ sau Java, unde tipurile de date abstracte sunt suportate de clase.O implementare a unui ADT include o descriere specifică a obiectelor tipului care se află definite și implementarea operațiunilor de acest tip. Aceasta înseamnă că obiectele sunt descrise fie ca date de tipuri simple, fie ca matrice, înregistrări sau uniuni. În plus, sunt utilizate tipuri de date predefinite sau ADT-uri definite mai devreme. Implementarea operatiilor consta in descrierea subrutinelor care efectueaza acțiunile necesare cu obiectele specificate. De exemplu, operațiile +, *, =. . etc., dar în același timp însăși implementarea acestor operațiuni este ascunsă. 28
Dezvoltarea de modele abstracte pentru date și modalități de prelucrare a acestor date este componenta esentialaîn procesul de rezolvare a problemelor cu ajutorul calculatorului. Vedem exemple în acest sens atât la un nivel scăzut în programarea de zi cu zi (de exemplu, când se utilizează matrice și liste legate, discutate în), cât și la un nivel înalt atunci când rezolvăm sarcini aplicate(ca atunci când rezolvați problema de conectivitate folosind pădurea de căutare unire în „Introducere”). Această prelegere discută tipuri de date abstracte ( tipul de date abstracte, denumit în continuare ADT), care vă permit să creați programe folosind abstracții de nivel înalt. Tipurile de date abstracte vă permit să separați transformările abstracte (conceptuale) pe care programele le efectuează asupra datelor de orice reprezentare particulară a unei structuri de date și orice implementare particulară a unui algoritm.
Toate sisteme de calcul pe baza nivelurilor de abstractizare: anumite proprietăți fizice ale siliciului și ale altor materiale permit adoptarea unui model abstract al unui bit, care poate prelua valorile binare 0-1; apoi, un model abstract al mașinii este construit pe proprietățile dinamice ale valorilor unui anumit set de biți; în continuare, pe baza principiului de funcționare a mașinii sub controlul programului pe limbajul mașinii este construit un model abstract al limbajului de programare; și, în final, se construiește un concept abstract al unui algoritm, care este implementat ca program C++. Tipurile de date abstracte fac posibilă continuarea acestui proces și dezvoltarea mecanismelor abstracte pentru anumite sarcini de calcul la un nivel mai înalt decât este oferit de sistemul C++, dezvoltarea mecanismelor abstracte concentrate pe aplicatii specificeși potrivit pentru rezolvarea problemelor din numeroase domenii de aplicare, precum și pentru a crea mecanisme abstracte de nivel superior care utilizează aceste constructe de bază. Tipurile de date abstracte ne oferă un set infinit de extensibil de unelte pentru a rezolva tot mai multe probleme noi.
Pe de o parte, utilizarea constructelor abstracte eliberează grijile legate de implementarea lor detaliată; pe de altă parte, când performanţă programul este important, trebuie să cunoașteți costurile pentru efectuarea operațiunilor de bază. Folosim o mulțime de abstracții de bază încorporate hardware calculator și care servesc drept bază pentru instrucțiunile mașinii; implementați alte abstracții în software; și utilizați abstracții suplimentare furnizate de software-ul de sistem scris anterior. Construcțiile abstracte de nivel înalt se bazează adesea pe mai mult desene simple. La toate nivelurile, se aplică același principiu de bază: trebuie să găsiți cel mai mult operațiuni importanteîn programe și majoritatea caracteristici importante date, iar apoi să definească precis atât la nivel abstract, cât și să dezvolte mecanisme concrete eficiente pentru implementarea lor. În această prelegere, vom analiza multe exemple de aplicare a acestui principiu.
Dezvoltarea unui nou nivel de abstractizare va necesita (1) definirea obiectelor abstracte de manipulat și a operațiunilor care trebuie efectuate asupra acestora; (2) să reprezinte datele într-o structură de date și să implementeze operațiunile; (3) și (cel mai important) pentru a se asigura că aceste obiecte sunt convenabile de utilizat pentru rezolvarea problemelor aplicate. Aceste puncte se aplică și pentru tipuri simple date, astfel încât mecanismele de bază pentru suportul tipurilor de date, care au fost discutate în „Structuri elementare de date”, pot fi adaptate scopurilor noastre. Cu toate acestea, limbajul C++ oferă extindere importantă mecanism al structurilor, numită clasă ( clasă ). Clasele sunt extrem de utile în crearea unor straturi de abstractizare și, prin urmare, sunt tratate ca instrumentul principal folosit în acest scop în restul cărții.
Definiție 4.1. Un tip de date abstract (ATD) este un tip de date (un set de valori și un set de operații asupra acestor valori) care este accesat doar printr-o interfață. Programul care folosește ADT va fi numit client, iar programul care conține specificația acestui tip de date va fi numit implementare.
Este cuvântul care face doar tipul de date abstract: în cazul unui ADT, programele client nu au acces la valorile datelor în alt mod decât operațiunile descrise în interfață. Reprezentarea acestor date și funcțiile care implementează aceste operațiuni sunt în implementare și sunt complet separate printr-o interfață de client. Spunem că interfața este opacă: clientul nu poate vedea implementarea prin interfață.
În programele C++, această distincție este de obicei făcută puțin mai clară, deoarece este cel mai ușor să creați o interfață prin includerea prezentarea datelor, dar specificând că programelor client nu li se permite accesul direct la date. Cu alte cuvinte, dezvoltatorii clienți s-ar putea să știe prezentarea datelor, dar nu îl pot folosi în niciun fel.
Ca exemplu, luați în considerare interfața tipului de date pentru puncte (Programul 3.3) din Secțiunea 3.1 „Structuri elementare de date”. Această interfață declară în mod explicit că punctele sunt reprezentate ca structuri constând dintr-o pereche de numere în virgulă mobilă, notate cu x și y. Această utilizare a tipurilor de date este comună în sisteme mari software: dezvoltăm un set de convenții de reprezentare a datelor (precum definim un set de operații aferente) și punem la dispoziție aceste reguli printr-o interfață astfel încât să poată fi utilizate de programele client care fac parte din sistem mare. Tipul de date asigură că toate părțile sistemului sunt în concordanță cu reprezentarea structurilor de date subiacente la nivelul întregului sistem. Oricât de bună ar fi această strategie, are un dezavantaj: dacă este necesar să se schimbe prezentarea datelor, va trebui să schimbați toate programele client. Programul 3.3 ne oferă din nou un exemplu simplu: unul dintre motivele dezvoltării acestui tip de date este comoditatea programelor client care lucrează cu puncte și ne așteptăm ca clienții să aibă acces la coordonatele individuale ale unui punct, dacă este necesar. Dar nu putem trece la o reprezentare diferită a datelor (să zicem, coordonate polare sau coordonate 3D, sau chiar alte tipuri de date pentru coordonate individuale) fără a schimba toate programele client.
În contrast, Programul 4.1 conține o implementare a unui tip de date abstracte care corespunde tipului de date din Programul 3.3, dar folosind o clasă de limbaj C++ care definește atât datele, cât și operațiile asociate acestora simultan. Programul 4.2 este program client A care funcționează cu acest tip de date. Aceste două programe efectuează aceleași calcule ca și programele 3.3 și 3.8. Ele ilustrează o serie de proprietăți principale ale claselor pe care le vom lua în considerare acum.
Când scriem o definiție ca int i într-un program, îi spunem sistemului să rezerve o zonă de memorie pentru date (onboard) tastați int, care poate fi accesat cu numele i. Limbajul C++ are termenul de obiect pentru astfel de entități. Când într-un program este scrisă o definiție precum POINT p, se spune că este creat un obiect din clasa POINT, la care se poate face referire prin numele p. În exemplul nostru, fiecare obiect conține două elemente de date, numite x și y. Ca și în cazul structurilor, ele pot fi menționate prin nume precum p.y.
Membrii de date x și y sunt numiți membri de date ai clasei. Clasa poate defini, de asemenea, funcții membre care implementează operațiunile asociate cu acest tip de date. De exemplu, clasa definită în Programul 4.1 are două funcții membre numite POINT și distanță.
Programele client, cum ar fi programul 4.2, pot apela funcții membre asociate cu un obiect prin specificarea numelor acestora în același mod ca și numele datelor conținute într-o structură structurală. De exemplu, expresia p.distance(q) calculează distanța dintre punctele p și q (aceeași distanță ar trebui returnată apelând q.distance(p) ). Funcția POINT(), prima funcție din Programul 4.1, este o funcție membru special numită constructor: are același nume ca o clasă și este apelată atunci când un obiect al acelei clase trebuie creat.
Programul 4.1. Implementarea clasei POINT (punct)
Această clasă definește un tip de date care constă dintr-un set de valori care sunt „perechi de numere în virgulă mobilă” (presupunând că sunt interpretate ca puncte într-un plan cartezian), precum și două funcții membre definite pentru toate instanțele POINT. clasă: funcția POINT() , care este un constructor care inițializează coordonatele cu valori aleatoare de la 0 la 1 și o funcție distanță(POINT) care calculează distanța până la un alt punct. Reprezentarea datelor este privat și numai funcțiile membre îl pot accesa sau modifica. Funcțiile membre în sine sunt publice (publice) și disponibile oricărui client. Codul poate fi salvat, de exemplu, într-un fișier numit POINT .cxx.
#include
Programul 4.2. Program client pentru clasa POINT (găsirea celui mai apropiat punct)
Această versiune a programului 3.8 este un client care utilizează POINT ADT definit în programul 4.3. Operațiune nouă creează o matrice de obiecte POINT (prin apelarea constructorului POINT() pentru a inițializa fiecare obiect cu valori aleatoare ale coordonatelor). Expresia a[i].distance(a[j]) apelează funcția membru distanță pe obiectul a[i] cu argumentul a[j] .
#include
Definirea POINT p în programul client are ca rezultat alocarea unei zone de memorie pentru un nou obiect și apoi (folosind funcția POINT()) atribuirea fiecăruia dintre cele două elemente de date ale sale o valoare aleatorie în intervalul de la 0 la 1.
Acest stil de programare, uneori numit programare orientată pe obiecte, este pe deplin susținut de constructia clasei C++. O clasă poate fi gândită ca o extensie a conceptului de structură, în care nu numai datele sunt combinate, ci și operațiunile pe acele date sunt definite. Pot exista multe obiecte diferite aparținând aceleiași clase, dar toate sunt similare prin aceea că membrii lor de date pot prelua același set de valori și același set de operațiuni poate fi efectuat asupra acelor membri de date - în general, sunt instanțe de același tip de date. În programarea orientată pe obiecte, obiectele sunt concepute pentru a-și procesa membrii datelor (spre deosebire de utilizarea funcțiilor independente pentru a procesa datele stocate în obiecte).
Ne uităm la exemplul unei clase mici descris mai sus doar pentru a ne familiariza cu caracteristicile de bază ale claselor; deci este departe de a fi complet. În codul real pentru clasa de puncte, vom avea multe mai multe operații. De exemplu, în programul 4.1, nici măcar nu există operații care să vă permită să aflați valorile coordonatelor x și y. După cum vom vedea, adăugarea acestor și alte operațiuni este o sarcină destul de simplă. În partea 5, vom arunca o privire mai atentă asupra claselor de puncte și a altor abstracții geometrice, cum ar fi liniile și poligoanele.
În C++ (dar nu în C), structurile pot avea și funcții asociate acestora. Diferența cheie dintre clase și structuri are de-a face cu accesul la informații, care este caracterizat de cuvinte cheie.
