CAPITOLUL 5.

STRUCTURI DE DATE

5.1. INTRODUCERE

Cea mai simpl[ ]i mai sugestiv[ defini\ie a informaticii este urm[toarea: informatica = studiul algoritmilor ]i datelor.

Unul dintre principalele obiective ale informaticii @l reprezint[ studiul algoritmilor. Acest studiu are @n vedere urm[toarele probleme:

ma]ini pentru execu\ia algoritmilor, care se ocup[ cu studiul metodelor de proiectare, organizare ]i construc\ie a unor ma]ini de calcul dedicate execu\iei eficace a algoritmilor;

limbaje pentru exprimarea algoritmilor, care se ocup[ cu studiul metodelor de exprimare precis[ a unui algoritm @ntr-un limbaj adecvat, de la nivelul abstract, foarte concis, p`n[ la programul detaliat @ntr-un limbaj de programare;

fundamentele algoritmilor., care se ocup[ cu g[sirea unor r[spunsuri la @ntreb[ri de genul:

problema P poate fi rezolvat[ algoritmic ?

care este num[rul minim de opera\ii necesare oric[rui algoritm de rezolvare a problemei P ?

analiza algoritmilor, care are ca obiectiv ob\inerea unui profil de performan\[ al unui algoritm dat, @n termenii timpului de calcul ]i volumului de memorie necesare pentru execu\ia sa;

validarea algoritmilor, care are ca obiectiv stabilirea corectitudinii unui anumit algoritm, adic[ dac[ el determin[ solu\ia corect[ a unei probleme dintr-o familie dat[ de probleme, pentru toate intr[rile admisibile posibile.

Dup[ cum se ]tie, toate calculatoarele moderne stocheaz[, reg[sesc ]i prelucreaz[ date. #n plus, orice algoritm se caracterizeaz[ printr-o mul\ime de date de intrare ]i o mul\ime de date de ie]ire. Studiul datelor pune @n discu\ie urm[toarele probleme:

ma]ini pentru stocarea datelor;

limbaje de descriere a manipul[rii datelor;

fundamente care descriu ce date putem ob\ine prelucr`nd date primare;

structuri de reprezentare a datelor.

Exist[ o leg[tur[ intim[ @ntre modul de structurare a datelor ]i sinteza algoritmilor. Aceast[ leg[tur[ este concentrat[ @n urm[toarea formul[ metaforic[ apar\in`nd lui Niklaus Wirth ''algoritm + structuri de date = programe''. Principalul obiectiv al structurilor de date const[ @n explorarea diverselor modalit[\i de structurare a datelor ]i, pentru fiecare @n parte, identificarea clasei de opera\ii care pot fi executate asupra sa ]i nu @n ultimul r`nd modul de reprezentare @n calculator al obiectelor apar\in`nd structurii respective astfel @nc`t aceste opera\ii s[ poat[ fi executate c`t mai eficient. Studiul structurilor de date are drept scop final @nsu]irea ]i st[p`nirea urm[toarelor dou[ tehnici fundamentale:

proiectarea unor reprezent[ri adecvate ale datelor

proiectarea ]i analiza algoritmilor care opereaz[ cu aceste reprezent[ri

5.2. TIPURI }I STRUCTURI DE DATE

No\iunile de tip de date ]i structur[ de date sunt folosite deseori drept sinonime @n referirile la datele prelucrate ]i modul lor de organizare @n cadrul unui algoritm au program. Cu toate acestea @ntre aceste dou[ no\iuni fundamentale exist[ diferen\e subtile, ele fiind relevate @n cele ce urmeaz[.

Tipuri de date. #n matematic[ se obi]nuie]te s[ se clasifice variabilele folosite @n func\ie de anumite caracteristici. Spre exemplu, se face o distinc\ie clar[ @ntre variabilele logice, reale ]i complexe sau @ntre variabile repezent`nd valori individule (scalare) ]i variabile reprezent`nd colec\ii de valori - mul\imi sau vectori sau @ntre func\ii, func\ionale ]i mul\imi de func\ii, etc. Aceast[ clasificare este cel pu\in la fel de important[ @n prelucrarea datelor. Astfel, @n programare este valabil urm[torul principiu: orice constant[, variabil[, expresie sau func\ie se caracterizeaz[ printr-un anumit tip de date.

Se nume]te tip o mul\ime de elemente numite valori sau obiecte, care pot fi clar distinse @ntre ele. #ntr-un limbaj de programare orice constant[ apar\ine unui anumit tip, orice variabil[ poate stoca valori de un anumit tip, orice expresie se evalueaz[ la o valoare de un anumit tip ]i orice func\ie @ntoarce o valoare de un anumit tip.

Orice limbaj de programare furnizeaz[ o mul\ime de tipuri predefinite. Acest lucru @nseamn[ c[ limbajul permite folosirea variabilelor de tipul respectiv ]i furnizeaz[ o mul\ime de opera\ii predefinite pentru manipularea acestor variabile @n cadrul unui program. Anumite tipuri de date predefinite corespund cu exactitate limbajului ma]in[ al calculatorului respectiv. Un exemplu @l reprezint[ tipurile @ntreg ]i real. Atragem aten\ia c[ este @ns[ posibil ca limbajul de programare s[ furnizeze tipul predefinit @ntreg reprezentabil pe dou[ cuvinte de memorie, @n timp ce @ntregii din limbajul ma]in[ sunt reprezenta\i pe un singur cuv`nt de memorie. Limbajele moderne de programare ]i tipuri predefinite compuse, cum sunt spre exemplu vectorii (Pascal, C, Fortran, Basic), structurile (Pascal, C, Cobol), ]irurile de caractere (Snobol, Turbo Pascal) sau chiar listele (Lisp).

O observa\ie important[ este c[ tipurile de date nu trebuie confundate cu echivalentele lor din matematic[. Spre exemplu, tipul @ntreg din programare nu trebuie confundat cu mul\imea Z a numerelor @ntregi din matematic[. Datorit[ reprezent[rii finite, tipul @ntreg din programare con\ine o mul\ime finit[ de elemente @n timp ce mul\imea Z este infinit[. Cu toate acestea, de cele mai multe ori se face abstrac\ie de aceast[ distinc\ie, ea fiind luat[ @n considerare c`nd este semnificativ[ (de exemplu c`nd apare posibilitatea unor dep[]iri, precizia este insuficient[ @n calcule, etc.).

#n concluzie, din punctul de vedere al modului de definire @n raport cu un anumit limbaj (de programare), tipurile de date se clasific[ @n tipuri predefinit ]i tipuri definite de utilizator. #n general, obiectele unui limbaj de programare apar\in uneia dintre urm[toarele categorii: constante, variabile, expresii ]i func\ii. Tipul unei constante rezult[ din forma sintactic[ (modul de scriere) a acesteia. #n limbajele moderne de programare (Pascal, C), tipul unei variabile rezult[ prin specificarea @n program a unui enun\ special numit declara\ie. #n mod normal, declara\ia unei variabile trebuie s[ precead[ @n program folosirii variabilei respective. Tipul unei expresii rezult[ din tipurile operanzilor ]i modul lor de compunere cu ajutorul operatorilor. Tipul unei func\ii rezult[ ca ]i @n cazul variabilelor din declara\ia func\iei. Declara\ia func\iei precizeaz[ tipurile argumentelor ]i tipul valorii de retur. @n unele limbaje, cum este limbajul C, se face distinc\ie @ntre declara\ia ]i defini\ia unei variabile sau func\ii.

Se nume]te declara\ie un enun\ care asociaz[ o variabil[ sau o func\ie cu tipul s[u. Se nume]te defini\ie un enun\ care asociaz[ o variabil[ sau func\ie cu tipul s[u ]i aloc[ spa\iu de memorie variabilei sau corpului func\iei respective.

Tipurile de date se pot clasifica dup[ diverse criterii. Am v[zut deja o astfel de clasificare @n tipuri predefinite ]i tipuri definite de utilizator. Dup[ cum un tip de date se define]te sau nu @n termenii altor tipuri de date avem tipuri primitive ]i tipuri derivate. Dac[ un obiect se poate descompune @n mai multe componente, atunci el se nume]te obiect compus, altfel se nume]te obiect simplu sau scalar. Un tip de date ale c[rui valori sunt compuse se nume]te tip compus, altfel se nume]te tip simplu sau scalar.

Un tip de date se nume]te dac[ pe mul\imea valorilor sale se poate defini o rela\ie de ordine. #n caz contrar el se nume]te neordonat. Spre exemplu, @n C, @ntregii, caracterele ]i realii reprezint[ tipuri ordonate. Un tip ordonat nu trebuie confundat cu un tip ordinal, pe care se poate defini o rela\ie de ordonare liniar[. O astfel de rela\ie face posibil[ definirea predecesorului ]i respectiv succesorului unui element. Un tip ordinal modeleaz[ o mul\ime finit[ sau num[rabil[. Spre exemplu, @n C, caracterele sunt un tip ordinal, @n timp ce realii nu.

Num[rul de valori distincte apar\in`nd unui tip T se nume]te cardinalitatea lui T ]i se noteaz[ cu |T|. Acest num[r ne furnizeaz[ o m[sur[ a volumului de memorie necesar pentru reprezentarea unei variabile cu tipul T.

Structuri de date. No\iunea de structur[ de date, spre deosebire de no\iunea de tip de date, desemneaz[, pe l`ng[ mul\imea de obiecte care alc[tuiesc un anumit tip, propriet[\ile obiectelor, rela\iile dintre obiecte ]i opera\iile asupra obiectelor. Defini\ia unei structuri de date se compune din trei p[r\i:

numele structurii

opera\iile asupra structurii

propriet[\ile structurii

Opera\iile asupra valorilor unei structuri de date se reprezint[ cu ajutorul func\iilor. De obicei, aplicarea unei func\ii se noteaz[ utiliz`nd nota\ia func\ional[. Aplicarea unei func\ii se poate simboliza ]i cu ajutorul nota\iei operatoriale, prin omiterea parantezelor ]i virgulelor. Nota\ia operatorial[ poate fi prefixat[ sau postfixat[. @n cadrul opera\iilor aplicabile obiectelor unei structuri de date se eviden\iaz[ opera\iile de baz[, care se clasific[ @n urm[toarele categorii:

constructori: specific[ modul de generare a noi obiecte apar\in`nd structurii respective. Atunci c`nd gestiunea obiectelor se face explicit de programator se pun @n eviden\[ prin constrast opera\iile destructor care au rolul de a elibera memoria alocat[ obiectelor, atunci c`nd acestea nu mai sunt necesare;

selectori: specific[ cum se acceseaz[ elementele care compun un obiect compus;

modificatori: specific[ cum se actualizeaz[ elementele care compun un obiect compus;

recunosc[tori: se recunosc pentru recunoa]terea diverselor propriet[ti ale obiectelor apar\in`nd structurii respective;

testori: se folosesc pentru compararea obiectelor apar\in`nd structurii respective.

Propriet[\ile unei structuri de date descriu cu exactitate modul @n care trebuie s[ func\ioneze opera\iile structurii, dar nu descriu modul @n care trebuie implementate opera\iile structurii ( exprima maniera @n care trebuie s[ func\ioneze opera\iile structurii, indiferent de modul lor de implementare). Cu alte cuvinte, propriet[\ile abstractizeaz[ opera\iile de modul lor de implementare. Din acest motiv, no\iunea de structur[ de date este cunoscut[ ]i sub numele de tip abstract de date, iar aceast[ manier[ de definire a structurilor de date se nume]te abstractizarea datelor.

Se nume]te structur[ de date un tuplu S = {D, d, O, P}, unde:

D este o mul\ime de tipuri de date implicate @n definirea lui S

d este tipul de date al obiectelor structurii S

este mul\imea opera\iilor definite pe structura S

P este mul\imea propriet[\ilor structurii S

Definirea unei structuri de date nu trebuie confundat[ cu modul ei de implementare. O implementare a unei structuri de date S este o transfomare care define]te modul de reprezentare al obiectelor apar\in`nd tipului de date al structurii @n func\ie de obiectele altei structuri de date T. #n plus, fiecare opera\ie a lui S trebuie definit[ @n termenii opera\iilor lui T.

5.3. TIPURI DE DATE FUNDAMENTALE

Obiecte ]i tipuri. Limbajele de programare pun la dispozi\ia programatorilor obiecte specifice cu care ace]tia urmeaz[ s[ ''simuleze'' reprezent[rile lor mentale asupra obiectelor din universul problemei. De asemenea, limbajele de programare posed[ ]i mijloace de asociere a valorilor din universul limbajului de programare @n scopul cre[rii de obiecte noi cu propriet[\i noi. Tipurile obiectelor din prima categorie se numesc predefinite sau fundamentale. Tipurile obiectelor din a doua categorie se numesc definite de programator. Tipurile predefinite se @mpart la r`ndul lor @n primitive sau elementare ]i structurate sau compuse. Obiectele elementare sunt elemente indivizibile ale universului limbajului de programare, iar structura lor intern[ nu este de regul[ accesibil[ programatorului. Spre deosebire de obiectele elementare, obiectele structurate sunt alc[tuite din mai multe componente, toate accesibile programatorului. Componentele pot fi elementare sau pot fi la r`ndul lor structurate. #ntre componentele unui obiect structurat exist[ de regul[ anumite rela\ii, specifice structurii respective, stabilite odat[ cu crearea ei. Explicitarea obiectelor ]i tipurilor contribuie @n mare m[sur[ la cre]terea lizibilit[\ii algoritmilor.

Tipuri de date primitive

Cele mai @nt`lnite tipuri primitive @n limbajele moderne de programare sunt:

tipurile numerice: sunt reprezent[ri ale unor mul\imi de numere cunoscute din matematic[, precum N, Z sau R. Vom avea @n consecin\[ date @ntregi f[r[ semn, @ntregi cu semn sau reali;

tipul caracter: este destinat reprezent[rii caracterelor alfanumerice;

tipul logic: este destinat reprezent[rii mul\imii valorilor logice {fals, adevarat};

tipul enumerare: este destinat reprezent[rii unei mul\imi finite de valori, fiecare valoare fiind desemnat[ printr-un nume simbolic;

tipul subdomeniu: este destinat reprezent[rii unui interval al unui tip ordonat liniar;

tipul referin\[: este destinat reprezent[rii adreselor altor obiecte. Tipul referin\[ se utilizeaz[ de obicei pentru implementarea unor obiecte abstracte complexe cum sunt listele ]i arborii.

Tipul @ntreg

Tipul @ntreg este destinat reprezent[rii unei submul\imi a numerelor @ntregi. Uneori se face distinc\ie @ntre @ntregii f[r[ semn ]i @ntregii cu semn. @ntregii f[r[ semn sunt numere @ntregi pozitive (naturale), @n timp ce @ntregii cu semn pot fi at`t pozitivi c`t ]i negativi. Tipul @ntreg f[r[ semn corespunde mul\imii N ]i tipul @ntreg cu semn corespunde mul\imii Z.

Tipul real

Tipul real modeleaz[ o submul\ime a numerelor reale. @n timp ce aritmetica @ntregilor produce @ntotdeauna rezultate exacte (@n limitele de reprezentare), aritmetica realilor admite existen\a unor erori de rotunjire. Aceste erori sunt cauzate de faptul c[ reprezentarea intern[ a realilor este finit[. Acesta este principalul motiv pentu care se face o distinc\ie explicit[ @ntre tipurile numerice @ntreg ]i real din majoritatea limbajelor de progrmare. Datorit[ faptului c[ mul\imea R a numerelor reale din matematic[ este nenum[rabil[, structura de date R este dificil de definit @n mod abstract.

Tipul logic

Tipul logic este destinat reprezent[rii mul\imii valorilor {adev[rat, fals}. Asupra obiectelor de acest tip se pot aplica opera\ii logice de tipul ]i, sau, nu, xor, etc., @n func\ie de facilit[\ile oferite de limbajul de programare utilizat. Unele limbaje de programare nu furnizeaz[ acest tip de date, utiliz`ndu-se @n locul s[u obiecte de tip numeric care sunt restric\ionate la dou[ valori: 0 ]i 1 (cum este cazul limbajului C).

Tipul caracter

De]i la @nceput calculatoarele numerice erau destinate @n special realiz[rii unor prelucr[ri numerice, ulterior s-a constatat c[ este posibil[ folosirea acestora ]i pentru implementarea unor prelucr[ri cu un pronun\at caracter nenumeric. Un astfel de exemplu @l reprezint[ procesarea textelor. @n acest scop este necesar[ reprezentarea @n cadrul programelor a caracterelor afi]abile, pentru aceasta folosindu-se tipul caracter. Tipul caracter modeleaz[ mul\imea finit[ a tuturor caracterelor afi]abile. Din nefericire, nu exist[ un set standard de caractere specific tuturor sistemelor de calcul. Din acest motiv, termenul ''standard'' trebuie interpretat @n acest context ca referindu-se la sistemul de calcul particular pe care este executat programul @n cauz[. Cel mai folosit set ''standard'' de caractere este cel definit de Organiza\ia Interna\ional[ pentru Standarde (ISO) ]i anume versiunea sa american[ -- codul ASCII, care const[ din 128 de caractere, dintre care primele 33 sunt caractere de control, iar celelalte 95 sunt caractere afi]abile. Caracterele sunt codificate intern prin valori @ntregi numite coduri. Deoarece codul ASCII are 128 de caractere, pentru codificarea caracterelor sale sunt suficien\i 7 bi\i. Cu tote acestea, se folose]te pentru codificare un octet, deoarece memoria intern[ a sistemelor de calcul este structurat[ de obicei sub forma unei secven\e de loca\ii cu dimensiunea de un octet. Principalul dezavantaj al codului ASCII este c[ permite un set de maxim 256 caractere (@n versiunea sa extins[ !). Exist[ ]i seturi de caractere care con\in mai mult de 256 de elemente ]i nu pot fi @n consecin\[ codificate pe un singur octet. Din acest motiv a fost introdus[ specifica\ia standard Unicode pentru reprezentarea seturilor de caractere care nu se pot reprezenta pe un singur octet (cum este cazul limbii chineze sau japoneze). Un caracter dintr-un astfel de set se nume]te caracter larg ]i pentru reprezentarea sa se folosesc doi octe\i. Orice caracter utilizat @n tehnica de calcul modern[ poate fi reprezentat cu ajutorul specifica\iei Unicode sub forma unui caracter larg. Pentru ca algoritmii care folosesc tipul caracter s[ depind[ c`t mai pu\in de setul de caractere utilizat, exist[ c`teva propriet[\i specifice tuturor seturilor de caractere:

tipul caracter con\ine cele 26 de litere latine ]i cele 10 cifre arabe, c`t ]i un num[r de caractere de punctua\ie, cum sunt ; : " . , ? / + - etc.

subseturile literelor ]i cifrelor sunt ordonate ]i coerente;

tipul caracter con\ine caracterul blanc (spa\iu) care poate fi folosit ca separator.

Tipul caracter este un tip ordinal, fiind definit[ @n consecin\[ func\ia standard ord care @ntoarce codul numeric al unui caracter. Inversa func\iei ord este @n cazul tipului caracter func\ia chr.

Tipul enumerare

Deseori este necesar[ definirea unui tip de date prin indicarea explicit[ a elementelor sale. @n aceste situa\ii se folose]te tipul enumerare. Tipul enumerare se utilizeaz[ pentru reprezentarea unei mul\imi finite de elemente. Fiecare element se desemneaz[ de obicei printr-un nume simbolic. C`teva exemple de tipuri enumerare sunt urm[toarele: {masculin,feminin}, {soldat, caporal, sergent, locotenent, capitan, maior, colonel, general}, {rosu, galben, verde}, {luni, marti, miercuri, joi, vineri, sambata, duminica}, {tren, autobuz, automobil, barca, avion}.

Elementele unui tip enumerare sunt considerate ordonate liniar, fiind posibil[ definirea predecesorului ]i respectiv urm[torului element. Din acest motiv un tip enumerare poate sta la baza definirii unui tip subdomeniu.

Tipul enumerare este definit ''explicit'', prin enumerarea tuturor elementelor sale. Cel pu\in @n principiu, putem de asemenea defini ''implicit'' un tip de date, prin enun\area unei propriet[\i a elementelor sale.

Tipul subdomeniu

O mul\ime se nume]te ordonat[ liniar dac[ putem enumera toate elementele sale. Spre exemplu, tipurile @ntreg, caracter, logic ]i enumerare modeleaz[ mul\imi ordonate liniar. Din acest motiv aceste tipuri se numesc tipuri ordinale. Un tip ordinal nu trebuie confunat cu un tip ordonat (pe care s-a definit o rela\ie de ordine). Spre exemplu, @ntregii ]i realii sunt tipuri ordonate, dar tipul real nu este ordinal. Din punct de vedere matematic, un tip ordinal modeleaz[ o mul\ime de elemente finit[ sau num[rabil[. Se ]tie c[ mul\imea numerelor reale nu este num[rabil[ ]i de aceea tipul real nu este un tip ordinal. Caracteristica esen\ial[ a unui tip ordinal este c[ putem vorbi despre succesorul ]i predecesorul unui element. De exemplu, succesorul lui 4 este 5, iar succesorul lui `c` este `d`. Deseori o variabil[ poate lua valori doar @ntr-un interval al unei mul\imi ordonate liniar. Fie T un tip ordonat liniar ]i fie min ]i max limita inferioar[, respectiv superioar[ a unui interval din T. Se nume]te tip subdomeniu acel tip de date care modeleaz[ valorile din intervalul [min...max]. C`teva exemple de tipuri subdomeniu sunt: [`a`..`z`], [luni..vineri], [locotenent..general], [1900..2100].Tipurile subdomeniu se utilizeaz[ de obicei pentru reprezentarea indicilor tablourilor.

Tipul referin\[

Numeroase prelucr[ri se refer[ la rela\iile dintre obiectele prelucrate ]i nu doar la valorile lor. #n astfel de cazuri poate fi necesar[ reprezentarea explicit[ a acestor rela\ii. Pentru aceasta, anumite obiecte trebuie s[ se poat[ referi la alte obiecte. Este posibil chiar ca un acela]i obiect s[ fie referit din dou[ sau mai multe locuri. #ntruc`t copierea valorii obiectului @n locul de unde a fost referit nu este o solu\ie acceptabil[ datorit[ consumului mare de memorie ]i dificult[\ilor de men\inere a consisten\ei, rezult[ c[ trebuie apelat la o alt[ tehnic[ ]i anume de a defini @n program obiecte care s[ poat[ referi alte obiecte. Pentru aceasta se folosesc tipul referin\[ ]i obiectele pointer.

Fiind dat un obiect o de tip T, el poate fi referit utiliz`nd un obiect de tipul referin\[ la T. Vom nota acest tip Ref( T). Putem de asemenea defini referin\e la obiecte pointer. Se obi]nuie]te ca ''leg[turile'' create @ntre obiecte prin intermediul pointerilor s[ se reprezinte grafic. Deseori trebuie s[ lucr[m cu referin\e c[tre obiecte al c[ror tip nu @l cunoa]tem. Pentru aceasta se folose]te tipul referin\[ generic[, desemnat prin cuv`ntul cheie ref. O referin\[ la un obiect se implementeaz[ ca adres[ a loca\iei de memorie, corespunz[toare obiectului respectiv. Opera\ia ref devine astfel opera\ia de @nc[rcare a adresei unui obiect. Opera\ia deref se implementeaz[ utiliz[nd tehnica adres[rii indirecte, prin care o anumit[ valoare este interpretat[ drept adresa unei loca\ii de memorie de unde se va extrage valoarea propriu-zis[. Limbajele de programare difer[ @n general prin libertatea pe care o ofer[ programatorului @n lucrul cu pointeri. Spre exemplu, limbajul Pascal nu permite dec`t o serie de opera\ii de baz[ asupra pointerilor, @n timp ce limbajul C este cu mult mai @ng[duitor, permi\`nd chiar efectuarea de opera\ii aritmetice cu pointeri.

Din cele discutate p`n[ acum, singura modalitate de a crea obiecte o constituie declararea acestora. O declara\ie are ca efect alocarea memoriei pentru obiectul respectiv la momentul compil[rii programului, obiectul fiind creat la @nc[rcarea programului, deci @naintea execu\iei sale efective. Aceast[ modalitate de alocare a memoriei se nume]te static[.

Principala caracteristic[ a acestui mod de alocare este faptul c[ obiectele sunt referite @n program prin identificatorul introdus la declararea lor. Acest lucru este posibil deoarece asocierea dintre identificator ]i loca\ia de memorie rezervat[ obiectului s-a f[cut @n faza de compilare a programului.

Obiectele pot fi @ns[ create ]i la momentul execu\iei. Aceast[ modalitate de alocare a memoriei se nume]te dinamic[. Un astfel de obiect nu va putea fi @ns[ accesibil prin program utiliz[nd un identificator, deoarce momentul execu\iei succede momentului compil[rii programului. Din acest motiv, un obiect creat dinamic se nume]te ]i obiect anonim. O modalitate elegant[ de a accesa obiectele create dinamic o constituie utilizarea tipului referin\[. Pentru aceasta se introduce operatorul nou care prime]te un tip T ]i creaz[ un obiect apar\in`nd lui T, @ntorc`nd o referin\[ la T. Fie ( mul\imea tuturor tipurilor ]i Ref mul\imea tuturor referin\elor. Dac[ operatorul nou @ntoarce referin\a vid[ vid, atunci @nseamn[ c[ obiectul nu a putut fi creat. Dac[ valoarea @ntoars[ este ( vid, atunci obiectul a fost creat ]i el poate fi accesat utiliz`nd numele deref(p). Opera\ia invers[ aloc[rii dinamice a unui obiect este eliberarea memoriei alocate. Aceast[ opera\ie se poate realiza automat, atunci c`nd obiectul respectiv nu mai este referit @n program sau manual de c[tre programator prin apelul operatorului standard elib.

Tipuri de date compuse

Din punct de vedere conceptual, orice obiect compus este un n-tuplu o =( o1,o2,...,on), de obiecte oi, 1 ( i ( n, n ( 2, fiecare obiect oi av`nd tipul Ti. Tipul lui o este tipul compus T = ( T1,...,Tn ). Fiecare dintre tipurile Ti poate fi la r`ndul s[u primitiv sau compus. Pentru orice tip compus, pe l`ng[ opera\iile fundamentale de atribuire ]i test de egalitate/inegalitate, se mai definesc de obicei urm[toarele dou[:

operatorul constructor, care construie]te un obiect compus o=(o1,o2,...,on), din obiectele componente oi, 1 ( i ( n

operatorul de selec\ie, care permite accesul at`t @n citire c`t ]i @n scriere la fiecare dintre componentele unui obiect compus.

Pentru referirea comod[ a tipurilor compuse se introduc identificatori.

Cele mai cunoscute tipuri compuse sunt tipul agregat (@nregistrare sau structur[) ]i tipul tablou (masiv sau vector).

Tipul agregat

Un obiect agregat, numit ]i @nregistrare sau structur[, este un obiect compus ale c[rui componente (numite ]i c`mpuri) sunt eterogene (au tipuri diferite) ]i au fiecare asociat c`te un nume simbolic, folosit @n cadrul opera\iei de selec\ie. Un tip agregat este definit pornind de la o mul\ime S de selectori ]i o mul\ime ( de tipuri asociate selectorilor printr-o func\ie bijectiv[ T : S((.

C`teva exemple sunt urm[toarele: complex = (real,imaginar), data = (zi, luna, an), persoana = (nume, prenume, data_nasterii, adresa).

Pentru a se indica accesul la componenta S a unui obiect agregat o, se folose]te @n majoritatea limbajelor (pseudocod, Pascal, C) nota\ia o.S. Cardinalitatea tipului compus agregat este egal[ cu produsul cardinalit[\ilor tipurilor sale componente.

La nivelul implement[rii, unui obiect agregat @i corespunde o zon[ compact[ de memorie a c[rei m[rime rezult[ din m[rimile componentelor obiectului repectiv. Dac[ se notez[ cu M(S) m[rimea componentei S a unui obiect agregat o atunci m[rimea zonei de memorie alocat[ lui o, notat[ cu M, se determin[ cu formula: M = (M(S). Orice referin\[ la un c`mp al unui obiect agregat se transform[ @n distan\a zonei alocate acestuia fa\[ de @nceputul zonei alocat[ obiectului. Distan\ele se calculeaz[ de regul[ la momentul compil[rii programului. Accesarea unui c`mp al un agregat se implementeaz[ de regul[ utiliz`nd tehnica adres[rii relative.

Tipul tablou

Deseori este necesar[ folosirea unui tip compus ale c[rui componente sunt toate de acela]i tip. Un astfel de tip se nume]te omogen. @n plus, accesul la componente are loc prin selectori care sunt elemente ale unei mul\imi finite ]i ordonat[ liniar. #n aceste situa\ii se va folosi tipul tablou.

Tipul tablou se define]te pornind de la un tip de baz[ T care modeleaz[ tipul componentelor ]i de la un tip subdomeniu I, care modeleaz[ mul\imea selectorilor, numi\i @n acest caz indec]i. Pentru a se indica accesul la componenta i a unui obiect tablou T se folose]te @n majoritatea limbajelor (pseudocod, Pascal, C) nota\ia T[i].

La nivelul implement[rii, unui tablou @i corespunde o zon[ contigu[ de memorie, carcterizat[ prin adres[ de @nceput ]i m[rime. S[ presupunem c[ min ]i respectiv max sunt limitele inferioar[ ]i respectiv superioar[ ale indicilor tabloului T ]i s[ presupunem de aasemenea c[ pentru reprezentarea unui element al tabloului, apar\in`nd tipului de baz[ T, sunt necesare n cuvinte de memorie. Rezult[ c[ zona de memorie alocat[ tabloului va avea (max-min+1)n celule, iar zona @n care este memorat elementul T[i] va @ncepe la adresa A = B+(i-min)n, unde B este adresa de @nceput a zonei alocate tabloului. Accesarea unui element al un tablou se implementeaz[ de regul[ utiliz`nd tehnica adres[rii indexate.

O opera\ie frecvent @nt`lnit[ @n cazul tablourilor este determinarea primului indice i al unei componente a tabloului a c[rei valoare este egal[ cu o valoare dat[ x. Aceast[ opera\ie se nume]te c[utare. O modalitate de implementare a acestei opera\ii se bazeaz[ pe scanarea secven\ial[ (element cu element) a tabloului p`n[ la @nt`lnirea componentei c[utate sau p`n[ la epuizarea tuturor elementelor tabloului. Aceast[ metod[ de c[utare se nume]te c[utare secven\ial[. Opera\ia de c[utare poate fi realizat[ mai rapid dac[ elementele vectorului sunt ordonate cresc[tor. @n acest caz, la fiecare pas de c[utare intervalul de c[utare va fi restr`ns la jum[tate. Ini\ial, intervalul de c[utare este 1..n. Aceast[ metod[ de c[utare se nume]te c[utare binar[ (prin @njum[t[\irea intervalului).

Tipul mul\ime

Numero]i algoritmi prelucreaz[ colec\ii de obiecte @n care ordinea elementelor nu conteaz[. @n astfel de situa\ii se recomand[ folosirea tipului mul\ime. Tipul mul\ime se define]te pornind de la un tip de baz[ T ]i reprezint[ toate submul\imile lui T. Un astfel de tip se mai nume]te ]i mul\imea putere a lui T ]i se noteaz[ cu 2T sau P(T).

C`teva exemple sunt urm[toarele: litera = [A..Z], vocala = [A, E, I, O, U], etc.

Pentru reprezentarea intern[ a obiectelor de tip mul\ime se folose]te de obicei func\ia caracteristic[. Fie U o mul\ime numit[ mul\ime universal[. Orice submul\ime X ( U se reprezint[ cu ajutorul func\iei caracteristice (X:U ({0,1}, definit[ astfel:

(X (u) =1, daca u ( x

(X (u) =0, daca u ( x

Valorile func\iei caracteristice se reprezint[ intern utiliz`nd un singur bit. Dac[ avem de reprezentat submul\imile unei mul\imi U cu n elemente, atunci pentru reprezentare vor fi necesari n bi\i. S[ presupunem c[ lungimea unui cuv`nt calculator este c bi\i. Atunci pentru reprezentarea unei submul\imi X ( U vor fi necesare [n/c] cuvinte ([] este partea @ntreag[ majorat[). Testarea apartenen\ei unui element la o mul\ime se face efectu`nd un ]i la nivel de bit cu o masc[ corespunz[toare elementului ]i verific`nd apoi dac[ rezultatul este nenul. Opera\ia de incluziune se implementeaz[ printr-o opera\ie ]i la nivel de bit cu o masc[ corespunz[toare submul\imii ]i verific`nd apoi dac[ rezultatul este identic cu masca. Opera\ia de complementare se implementeaz[ utiliz`nd o instruc\iune ma]in[ de complementare bit cu bit a unui cuv`nt.

Tipuri cu variante

#n practic[ este uneori convenabil s[ se considere c[ mai multe tipuri diferite sunt variante ale aceluia]i tip. #n acest caz se va defini un tip cu variante a c[rui mul\ime de valori este egal[ cu reuniunea disjunct[ a tipurilor ini\iale. Un tip cu variante se define]te pornind de la o mul\ime de tipuri {T1,...,Tn}. Un exemplu @n care este necesar s[ definim un tip cu variante este reprezentarea coordonatelor unui punct @n plan @n cazul @n care ele pot fi coordonate carteziene sau polare. Unui obiect agregat cu variante i se va aloca un spa\iu de memorie egal cu valoarea maxim[ necesar[ tipurilor sale componente.

5.4 LISTE

5.4.1. LISTE LINIARE

Una dintre cele mai simple ]i mai des folosite structuri de date este lista liniar[, cunoscut[ ]i sub numele de list[ ordonat[ sau secven\[. O list[ liniar[ const[ dintr-o @n]iruire de elemente X1, X2, ..., Xn numite noduri, apar\in`nd de obicei unui acela]i tip de baz[ T. Propriet[\ile structurale esen\iale ale acestui ]ir se rezum[ la pozi\ia relativ[ a elementelor, a]a cum apar ele @n cadrul ]irului. Singurele lucruri care ne intereseaz[ la o astfel de structur[ sunt:

dac[ n>0 atunci X1 este primul nod ]i Xn este ultimul nod

dac[ 1