Structuri complexe de date in ingineria programarii

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

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

var_student, primul_student, ultimul student;

Tipul de date de mai sus declara structuri recursive, in ambele sensuri, datorita campurilor 'urmator' si 'anterior', care furnizeaza adresa urmatoarei componente (nod) , respectiv adresa componentei anterioare, si care nu sunt altceva decat pointeri spre structuri de date de tipul celei din care fac parte insusi campurile respective ('urmator' si 'anterior') .

In cazul listelor dublu inlantuite campul 'urmator', pentru ultimul nod, are valoare nula NULL iar campul 'anterior' pentru primul nod are, de asemenea, valoarea nula NULL

Operatii asupra listelor simplu si dublu inlantuite.

Principalele operatii care se pot efectua cu listele simplu si dublu inlantuie sunt: crearea listei, adaugarea unei componente , acesul la o componenta, modificarea si stergerea unei componente si stergerea unei liste intregi. Operatia de creare se face incepand cu prima componenta si adaugarea, una dupa alta, de componente la sfarsitul listei sau incepand cu ultima componenta si adaugarea, una dupa alta, de componente la inceputul listei, realizandu-se concomitent inlantuirea componentelor prin campurile de adresa 'urmator' si/sau 'anterior'. Operatia de adaugare se poate face la inceputul, la sfarsitul sau in mijlocul listei. Adaugarea in interiorul listei se mai numeste si inserare. Inserarea, modificarea sau stergerea unei componente presupune si o parcurgere a listei pentru a determina locul unde trebuie facuta inserarea, modificarea sau stergerea. In procesul de actualizare a unei liste trebuie modificate inlantuirile de adrese la toate componentele implicate in actualizare.

Mai jos sunt ilustrate modificarile inlantuirii de adrese in diferite cazuri de actualizare:

Fie lista de studenti dublu inlantuita cu structura urmatoare:

adresa memorie nod

si lista efectiv creata cu dubla inlantuire a componentelor (a nodurilor) :

1000

2000

3000

4000

5000

6000

a) . Adaugarea unei componente la inceputul listei presupune urmatoarele:

- completarea campului 'anterior' al componentei de adaugat la inceputul listei cu NULL (var_student->anterior = NULL) , devenind astfel prima componenta din lista.

- completarea campului 'urmator' al componentei de adaugat la inceputul listei cu adresa primei componente din lista (var_student->urmator = primul_student = 1000) .

- completarea campului 'anterior' al primei componente din lista, care avea valoarea NULL, cu adresa componentei de adaugat (primul_student->anterior = 8000) ;

- atribuirea variabilei corespunzatoare primei componente a adresei componentei de adaugat (primul_student = var_student = 8000)

Dupa aceasta adaugarea prima componenta din lista si componenta de adaugat vor avea urmatorele structuri:

1000

8000

b) . Adaugarea unei componente la sfarsitul listei presupune urmatoarele:

- completarea campului "urmator" al componentei de adaugat la sfarsitul listei cu NIL (var_student->urmator = NULL) , devenind astfel ultima componenta din lista.

- completarea campului "anterior" al componentei de adaugat la sfarsitul listei cu adresa ultimei componente din lista (var_student->anterior = ultimul_student = 6000) .

- completarea campului "urmator" al ultimei componente din lista, care avea valoarea NULL, cu adresa componentei de adaugat (ultimul_student->urmator = 8000) ;

- atribuirea variabilei corespunzatoare ultimei componente a adresei componentei de adaugat (ultimul_student = var_student = 8000)

Dupa aceasta adaugare ultima componenta din lista si componenta de adaugat vor avea urmatorele structuri:

6000

8000

c) . Inserarea unei componente in interiorul listei presupune urmatoarele:

-determinarea componentei dupa care se va face inserarea, prin parcurgerea secventiala a listei de la inceput pana cand conditia de cautare devine adevarata (de exemplu pana cand var_student->matricol = 120, adica nume si prenumme = malaescu ioana) .

- completarea campului "anterior" al componentei de inserat cu adresa componentei dupa care se va face inserarea (var_student_de_inserat->anterior = var_student = 3000) .

- completarea campului "urmator" al componentei de inserat cu adresa componentei inaintea careia se va face inserarea (var_student_de_inserat->urmator = var_student->urmator = 4000) .

- modificarea campului "urmator" al componentei dupa care se va face inserarea (cea care are var_student->matricol = 120) cu adresa componentei de adaugat (inserat) in lista (var_student->urmator = var_student_de_inserat = 8000) .

- modificarea campului "anterior" al componentei inaintea careia se va face inserarea (cea care are var_student->urmator->matricol = 130) cu adresa componentei de inserat in lista (var_student->urmator->anterior = var_student_de_inserat = 8000) .

- atribuirea variabilei curente a adresei componentei de adaugat (inserat) (var_student = var_student_de_inserat = 8000)

Dupa aceasta adaugare (inserare) cele 3 componente din lista implicate in aceasta actualizare vor avea urmatoarele structuri:

3000

4000

8000

d) . Stergerea unei componente de la inceputul listei presupune urmatoarele:

- atribuirea la variabila curenta a adresei celei de-a doua componente din lista (var_student = primul_student->urmator = 2000) .

- modificarea campului 'anterior' al celei de-a doua componente din lista cu valoarea NULL (var_student->anterior = NULL) , devenind astfel prima componenta din lista.

- atribuirea variabilei primei componente din lista a adresei celei de-a doua componenta din lista (primul_student = var_student = 2000)

Dupa stergere componentele din lista implicate in aceasta actualizare vor avea urmatorele structuri:

1000

2000

iar primul_student va fi:

2000

e) . Stergerea unei componente de la sfarsitul listei presupune urmatoarele:

- atribuirea la variabila curenta a adresei penultimei componente din lista (var_student = ultimul_student->anterior = 5000) .

- modificarea campului 'urmator' al penultimei componente din lista cu valoarea NULL (var_student->urmator = NULL) , devenind astfel ultima componenta din lista.

- atribuirea variabilei corespunzatoare ultimei componente din lista a adresei penultimei componente din lista (ultimul_student = var_student = 5000)

Dupa stergere componentele din lista implicate in aceasta actualizare vor avea urmatorele structuri:

5000

6000

iar ultimul_student va fi:

5000

f) . Stergerea unei componente din interiorul listei presupune urmatoarele:

- determinarea componentei care urmeaza sa fie stearsa, prin parcurgerea secventiala a listei de la inceput pana cand conditia de cautare devine adevarata (de exemplu pana cand campul var_student->matricol = 140, adica nume si prenumme = logan cristina) .

- modificarea campului 'urmator' al componentei aflata in fata componentei de sters cu adresa componentei care urmeaza dupa componenta de sters (sarirea componentei de sters prin var_student->anterior->urmator = var_student->urmator = 6000) .

- modificarea campului 'anterior' al componentei aflata dupa componenta de sters cu adresa componentei aflata inaintea celei de sters (var_student->urmator->anterior = var_student->anterior = 4000) .

- atribuirea variabilei curente a adresei componentei aflata dupa componenta de sters (var_student = var_student->urmator = 6000)

Dupa stergere componentele din lista implicate in aceasta actualizare vor avea urmatorele structuri:

4000

5000

6000

g) . Modificarea unei componente din interiorul listei presupune urmatoarele:

- determinarea componentei care urmeaza sa fie modificata , prin parcurgerea secventiala a listei de la inceput pana cand conditia de cautare devine adevarata (de exemplu pana cand campul var_student->matricol = 110, adica nume si prenumme = ionescu ilie) .

- modificarea campurilor de date dorite, in afara campurilor de adrese care realizeaza inlantuirea componentelor din lista (var_student->nume = noul_nume, var_student->nume = noul_prenume sau var_student->nume = noua_medie) .

Exemplul 1 :

Sa se ceeze o lista dublu inlantuita cu coordonatele spatiale ale mai multor puncte din spatiu si apoi sa se afiseze pe ecran punctele cu coordonatele lor de la inceput spre sfarsit si invers.

#include<stdio.h>

#include<stdlib.h>

#include<alloc.h>

#include<conio.h>

void main (void)

*var_punct, *primul_punct, *ultimul_punct;

float wx, wy, wz;

char raspuns;

int n = 0, nf;

/* citirea coordonatelor primului punct */

primul_punct = (struct tip_punct*) malloc (sizeof (struct tip_punct) ) ;

if (primul_punct = = NULL)

printf ('n abscisa punctului P (%d) , x%d = ', n, n) ;

scanf ('%f', &wx) ;

printf ('n ordonata punctului P (%d) , y%d = ', n, n) ;

scanf ('%f', &wy) ;

printf ('n cota punctului P (%d) , z%d = ', n, n) ;

scanf ('%f', &wz) ;

primul_punct->x = wx;

primul_punct->y = wy;

primul_punct->z = wz;

primul_punct->anterior = NULL;

primul_punct->urmator = NULL;

ultimul_punct = primul_punct;

var_punct = primul_punct;

printf ('n continuati adaugarea de puncte? (d/n) :') ;

raspuns = getche () ;

while ( (raspuns = = 'd') || (raspuns = = 'd') )

ultimul_punct->x = wx;

ultimul_punct->y = wy;

ultimul_punct->z = wz;

ultimul_punct->anterior = var_punct;

ultimul_punct->urmator = NULL;

var_punct->urmator = ultimul_punct;

var_punct = ultimul_punct;

printf ('n continuati adaugarea de puncte? (d/n) :') ;

raspuns = getche () ;

}

/* listarea punctelor de la inceput pana la sfarsit */

printf ('n lista punctelor de la inceput pana la sfarsit:') ;

printf ('n = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ') ;

var_punct = primul_punct;n = 0;

while (var_punct->urmator! = NULL)

printf ('n P%d (%f, %f, %f) ', n, var_punct->x, var_punct->x, var_punct->x) ;

printf ('n = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ') ;

nf = n;

/* listarea punctelor de la sfarsit catre inceput */

printf ('n lista punctelor de la sfarsit catre inceput:') ;

printf ('n = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ') ;

var_punct = ultimul_punct;n = 0;

while (var_punct->anterior! = NULL)

printf ('n P%d (%f, %f, %f) ', n, var_punct->x, var_punct->x, var_punct->x) ;

printf ('n = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ') ;

}

Variabilele alocate dinamic vor fi memorate in zona Heap. La finalul executiei programului se poate sti adresa primului, respectiv ultimului punct memorat. Locurile din memorie ale celorlalte puncte sunt necunoscute.

Parcurgerea si extragerea datelor referitoare la puncte sunt permise numai secvential, cu ajutorul variabilelor de tip pointer incluse in variabilele dinamice (anterior, urmator) .

Daca in variabila de tip pointer var_punct se pune continutul variabilei primul_punct, atunci var_punct = primul_punct si se poate referi primul punct prin var_punct. Referirea la un camp al variabilei dinamice de tip punct se face prin var_punct-> urmat de numele campului:

var_punct-> x - contine abscisa primului punct.

var_punct -> y - contine ordonata primului punct.

var_punct -> z - contine cota primului punct.

var_punct->urmator - contine adresa unde este memorat urmatorul punct.

De asemenea se poate initia un sir de instructiuni pentru a extrage pe rand datele referitoare la punctele memorate astfel:

var_punct = var_punct->urmator

(var_punct va contine adresa de memorie in care a fost memorat urmatorul punct)

Referirea la campurile noului punct se va face la fel ca mai inainte. Se va continua aceasta procedura de prelucrare a datelor referitoare la punctele consecutive pana cand variabila var_punct va avea valoarea egala cu variabila ultimul_punct, sau cand campul var_punct->urmator va avea valoarea NULL.

Se observa ca variabilele dinamice (de tip pointer) pot interveni in program in doua moduri.

Primul, cand se foloseste variabila simplu, fara referire, caz in care singurele operatii permise intre ele sunt cele de atribuire (initializarea unei variabile dinamica cu constanta NULL sau tansferul continutului intre variabile dinamice de acelasi tip) .

Al doilea mod este cand se foloseste ca si referire la o variabila dinamica (var_dinamica1-> var_dinamica2->) caz in care se lucreaza cu variabile dinamice.