In cadrul capitolului 1 au fost prezentate structurile fundamentale de date: tabloul, articolul si multimea.
Ele se numesc fundamentale deoarece:
Constituie elementele de baza cu ajutorul carora se pot forma structuri mai complexe,
Apar foarte frecvent in practica.
Scopul definirii tipurilor de date urmat de specificarea faptului ca anumite variabile concrete sunt de un anumit tip, este:
De a fixa domeniul valorilor pe care le pot lua aceste variabile,
De a preciza structura, dimensiunea si amplasarea zonelor de memorie care le sunt asociate.
Intrucat toate aceste elemente sunt fixate de la inceput de catre compilator, astfel de variabile si structurile de date aferente lor se numesc statice.
In practica programarii insa exista multe probleme care presupun structuri ale informatiei mai complicate, a caror caracteristica principala este aceea ca se modifica structural in timpul executiei programului, motiv pentru care se numesc structuri dinamice.
Este insa evident faptul, ca la un anumit nivel de detaliere, componentele unor astfel de structuri sunt tipuri de date fundamentale.
In general, indiferent de limbajul de programare utilizat, o structura de date statica este aceea care ocupa pe toata durata executiei programului caruia ii apartine, o zona de memorie fixa, de volum constant.
Memoria necesara unei structuri statice se rezerva in faza de compilare deci inainte de lansarea programului.
Se considera statice acele structuri care au volumul efectiv constant
Se considera tot statice acele structuri de date cu volum variabil pentru care programatorul poate aprecia o margine superioara a volumului si pentru care se aloca volumul de memorie corespunzator cazului maxim in faza de compilare.
In contrast, o structura de date dinamica este aceea structura al carei volum de memorie nu poate fi cunoscut in faza de compilare deoarece el este functie de maniera de executie a algoritmului.
Cu alte cuvinte acest volum poate sa creasca sau sa descreasca in dependenta de anumiti factori cunoscuti numai in timpul rularii.
In consecinta alocarea memoriei la o structura dinamica are loc in timpul executiei programului.
In general, orice variabila declarata in partea de declarare a variabilelor, cu exceptia celor de tip secventa, reprezinta o structura statica, pentru care se rezerva o zona de memorie constanta.
Prin declararea unei variabile statice se precizeaza numele si tipul ei, numele fiind un identificator prin intermediul caruia programul respectiv programatorul poate face referire la aceasta variabila.
Pana in momentul de fata, singurele structuri dinamice abordate au fost cele de tip secventa.
Datorita faptului ca variabilele corespunzatoare lor se presupun inregistrate in memorii externe, ele se considera structuri dinamice speciale si nu fac obiectul prezentului paragraf.
De fapt atat structurile dinamice cat si cele statice sunt formate in ultima instanta din componente de volum constant care se incadreaza intr-unul din tipurile cunoscute si care sunt inregistrate integral in memoria centrala.
In cadrul structurilor dinamice aceste componente se numesc de regula noduri.
Natura dinamica a acestor structuri rezulta din faptul ca numarul nodurilor se poate modifica pe durata rularii.
Atat structurile dinamice cat si nodurile lor individuale se deosebesc de structurile statice prin faptul ca ele nu se declara si in consecinta nu se poate face referire la ele utilizand numele lor, deoarece practic nu au nume.
Referirea unor astfel de structuri se face cu ajutorul unor variabile statice, definite special in acest scop si care se numesc variabile indicator (pointer).
Variabilele referite in aceasta maniera se numesc variabile indicate.
Utilizarea structurilor de date dinamice alaturi de alte aplicatii speciale impun definirea unui tip special de variabile numite variabile indicator.
Valorile acestor variabile nu sunt date efective ci ele precizeaza (indica) locatii de memorie care memoreaza date efective.
Cu alte cuvinte, valoarea unei astfel de variabile indicator reprezinta o referinta la o variabila de un anumit tip precizat, numita variabila indicata.
Pentru a preciza natura unor variabile indicator, s-a introdus un nou tip de date abstract si anume tipul de date abstract indicator.
Descrierea de principiu a unui astfel de tip apare in [2.a].
TDA Indicator
Modelul matematic: Consta dintr-o multime de valori care
indica adresele de memorie ale unor variabile numite indicate, apartinand unui tip specificat. Aceasta multime de valori cuprinde si indicatorul vid care nu indica nici o variabila.
Notatii: p,q - variabile de TipIndicator;
e - variabila de TipIndicat;
b - valoare booleana. [2.a]
Operatori
New(p) ‑ procedura care aloca memorie pentru o
variabila indicata si plaseaza valoarea adresei
de memorie (indicatorul) in variabila p;
Dispose(p) - procedura care elibereaza zona de
memorie (locatia) corespunzatoare variabilei
indicate p;
MemoreazaIndicator(p,q) - copiaza indicatorul p in q;
MemoreazaValoareIndicata(p,e) - copiaza valoarea
lui e in zona (locatia) indicata de p;
e:=FurnizeazaValoareIndicata(p) ‑ functie care
returneaza valoarea memorata in zona (locatia)
indicata de p;
b:=IndicatorIdentic(p,q) ‑ functie booleana ce
returneaza valoarea true daca p s q, adica cele
doua variabile indicator indica aceeasi locatie
de memorie.
Tipul de date abstract indicator poate fi implementat in mai multe moduri.
In continuare se prezinta doua astfel de modalitati una bazata pe pointeri si o a doua bazata pe cursori.
Dupa cum se cunoaste, variabilele pointer, sunt variabile statice obisnuite care se declara ca orice alta variabila.
Elementul particular al acestor variabile este faptul ca ele se declara de tip pointer.
Inainte de a preciza acest tip, se va clarifica semnificatia variabilelor pointer.
Valoarea unei astfel de variabile este de fapt o adresa de memorie care poate fi adresa unei structuri dinamice sau a unei componente a ei.
In consecinta, in limbaj de asamblare accesul la variabila indicata de o variabila pointer se realizeaza prin adresarea indirecta a celei din urma.
In limbajele de nivel superior acelasi lucru se realizeaza prin atasarea unor caractere speciale numelui variabilei pointer in dependenta de limbajul utilizat [2.2.a].
VariabilaIndicata s VariabilaPointer^
//Precizarea unei variabile indicate - varianta C
VariabilaIndicata s *VariabilaPointer (in C) [2.2.a]
In plus, in limbajul C s-a definit operatorul & care se permite determinarea adresei unei variabile indicate si a fost dezvoltata o aritmetica speciala a pointerilor.
O regula deosebit de importanta stabileste ca, spre deosebire de un limbaj de asamblare, in limbajele de nivel superior se stabileste o legatura fixa intre orice variabila pointer si tipul variabilei indicate.
O variabila pointer data se refera in mod obligatoriu la o variabila indicata de un anumit tip.
Aceasta restrictie mareste siguranta in programare si constituie o deosebire neta intre variabilele pointer definite in limbajele de nivel superior si adresele obisnuite din limbajele de asamblare.
Un tip pointer se defineste precizand tipul variabilei indicate precedat de caracterul '^' in Pascal respectiv caracterul '*' in limbajul C [2.2.b].
TYPE TipPointer = ^TipIndicat; (Pascal)
//Definirea unui tip pointer - varianta C
tip_indicat *variabila_pointer; (C) [2.2.b]
In limbajul C aceasta restrictie poate fi evitata utilizand tipul generic void care permite declararea unui pointer generic care nu are asociat un tip de date precis.
void *variabila_pointer; [2.2.c]
Alocarea sau eliberarea memoriei unei structuri dinamice in timpul rularii cade in competenta programatorului si se realizeaza cu ajutorul unor operatori standard specifici dependenti de limbaj.
Pentru exemplificare in secventele urmatoare se prezinta implementarea TDA Indicator in limbajele Pascal respectiv C,
Implementari sunt realizate prin intermediul unor operatori definiti la nivelul limbajului.
TYPE TipPointer = ^TipIndicat;
VAR p,q: TipPointer;
e: TipIndicator; [2.2.d]
b: boolean;
New(p);
Dispose(p);
p:= q;
p^:= e;
e:= p^;
b:= p=q;
//TDA Indicator - implementare C
tip_indicat *p,*q,e;
int b; [2.2.e]
p=malloc(sizeof(tip_indicat));
free(p);
p:= q;
*p:= e;
e:= *p;
b=(p==q);
Daca in limbajele care definesc tipul pointer (referinta), implementarea TDA Indicator este imediata si realizata chiar la nivelul limbajului, in limbajele care nu dispun de aceasta facilitate sau in situatii speciale, implementarea acestui tip de date se poate realiza cu ajutorul cursorilor.
Un cursor este o variabila intreaga utilizata pentru a indica o locatie intr-un tablou de variabile indicate.
Ca si metoda de conectare, un cursor este perfect echivalent cu un pointer cu deosebirea ca el poate fi utilizat in plus si in limbajele care nu definesc tipul referinta.
Interpretand valoarea unei variabile intregi ca si un indice intr-un tablou, in mod efectiv acea variabila va indica locatia respectiva din tablou.
Cu ajutorul acestei tehnici, pot fi implementate practic toate structruile de date care presupun inlantuiri, dupa cum se va vedea in capitolele urmatoare.
Este insa evident faptul ca sarcina gestionarii zonei care se aloca dinamic revine exclusiv programatorului, cu alte cuvinte utilizatorul trebuie sa-si dezvolte proprii operatori de tip New respectiv Dispose .
Programarea orientata spre obiecte a impus noi dezvoltari ale posibilitatilor de acces la elementele cu care programatorul opereaza in cadrul unui program.
Astfel limbajele orientate spre obiecte cum ar fi C++ sau JAVA definesc asa numitele referinte care de fapt sunt o forma de implementare a tipului indicator.
O referinta apare ca fiind similara in multe privinte cu un pointer, dar de fapt nu este un pointer.
O referinta este un alias (un alt nume) pentru o variabila precizata.
Ea are un nume care poate fi folosit in locul variabilei originale.
Deoarece este un alias si nu un pointer, variabila pentru care este declarata referinta trebuie sa fie specificata in momentul declararii referintei.
In plus spre deosebire de un pointer o referinta nu poate fi modificata pentru a indica o alta variabila.
X
Exemplul 2.3. Considerand in limbajul C++ o variabila declarata dupa cum urmeaza:
long numar = 0;
Se poate declara o referinta pentru ea utilizand urmatoarea declaratie:
long& ref_numar = numar; // Declarare referinta
In acest caz se poate spune ca de fapt ref_numar este de tip 'referinta la long'.
Referinta poate fi in continuare utilizata in locul variabilei originale. Spre exemplu atribuirea
ref_numar += 13;
Are ca efect incrementarea variabilei numar cu 13.
Spre deosebire de referinta anterior precizata, un pointer la aceeasi variabila poate fi declarat astfel:
long* pointer_numar = &numar;
Ceea ce permite incrementarea variabilei numar dupa cum urmeaza:
*pointer_numar += 13;
Exista o distinctie evidenta intre utilizarea unui pointer si utilizarea unei referinte.
Pointerul este evaluat la fiecare utilizare si in conformitate cu adresa pe care o contine la momentul respectiv este accesata variabila indicata.
Referinta nu este necesar sa fie evaluata la fiecare utilizare; odata definita ea nu mai poate fi modificata, lucru care nu este valabil si pentru pointer.
Referinta este complet echivalenta cu variabila la care se refera.
La o analiza sumara referinta nu pare a fi altceva decat o notatie alternativa pentru o anumita variabila deoarece ea se comporta in acest sens.
In realitate adevaratele valente ale acestui concept sunt puse in evidenta in cazul utilizarii obiectelor.
Astfel, in limbajele orientate spre programarea pe obiecte, in momentul in care se asigneaza obiecte variabilelor sau se transmit obiecte ca argumente pentru metode, se transmit de fapt referintele acelor obiecte si nu obiectele ca atare sau copii ale lor.
Acest lucru are o importanta cu totul particulara in dezvoltarea de aplicatii orientate spre obiecte.
Spre exemplu in limbajul JAVA nu exista pointeri expliciti nici asa numita 'aritmetica a pointerilor' ci doar referinte, fara ca acest lucru sa restranga libertatea de programare ci dimpotriva.
In cadrul paragrafelor acestui capitol, pana in prezent, recursivitatea a fost prezentata ca o proprietate specifica algoritmilor, implementata in forma unor proceduri care se apeleaza pe ele insele.
In cadrul acestui paragraf se va prezenta extinderea acestei proprietati si asupra tipurilor de date in forma asa-numitelor 'structuri de date recursive'.
Prin analogie cu algoritmii, prin structura de date recursiva se intelege o structura care are cel putin o componenta de acelasi tip ca si structura insasi.
Si in acest caz, definitiile unor astfel de tipuri de date pot fi recursive in mod direct sau in mod indirect (vezi &5.1).
Cel mai simplu exemplu de structura recursiva il reprezinta lista inlantuita simpla a carei definire formala apare in [3.a].
TYPE TipLista = RECORD
info: TipInfo; [3.a]
urm: TipLista (incorect)
END
Un alt exemplu de structura recursiva este arborele genealogic al unei persoane, adica structura care precizeaza toate rudele directe ascendente ale persoanei in cauza.
O astfel de structura poate fi definita ca si un articol cu trei componente, prima reprezentand numele persoanei, celelalte doua fiind arborii genealogici ai parintilor.
Aceasta se exprima formal astfel [3.b]:
TYPE TipGenealogie = RECORD
nume: string; [3.b]
tata, mama: TipGenealogie (incorect)
END;
Datorita campurilor urm respectiv tata si mama, care au acelasi tip ca si structura insasi, tipurile definite sunt recursive.
Se face precizarea ca definitiile de mai sus nu sunt corecte, deoarece se utilizeaza identificatorii TipLista repectiv TipGenealogie inainte de a fi complet definiti (utilizarea unui tip in curs de definire). Acest neajuns va fi remediat ulterior.
Se constata usor ca cele doua tipuri definesc structuri infinite.
Aceasta este o consecinta directa a recursivitatii respectiv a faptului ca exista campuri de tip identic cu cel al structurii complete.
Este insa evident ca in practica nu se pot prelucra structuri infinite.
In realitate nici listele nici arborii genealogici nu sunt infiniti.
In cazul arborilor genealogici spre exemplu, urmarind suficient de departe ascendenta oricarei persoane se ajunge la stramosi despre care lipseste informatia.
Tinand cont de aceasta, se va modifica definitia tipului TipGenealogie astfel:
Daca se ajunge la o persoana necunoscuta atunci structura va contine un singur camp notat cu 'XX',
In orice alt caz structura contine trei campuri conform definitiei anterioare.
In figura 3.a se poate urmari o structura de TipGenalogie conform definitiei modificate.
|
PETRU |
STEFAN |
ADAM |
XX |
|
|||||||||||||||||||||
|
XX | |||||||||||||||||||||||||
|
MARIA |
XX | ||||||||||||||||||||||||
|
EVA |
XX |
Fig.3.a. Exemplu de structura de date recursiva Cu privire la tipurile de date recursive se precizeaza in general ca pentru a evita structuri infinite, definitia tipului trebuie sa contina o conditie, de care depinde prezenta efectiva a componentei (sau a componentelor) recursive. Ca si in exemplul de mai sus, in anumite conditii, componentele avand acelasi tip ca si structura completa, pot sa lipseasca. In acceptiunea acestor conditionari pot exista structuri recursive finite. Structurile recursive pot fi implementate in limbajele de programare avansate numai in forma unor structuri dinamice. Prin definitie, orice componenta care are tipul identic cu structura completa, se inlocuieste cu un pointer care indica acea componenta. In secventele [3.c,d] apar pentru exemplificare definiri ale structurii recursive TipGenealogie in varianta Pascal respectiv C. TYPE PointerGenealogie = ^TipGenealogie; TipGenealogie = RECORD nume: string; [3.c] tata,mama:PointerGenealogie END; // Structura de date recursiva - arborele genealogic al unei persoane - varianta C struct genealogie Dupa cum s-a precizat, in anumite conditii, o componenta poate sa lipseasca dintr-o structura recursiva. In acest scop, multimea valorilor oricarui tip referinta se extinde cu referinta vida (pointer nul) care nu se refera la nici o variabila indicata. Acest pointer se noteaza cu NIL respectiv NULL, el apartinand prin definitie oricarui tip referinta. Absenta unei componente recursive se va indica asignand pointerul referitor la aceasta componenta cu referinta vida. Cu aceste precizari, structura recursiva din figura 3.a poate fi reprezentata ca in si in figura 3.b.
Fig.3.b. Implementarea unei structuri de date recursive Un alt exemplu de structura recursiva este cel al expresiilor aritmetice. In acest caz recursivitatea rezulta din faptul ca orice expresie aritmetica poate contine un operand care este o alta expresie aritmetica inchisa intre paranteze. In exemplul care urmeaza se va considera cazul simplu in care prin expresia aritmetica se intelege: Fie un operand simplu (care va fi reprezentat ca un identificator cu o singura litera) Fie o expresie aritmetica urmata de un operator urmat de o expresie aritmetica. Definirea unei astfel de structuri se poate realiza dupa cum se prezinta in secventa [3.e]. TYPE PointerExpresie= ^TipExpresie; TipExpresie = RECORD [3.e] Operator: CHAR; Operand1,Operand2: PointerExpresie END; In cadrul acestei definitii se considera ca: Daca in campul operator se gaseste unul din caracterele ' + ',' - ', ' * ' sau ' / ', atunci celelalte doua campuri contin cate un pointer la o alta expresie, Daca in campul operator se gaseste o litera, atunci celelalte doua campuri vor contine NIL. S-a aratat in &5.2.4, ca orice algoritm recursiv poate fi inlocuit cu un algoritm iterativ echivalent. Aceasta proprietate se pastreaza si pentru structurile recursive de date si anume orice structura recursiva poate fi inlocuita cu o structura de tip secventa. Astfel, o definitie de tip recursiv de forma [3.f]: TYPE IndicatorStructura = ^TipStructura TipStructura = RECORD continut: TipContinut; [3.f] legatura: IndicatorStructura END; Este echivalenta si inlocuibila imediat cu tipul secvential [3.g]: TYPE TipStuctura = FILE OF TipContinut [3.g] Se observa ca o structura recursiva se poate inlocui imediat cu una secventiala daca si numai daca numele tipului recursiv apare in propria definitie recursiva o singura data la sfarsitul (sau la inceputul) acesteia. Aceasta observatie este valabila si pentru procedurile recursive (vezi &5.2.4). In cazul altor structuri de date recursive cu un grad mai ridicat de complexitate (de regula bazate pe arbori de diferite ordine) se poate realiza transformarea intr-o structura secventiala prin traversarea arborelui asociat structurii intr-o maniera ordonata specifica (spre exemplu in in, pre sau post ordine).
| |||||||||||||||||||||||
.com