Proiectarea și Utilizarea Structurilor de Date și Algorimilor

Cursul îşi propune să asigure studenţilor cunoştinţe aprofun¬date privind proiectarea şi utilizarea structurilor de date şi algorimilor, în contextul anumitor tehnici de programare.

Pe importanţa domeniului nu trebuie insistat prea mult, dat fiind că presiunea exercitată asupra industriei software-ului este mai mare ca oricând şi având în vedere creşterea dramatică a numărului de utilizatori, noile tipuri de aplicaţii şi noile modele de calcul, precum şi faptul că performanţa este aspectul critic al succesului.

Sunt prezentate tipuri de date, inistându-se pe cele definite de utilizator. De asemeni, sunt abordate structurile de date (liste, arbori, grafuri) prin prisma tehnicilor de rezultate din necesitatea combinării procesărilor on-line, a încărcării şi a creşterii sprijinului decizional.

Cursul tratează aspectele legate, pe de o parte, de cunoaşterea modalităţilor de rezolvare a problemelor cu care utilizatorul are de-a face, eventual a unor metode generale de rezolvare, aplicabile unor categorii largi de probleme, iar pe de altă parte cunoaşterea unei metode sistematice de trecere de la problemă la program, prin intermediul algoritmilor specifici.

1. TIPURI DE DATE

În memoria calculatorului orice dată apare ca o succesiune de biţi. Modul în care pentru astfel de succesiuni se asociază o valoare depinde de interpretarea ce i se dă. La nivelul limbajului de programare o astfel de interpretare este reprezentată de tipul datelor. Un tip de date este o mulţime de valori şi un set de operaţii definit asupra acestora. Majoritatea limbajelor de programare oferă cel puţin echivalentul unui tip întreg. Pentru acest tip valorile posibile sunt cuprinse între două limite. Valorile concrete pentru aceste limite pot să varieze de la o implementare la alta. Setul de operaţii considerat pentru tipul întreg conţine de obicei operaţii aritmetice şi relaţionale.

La nivelul limbajului de programare datele apar ca variabile sau constante. În cazul variabilelor tipul este fixat prin declararea acestora:

Int x; /* în C*/

Pentru constante tipul rezultă din forma de scriere. De exemplu 125 este o constantă de tip întreg, iar 3.14 e-2 o constantă de tip real.

Orice limbaj de programare pune la dispoziţia programatorului câteva tipuri de date predefinite ( standard). De exemplu în C int, char, float, etc. Acestea sunt tipuri simple de date, care se referă la valori elementare. Totodată, limbajele de programare includ mecanismele necesare construiri unor tipuri noi, prin restrângeri sau combinări ale tipurilor deja definite. Aceste mecanisme se numesc

constructori de tipuri şi joacă un rol esenţial în programare. Exemple de constructori sunt enumerările şi subdomeniile, care definesc tipuri simple. Alţi constructori, foarte des folosiţi, sunt tablourile şi înregistrările. Ei produc tipuri structurate, prin combinarea unor tipuri cunoscute.

Noile tipuri construite pot avea nume sau pot fi anonime. În general limbajele de programare au mecanisme prin care asociază nume diferitelor tipuri definite de utilizatori ( type, typedef).

De asemeni, orice limbaj include:

• Mecanismele de definire a tipurilor, deci de precizare a structurii şi a tipurilor componente (aceste mecanisme sunt constructorii, menţionaţi anterior);

• Mecanismele de selecţie a valorii unei componente;

• Definiţiile operaţiilor permise asupra valorilor (compuse) ale tipului definit.

În mod necesar, operaţiile permise asupra unei componente sunt cele specifice tipului componentei.

Un limbaj de programare îl oferă programatorului pentru definirea de tipuri noi. Sunt însă destule situaţii în care structurile pe care un limbaj le permite nu ajung. O problemă de clasificare se rezolvă mai uşor cu o structură arborescentă, iar o problemă de optimizare a traseelor de transport în comun se rezolvă mai natural pe o structură de graf.

Limbajele de programare orientate pe obiecte rezolvă elegant aceste probleme, permiţând definirea de tipuri care “imită” fidel caracteristicile şi comportarea obiectelor din realitatea problemelor de rezolvat. Un pas important în aceeaşi direcţie poate fi făcut si cu mijloacele mai modeste ale unui limbaj tradiţional. În acest sens, sunt importante aspecte:

• Cum putem reprezenta mai simplu legăturile dintre componentele unei structuri;

• Cum putem asocia structurilor operaţii de acces şi de modificare a componentelor;

• Cum putem conferi acestor operaţii o generalitate cât mai mare;

• Cum putem izola structura, cum o putem “încapsula”, asigurând astfel atât protejarea sa faţă de restul programului, cât şi ascunderea amănuntelor de implementare a structurii.

1.1. Tipuri de date definite de utilizator

Informaţia prelucrată în program este organizată în general în ansambluri de date de tipuri diferite, astfel încât tipurile predefinite nu sunt suficiente pentru o reprezentare convenabilă. (Diversitatea aplicaţiilor programării, a fenomenelor şi mărimilor ce pot fi modelate cu ajutorul sistemelor de calcul face practic imposibilă stabilirea "apriori" a tuturor tipurilor de date care ar fi necesare unui proiect).

Ca urmare, strategia adoptată de realizatorii unor limbaje de programare este următoarea:

• se pune la dispoziţia utilizatorului un nucleu de tipuri de date primitive suficient de mic pentru a nu încărca limbajul, dar având un grad mare de generalitate (date întregi, reale, adrese, caractere, etc.)

• se oferă posibilitatea compunerii datelor, astfel încât pornind de la primitivele limbajului, să se construiască structuri de date oricât de complicate.

Limbajul C oferă următoarele posibilităţi:

- declaraţia typedef - asociază un nume unui tip.

- structura - este o colecţie de obiecte de orice tip referite cu un nume comun.

- câmpul de biţi - este un membru al unei structuri care are alocat un grup de biţi, în interiorul unui cuvânt de memorie.

- uniunea - permite utilizarea în comun a unei zone de memorie de către mai multe obiecte de tipuri diferite.

- enumerarea - este o listă de identificare cu valori întregi, constante.

1.1.1. Structuri

O declaraţie de structură precizează identificatorii şi tipurile elementelor componente şi constituie o definire a unui tip de date nou. Acestui tip i se poate asocia un nume.