Alocarea dinamica a memoriei
De cele mai multe ori , în aplicatii ,datele sunt grupate în colectii de date ,care trebuie organizate într-un anumit mod pentru a putea fi prelucrate. Pornind de la aceasta idee, a aparut notiunea de structura de date.
O colectie de date înzestrata cu informatii structurale, care permit identificarea si selectia componentelor, se numeste structura de date.
Componentele unei structuri de date pot fi identificate si selectate fie prin numele lor, fie prin intermediul relatiilor structurale. Cea mai simpla relatie structurala este pozitia fiecarei componente în cadrul structurii. Asupra unei structuri de date se pot aplica mai multe tipuri de operatii:
vizualizarea elementelor structurii sub diverse forme;
actualizarea (adaugarea, modificarea sau stergerea anumitor componente);
îmbogatirea structurala prin adaugarea unor informatii de legatura;
sortarea (aranjarea componentelor într-o anumita ordine stabilita de un anumit criteriu de ordonare) etc.
Memoria calculatorului este alcatuita din locatii de memorie succesive si etichetate. Aceasta eticheta poarta numele de adresa. Fiecare variabila, în momentul declararii ei are alocata o locatie de memorie, cunoscuta prin adresa sa. Un pointer este o variabila care ia ca valori adrese de memorie. Deci se poate memora adresa fiecarei variabile, chiar daca nu o cunoastem. Trebuie sa anuntam pointerul care va prelua aceasta valoare: deci sa-l declaram.
Cum declaram si cum utilizam un pointer?
Pointerul se declara ca o variabila, adica prin tip si prin nume: <tip> *<nume>; unde <tip> reprezinta tipul variabilelor a caror adresa va fi memorata în variabila pointer; * este un simbol pentru a indica faptul ca variabila este un pointer;<nume> este identificatorul C++ pentru numele variabilei.
Observatii
simbolul " * " poate sa apara oriunde între <tip> si <nume>;
tipul pionterului este dat de tipul variabilei a carei adresa de memorie dorim sa o retinem în pointer si deci nu exista tipul pointer ca atare;
Toti pointerii odata creati vor fi initializati cu ceva. Daca nu stim exact ce adresa vom memora în pointerul respectiv îl vom initializa cu 0 adica valoarea NULL în limbajul C++, respectiv NIL în limbajul Pascal. Acest pointer se va numi pointer nul. Pointerul nul nu retine nici o adresa. Un pointer care nu se initializeaza se va numi pointer salbatic( wild pointer) si este foarte periculos. Iata un exemplu în care se lucreaza cu un poiter neinitilizat:
int x, *p; x=10;
.... *p=x;
Observatie!
Atribuirea *p=x; face ca valoarea memorata în x sa fie "scrisa" într-o zona de memorie necunoscuta. Este foarte posibil ca acest lucru sa nu creeze probleme atât timp cât programul are dimensiuni mici si zona alocata arbitrar pointerului nu intra în zona de program, de date sau a sistemului de operare. Dar marindu-se programul probabilitatea ca p sa pointeze o zona importanta de memorie creste, caz în care programul nu mai ruleaza complet sau chiar se opreste.
Pentru a initializa un pointer cu adresa unei variabile se apeleaza la operatorul de adresare &. În exemplul urmator vom crea un pionter si în el vom memora adresa unei variabile de tip int:
int x=10;
int *px=0; // se construieste pointerul nul;
px=&x;// se salveaza în px adresa lui x;
Observatii:
stim ca variabila px este un pointer pentru ca are simbolul "* " în fata;
stim ca variabila px contine adresa variabilei x deoarece aceasta este precedata de operatorul de adresare &;
Utilizând un pointer, se poate afla valoarea variabilei a carei adresa este memorata în pointerul respectiv. Accesul la valoarea variabilei prin intermediul pointerului se realizeaza prin indirectare(deferentiere) Numele acestui proces provine de la faptul ca valoarea se acceseaza indirect prin pointer. Deci prin indirectare întelegem accesarea valorii de la adresa memorata în pointer. În concluzie pointerul furnizeaza o metoda indirecta de a lucra cu valoarea pastrata la o anumita adresa si indirectarea se realizeaza utilizând operatorul " * ".Cum schimbam valoarea unei variabile folosind indirectarea?
int *px ;
int x=1;
px=&x; //px contine adresa lui x;
*px=5; /* se schimba continutul lui x prin intermediul pointerului care retine adresa lui x */
Operatorul * este utilizat în doua moduri distincte în lucrul cu pointerii:
Când un pointer este declarat, * indica faptul ca avem de-a face cu o variabila pointer si nu cu o variabila obisnuita;
Când un pointer este deferentiat, * indica faptul ca avem acces la valoarea de la adresa memorata de pointer.
Este foarte important sa facem distinctie între pointer , adresa memorata într-un pointer si valoarea care se gaseste la adresa respectiva. Acest aspect constituie sursa de confuzii si erori în lucrul cu pointerii.
Pointerii pot fi folositi la ascunderea variabilelor. Se poate folosi indirectarea simpla, dubla etc. Nivelul de indirectare se poate mari, dar acest lucru determina un acces mai dificil la continutul locatiilor de memorie.
Ce este memoria heap si cum o manipulam?
De ce sa utilizam pointerii, daca se poate accesa valoarea direct prin variabila? Singurul motiv pentru care lucram cu pointerii în acest mod este acela de a demonstra cum lucreaza. In mod real pointerii sunt utilizati pentru:
Lucrul cu memoria heap;
Transmiterea parametrilor prin referinta în cadrul functiilor;
Manipularea claselor polimorfice;
Deoarece memoria interna a calculatorului cuprinde spatiul global, memoria heap
registri, spatiu de cod si stiva vom arata de ce e important lucrul cu pointeri. Pe stiva sunt memorate variabilele locale si parametrii functiilor, în timp ce în spatiul global sunt memorate variabilele globale. În spatiul de cod este stocat codul, sursa (programul),iar registrii sunt utilizati pentru administrarea interna a functiilor. Restul memoriei este memoria heap.
Sa ne referim la utilitatea memoriei heap. Variabilele locale nu sunt vazute decât în timpul executie functiei în care apar. Variabilele globale rezolva problema accesului neconditionat de oriunde din program, dar conduce la crearea unui cod dificil de urmarit. Memoria heap vine sa rezolve ambele tipuri de probleme ridicate de folosirea celor doua tipuri de variabile: locale si globale. Administrarea memoriei heap presupune lucrul cu adrese de memorie. Accesarea unei valori stocate în heap nu se poate face decât prin adresa locatiei rezervate anterior memorarii valorii respective.
Daca spatiul alocat pe stiva este eliberat în mod automat când o functie îsi termina executia, spatiul alocat în memoria heap, cu ajutorul unui pointer, se elibereaza în mod deliberat de utilizator când nu îi mai foloseste. Avantajul accesarii memoriei în acest mod vis-a-vis de utilizarea variabilelor globale este acela ca numai functiile cu acces la pointeri au acces la date. Acest lucru realizeaza o interfata cu datele mai bine controlate. Evident pentru acest lucru este necesar sa se poata crea un pointer în memoria heap si sa se transmita acel pointer între functii. Alocarea spatiului în memoria heap se realizeaza prin utilizarea operatorului new numit operator de alocare.
Sintaxa: new <tip> [<dimensiune>]: unde <tip> reprezinta tipul valorii care va fi memorata în heap, <dimensiune> reprezinta numarul de locatii de tipul <tip> alocate. New returneaza o adresa de memorie care va fi asignata unui pointer, daca mai exista spatiu disponibil, sau 0(NULL) în caz contrar. Zona heap, fiind limitata exista posibilitatea ca alocarea sa nu se poata face când aceasta este plina. Din acest motiv dupa alocarea zonei prin new trebuie sa se verifice daca aceasta a avut loc în mod real. Exemplu:
int *x;
p=new int;
if (p!=NULL) // if(p = = 0)
cout<<"Heap-ul este plin";
Odata ce spatiul de memorie alocat nu va mai este necesar, este cazul sa-l disponibilizati. Acest lucru se realizeaza apelând la operatorul delete. Sintaxa: delete <pointer>; delete [ ] <pointer>; delete <nume vector> [ ];unde: <pointer> reprezinta numele variabilei pointer care a preluat adresa unei locatii alocate în heap prin new. A doua varianta se utilizeaza pentru disponibilizarea unei zone de memorie având mai multe locatii iar a treia variantǎ se utilizeazǎ pentru eliberarea unei zone de memorie alocate printr-un vector.
Trebuie retinut cǎ pointerul însusi, spre deosebire de memoria pointatǎ de acesta, este o variabilǎ care se declarǎ într-o functie. Prin urmare când functia în care a fost declarat îsi încheie executia, pointerul se pierde, este sters de pe stivǎ. Memoria alocatǎ cu new si controlatǎ de pointerul respectiv în schimb nu este eliberatǎ automat. Respectiva zonǎ de memorie devine indisponibilǎ generând o gaurǎ de memorie(memory leak).Zona de memorie nu se mai "reface" nici când programul se terminǎ.
O altǎ cale prin care se pot crea gǎuri de memorie este datǎ de reasignarea unui pointer înainte de disponibilitatea zonei pointate anterior de acesta. De exemplu:
int *p=new int; (1)
p=10; (2)
p=new int; (3)
*p=100; (4)
delete p; (5)
Desi se disponibilizeazǎ în linia (5) zona alocatǎ prin p, acest lucru se referǎ numai la a doua alocare efectuatǎ în linia (3).Zona alocatǎ în linia (1) este irecuperabilǎ, adresa acesteia fiind pierdutǎ. Evitarea acestui aspect se realizeazǎ introducând între linia (2) si (3) delete p; Se pot declara si pointeri constanti folosind cuvântul cheie const.
const int *p1;
int *const p2;
const int * const p3;
Unde p1 este un pointer la un întreg constant. Valoarea variabilei la care pointeazǎ nu poate fi schimbatǎ. P2 este un pointer constant la un întreg. Valoarea variabilei la care pointeazǎ poate fi schimbatǎ dar p2 nu poate sǎ retinǎ altǎ adresǎ decât cea primitǎ initial.P3 este un pointer constant la un întreg constant. Valoarea de la adresa retinutǎ de pointer nu poate fi schimbatǎ dar nici valoarea retinutǎ în pointerul p3 nu poate fi alteratǎ. Pentru a vedea cine rǎmâne constant priviti în dreapta cuvântului cheie const.
Când operǎm cu pointeri avem posibilitatea sǎ-i comparǎm(compararea adreselor de memorie pe care le memoreazǎ ei),adunarea si scǎderea unui întreg cu / dintr-un pointer; incrementarea, decrementarea etc. Este permisǎ utilizarea operatorilor relationali si de egalitate.
Adunarea unui întreg la un pointer. Fie p un pointer si n un întreg reprezentat prin alocarea unei variabile întregi sau o constantǎ de acelasi tip. Expresia p + n constǎ în mǎrirea valorii adresei retinute în pointerul p cu n* dimensiunea în octeti necesarǎ reprezentǎrii tipului pointerului p. Deoarece tipul float necesitǎ patru octeti, adresele cresc din patru în patru.
Scǎderea unui întreg dintr-un pointer. Operatia este opusǎ celei prezentate anterior. Deci p-n va conduce la micsorarea valorii pǎstrate în p cu n* dimensiunea în octeti necesarǎ reprezentǎrii tipului pointerului p.
Incrementarea si decrementarea pointerilor Aceastǎ operatie este identicǎ cu adunarea, respectiv scǎderea, lui 1 la un pointer. Astfel ++p sau p++ este identic cu a scrie p=p+1 sau p+=1,dupǎ cum - - p sau p- - este acelasi lucru cu a scrie p=p-1 sau p- =1, cu respectarea regulilor care se cunosc de la operatorii de incrementare / decrementare.
Declararea unui tablou oferǎ posibilitatea de a lucra cu pointeri. Numele tabloului desemneazǎ un pointer constant si are ca valoare adresǎ de memorie a primului element din tablou. Datoritǎ acestui aspect, accesarea elementelor din tablou se poate face si cu ajutorul pointerului desemnat prin variabila ce reprezintǎ tabloul. In mod clasic elementul i al unui tablou este desemnat prin a[i]. Prin utilizarea pointerului constant a, *(a + i).De ce asa? Pentru cǎ a reprezenta adresa locatiei de memorie a primului element: a[0],adresa elementului i, conform operatiilor cu pointeri, va fi a + i. Continutul locatiei respective va fi *(a + i).
Elementele unei matrici sunt memorate pe linii, într-un spatiu continuu de memorie. Pentru a accesa un element trebuie sǎ identificǎm locatia unde începe linia pe care se afla elementul, iar apoi sǎ ne deplasǎm în cadrul acestei linii cu atâtea locatii cât este indicele de coloanǎ. Astfel a[i][j] se identificǎ la nivelul pointerilor cu *(*(a + i)+j).Deoarece numele tabloului reprezintǎ un pointer
constant, zona de memorie alocatǎ de acesta nu se poate schimba.
int a[10] , *p ;
a = p ; //eroare ,a este un pointer constant;
n schimb este posibil sǎ gestionǎm printr-un pointer o zonǎ de memorie alocatǎ prin declararea unui tablou.
REFERINŢE
O referinta este un alias al unui obiect. Atunci când creǎm o referintǎ, aceastǎ se initializeazǎ cu numele unui obiect, numit obiect tintǎ. Din acest moment referinta actioneazǎ ca un nume alternativ al obiectului tintǎ iar toate operatiile care se vor efectua asupra referintei se vor rǎsfrânge asupra obiectului tintǎ.
Declararea unei referinte se face respectând urmǎtoarea sintaxa:
<tip> & <nume_referinta>=<obiect_tintǎ>;
<tip> --- este acelasi cu tipul obiectului tintǎ;
<nume_referintǎ>---este un identificator al limbajului de programare (C++);
Pentru a putea declara o referintǎ asupra unui obiect tintǎ trebuie ca obiectul tintǎ sǎ fi fost deja declarat (anterior referintei).Operatorul de referentiere &, care apare în declararea referintei are acelasi simbol cu operatorul de adresǎ, dar nu sunt unul si acelasi operator.
Asa cum am vǎzut mai sus, o variabilǎ poate fi gestionatǎ în direct prin pointeri. Dar acest lucru poate fi fǎcut într-o manierǎ mai simplǎ prin referinte ,
Cu o micǎ diferentǎ, referintele nu pot fi reinitializate, fiind pentru totdeauna aliasurile obiectelor tintǎ pentru care au fost construite initial.
În lucrul cu subprograme (functii si proceduri), se întâmpinǎ probleme din douǎ motive: argumentele functiilor fiind transmise prin valoare, efectul operatiilor asupra lor nu era sesizat decât în interiorul functiei, si nu se poate returna din functie decât o valoare, instructiunea return acceptând un singur parametru Eliminarea acestor neajunsuri se poate face prin transmiterea parametrilor prin referinte. În C++, acest lucru se poate face utilizând pointerii sau referintele. Sintaxa diferǎ în cele douǎ cazuri dar rezultatul este acelasi.
De exemplu:
#include<stdio.h>
#include<conio.h>
void cub(int x)
void main()
Iesirea va fi: a=10 x=1000
si o linie mai jos a=10.Se observǎ cǎ variabila "a" nu si-a modificat valoarea dupǎ apelul functiei "cub". Aceasta deoarece transmiterea parametrilor în cazul functiei "cub" s-a fǎcut prin valoare. Se observǎ în schimb cǎ parametrul x si-a schimbat valoarea în cadrul functiei. Pentru cǎ aceastǎ schimbare sǎ se observe si în programul apelant, utilizǎm pointerii sau referintele. Astfel rescriem functia "cub" în cele douǎ variante:
#include<stdio.h>
#include<conio.h>
void cub_pointeri(int *x)
void cub_referinte(int &x)
main()
iesirea va fi:
a din apelul cub_pointeri=8
a din apelul cub_referinte=512
Deoarece cub_pointeri lucreazǎ cu pointeri, vom identifica valoarea prin cotinutul de la adresa x. De aceea apare *x. Apelul functiei trebuie sǎ transmitǎ adresa lui x; prin urmare apare ca parametru efectiv &a. Iar functia cub_referinte lucreazǎ cu aliasul variabilei a si atât apelul cât si manevrarea variabilelor în cadrul functiei este mult mai naturalǎ.
Din cele arǎtate mai sus, ar fi de preferat utilizarea referintelor. Acestea sunt clare si usor de utilizat. Totusi referintele nu sunt reasignate. Astfel dacǎ doriti sǎ retineti adresa unui obiect într-o variabilǎ si apoi aceeasi variabilǎ sǎ retinǎ adresa altui obiect, trebuie sǎ utilizati pointerii. Referintele nu pot fi nule. Prin urmare dacǎ un obiect într-o conditie se va analiza vis-a-vis de valoarea NULL,
nu vor fi utile referintele, ci pointerii. Dacǎ operatorul new nu poate aloca memorie de heap, returneazǎ un pointer NULL. Pentru ca referintele nu pot avea valoarea NULL, nu trebuie sǎ se initializeze o referintǎ cu un pointer pânǎ nu se verificǎ dacǎ pointerul nu are valoarea NULL.
CONCLUZII
Utilizati transmiterea prin referintǎ ori de câte ori este posibil;
Nu lucrati cu pointeri dacǎ nu se poate lucra cu referinte;
Nu returnati referinta nici unui obiect local;
STRUCTURI DE DATE ALOCATE DINAMIC
Ati sesizat cǎ spatiul de memorie alocat unui tablou este acelasi de la începutul si pânǎ la sfârsitul executiei programului în care erau declarate. Pe de altǎ parte, de cele mai multe ori rǎmânea spatiu neutilizat. Alocati un vector de 10 elemente, dar utilizati doar 5 în program. Sau se poate întâmpla sǎ mai avem nevoie de spatiu în plus fatǎ de numǎrul maxim declarat. La fel se poate întâmpla si în cazul matricilor. Aceste neajunsuri nu se puteau remedia decât umblând la declaratia tabloului---si mai exact, la dimensiunea acestuia. În nici un caz nu se puteau rezolva aceste aspecte prin program, în cursul executiei lui.
Ca orice resursǎ memoria trebuie gestionatǎ eficient si în acest scop se face apel la alocarea dinamicǎ.
Alocarea dinamicǎ, spre deosebire de cea staticǎ, permite gestionarea memoriei în timpul executiei programului. Asadar se pot face alocǎri si eliberǎri ale spatiului de memorie "din mersul" programului, lucru imposibil în abordarea staticǎ a rezolvǎrii unei probleme. Dacǎ în alocarea staticǎ se lucreazǎ cu tablouri în alocarea dinamicǎ se lucreazǎ cu liste.
Lista liniarǎ înlantuitǎ reprezintǎ o structurǎ dinamicǎ de date (ea poate fi abordatǎ si static, cu ajutorul vectorilor), în care elementele constituitive respectǎ o anumitǎ ordine, în sensul cǎ fiecare element, cu exceptia primului, are un predecesor si fiecare element, cu exceptia ultimului are un succesor. Se numeste nod(celula, element) o unitate de informatie de sine stǎtǎtoare (elementarǎ)care poate sǎ continǎ informatii utile si date de legǎturǎ. Cu alte cuvinte lista este o multime de noduri(celule).
Din categoria listelor vom prezenta în continuare: liste liniare simplu înlǎntuite, liste liniare dublu înlǎntuite, liste circulare, stive si cozi.
Liste simplu înlǎntuite :elementele au un singur pointer spre ele si sunt reprezentate de zona de informatie si zona de legǎturǎ (pointerul) ce retine adresa urmatorului nod în listǎ.
Liste dublu înlǎntuite: elementele au doi pointeri spre ele si sunt reprezentate de asemenea de zona de informatie si zonele de legǎturǎ
(pointerii) ce retin adresa nodului anterior si a celui urmǎtor.
Liste circulare :care pot fi dublu sau simplu înlǎntuite, au particularitatea cǎ ultimul element este legat de primul, adicǎ pointerul ultimului element vede adresa primului element.
Stiva: este o listǎ liniarǎ cu proprietatea cǎ adǎugarea si eliminarea elementelor se face pe la un singur capǎt, numit vârful stivei .O stivǎ care nu contine nici un element se numeste stivǎ vidǎ. În orice moment, putem scoate din stivǎ numai elementul care a fost introdus ultimul, motiv pentru care vom spune cǎ stiva functioneazǎ dupǎ principiul LIFO(last in first out).
Coada: este o listǎ, în care adǎugarea elementelor se face pe la un capǎt
numit "capǎt de introducere", iar eliminarea elementelor se face pe la celǎlalt capǎt numit "capǎt de extragere". In orice moment, putem scoate din coadǎ numai elementul care în acel moment se aflǎ la capǎtul de extragere. Astfel spus elementele ies din coadǎ în ordinea inversǎ intrarii. Datorita acestei proprietǎti, se vor numi cozi FIFO(first in first out)
ARBORI BINARI DE CĂUTARE
Numim arbore binar de cǎutare un arbore binar în care orice nod, cu exceptia nodurilor terminale, se bucurǎ de proprietatea cǎ valoarea cheii este mai mare decât informatia din nodul fiu din stânga si mai micǎ decât informatia din nudul fiu din dreapta. Din definitie deducem cǎ în arborele binar de cǎutare, informatia din noduri este unicǎ. Numim câmp cheie acel câmp din structura nodului în functie de valoarea cǎruia se creeazǎ si se exploateazǎ arborele. În cele ce urmeazǎ când ne vom referi la informatia nodului vom considera valoarea câmpului cheie al nodului respectiv. O proprietate foarte importantǎ a arborelui binar de cǎutare este aceea cǎ oferǎ posibilitatea ordonǎrii crescǎtoare a valorilor din câmpurile cheie, prin parcurgerea lui în inordine. Prin modul de constructie se observǎ cǎ în arborele de cǎutare, gǎsirea unei informatii se face respectând urmǎtorul algoritm: se cautǎ în nodul curent; dacǎ informatia s-a gǎsit, algoritmul se încheie, altfel, dacǎ informatia este mai mare decât informatia din nodul curent, se cautǎ în subarborele drept al acestuia, altfel în subarborele stâng.
Structurile arborescente reprezintǎ structuri neliniare de date, cu multiple aplicatii în programarea si utilizarea calculatoarelor. Într-un limbaj simplist
structurile arborescente exprimǎ relatii de "ramificare" între nodurile unui arbore, asemǎnǎtoare configuratiei arborilor din natura, cu deosebirea cǎ, în informaticǎ, arborii "cresc" în jos. Se numeste arborescentǎ un arbore care are un nod special numit radacina iar celelalte noduri pot fi repartizate în multimi disjuncte V1,V2,.Vm(m>=0),astfel încât în fiecare din aceste multimi disjuncte existǎ un nod adiacent cu rǎdǎcina iar subgrafurile generate de acestea sunt la rândul lor arborescente.
În particular o arborescentǎ cu un singur nod este formatǎ doar din nodul rǎdǎcinǎ. Dacǎ ordinea relativǎ a arborescentelor generate de multimile V1,V2,.Vm din definitie are importantǎ, arborescenta se numeste arbore ordonat. În reprezentarea graficǎ a unei arborescente, nodurile se deseneazǎ pe nivele, astfel: rǎdǎcina se afla pe primul nivel, varfurile adiacente cu rǎdǎcina pe nivelul urmǎtor, si asa mai departe.
Nivel 0 a Nodurile
adiacente cu rǎdǎcina
si care se deseneazǎ pe nivelul
Nivel 1 b c urmǎtor ,se numesc descendenti
ai rǎdǎcinii. În mod analog
Pentru un nod dat, nodurile adia
Nivel 2 d e f cente lui care se
afla pe nivelul
urmǎtor în arbore se numesc
Nivel 3 g descendentii nodului respectiv.
Descendentii aceluiasi nod se mai numesc si frati. În figurǎ nodurile b si c sunt noduri-frate si totodatǎ reprezintǎ descendentii rǎdǎcinii. Varfurile d, e, f sunt descendentii nodului c. Dacǎ un nod x este descendentul nodului y, mai spunem cǎ y este pǎrintele nodului x. Folosim deci termenii "descendent" si "pǎrinte" pentru a exprima relatii între noduri aflate pe nivele consecutive în reprezentarea arborilor. Terminologia utilizatǎ în structurile arborescente include chiar cuvinte ca fiu, tatǎ, frati, unchi, strǎbunic, veri, cu înteles similar celui din vorbirea curentǎ.
Un arbore binar este un arbore ordonat în care fiecare nod are cel mult doi descendenti. Asadar, un arbore binar contine o radacina si cel mult doi subarbori binari disjuncti ce descind din aceasta, pe care îi numim subarborele stâng, respectiv subarborele drept. Daca un subarbore lipseste spunem ca este vid.
Arborele
binar din figura alaturata are ca subarborele
1 stâng arborele binar cu
radacina 2 iar ca subarbore drept
2 3 arborele binar cu
radacina 3. Arborele binar cu radacina 2
are atât subarborele
stâng cât si cel drept vizi. Arborele
4 binar cu
radacina 3 are subarborele drept vid, iar
5 6 subarborele stâng nevid (arborele binar cu radacina 4).
Sa observam ca un arbore binar nu reprezinta un caz particular de arbore. De exemplu, arborii binari de mai jos sunt distincti (primul are radacina a si subarborele drept vid, iar al doilea are radacina a cu subarborele stâng vid), desi ca arbori sunt identici.
Un vârf fara descendenti se numeste nod terminal
sau frunza. Pentru arborele binar din figura de mai sus a a
nodurile 2, 5 si 6 sunt noduri frunza. Într-un arbore binar,
nivelele nodurilor se numeroteaza cu zero începând de la
radacina. Astfel, radacina se a afla pe
nivelul 0, fii radacinii
pe nivelul 1, fii acestora pe nivelul 2 si asa mai departe. Un b b
arbore binar în care fiecare nod care nu este terminal are exact
doi descendenti se numeste arbore binar complet. Arborele de mai jos este un arbore binar complet:
Un
arbore binar complet cu n noduri terminale,
toate situate pe acelasi nivel, are în total 2n-1
2 3 noduri .Vom arata mai întâi ca n=2r, unde r este
ultimul nivel al arborelui, cel pe care se afla
nodurile terminale.
Demonstram prin indicatie
4 7 dupa numarul nivelului, ca în arborele binar din
ipoteza, pe nivelul k se gasesc 2k noduri (k este
cel
5 6 mult egal cu numarul de ordine al ultimului nivel
din arbore). Într-adevar, pe nivelul 0 se afla doar
radacina, deci 20=1 noduri. Presupunem ca pe nivelul k se gasesc 2k noduri si sa demonstram ca pe nivelul k+1 se gasesc 2k+1 noduri. Daca nivelul k+1 apartine arborelui, atunci nodurile de pe acest nivel sunt doua câte doua descendente din nodurile de pe nivelul k, nivel pe care, conform ipotezei, sunt 2k noduri. Prin urmare, numarul total de noduri de pe nivelul k+1 este 2 * 2k = 2k+1. Rezulta ca pe ultimul nivel r al arborelui binar vor fi 2r noduri.
Sa calculam acum numarul total din arbore: 20+21+.+2r = 2r+1-1 = 2 * 2r-1 = 2n-1.
Un arbore binar complet are un numar impar de noduri.
REPREZENTAREA ARBORILOR BINARI
Existǎ mai multe moduri de reprezentare a arborilor binari:
a) reprezentarea standard---se specificǎ rǎdǎcina RAD si, pentru fiecare varf, se precizeazǎ descendentul stang si descendentul drept, in caz cǎ acestia existǎ. Modul concret în care se precizeazǎ descendentii poate sǎ difere:putem utiliza vectori, asa cum vom detalia imediat sau putem folosi avantajele alocǎrii dinamice, care permite sa legǎm un nod de pǎrintele sau utilizand adrese reale de memorie.in prima variantǎ se folosesc doi vectori S si D ,pentru fiecare varf i,S[i] fiind descendentul stang iar D[i] descendentul drept.In general informatia continutǎ de un anumit nod diferǎ de numǎrul sǎu de ordine.De exemplu un arbore binar poate avea ca informatii în noduri nume de persoane.In acest caz, se mai utilizeazǎ un vector INF, astfel încat pentru fiecare nod i, INF[i] sǎ continǎ informatia asociatǎ nodului respectiv.Pentru arborele din figura de mai sus,cu n=7 vǎrfuri,avem: RAD=1,S=(2,0,4,5,0,0,0) iar D=(3,0,7,4,0,0,0). Se observǎ cǎ in general nu este esential sǎ precizǎm rǎdǎcina,ea putǎnd fi dedusǎ din vectorii S si D, dat fiind faptul cǎ rǎdǎcina este singurul varf care nu este descendentul vreunui alt varf.Cu ajutorul alocǎrii dinamice se defineste urmǎtoarea structurǎ:
typedef struct nod TNOD;
si se declarǎ: TNOD * rad;
In definirea tipului de date TNOD am considerat un singur camp de tip int pentru a retine numǎrul de ordine al varfului.Este desigur permis ca structura respectivǎ sǎ continǎ oricate campuri (de diverse tipuri) pentru memorarea informatiilor asociate nodurilor. Esentiale pentru prelucrarea arborelui sunt legǎturile stanga si dreapta(respectiv st si dr) pentru fiecare nod, si adresa nodului rǎdǎcinǎ rad.
b) se utilizeazǎ doi vectori DESC si TATA:in vectorul DESC ,avand valori -1,0,1,
se precizeazǎ pentru fiecare nod ce fel de descendent este el pentru tatǎl sau.(stang
nu are parinte sau drept) iar in vectorul TATA se indicǎ pentru fiecare nod nodul pǎrinte.cum nodul rǎdǎcinǎ,nu are nod pǎrinte,componenta corespunzatoare din vectorul TATA este 0.Pentru arborele binar din figura de mai sus,cu n=7 varfuri, avem TATA=(0,1,1,3,4,4,3) si DESC=(0,-1,1,-1,-1,1,1).
PARCURGEREA ARBORILOR BINARI
Prin parcurgerea unui arbore se intelege examinarea in mod sistematic a nodurilor sale, asfel încat fiecare nod sǎ fie accesat o datǎ si numai o datǎ.Aceastǎ misiune este numitǎ si "vizitare" a varfurilor arborilor si are ca scop prelucrarea informatiilor continute de acestea.Arborele este o structurǎ neliniarǎ de organizare a datelor,iar rolul traversǎrii sale este tocmai conceperea unei aranjǎri liniare a varfurilor fructificand avantajele acestei organizari.
Exista trei modalitǎti principale de parcurgere a arborilor binari:
preordine: se viziteazǎ rǎdǎcina, se traverseazǎ subarborele stang in preordine, se traverseazǎ subarborele drept in preordine;
inordine:se traverseazǎ subarborele stang in inordine,se viziteazǎ rǎdǎcina,se traverseazǎ subarborele drept in inordine;
postordine:se traverseazǎ subarborele stang in postordine,se traverseazǎ subarborele drept in postordine,se viziteazǎ rǎdǎcina;
Pentru arborele binar de mai sus(n=7 noduri),parcurgerea in preordine genereazǎ varfurile in ordinea 1,2,3,4,5,6,7;parcurgerea in inordine furnizeazǎ varfurile in ordinea:2,1,5,4,6,3,7;iar parcurgerea in postordine conduce la:2,5,6,4,7,3,1;
FORMA PREFIXATA A EXPRESIILOR ARITMETICE
Notatia polonezǎ a expresiilor aritmetice este una dintre cele mai importante aplicatii ale arborilor binari si a fost introdusǎ de matematicianul polonez J.Lukasiewicz. Se stie cǎ un program scris într-un limbaj de programare este supus unui proces complex de transformǎri, panǎ ce el ajunge în format direct executabil de cǎtre procesorul unui calculator. Vom vorbi aici despre modalitatea prin care expresiile aritmetice sunt transformate în fazǎ de compilare într-o formǎ intermediarǎ care stǎ la baza generǎrii codului obiect corespunzǎtor(necesar în faza de executie pentru evaluarea acelei expresii)
Vom defini in continuare notatia fǎrǎ paranteze asociatǎ expresiilor aritmetice.
Vom lucra, pentru simplitate, cu expresii aritmetice alcǎtuite din operanzi care sunt variabile al cǎror nume este format dintr-o singurǎ litera si constante alcǎtuite doar dint-o singurǎ cifrǎ. operatorii permisi in expunerea noastrǎ sunt doar cei binari, si anume: adunarea(+), scǎderea(-),înmultirea(*),împǎrtirea(/) si ridicarea la putere(^).
Mai întai sǎ vedem cum putem asocia unei expresii aritmetice E, admise in contextul în care lucrǎm, un arbore binar complet.
A1.Dacǎ E este formatǎ dintr-un singur operand, îi asociem un arbore binar format doar din rǎdǎcinǎ, în care punem operandul respectiv.
A2.Dacǎ E=E1 op E2 unde "op" este unul din operatorii permisi, iar E1 si E2 sunt expresii aritmetice, îi asociem lui E arborele binar complet care are în rǎdǎcinǎ operatorul "op", ca subarbore stang arborele binar asociat expresiei E1 iar ca subarbore drept arborele binar asociat expresiei E2.
A3.Dacǎ E=(E1) unde E1 este o expresie aritmeticǎ, îi asociem expresiei E arborele binar asociat expresiei E1.
Pentru expresiile aritmetice simple a+b, a-b, a*b, a/b, a^b arborii binari asociati sunt desenati mai jos:
Sǎ observǎm cǎ, deoarece operatiile de scǎdere, împǎrtire si ridicare la putere,nu sunt comutative, arborii obtinuti sunt într-adevǎr binari, deoarece se face distinctie între descendentul stang(care contine primul operand) si descendentul drept(care contine al doilea operand).
Pentru expresia a*b+c/d-e arborele binar complet asociat este urmǎtorul:
Sǎ introducem
în
continuare notatia polonezǎ
prefixatǎasociatǎ unei expresii
aritmetice E:
Definitie: fie E o expresie
aritmeticǎ.forma polonezǎ
prefixata "E" a lui E se
obtine astfel:
P1:Daca E=a,unde a este o
Constanta sau o variabila, "E"
=a .
P2:Daca E=E1 op E2 atunci
"E"=op "E1" "E2", pentru
orice expresii aritmeticeE1 si E2.
P3: Daca E=(E1) atunci "E"= "E1",pentru orice expresie aritmetica E1.
Pentru expresiile a+b, a-b, a*b, a/b, a^b notatiile poloneze sunt: +ab,-ab, ab, /ab, si respectiv ^ab. Pentru expresia E=ab+c/d-e forma poloneza prefixata este
+ *ab/cde.
Intr-adevar "a*b+c/d-e" = -"a*b+c/d" e = - + "a*b" "c/d" e = - + * ab / cd e.
Sa observam ca daca parcurgem in preordine arborele binar din ultima figura obtinem forma poloneza prefixata asociata expresiei E.Acest lucru este adevarat pentru orice expresie arutmetica,deoarece modul in care se asociaza arborele binar complet prin regulile A1,A2,A3 este in stransa legatura cu modul in care se defineste forma poloneza prefixata prin regulile P1,P2,P3.Obtinem deci urmatorul rezultat:parcurgerea in preordine a unui arbore binar asociat unei expresii aritmetice E da forma poloneza prexita a expresie E.
Observatii:
forma poloneza asociata unei expresii aritmetice nu este unica; astfel :
"a+b+c"= +"ab+c"= +a+bc dar si "a+b+c"= + "a+bc"= + +abc;
in forma poloneza prefixata nu se mai folosesc paranteze,acestea nemaifiind necesare pentru a marca prioritatile de calcul;
am definit forma poloneza prefixata pentru expresii aritmetice care folosesc numai operatori binari.Se pot accepta si operatori unari + si - ,dar mult mai simpla este asimilarea lor cu operatorii binari + si -.Astfel vom scrie 0+a in loc de +a si 0-a in loc de -a.
Modul in care se foloseste forma poloneza prefixata pentru evaluarea unei expresii aritmetice E este urmatorul:
Se parcurge forma poloneza prefixata de la dreapta la stanga,utilizandu-se o stiva pentru memorarea operanzilor in rezerva.Daca simbolul curent nu este operand,el se introduce in stiva (evident, in varful ei).Daca simbolul citit este un operator,se aplica acest operator primilor doi operanzi din stiva,obtinandu-se un rezultat r;cei doi operanzi sunt eliminati din stiva si se adauga in stiva rezultatul r obtinut.Se trece apoi la prelucrarea urmatorului simbol din sirul care contine forma poloneza prefixata a expresiei aritmetice E.
Acesta este un mod simplificat dar suficient de intuitiv de utilizare a formei poloneze prefixate pentru evaluarea expresiilor aritmetice.A reiesit ca in stiva se pun direct valorile operanzilor, ceec ce,pe de o parte este greu,pe de alta parte de multe ori este imposibil, deoarece, valorile unor operanzi nu se cunosc in faza de compilare,acestea urmand a fi citite in faza de executie. In realitate dupa generarea formei poloneze a unei expresii aritmetice,se genereaza o succesiune de instructiuni in cod masina care vor evalua expresia in faza de executie.pentru aceasta se foloseste de asemenea o stiva,dar in ea vor fi trecute adresele operanzilor si nu valorile lor, pentru ca in succesiunea instructiunilor ce vor evalua expresia aritmetica se folosesc adresele operanzilor.pentru rezultatele intermediare se folosesc zone auxiliare de memorie.
Ne propunem in continuare sa realizam un program ,care pornind de la o expresie aritmetica oarecare,admisa,sa-i determine forma poloneza prefixata. Pentru aceasta vom asocia expresiei date arborele binar complet conform regulilor A1,A2,A3,pe care apoi il vom parcurge in preordine.
Pentru construirea arborelui binar complet asociat,am folosit o serie de functii care reflecta definitia(recursiva) o unor expresii aritmetice pe baza unor componente mai simple: termeni,factori,subexpresii care contin operatorul de ridicare la putere.Vom prezenta mai jos un program care rezolva aceasta problema:
# define NMAX 40
# include<stdio.h>
# include<alloc.h>
# include<fstream.h>
typedef struct nod TNOD;
typedef TNOD *ADR_TNOD;
int i,n ;
char c, sir[NMAX] ;
void urmator(void)
void factor (ADR_TNOD * r);
void termen(ADR_TNOD * r);
void putere(ADR_TNOD * r);
void expr(ADR_TNOD * r)
}
void termen(ADR_TNOD *r)
void factor (ADR_TNOD *r)
void putere (ADR_TNOD * r)
void afisare(ADR_TNOD r)
void main()
APLICATII
LISTE LINIARE SIMPLU INLANTUITE
Vom prezenta mai jos un program care exploateaza o lista liniara simplu inlantuita:
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
struct elem;
void adaugare(elem * &prim,int inf)
elem * creare()
}
return prim;
elem * creare_prin_adaugare()
return prim;
void inserare_inainte(elem * &prim,int v,int inf)
if(crt!=NULL)
else
void inserare_dupa(elem * prim,int v,int inf)
//parcurgem lista;
if (crt!=NULL)//daca am gasit informatia
else
void stergere(elem * &prim,int v)
if (crt!=NULL) //am gasit informatia
else
void parcurgere(elem * prim)
cout<<"\n";
getch();
void main()
while(optiune<1&&optiune>8);
switch(optiune)
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:
while(optiune!=8);
Scrieti un subprogram care primeste prin intermediul primului sau parametru a(de tip adresa) adresa primului element al unei liste liniare
simplu inlantuite,prin intermediul celui de-al doilea parametru n, primind o valoare nenula de cel mult 3 cifre.Subprogramul trebuie sa returneze
prin cel de-al treilea parametru b(tot de tip adresa), adresa celui de-al n-lea element al listei sau adresa nula daca nu exista un asemenea element.
# include<stdio.h>
struct elem;
void lista(elem *a,int n,elem * &b)
void main ()
//listei
lista(prim,3,nou);
if (nou==NULL)
printf("nu exista acest element");
else printf(" elementul este %d",nou->inf);
Scrieti un subprogram care citeste de la tastatura 20 de numere si creeaza o lista simplu inlantuita prin inserarea succesiva a numerelor in lista astfel incat in final,lista sa contina numere aflate in ordine descrescatoare. Subprogramul va returna adresa de inceput a listei create.
Se vor defini tipurile de date necesare si se va evita utilizarea altor structuri de date auxiliare.
#include<stdio.h>
struct elem ;
elem *lista(void)
return(s1);
void main (void)
Scrieti un subprogram care elimina unul sau doua elemente(daca lista contine un numar par de noduri) din mijlocul unei liste.Subprogramul primeste ca parametru adresa de inceput a listei.Se vor defini si tipurile de date necesare subprogramului.*/
struct elem;
#include<stdio.h>
void list(elem *prim)
void stergere(elem *prim)
if (i%2==0)
else
void main (void)
list(prim);
printf("\n");
stergere(prim);
list(prim);
Scrieti declaratiile necesare pentru definirea unei liste dublu inlantuite,stiind ca un element al listei memoreaza ca informatie un numar natural de cel mult doua cifre.Stiind ca exista o lista dublu inlantuita ale carei capete sunt marcate prin adresa nula,scrieti un subprogram care determina numarul de elemente ele listei.Subprogramul primeste printr-un parametru adresa unui element oarecare din lista si returneaza valoarea
reprezentand numarul de elemente din lista.
#include<stdio.h>
struct elem;
int nr(elem *crt)
aux=crt;
while (aux->succ!=NULL)
return(nr1+nr2+1);
}
void main ()
ultim->succ=NULL;
int k=nr(prim->succ->succ);
printf("numarul de elemente este=%d",k);
Scrieti declaratiile necesare pentrudefinirea unei liste simplu inlantuite,stiind ca un element al listei memoreza un caracter.Scrieti un subprogram care verifica daca exista doua pozitii succesive intr-o lista circulara simplu inlantuita, pozitii care sa contina exact acelas caracter. Subprogramul primeste print-un parametru adresa unui element oarecare din lista si returneaza valoarea 1 daca exista doua caractere succesive identice in lista si 0 in caz contrar.*/
#include<stdio.h>
struct elem;
int exista (elem *prim)
while(pred !=prim);
return 0;
}
void main (void)
crt->succ=prim;
if(exista(prim)==1)
printf("EXISTA DOUA LITERE SUCCESIVE IDENTICE");
else
printf("NU EXISTA DOUA LITERE SUCCESIVE IDENTICE");
Sa se interclaseze doua liste alocate dinamic,care sunt ordonate crescator
si contin numere intregi.
#include<iostream.h>
#include<conio.h>
typedef struct elem element;
element* creare()
else
if(prim->val>info)
else
if(p1)
else
}
}
return prim;
void parcurgere (element * prim)
cout<<"\n";
getch();
element* interclasare(element* plimbaret1, element* plimbaret2)
else
ultim=cap;
while (plimbaret1 && plimbaret2)
if (plimbaret1->val> plimbaret2->val)
else
if(plimbaret1)
ultim->next=plimbaret1;
else
ultim->next=plimbaret;
return cap;
void main()
Sa se creeze un program care sa creeze si sa exploateze un arbore binar
de cautare.
#include<conio.h>
#include<iostream.h>
typedef struct nod NOD;
NOD *tns;
void adaug(NOD * &r,int info)
else
if (r->info>info)
adaug(r->s,info);
else
if (r->info<info)
adaug(r->d,info);
else
cout<<"informatie duplicat"<<endl;
void creare(NOD * &r)
void inord(NOD *p)
void cauta(NOD *p,int x)
NOD * detmin(NOD *p)
return p;
NOD* cauta_sterge(NOD *pint x)
else
if (p->info>x)
else
return p;
void sterge(NOD * &r,int x)
else
if (ns->d==ns->s)//nodul nu are descendenti;
else
if(ns->d==NULL && ns->s)//nodul de sters are descendent stang
else
if(ns->s==NULL && ns->d)//nodul are descendent drept
else//nodul are doi descendenti;
else//minim are descendent drept
while(ns1->s && ns1->info<ns1->s->info)
}
main()
cout<<"\nDoriti sa cautati o informatie in arbore 1-da/0-nu?";
cin>>opt;
while(opt)
getch();
9 Sa se inverseze legaturile intr-o lista liniara simplu inlantuita
#include<iostream.h>
#include<conio.h>
typedef struct nodNOD;
void creare(NOD* *p)
void parcurgere (NOD* prim)
cout<<"\n";
getch();
void inversare(NOD* &cap)
cap=p;
}
void main(void)
Sa se realizeze reuniunea a doua multimi reprezentate ca liste liniare cu legaturi.
Solutie: Dându-se doua liste simplu înlantuite, pentru a determina reuniunea lor se considera toate elementele din a doua lista care nu se gasesc în prima lista si se insereaza în lista finala care este initializata cu elementele din prima lista. Listele se considera implementate fara header. Vom da în continuare functia care realizeaza lista de capat L ce reprezinta reuniunea elementelor listelor de capete L1 si L2.
void Reuniune(celula *&L, celula *L1, celula *L2)
Prima lista este vida
while(L2 != NULL) // Se parcurg elementele din a doua lista
else delete(k); // Element comun celor doua liste
}
. Sa se realizeze intersectia a doua multimi reprezentate prin liste liniare simplu înlantuite.
Solutie: Intersectia a doua multimi reprezentate ca liste simplu înlantuite se poate obtine parcurgând a doua multime si, în cazul în care un element apartine primei liste se insereaza în lista L care reprezinta intersectia celor doua multimi si care se considera initial ca lista vida. În final se elibereaza elementele primei liste.
void Intersectie(celula *&L, celula *L1, celula *L2)
else delete(k); // Element comun celor doua liste
}
while(L1 != NULL) // Eliminare elemente din prima lista
while(L2 != NULL) // Eliminare elemente din a doua lista
. Fiind data o lista simplu înlantuita de numere întregi, sa se creeze cu elementele ei doua liste ce contin elementele pare si respectiv impare ale ei.
Solutie: Se parcurge lista initiala si în cazul în care elementul este par se insereaza în prima lista, iar daca este impar se insereaza în a doua lista. Functia care realizeaza aceasta este urmatoarea:
void ValParImpar(celula *L, celula *&L1, celula *&L2)
else
}
. Sa se împarta elementele unei liste cu legaturi în doua liste, prima continând elementele de ordin impar si cea de-a doua pe cele de ordin par.
Solutie: Rezolvarea problemei presupune schimbarea legaturilor astfel: primul element din lista initiala va fi legat de al treilea, al doilea de al patralea etc.
void PozParImpar(celula *L, celula *&L1, celula *&L2)
p = L2 = L->leg;
while(p != NULL)
p1->leg = NULL;
. Sa se inverseze legaturile unei liste simplu înlantuite în asa fel încât primul element sa devina ultimul si reciproc.
Solutie: Presupunem cazul listei reprezentate fara header. Rezolvarea problemei presupune folosirea a trei pointeri: p1, L, p3 care fac referire la trei elemente consecutive din lista; p1 si L se folosesc pentru inversarea legaturii, iar p3 va retine adresa capatului partii din lista initiala, nemodificata înca.
void Inversare(celula *&L)
L->leg = p1;
. Sa se elimine duplicatele dintr-o lista simplu înlantuita.
Solutie: Pentru rezolvarea problemei se considera fiecare element al listei si se cauta în lista dupa acesta daca exista un alt element egal cu el caz în care se elimina din lista acest element. Se observa ca nu se schimba capatul listei.
void Dubluri(celula *L)
else p1 = k;
p = p->leg;
. Sa se creeze un arbore binar complet (plin) si sa se parcurga arborele în preordine, inordine si postordine, folosind pentru parcurgeri functii recursive.
Solutie: Deoarece într-un arbore binar complet (plin) fiecare nod are exact doi descendenti, arborele are 2n-1 noduri, unde n reprezinta numarul de nivele al acestuia (nodul radacina al arborelui considerându-se pe nivelul 1). De exemplu, un arbore binar complet cu 4 nivele poate arata astfel:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
În acest caz, parcurgerea în preordine (radacina, descendent stâng, descendent drept) înseamna vizitarea nodurilor 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15 parcurgerea în inordine (descendent stâng, radacina, descendent drept) înseamna 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15 si parcurgerea în postordine (descendent stâng, descendent drept, radacina) înseamna 8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1. Un program C++ ce rezolva problema poate fi:
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
struct nod
*rad; //arborele este dat de adresa celulei radacina
int n;
void CreareArb(nod *&rad); //nerecursiv, pe nivele
void Preordine(nod *p);
void Inordine(nod *p);
void Postordine(nod *p);
void StergeArb(nod *rad)
void main()
void CreareArb(nod *&rad) //crearea se face pe nivele
else
nv++;
}
}
for (int j=pow(2,n-1);j<pow(2,n);j++) //ultimul nivel
void Preordine(nod *p)
void Inordine(nod *p)
void Postordine(nod *p)
void StergeArb(nod *rad)//recursiv, in preordine
}
. Sa se implementeze variantele nerecursive ale parcurgerii arborelui în preordine, inordine si postordine.
Solutie: Variantele nerecursive folosesc o stiva si functiile pentru prelucrarea acesteia:
int ns; //numarul de elemente efective din stiva
nod *stiva[100];
void InitStiva()
int StivaVida()
void InserareStiva(nod* elem)
nod* VarfStiva()
În acest caz, functiile nerecursive pentru parcurgerea în preordine si inordine pot fi:
void PreordineNerecursiv(nod *p)
if (StivaVida()) break;
else
}
void InordineNerecursiv(nod *p)
if (StivaVida()) break;
else
}
La parcurgerea în postordine, pentru ca trebuie parcursi atât subarborele drept cât si cel drept înainte de a vizita nodul, trebuie retinut fiecare nod de doua ori în stiva: o data pentru a putea avea acces la legatura din stânga si a doua oara pentru legatura din dreapta. De aceea fiecarui nod introdus în stiva i se poate asocia o componenta a unui vector cu valoarea 0 daca a fost introdus în stiva o data sau 1 când este introdus în stiva a doua oara:
int nr_retineri[100];
În acest caz, functia nerecursiva pentru parcurgerea arborelui în postordine poate fi:
void PostordineNerecursiv(nod *p)
while (!StivaVida())
else cout<<p->info<<" ";
}
if (StivaVida()) break;
}
. Sa se implementeze crearea recursiva a unui arbore binar.
Solutie: Crearea recursiva a arborelui se poate face în preordine (întâi se creeaza nodul, apoi recursiv descendentii), informatia nodurilor dându-se în preordine. Pentru nodurile finale ale arborelui se poate da ca informatie un element din afara domeniului informatiei din nod (de exemplu, când nodurile arborelui sunt de tip întreg se poate da un caracter, constanta NULL, etc.). În acest caz, functia C++ poate arata astfel:
void CreareArb_Preordine(nod* &rad)
else
. Sa se implementeze operatia de adaugare a unui nod si de cautare a unui element într-un arbore binar de cautare.
Solutie: Cum arborele binar de cautare are proprietatea ca pentru fiecare nod neterminal al arborelui valoarea sa este mai mare decât valorile nodurilor din subarborele stâng si mai mica sau egala decât valorile nodurilor din subarborele drept, atunci cautarea unui element se poate face recursiv astfel:
int Exista(nod *rad, int elem)
//verifica existenta elementului in arbore
else return 0;
}
Un nou nod se insereaza în arbore cautând pozitia corespunzatoare si se insereaza întotdeauna ca nod frunza. Astfel parcurgerea arborelui în inordine va duce la afisarea valorilor nodurilor în ordine crescatoare.
int Adauga(nod *&rad, int elem)
else
if (elem<rad->info) return Adauga(rad->ls,elem);
else return Adauga(rad->ld,elem);
}
Înainte de apelul functiei trebuie facuta initializarea arborelui, care consta în executarea instructiunii rad=NULL. De exemplu:
Initial rad=NULL
Adauga(rad , 5) va conduce la arborele: 5
Adauga(rad , 9) va conduce la arborele: 5
Adauga(rad , 7) va conduce la arborele: 5
7
Adauga(rad , 3) va conduce la arborele: 5
3 9
7
Adauga(rad , 8) va conduce la arborele: 5
3 9
7
8
Adauga(rad , 12) va conduce la arborele: 5
3 9
7 12
8
etc.
(Problema lui Josephas) Se da o lista cu elementele 1, 2, ., n. Începând de la primul element, cu un pas dat sa se afiseze si sa se elimine toate elementele listei.
Solutie: Se foloseste o implementare cu lista circulara simplu înlantuita fara header, primul element fiind la adresa data de pointerul L si ultimul element al listei fiind legat la adresa data de pointerul u. Functia care rezolva problema este data în continuare:
L
x xn-1 xn
void Josephas(celula *L, int pas)
while(p->leg != L) p = p->leg;
cout << "Elementele sunt urmatoarele: ";
while(L->leg != L)
k = L; p->leg = L = k->leg;
cout << k->info; delete(k);
}
cout << L->info; delete(L);
. Sa se implementeze operatiile cu liste dublu înlantuite.
Solutie: Se foloseste o reprezentare a listei
fara header si spre deosebire de listele simplu
înlantuite aici exista doua legaturi ale unei celule:
una spre celula din stânga (anterioara) si una spre celula din
dreapta (urmatoare)
L
x1 . xn-1 xn NULL
NULL .
În acest caz, structura unei celule este:
struct celula
*L;
Codul C++ pentru initializarea listei poate fi:
void Initializare()
Inserarea unui nou element a la începutul listei se poate face astfel:
void InserareInc(int a)
Inserarea unui nou element a dupa al m-lea elemnt din lista sau la sfârsitul listei, daca m este mai mare decât numarul de elemente din lista se poate face astfel:
void InserareInt(celula *&L, int a, int m)
k->legs = s;
k->legd = d;
if(s != NULL) s->legd = k;
else L = k;
if(d != NULL) d->legs = k;
Inserarea unui nou element a la sfarsitul listei se poate face astfel:
void InserareSf(celula *&L, int a)
while(s->legd != NULL) s = s->legd;
s->legd = k; k->legs = s;
Eliminarea primului element din lista se poate face astfel:
void StergereInc(celula *&L, int &a)
a = k->info;
L = L->legd;
if(L != NULL) L->legd = NULL;
delete(k);
Eliminarea elementului de ordin m din lista se poate face astfel:
void StergereInt(celula *&L, int &a, int m)
if(m) cout << "Nu exista element de ordinul dat";
else
Eliminarea ultimului element din lista se poate face astfel:
void StergereSf(celula *&L, int &a)
a = k->info;
if(s != NULL) s->legd = NULL;
else L = NULL;
delete(k);
. Sa se implementeze operatiile elementare (initializare, inserare element si eliminare element) pentru o stiva reprezentata secvential.
Solutie: Stiva este data de vectorul elementelor si de pozitia vârfului stivei care indica primului loc liber din vector, aici facându-se inserarea unui element si fiind, de fapt, egal cu numarul de elemente din lista.
#define M 50 //dimensiunea maxima a vectorului
int V; //pozitia varfului stivei in vector
int x[M]; //vectorul elementelor
0 1 . V-1 V . M-1
x0 x1 . xV-1 .
Operatia de initializare presupune doar initializarea pozitiei vârfului cu valoarea 0 (prima pozitie libera din vector, care în C++ este 0).
void InitializareStiva()
V . M-1
Introducerea unui element a în stiva se face astfel: pe pozitia V se pune noul element si apoi se trece vârfului pe pozitîa urmatoare.
void InserareElem(int a)
Eliminarea unui element a din stiva consta în pozitionarea vârfului stivei pe elementul anterior si preluarea valorii lui.
void StergereElem(int &a)
. Sa se implementeze operatiile elementare (initializare, introducere element, eliminare element, afisarea elementelor stivei si stergerea tuturor celulelor) pentru o stiva cu reprezentare cu legaturi simple.
Solutie: O reprezentare grafica a implementarii dinamice a stivei este:
V → x1 x2 . xn NULL
Structura celulelor stivei este cea a listelor liniare simplu înlantuite:
struct celula *V;
unde V este vârful stivei.
Operatia de initializare se face cu functia:
Void Initializare()
Operatia de introducere a unui element a în stiva presupune crearea unei noi celule în care se pune noul element, legarea acestuia de fostul vârf al stivei si mutarea vârfului stivei pe noul elenment:
V → x1 x2 . xn NULL
k
a
void Inserare(int a)
Eliminarea unui element din stiva, adica stergerea vârfului stivei, presupune pastrarea adresei celulei din vârf într-un pointer k, mutarea vârfului stivei pe urmatorul element din stiva si eliberarea celulei de la adresa data de k, dupa ce i s-a retinut valoarea.
void Stergere(int &a)
else cout << "Stiva vida";
Afisarea elementelor stivei se face prin parcurgerea listei de la vârful spre baza:
void Listare()
}
Eliminarea celulelor din stiva se face parcurgând stiva de la vârf la baza:
void StergeStiva()
. Sa se calculeze nerecursiv valoarea functiei Manna-Pnueli pentru o valoare întreaga data a argumentului x.
Solutie: Functia Manna-Pnueli este definita în felul urmator:
De exemplu, pentru x
= 8: f(8) = f(f(10)) = f(f(f(12))) = f(f(11)) = f(f(f(13))) =
= f(f(12)) = f(11) = f(f(13))
= f (12) = 11.
Pentru calculul valorii functiei nerecursiv, se poate folosi o stiva, în care initial se pune valoarea lui x, în exemplul de mai sus 8. Daca vârful stivei este mai mic decât 12, se adauga în stiva elementul cu 2 unitati mai mare decât acesta; altfel, daca stiva are mai mult de un element se scot doua elemente din stiva; se pune în stiva elementul mai mic cu o unitate decât vechiul vârf al stivei. Procesul se termina când stiva devine vida, rezultatul calculat fiind ultimul element extras mai putin cu o unitate.
12 13
10 10 11 11 12 13
8 8 8 8 8 8 11 11 12 => f (8) = 12 - 1 =11.
Un program C++ ce rezolva problema poate fi urmatorul:
# include <iostream.h>
# include <conio.h>
struct celula
*V;
void Initializare();
void Inserare(int a);
void Stergere(int *a);
void Listare();
void main()
else
else
}
} while(1);
void Initializare()
void Inserare(int x)
void Stergere(int *a) // Se presupune stiva nevida
void Listare()
}
cout << endl;
getch();
. Sa se implementeze operatiile elementare pe o coada reprezentata înlantuit.
Solutie: Implemetarea înlantuita a cozilor se poate face folosind o lista cu header si doi pointeri: pointerul V catre header si pointerul B catre ultima celula efectiva din lista. Insearea unui nou element se face dupa celula la care se refera B (la sfârsitul cozii) si eliminarea se face la prima celula efectiva de dupa header. În acest caz structura listei este:
struct celula
*V,*B;
iar functiile de initializarea cozii, de inserare si stergere a unui element în/din coada, respectiv de stergere a cozii se pot face astfel:
void Initializare()
void Inserare(int a)
void Stergere(int &a)
void Listare()
}
void StergeCoada()
delete(V);
|
