Se poate pune in evidenta caracterul dual al datelor:
a. Datele sunt piese de informatie care apartin domeniului problemei: numere, siruri de caractere, imagini, secvente sonore etc. Sub acest aspect, fiecare din ele are o anumita semnificatie, care depinde de rolul indeplinit in problema respectiva. De exemplu, in probleme diferite, acelasi numar intreg poate fi varsta unei persoane, numarul de dosare dintr-un birou, numarul de exemplare ale unei carti intr-o librarie etc. b. Datele sunt structuri simbolice prin care se
reprezinta piesele de informatie in calculator sau in documentele
folosite de om. Sub acest aspect, se ignora semnificatia datelor, punandu-se
accentul pe forma de reprezentare a acestora si pe operatiile
la care pot fi supuse. Din acest punct de vedere, datele se grupeaza in
tipuri
de date, astfel ca toate datele de acelasi tip respecta aceleasi conventii
de reprezentare si suporta aceleasi operatii.
|
Datele pot fi primitive sau structurate.
In limbajul Java, tipurile de date primitive sunt:
Tipul char din limbajul Java are o situatie deosebita:
|
Tipuri similare exista si in celelalte limbaje de programare, dar pot diferi atat denumirile tipurilor, cat si formele de reprezentare externa si interna a datelor respective.
Structura de date este un mod de organizare si reprezentare
a datelor, care contine atat datele propriu-zise, cat si legaturile dintre
ele.
La nivel conceptual, structura de date abstracta este
o schema care contine componente si relatii intre aceste
componente. Componentele pot fi date primitive sau structuri
de date. Pentru fiecare structura se specifica si un set de operatii
care pot fi efectuate asupra intregii structuri sau a componentelor ei.
La nivelul implementarii, limbajele de programare furnizeaza mijloace prin care se pot construi anumite structuri de date considerate de baza in limbajul respectiv si - eventual - de construire a structurilor din ce in ce mai complexe, pornind de la datele primitive si structurile de baza. Operatiile asupra structurilor se implementeaza sub forma de functii sau proceduri. In programarea procedurala traditionala, structurile de date si functiile sau procedurile prin care se realizeaza operatiile asupra acestora se implementeaza separat, legatura dintre ele realizandu-se doar la nivel conceptual si nu prin mijloace specifice limbajului folosit. In programarea orientata pe obiecte, structurile de date se realizeaza sub forma de clase, care cuprind atat datele si legaturile dintre ele, cat si metodele prin care se realizeaza operatiile asupra structurii respective. |
Principalele structuri de date pentru care limbajele de programare procedurala ofera mijloace specifice de declarare sunt tabloul si inregistrarea.
Structura de tablou are la baza conceptul de matrice din matematica.
Astfel, de exemplu, tabloul
a = [a0 a1 a2 a3] are patru componente asezate pe o singura directie in spatiu si au un singur indice, cu valori de la zero la 3. In matematica, un astfel de tablou este o matrice cu o singura linie (numita si vector-linie) daca elementele sunt asezate orizontal, ca in exemplul de mai sus, sau este o matrice cu o singura coloana (un vector-coloana) daca elementele sunt asezate pe o directie verticala. In prelucrarea pe calculator nu se ia in consideratie orientarea orizontala sau verticala, ci numai faptul ca elementele sunt dispuse pe o singura directie (liniar). In cazul unei matrice cu mai multe linii si coloane, componentele sunt
plasate pe doua directii (intr-un plan) si au fiecare doi indici, ca in
exemplul urmator:
Remarcam ca matricea (tabloul bidimensional) poate fi considerat drept un tablou unidimensional, ale carui componente sunt ele insele tablouri unidimensionale. De exemplu este un vector-linie, ale carui componente sunt vectori-coloana. Pornind de la aceasta observatie, putem extinde conceptul de tablou la mai mult de doua dimensiuni. Putem, astfel, sa consideram ca un tablou tridimensional (o matrice spatiala) este un tablou unidimensional, ale carui componente sunt tablouri bidimensionale. Un astfel de tablou poate fi imaginat ca avand mai multe "pagini", unde fiecare "pagina" este o matrice bidimensionala. In acest caz, componentele au trei indici, care indica in mod corespunzator linia, coloana si pagina in care este situata componenta respectiva. Extinzand la cazul multidimensional, putem considera ca un tablou cu n dimensiuni este un tablou unidimensional, ale carui componente sunt tablouri cu n-1 dimensiuni, fiecare componenta avand n indici. |
Structura de tablou a fost introdusa in limbajul FORTRAN (1956), fiind
prezenta in toate limbajele de programare pentru calcule stiintifice si
ingineresti si in majoritatea celorlalte limbaje de programare de nivel
superior. Ca exemple putem da limbajele Fortran, Basic, Pascal, C, C++,
Java. Exista, totusi, deosebiri intre aceste limbaje atat din punct de
vedere al formei sintactice a declaratiei de tablou, cat si in ce priveste
modul de implementare a tablourilor.
In majoritatea limbajelor se considera ca intr-o matrice (tablou bidimensional) toate liniile au aceeasi lungime si - in mod corespunzator - intr-un tablou n-dimensional, toate componentele sale cu n-1 dimensiuni sunt omogene nu numai sub aspectul tipului, ci si al dimensiunilor. Se considera, de asemenea, ca tabloul ocupa in memorie o zona compacta (de unde si denumirea de masiv). Avand insa in vedere ca memoria calculatorului este o structura liniara (toate locatiile din memorie sunt - conceptual vorbind - dispuse liniar fiind indicate prin adresa lor), inseamna ca orice tablou multidimensional trebuie desfasurat in memorie pe o singura directie. Desfasurarea pe o singura directie a elementelor unui tablou se poate face in moduri diferite, depinzand de limbajul folosit. Astfel, in limbajul FORTRAN, se considera ca elementele tabloului sunt plasate in memorie coloana dupa coloana, in timp ce in limbajele Pascal si C se considera ca desfasurarea se face linie dupa linie. In consecinta, in Pascal si 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. Datorita acestui fapt, se poate considera ca, la nivel de implementare, orice tablou multidimensional este echivalent cu unul unidimensional. Se pot stabili formule de calcul, prin care se determina valoarea indicelui componentei in desfasurarea unididimensionala a tabloului, daca se cunosc dimensiunile tabloului si valorile indicilor aceleeasi componente in amplasarea spatiala. De exemplu, in cazul unei matrice cu N linii si M coloane desfasurate pe linii (ca in Pascal sau C), intre indicele k al desfasurarii liniare si indicii i,j ai componentei respective a matricei exista urmatoarea relatie: Domeniile de valori ale indicilor depind, de asemenea, de limbajul folosit. In Fortran, indicii sunt numere naturale, primul indice fiind 1. In C, C++ si Java, indicii sunt tot numere intregi pozitive, dar cel mai mic indice este zero. In Pascal, indicii pot fi numere intregi, caractere sau tipuri enumerate, iar marginile inferioara si superioara ale intervalului de valori pentru fiecare indice se declara prin program. Despre particularitatile tablourilor in Java vom discuta separat. |
Referirea la o componenta a tabloului se face prin mumele tabloului
insotit de indicele (indicii) componentei respective. In Pascal, C, C++
si Java indicii se scriu intre paranteze drepte. De exemplu, b[2][3]
este componenta din linia 2 si coloana 3 a matricei b. Remarcam
deci ca accesul la orice componenta a tabloului se face direct, fara a
fi necesara parcurgerea celorlalte elemente.
In numeroase aplicatii ale calculatoarelor, este necesar sa se prelucreze
date grupate sub forma de inregistrari, situate fizic fie in fisiere,
fie in memoria interna. Sa consideram, de exemplu, evidenta materialelor
dintr-o magazie. Fiecare material se caracterizeaza prin mai multe atribute,
cum sunt: codul materialului, denumirea materialului, cantitatea. Informatia
despre un material ar putea fi, deci, pastrata pe un formular de hartie
avand, ca exemplu, urmatorul continut:
MATERIAL
Prima linie contine titlul formularului, iar urmatoarele linii contin
atributele acestuia. Acest formular contine trei date: numarul intreg 13027522,
sirul de caractere "Panza alba de bumbac" si numarul real 127.53.
Pentru prelucrarea pe calculator, aceste date sunt grupate intr-o inregistrare
de
forma
Remarcam deci ca aceasta structura, care se introduce in memoria calculatorului,
contine numai datele, nu si alte informatii, cum ar fi denumirile
atributelor si tipurile de date din fiecare camp. Descrierea acestei structuri
se face in program, folosind o instructiune numita declaratie
de structura. Forma declaratiei depinde de sintaxa limbajului de programare
utilizat. De exemplu, in limbajul Pascal declaratia poate avea forma
In limbajul C, aceleasi declaratii se fac sub forma
S-a schimbat sintaxa declaratiilor, dar semnificatia este aceeasi ca in Pascal. In ambele limbaje, notatia a.cod inseamna valoarea campului cod al inregistrarii (structurii) a, deci un camp al unei inregistrari este specificat in program sub forma nume_variabila.nume_camp. Structura de inregistrare a fost introdusa prima data in limbajul COBOL (creat in 1959) si este utilizata in toate limbajele care sunt orientate pe folosirea fisierelor sau a bazelor de date, fiind prezenta si in unele limbaje de uz general, cum sunt Pascal si C. Remarcam ca nici in Pascal, nici in C nu este predefinit un tip de date numit Material, dar limbajul pune la dispozitia programatorului modalitatea prin care el poate sa defineasca un astfel de tip. |
Inregistrarea (engl: record) este o structura de date neomogena cu urmatoarele caracteristici:
Campurile de date dintr-o inregistare pot contine nu numai date primitive, ci si structuri de date. In particular, orice camp al unei inregistrari poate fi el insusi o inregistrare.
Se stie ca in conceptul de tip de tipul de date sunt cuprinse
atat multimea de valori, cat si multimea de operatii aplicabile
valorilor respective. Din acest punct de vedere, inregistrarea nu este
un tip de date complet definit, deoarece la declararea inregistrarii se
descrie numai structura de date, definindu-se astfel numai multimea de
valori pe care aceasta le poate avea. Operatiile se fac numai asupra datelor
primitive continute in campuri, respectand conventiile pentru tipul de
care aceste campuri apartin.
Intrucat clasa contine atat date, cat si metode, ea se incadreaza complet in conceptul de tip de date enuntat mai sus. |
In timpul executarii programului, datele primitive se gasesc in memoria calculatorului sub forma unor valori plasate in anumite zone de memorie. In mod corespunzator, structurile de tablou sau de inregistrare sunt plasate in anumite zone de memorie. Daca, la nivel conceptual, structurile de date sunt plane sau spatiale, valorile componentelor acestora sunt asezate in zona de memorie alocata structurii respectand o anumita conventie de desfasurare liniara, cum s-a aratat mai sus in cazul tablourilor. |
Variabila este numele dat in program unei zone de memorie in
care se gaseste o valoare. Dupa tipul acesteia, valoarea poate fi,
in principiu, o data primitiva sau o structura de date. Operatiile prevazute
i program nu se fac asupra variabilelor, ci asupra valorilor acestora.
De exemplu, expresia c=a*b este interpretata astfel: se inmulteste valoarea variabilei a cu valoarea variabilei b, iar valoarea rezultata se atribuie variabilei c. Cu alte cuvinte, se inmulteste valoarea situata in zona de memorie alocata variabilei a cu valoarea situata in zona de memorie alocata variabilei b, iar valoarea rezultata se pune in zona de memorie alocata variabilei c. |
Pointerul este o variabila speciala, a carei valoare este o adresa
de memorie. Pointerii se folosesc in numeroase limbaje de nivel superior,
printre care Pascal, C si C++, dar nu exista in limbajul Java. Asupra pointerilor
se pot face operatii de atribuire, adunare cu o constanta si afisare.
De exemplu, in limbajul C sau C++ declaratia
double a, b, *p1, *p2; are semnificatia ca a si b sunt variabile de tip double, in timp ce p1 si p2 sunt pointeri la variabile de tip double. Aceasta inseamna ca in zonele de memorie care apartin variabilelor a si b se gasesc chiar valorile acestor variabile (sub forma de date de tip double, pe cate 8 octeti), in timp ce in zonele de memorie alocate pentru variabilele p1 si p2 se gasesc adresele la care sunt situate in memorie niste date de tip double (adresele fiind numere intregi, fara semn, pe doi octeti fiecare). Expresia p1=&a are semnificatia ca se atribuie ca valoare variabilei p1adresa la care se gaseste in memorie valoarea variabilei a. Pointerului i se poate atribui, insa, ca valoare orice adresa din memorie, chiar daca aceasta nu este adresa alocata unei variabile din program, fiind permise, de exemplu, atribuiri de forma p1=1735, sau p2=#7FFF. De asemenea, valoarea pointerului poate fi afisata pe ecran. Totodata, in expresii se pot folosi si 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, obtinandu-se ca rezultat o valoare numerica de tip double. In schimb, expresia p1+3 are semnificatia ca la adresa p1 se adauga o cantitate egala cu de trei ori lungimea unei date de tip double (conform tipului pointerului) si se obtine o noua adresa a unei date de tip double. In limbajul Java nu se folosesc pointeri, dar am avut nevoie de aceste exemple pentru a explica deosebirea dintre pointeri si referinte. |
Referinta este, in programare, o indicatie privind locul in care poate fi gasita o data sau o structura de date fiind, din acest punct de vedere, o abstractizare a conceptului de adresa. Deosebirea dintre referinta si adresa este ca referinta nu este considerata a fi un numar, si deci asupra ei nu pot fi efectuate operatii aritmetice si nici nu poate fi afisata sau supusa altor operatii de intrare/iesire.
Variabila referinta este o variabila, a carei valoare este o referinta. In unele limbaje de programare (de exemplu in Pascal) termenul de "variabila referinta" (sau simplu "referinta") este folosit ca sinonim al celui de pointer.
In limbajul C++ se face distinctie intre pointeri si referinte: variabila
referinta este considerata doar drept un sinonim (un alt nume) al variabilei
obisnuite.
De exemplu, in C++ instructiunea
|
In limbajul Java, se considera ca variabilele simple au ca valori
date primitive, iar variabilele referinta au ca valori referinte
la obiecte (la instante ale claselor).
In consecinta, variabilele referinta se comporta ca niste pointeri,
in sensul ca:
|
ClasaIn limbajul Java clasa este ea insasi un obiect, mai exact o instanta a clasei java.lang.Class, care este prezenta in memoria masinii virtuale Java in timpul executarii programului si contine:
Instantele oricarei clase sunt, de asemenea, obiecte si contin:
TabloulIn limbajul Java, reprezentarea tabloului ca un masiv de date, ale carui componente ocupa in memorie o zona compacta ramane valabila numai pentru tablourile unidimensionale cu componente de tipuri primitive. Totusi, chiar si aceste tablouri, se deosebesc de cele din alte limbaje: in Java, tabloul este un obiect, care - in afara de componentele propriu-zise - contine si un camp de tip int numit length, care are ca valoare numarul de componente. In consecinta, daca tab este un tablou, atunci tab.length este numarul de componente ale acestui tablou.Tablourile multidimensionale sunt implementate prin structuri arborescente, in care frunzele sunt componentele propriu-zise, iar fiecare nod intermediar de nivel k este un tablou unidimensional ale carui componente sunt referinte la nodurile de nivel k+1. In aceste conditii dispare si cerinta de omogenitate a dimensiunilor subtablourilor unui tablou. De exemplu, nu mai este necesar ca toate liniile unei matrice sa aiba acelasi numar de coloane. In schimb, pentru tablourile cu componente de tipuri primitive, se pastreaza conditia omogenitatii de tip a componentelor. De exemplu, in instructiunea Remarcam ca, intrucat fiecare nod al structurii arborescente, prin care se implementeaza in Java tabloul multidimensional, este un tablou unidimensional, acesta contine si campul length. In consecinta, in cazul matricei b din exemplul de mai sus, expresia b.length are valoarea 3 si reprezinta numarul de linii al matricei, iar expresia b[i].length are ca valoare lungimea liniei de indice i a aceleeasi matrici. Sa consideram acum instructiunea: |