Ingineria Sistemelor de Programe - Capitolul 2

Capitolul II

Structuri complexe de date in ingineria programarii

1. Generalitati

Variabilele utilizate in Limbajul C/C++, din punct de vedere al alocarii spatiului de memorie necesar sunt de doua feluri: variabile alocate in mod static si variabile alocate in mod dinamic. Variabilele alocate in mod static (tipurile intregi, reale, caracter, tipurile tablou de intregi, reale si caracter etc.) sunt alocate in zona de memorie a proramului, chiar in faza de compilare.

Structura, tipul si locul ocupat in memorie nu se pot modifica pe parcursul executarii programului. De asemenea, la declararea lor, toate caracteristicile trebuie sa fie bine precizate. Variabilele dinamice ofera posibilitatea alocarii memoriei aferente variabilelor referite de variabilele dinamice pe parcursul executiei programului (fiind cunoscuta sub numele de alocare dinamica), in functie de necesitati, permitand totodata eliberarea memoriei ocupate de acestea dupa ce nu mai sunt necesare in continuare.

Variabilele dinamice trebuie sa aiba tipul bine definit, si sunt identificate prin variabile de tip pointeri spre anumite tipuri de variabile. Alocarea dinamica este mijlocul prin care un program poate obtine memorie pe parcursul executiei sale intr-o zona de memorie speciala, diferita de zona de memoria a programului, numita zona heap. Se cunoaste ca declarararea unui tip de data nu necesita alocarea de memorie. Alocarea memoriei aferente se face in timpul compilarii programului in momentul intalnirii declaratiei unei variabile sau constante de un anumit timp, lungimea zonei alocate fiind calculata corespunzator tipului asociat variabilei. Un asemenea mod de alocare este specific variabilelor alocate in mod static.

In timpul compilarii, la intalnirea unei variabile alocate dinamic, se va aloca o zona de memorie de patru bytes care, dupa alocarea dinamica pe parcursul executarii programului, va contine adresa de memorie din zona heap a primei locatii de memorie libera unde se va aloca spatiul necesar pentru variabila referita sau adresata de variabila dinamica.

Dupa cum s-a precizat, alocarea dinamica a spatiului de memorie din zona heap pentru variabila referita de variabila dinamica (pointer catre variabila referita) se face cu functia malloc() dupa cum urmeaza:

tip_variabila_referita *ptr_variabila_reterita;

ptr_variabila_reterita = malloc(size_t numar_de_octeti);

unde:

- ptr_variabila_reterita – este un pointer (variabila dinamica) catre o variabila de un tip precizat de tip_variabila_referita.

- tip_variabila_referita – este tipul variabilei referita de variabila de tip pointer si poate fi un tip standard sau definit de utilizator.

- numar_de_octeti – este numarul de octeti precizat sau calculat ai zonei de memorie din zona heap, alocata dinamic, unde se va memora variabila referita de variabila dinamica (ptr_variabila_reterita).

Eliberarea spatiului de memorie ocupat de variabila referita prin variabila dinamica (ptr_variabila_reterita) se face cu functia free() cu sintaxa:

free(ptr_variabila_reterita).

2. Declararea si utilizarea listelor in ingineria programarii in C/C++.

In practica programarii calculatoarelor, de multe ori, apare necesitatea organizarii informatiilor de prelucrat sub forma unor liste. Pot fi date nenumarate exemple:lista produselor dintr-un magazin, lista persoanelor dintr-o asociatie de locatari, lista studentilor admisi la facultate etc. O lista, ca si un fisier, contine o multime de componente de acelasi tip. In general o componenta a unei liste contine, la randul sau, alte informatii (date) de acelasi tip sau de tipuri diferite. De exemplu, lista studentilor admisi la facultate contine urmatoarele informatii (date):cod student, nume, prenume, nota 1, nota 2, nota 3 si media. Din acest exemplu se constata ca, in majoritatea cazurilor, un element al listei trebuie reprezentat sub forma unui tip structurat de date (struct, tablou ).

In practica declararii si utilizarii listelor se pot consemna urmatoarele operatii: crearea listelor, actualizarea listelor (adaugarea, modificarea sau stergerea de componente) si exploatarea listelor (cautarea anumitor componente, listarea, calcule cu datele componentelor si furnizarea rezultatelor acestor calcule etc)

Cea mai simpla metoda de reprezentare a unei liste este sub forma unui tablou unidimensional (vector, sir) asa cum s-a vazut la datele de tip tablou. Solutia aceasta este convenabila atunci cand numarul componentelor din lista este fix si cunoscut apriori, sau cand se poate preciza numarul maxim de componente din lista si cand acesta are o valoare rezonabila. Sa presupunem, ca din lista studentilor admisi, dorim sa creem o lista cu studentii bursieri si o lista cu studentii nebursieri. Daca se noteaza cu N numarul studentilor dintr-un an de studiu rezulta ca dimensiunea maxima a fiecarei din aceste liste este N. Acest lucru inseamna ca trebuie rezervat spatiu de memorie pentru 2*N componente. Dar, tot timpul numarul studentilor bursieri + numarul studentilor nebursieri = N, prin urmare s-a alocat de 2 ori mai mult spatiu de memorie decat era necesar. Mai mult, inserarea unei componente noi in lista presupune deplasarea tuturor componentelor tabloului aflate dupa locul in care dorim sa inseram o noua componenta, spre dreapta, iar stergerea unei componente (scoaterea din lista) presupune deplasarea la stanga cu o pozitie a tuturor componentelor tabloului aflate dupa componenta care s-a scos, pentru ocuparea locului ramas gol.

Liste simplu inlantuite in Limbajul C/C++.

Eliminarea incovenientelor semnalate mai sus se poate face prin implemantarea listelor cu ajutorul structurilor de date dinamice. In aceste tipuri de liste componentele acestora se pot aloca in zone necontinue de memorie realizandu-se inlantuirea acestora printr-un sistem de adrese ca in exemplu urmator:

struct tipstudent

{

int matricol;

char nume[15]

char prenume[15];

float nota1;

float nota2;

float media;

struct tipstudent *urmator;

} varstudent, primul_student, ultimul student;

Tipul de data de mai sus, “tipstudent”, declara structuri recursive de tip strucura datorita campului "urmator" care furnizeaza adresa urmatoarei componente din lista (a urmatorului student). Acest camp nu este altceva decat un pointer (indicator) la o structura de date de tipul celei din care face parte insusi campul "urmator" si care va avea valoarea NULL pentru ultima componenta din lista. O asemenea lista poarta numele de lista simplu inlantuita, deoarece legatura dintre componente este facuta intr-un singur sens, de la prima la ultima componenta. Componentele unei liste se mai numesc noduri. Nodul este o structura recursiva care contine un pointer (adresa) catre urmatorul nod din lista. In acest caz exista un nod pentru care pointerul (adresa) spre urmatorul nod are valoarea NULL si care nu este altceva decat ultimul nod.

Liste dublu inlantuite in Limbajul C/C++.

O lista dublu inlantuita, spre deosebire de lista simplu inlantuita, presupune realizarea inlantuirii componentelor sale in ambele sensuri, de la prima componenta spre ultima si invers, de la ultima componenta spre prima componenta. In acest sens, in fiecare componenta, trebuie prevazute doua adrese de inlantuire (2 pointeri), una care sa precizeze adresa urmatoarei componente din lista, si alta care sa precizeze adresa componentei anterioare, ca in exemplul urmator:

struct tipstudent

{

int matricol;

char nume[15]

char prenume[15];

float nota1;

float nota2;

float media;

struct tipstudent *urmator;

struct tipstudent *anterior;