Se poate pune în evidență caracterul dual al datelor:
a. Datele sunt piese de informație care aparțin domeniului problemei: numere, șiruri de caractere, imagini, secvențe sonore etc. Sub acest aspect, fiecare din ele are o anumită semnificație, care depinde de rolul îndeplinit în problema respectivă. De exemplu, în probleme diferite, același număr întreg poate fi vârsta unei persoane, numărul de dosare dintr-un birou, numărul de exemplare ale unei cărți într-o librărie etc. b. Datele sunt structuri simbolice prin care se
reprezintă piesele de informație în calculator sau în documentele
folosite de om. Sub acest aspect, se ignoră semnificația datelor,
punându-se accentul pe forma de reprezentare a acestora și pe operațiile
la care pot fi supuse. Din acest punct de vedere, datele se grupează în tipuri
de date, astfel că toate datele de același tip respectă aceleași
convenții de reprezentare și suportă aceleași operații.
|
Datele pot fi primitive sau structurate.
În limbajul Java, tipurile de date primitive sunt:
Tipul char din limbajul Java are o situație deosebită:
|
Tipuri similare există și in celelalte limbaje de programare, dar pot diferi atât denumirile tipurilor, cât și formele de reprezentare externă și internă a datelor respective.
Structura de date este un mod de organizare și
reprezentare a datelor, care conține atât datele propriu-zise, cât și
legăturile dintre ele.
La nivel conceptual, structura de date abstractă
este o schemă care conține componente și relații între
aceste componente. Componentele pot fi date primitive sau structuri
de date. Pentru fiecare structură se specifică și un set de operații
care pot fi efectuate asupra întregii structuri sau a componentelor ei.
La nivelul implementării, limbajele de programare furnizează mijloace prin care se pot construi anumite structuri de date considerate de bază în limbajul respectiv și - eventual - de construire a unor structuri din ce în ce mai complexe, pornind de la datele primitive și structurile de bază. Operațiile asupra structurilor se implementează sub formă de funcții sau proceduri. În programarea procedurală tradițională, structurile de date și funcțiile sau procedurile prin care se realizează operațiile asupra acestora se implementează separat, legătura dintre ele realizându-se doar la nivel conceptual și nu prin mijloace specifice limbajului folosit. În programarea orientată pe obiecte, structurile de date se realizează sub formă de clase, care cuprind atât datele și legăturile dintre ele, cât și metodele prin care se realizează operațiile asupra structurii respective. |
Principalele structuri de date pentru care limbajele de programare procedurală oferă mijloace specifice de declarare sunt tabloul și înregistrarea.
Structura de tablou are la bază conceptul de matrice
din matematică. Astfel, de exemplu, tabloul a = [a0 a1 a2 a3] are patru componente asezate pe o singură direcție în spațiu și au un singur indice, cu valori de la zero la 3. În matematică, un astfel de tablou este o matrice cu o singură linie (numită și vector-linie) dacă elementele sunt așezate orizontal, ca în exemplul de mai sus, sau este o matrice cu o singură coloană (un vector-coloană) dacă elementele sunt asezate pe o direcție verticală. În prelucrarea pe calculator nu se ia în considerație orientarea orizontală sau verticală, ci numai faptul că elementele sunt dispuse pe o singura direcție (liniar). În cazul unei matrice cu mai multe linii și coloane,
componentele sunt plasate pe două direcții (într-un plan) și au fiecare
doi indici, ca în exemplul următor: Remarcăm că matricea (tabloul bidimensional) poate fi considerată drept un tablou unidimensional, ale cărui componente sunt ele însele tablouri unidimensionale. De exemplu, putem considera că matricea este un vector-coloană, ale cărui componente sunt vectori-linie. Pornind de la această observație, putem extinde conceptul de tablou la mai mult de două dimensiuni. Putem, astfel, să considerăm că un tablou tridimensional (o matrice spațială) este un tablou unidimensional, ale cărui componente sunt tablouri bidimensionale. Un astfel de tablou poate fi imaginat ca având mai multe "pagini", unde fiecare "pagină" este o matrice bidimensională. În acest caz, componentele au câte trei indici, care indică în mod corespunzător linia, coloana și pagina în care este situată componenta respectivă. Extinzând la cazul multidimensional, putem considera că un tablou cu n dimensiuni este un tablou unidimensional, ale cărui componente sunt tablouri cu n-1 dimensiuni, fiecare componentă a tabloului având n indici. |
Structura de tablou a fost introdusă în limbajul FORTRAN
(1956), fiind prezentă în toate limbajele de programare pentru calcule
științifice și inginerești și în majoritatea celorlalte limbaje de
programare de nivel superior. Ca exemple putem da limbajele Fortran,
Basic, Pascal, C, C++, Java. Există, totuși, deosebiri între aceste
limbaje atât din punct de vedere al formei sintactice a declarației de
tablou, cât și în ce privește modul de implementare a tablourilor.
În majoritatea limbajelor se consideră că într-o matrice (tablou bidimensional) toate liniile au aceeași lungime și - în mod corespunzător - într-un tablou n-dimensional, toate componentele sale cu n-1 dimensiuni sunt omogene nu numai sub aspectul tipului, ci și al dimensiunilor. Se consideră, de asemenea, că tabloul ocupă în memorie o zonă compactă (de unde și denumirea de masiv). Având însă în vedere că memoria calculatorului este o structură liniară (toate locațiile din memorie sunt - conceptual vorbind - dispuse liniar fiind indicate prin adresa lor), înseamnă că orice tablou multidimensional trebuie desfășurat în memorie pe o singură direcție. Desfășurarea pe o singura direcție a elementelor unui tablou se poate face în moduri diferite, depinzând de limbajul folosit. Astfel, în limbajul FORTRAN, se consideră că elementele tabloului sunt plasate în memorie coloană după coloană, în timp ce în limbajele Pascal si C se consideră ca desfășurarea se face linie după linie. În consecință, în Pascal și C componentele matricei b din exemplul de mai sus vor fi plasate astfel: b00 b01b02 b03 b04 b10 b11 b12 b13 b14 b20 b21 b22 b23 b24. Datorită acestui fapt, se poate considera că, la nivel de implementare, orice tablou multidimensional este echivalent cu unul unidimensional. Se pot stabili formule de calcul, prin care se determină valoarea indicelui componentei în desfășurarea unididimensională a tabloului, dacă se cunosc dimensiunile tabloului și valorile indicilor aceleeași componente în amplasarea spațială. De exemplu, în cazul unei matrice cu N linii si M coloane desfășurate pe linii (ca în Pascal sau C), între indicele k al desfășurării liniare și indicii i,j ai componentei respective a matricei există următoarea relație: k=i*M+j În exemplul de mai sus, elementul b23 va avea, în desfășurarea liniară a tabloului, indicele k=2*5+3=13.Domeniile de valori ale indicilor depind, de asemenea, de limbajul folosit. În Fortran, indicii sunt numere naturale, primul indice fiind 1. In C, C++ si Java, indicii sunt tot numere întregi pozitive, dar cel mai mic indice este zero. În Pascal, indicii pot fi numere întregi, caractere sau tipuri enumerate, iar marginile inferioară și superioară ale intervalului de valori pentru fiecare indice se declară prin program. Despre particularitațile tablourilor în limbajul Java vom discuta separat. |
Referirea la o componentă a tabloului se face prin mumele
tabloului însoțit de indicele (indicii) componentei respective. În
Pascal, C, C++ și Java indicii se scriu între paranteze drepte. De
exemplu, b[2][3] este componenta din linia 2 și coloana 3 a
matricei b. Remarcăm, deci, că accesul la orice componentă a
tabloului se face direct, fără a fi necesară parcurgerea celorlalte
elemente.
În numeroase aplicații ale calculatoarelor, este necesar să
se prelucreze date grupate sub forma de înregistrări, situate
fizic fie în fișiere, fie în memoria internă. Să considerăm, de exemplu,
evidența materialelor dintr-o magazie. Fiecare material se
caracterizează prin mai multe atribute, cum sunt: codul materialului,
denumirea materialului, cantitatea. Informația despre un material ar
putea fi, deci, păstrată pe un formular de hârtie având, ca exemplu,
următorul conținut:
MATERIAL Prima linie conține titlul formularului, iar următoarele linii
conțin atributele acestuia. Acest formular conține trei date: numărul
întreg 13027522, șirul de caractere "Pânză albă de bumbac" și
numărul real 127.53. Pentru prelucrarea pe calculator, aceste
date sunt grupate într-o înregistrare de forma
Remarcăm deci că această structură, care se introduce în
memoria calculatorului, conține numai datele, nu și alte
informații, cum ar fi denumirile atributelor și tipurile de date din
fiecare câmp. Descrierea acestei structuri se face în program,
folosind o instrucțiune numită declarație de structură. Forma
declarației depinde de sintaxa limbajului de programare utilizat. De
exemplu, in limbajul Pascal declarația poate avea forma In limbajul C, aceleasi declarații se fac sub forma S-a schimbat sintaxa declarațiilor, dar semnificatța este aceeași ca în Pascal. În ambele limbaje, notația a.cod înseamnă valoarea câmpului cod al înregistrării (structurii) a, deci un câmp al unei înregistrări este specificat în program sub forma nume_variabilă.nume_camp. Structura de înregistrare a fost introdusă prima dată în limbajul COBOL (creat în 1959) și este utilizată în toate limbajele care sunt orientate pe folosirea fișierelor sau a bazelor de date, fiind prezentă și în unele limbaje de uz general, cum sunt Pascal și C. Remarcăm că nici în Pascal, nici în C nu este predefinit un tip de date numit Material, dar limbajul pune la dispoziția programatorului modalitatea prin care el poate să definească un astfel de tip. |
Înregistrarea (engl: record) este o structură de date neomogenă cu următoarele caracteristici:
Câmpurile de date dintr-o înregistare pot conține nu numai date primitive, ci și structuri de date. În particular, orice câmp al unei înregistrări poate fi el însuși o înregistrare.
Se știe că în conceptul de tip de date sunt cuprinse
atât mulțimea de valori, cât și mulțimea de operații
aplicabile valorilor respective. Din acest punct de vedere,
înregistrarea nu este un tip de date complet definit, deoarece la
declararea înregistrării se descrie numai structura de date,
definindu-se astfel numai multimea de valori pe care aceasta le poate
avea. Operațiile se fac numai asupra datelor primitive conținute în
câmpuri, respectând convențiile pentru tipul de care aceste campuri
aparțin.
Întrucât clasa conține atât date, cât și metode, ea se încadrează complet în conceptul de tip de date enunțat mai sus. |
In timpul executării programului, datele primitive se găsesc în memoria calculatorului sub forma unor valori plasate în anumite zone de memorie. În mod corespunzător, structurile de tablou sau de înregistrare sunt plasate în anumite zone de memorie. Dacă, la nivel conceptual, structurile de date sunt plane sau spațiale, valorile componentelor acestora sunt așezate în zona de memorie alocată structurii, respectând o anumită convenție de desfășurare liniară, cum s-a arătat mai sus în cazul tablourilor. |
Variabila este numele dat în program unei zone de memorie în
care se găsește o valoare. După tipul acesteia, valoarea poate
fi, în principiu, o dată primitivă sau o structură de date. Operațiile
prevăzute în program nu se fac asupra variabilelor, ci asupra valorilor
acestora.
De exemplu, expresia c=a*b este interpretată astfel: se inmulteste valoarea variabilei a cu valoarea variabilei b, iar valoarea rezultată se atribuie variabilei c. Cu alte cuvinte, se înmulțește valoarea situată în zona de memorie alocată variabilei a cu valoarea situată în zona de memorie alocată variabilei b, iar valoarea rezultată se pune în zona de memorie alocată variabilei c. |
Pointerul este o variabilă specială, a cărei valoare este o adresă
de memorie. Pointerii se folosesc în numeroase limbaje de nivel
superior, printre care Pascal, C si C++, dar nu există în limbajul Java.
Asupra pointerilor se pot face operații de atribuire, adunare cu o
constantă și afișare.
De exemplu, în limbajul C sau C++ declarația double a, b, *p1, *p2; are semnificația că a și b sunt variabile de tip double, în timp ce p1 si p2 sunt pointeri la variabile de tip double. Aceasta înseamnă că în zonele de memorie care aparțin variabilelor a și b se găsesc chiar valorile acestor variabile (sub forma de date de tip double, pe câte 8 octeți), în timp ce în zonele de memorie alocate pentru variabilele p1 și p2 se găsesc adresele la care sunt situate în memorie niște date de tip double (adresele fiind numere întregi, fără semn, pe doi octeți fiecare). Expresia p1=&a are semnificația că se atribuie ca valoare variabilei p1 adresa la care se găsește în memorie valoarea variabilei a. Pointerului i se poate atribui, însă, ca valoare orice adresă din memorie, chiar dacă aceasta nu este adresa alocată unei variabile din program, fiind permise, de exemplu, atribuiri de forma p1=1735, sau p2=#7FFF. De asemenea, valoarea pointerului poate fi afișată pe ecran. Totodată, în expresii se pot folosi și valorile indicate de pointeri. Astfel, continuand exemplul de mai sus, expresia *p1/*p2 are semnificatia ca se imparte valoarea de tip double situata in memorie la adresa p1 la valoarea de tip double de la adresa p2, obținându-se ca rezultat o valoare numerică de tip double. În schimb, expresia p1+3 are semnificația că la adresa care este valoarea pointerului p1 se adaugă o cantitate egală cu de trei ori lungimea unei date de tip double (conform tipului pointerului) și se obține o nouă adresă a unei date de tip double. În limbajul Java nu se folosesc pointeri, dar am avut nevoie de aceste exemple pentru a pune în evidență deosebirea dintre pointeri și referințe. |
Referința este, în programare, o indicație privind locul în care poate fi gasită o dată sau o structură de date fiind, din acest punct de vedere, o abstractizare a conceptului de adresă. Deosebirea dintre referință și adresă este că referința nu este considerată a fi un număr, și deci asupra ei nu pot fi efectuate operații aritmetice și nici nu poate fi afișată sau supusă altor operații de intrare/iesire.
Variabila referință este o variabilă, a cărei valoare este o referință. În unele limbaje de programare (de exemplu în Pascal) termenul de "variabilă referință" (sau simplu "referință") este folosit ca sinonim al celui de pointer.
În limbajul C++ se face distincție între pointeri si
referințe: variabila referință este considerată doar drept un sinonim
(un alt nume) al variabilei obișnuite.
De exemplu, în C++ instrucțiunea |
În limbajul Java, se consideră că variabilele simple au ca
valori date primitive, iar variabilele referință au ca valori referințe
la obiecte (la instanțe ale claselor).
In consecință, în limbajul Java, variabilele referință se
comportă ca niște pointeri, în sensul că:
|
ClasaÎn limbajul Java, clasa este ea însăși un obiect, mai exact o instanță a clasei java.lang.Class, care este prezentă în memoria mașinii virtuale Java în timpul executării programului și conține:
Instanțele oricărei clase sunt, de asemenea, obiecte și conțin:
TabloulÎn limbajul Java, reprezentarea tabloului ca un masiv de date, ale cărui componente ocupă în memorie o zonă compactă rămâne valabilă numai pentru tablourile unidimensionale cu componente de tipuri primitive. Totuși, chiar și aceste tablouri, se deosebesc de cele din alte limbaje: în Java, tabloul este un obiect, care - în afară de componentele propriu-zise - conține și un câmp de tip int numit length, care are ca valoare numărul de componente. În consecință, dacă tab este un tablou, atunci tab.length este numărul de componente ale acestui tablou.Tablourile multidimensionale sunt implementate prin structuri arborescente, în care frunzele sunt componentele propriu-zise, iar fiecare nod intermediar de nivel k este un tablou unidimensional, ale cărui componente sunt referințe la nodurile de nivel k+1. În aceste condiții dispare și cerința de omogenitate a dimensiunilor subtablourilor unui tablou. De exemplu, nu mai este necesar ca toate liniile unei matrice sa aibă același număr de coloane. În schimb, pentru tablourile cu componente de tipuri primitive, se păstrează condiția omogenitații de tip a componentelor. De exemplu, în instrucțiunea Remarcăm că, întrucât fiecare nod al structurii arborescente, prin care se implementează in Java tabloul multidimensional, este un tablou unidimensional, acesta conține și câmpul length. În consecință, în cazul matricei b din exemplul de mai sus, expresia b.length are valoarea 3 si reprezintă numărul de linii al matricei, iar expresia b[i].length are ca valoare lungimea liniei de indice i a aceleeasi matrici. Să considerăm acum instrucțiunea: Prin această instrucțiune se creează în memorie un tablou cu 7 componente, care sunt referințe la obiecte din clasa String. Tabloul de referințe ocupă în memorie o zonă compactă, în schimb obiectele conținute pot fi amplasate oriunde în memorie. În fine, în cazul instrucțiunii |