Programare Procedurala

Universitatea "Lucian Blaga" din Sibiu Facultatea de tiine

Prof.univ.dr. Valer Roca

CAPITOLE DE PROGRAMARE PROCEDURAL

Sibiu 2008

Prof.dr.Valer Roca ULBS

1

PrefaPrezenta lucrare, intitulat Capitole de programare procedural, se adreseaz studenilor de la specializarea Informatic, de la Facultatea de tiine, Universitatea Lucian Blaga din Sibiu. Lucrarea a fost conceput ca manual n sprijinul cursului de Programare procedural, care se pred n semestrul I al anului I, studiii de licen, pentru a acoperi cteva capitole fundamentale de programare. In elaborarea lucrrii s-a avut n vedere c exist o bogat literatura de specialitate, inclusiv cri on-line, n limba romn i n limba englez, care pot s fie utilizate de studeni n studiul programrii C/C++, dar se simte nevoia, cel puin pentru o tematic de baz, s se adopte o tratare orientat, mai cu seam, spre tehnica programrii. Cele cinci capitole acoper aspectele fundamentale cu privire la programarea structurilor dinamice de date (cu referire la liste i arbori), la lucrul cu fiiere, inclusiv tratarea algoritmicii pentru probleme reprezentative, la modul n care se poate realiza prezentarea grafic a datelor (cu unele elememte de animaie), la controlul monitorului n modul consol, cu cteva elemente de programare a sunetelor, pentru a realiza o interfa atractiv a programelor i, lucrarea se ncheie, cu un capitol de faciliti pe care le ofer, n plus, limbajul C++ pentru realizarea programrii procedurale. Desigur c lucrarea presupune cunotinele de baz pentru programare n limbalul C/C++ i, prin studiul ei, studenii pot aprofunda, ntr-un numr relativ redus de pagini, prile corespunztoare din programa disciplinei menionate. Lucrarea poate fi parcurs secvenial sau prin selecie, avnd la dispoziie un cuprins sub form de linkuri interne.

Autor: Prof.univ.dr. Valer Roca Prof.dr.Valer Roca ULBS 2

CUPRINS 1. Structuri dinamice de date1.1 Pointeri1.1.1 Declararea i utilizarea pointerilor 1.1.2 Operaii asupra pointerilor 1.1.3 Echivalena indexrii i expresiei cu pointeri. Scderea pointerilor 1.1.4 Pointerii i parametrii funciilor 1.1.5 Declaraii cu pointeri i interpretarea lor

1.2 Variabile dinamice 1.3 Array-uri dinamice 1.4 Liste nlnuite i arbori1.4.1 Liste nlnuite 1.4.2 Arbori binari

1.5 Realizarea operaiilor de baz pe liste nlnuite1.5.1 Traversarea unei liste 1.5.2 Inserarea ntr-o list 1.5.3 Stergere ntr-o list 1.5.4 Distrugerea unei liste

1.6 Realizarea operaiilor de baz pe arbori binari de cutare1.6.1 Traversarea arborilor binari 1.6.2 Cutarea n arbori binari 1.6.3 Inserare n arbori binari de cutare

1.7 Realizarea programelor care utilizeaz structuri dinamice 1.8 Un exemplu de utilizare a structurilor dinamice

2. Utilizarea fiierelor2.1 Tipuri de fiiere admise 2.2 Implementarea lucrului cu fiiere2.2.1 Streamuri 2.2.2 Controlul unui stream 2.2.3 Modul de lucru cu streamul

2.3 Citire din streamuri text2.3.1 Citire la nivel de caracter 2.3.2 Citire la nivel de cmp 2.3.3 Citire la nivel de linie

2.4 Scriere n streamuri text2.4.1 Scriere la nivel de caracter 2.4.2 Scriere la nivel de cmp


3

2.4.3 Scriere la nivel de linie

2.5 Citire i scriere n streamuri binare 2.6 Controlul sfritului de fiier i poziionarea n fiier 2.7 Algoritmica lucrului cu fiiere2.7.1 Prelucrarea secvenial 2.7.2 Controlul paginilor n realizarea rapoartelor 2.7.3 Construirea fiierelor binare pentru aplicaii de eviden 2.7.4 Indexarea fiierelor 2.7.5 Prelucrare pe grupe de articole

2.8 Un exemplu de aplicaie de lucru cu fiier binar

3. Prezentarea grafic a datelor3.1 Regimul grafic al monitorului 3.2 Utilizarea modului grafic 3.3 Grafic n culori 3.4 Vizor pentru desen 3.5 Desen prin puncte i vectori 3.6 Raportul de aspect 3.7 Scrierea textelor n modul grafic 3.8 Primitive pentru figuri 3.9 Transformarea coordonatelor 3.10 Elemente de animaie3.5.1 Aspecte generale 3.5.2 Facilitii pentru animaie date de sistemul grafic

4. Controlul monitorului i al difuzorului4.1 Regimul text al monitorului 4.2 Faciliti de lucru cu texte n modul pagin4.2.1 Stabilirea unui mod text al consolei 4.2.2 Utilizarea ferestrelor de scriere

4.3 Faciliti de sunet

5. Faciliti n C++ pentru programare procedural5.1 Declararea de articole 5.2 Referine 5.3 Operatorii de alocare i de eliberare 5.4 Funcii cu argumente implicite 5.5 Suprancrcarea funciilor 5.6 Tipuri abstracte de date


4

1. Structuri dinamice de dateLimbajul C, prin mecanismul lucrului cu pointeri, ofer programatorilor faciliti deosebite pentru construirea i utilizarea variabilelor dinamice, a listelor i a arborilor.

1.1 PointeriAa dup cum s-a artat ntr-un capitol anterior, pointerii sunt variabile de adres legate de un anumit tip de dat standard sau declarat de programator. Mecanismul utilizrii pointerilor ofer o mai mare fexibilitate n folosirea memoriei, dect referirea direct prin variabile statice. Figura 1.1 sugereaz modul n care, prin utilizarea adresei dat de un pointer, se acceseaz valoarea dintr-o alt locaie de memorie. Referirea locaiei se face indirect i tehnica aceasta este denumit referire prin indirectare.

Adres

Valoare

numepointer

Fig.1.1 Referirea locaiilor prin pointeri

1.1.1 Declararea i utilizarea pointerilor Din punctul de vedere al limbajului, un pointer trebuie, mai nti, s fie declarat i apoi s fie ncrcat cu adresa locaiei, nainte de a putea fi utilizat. In secvenele care urmeaz, se utilizeaz pointeri la tipuri standard i la o structur de date. double x = 3.65, *px, z; int k = 5; struct {int *a; char t; double y;} s, *ps; px = &x; ps = &s;


5

(*ps).y = 1.2; ps->a = &k; z = *px + ps->y + *(ps->a); Se remarc modul simplu de utilizare a pointerului px, sub forma *px, pentru a referi valoarea 3.65, din locaia variabilei x. In cazul utilizrii structurilor de date, limbajul ofer forme alternative de scriere care sunt echivalente. In aceast secven, referirea la variabila y, de forma (*ps).y este echivalent cu forma ps->y. Programatorii prefer forma ultim care este mai uor de neles, mai ales atunci cnd apar indirectri n lan, aa cum este cazul cu referirea valorii la care trimite pointerul a: forma *(ps->a) este mai clar dect forma *((*ps).a). In aceste scrieri * i -> sunt considerai operatori de indirectare i, n expresii, ei se bucur de proprietatea de asociativitate la dreapta. De aceea, referirile de forma p1->(p2>->(pn-1->(pn->a))) pot fi scrise, fr paranteze sub forma p1->p2->->pn->a i devin mai clare. 1.1.2 Operaii asupra pointerilor Limbajul stabilete operaiile acceptate aupra variabilelor pointeri, avnd n vedere structura adresei de memorie ca un cuplu de forma (adres segment, deplasare n segment), aa cum este cazul modelelor de memorie cu segmente. De exemplu, o operaie de adunare ntre doi pointeri nu este corect deoarece nu produce o adres valid, adunarea prilor de adres de segment ne avnd sens. Redm, n continuare, operaiile acceptate, cu modul de scriere i semificaia acestuia. Adunarea/scderea unei constante ntregi pozitive se red prin expresia pointer k i este interpretat n raport de tipul pointerului. Adresa rezultat se determin sub forma pointer k*sizeof(tip), unde tip este tipul de care este legat pointerul. In particular, adunarea sau scderea lui k=1 nu nseamn incrementare/decrementare, ci agugarea lungimii tipului. Atenie, deci, la forma de scriere i la semificaia expresiei respective ! In secvena: double x, *px, *pz; double *py; py = NULL; px = &x; px = px + 4; pz = px; se atribuie lui px adresa x, & fiind operatorul de adres. Apoi, noua valoare a lui px este adresa lui x mrit cu 4*8 = 32 i nu cu 4, cum s-ar putea crede din forma instruciunii de atribuire. Atribuirea de valoare are semificaie pentru oricare pointer, dac aceasta este valoarea conveniona NULL, avnd semificaia de adres nul. In secvena de mai sus, py primete o astfel de valoare. Altminteri, unui pointer poate s i se atribuie numai adresa unei variabile de acelai tip sau valoarea unui pointer de acelai tip. In secvena de mai sus, x i px se refer la acelai tip double, de aceea atribuirea px = &x este corect. Din aceleai motiv, este corect i atribuirea pz = px. Compararea se poate face cu valoarea NULL pentru oricare pointer, utiliznd operatorii = i !=. Altminteri, compararea are sens numai pentru pointeri de acelai tip i n expresiile respective pot fi utilizai oricare dintre operatorii relaionali. Pentru secvena de mai sus, se pot scrie expresii relaionale de forma px != py , pz > px etc. 1.1.3 Echivalena indexrii i expresiei cu pointeri. Scderea pointerilor


6

Aa dup cum se tie, un array n C are o structur aparte, numele de variabil dat acestuia fiind considerat un pointer constant la primul element. In aceste condiii, limbajul a introdus, urmtoarea echivalen: tab[k] *(tab+k) unde tab este numele variabilei array, iar k este indice. Aplicnd regula de semificaie a expresiei cu pointeri din dreapta, rezult modul de calcul al adresei i faptul c, n ambele cazuri, este referit acelai element, dar prin forme diferite de scriere. Echivalena este valabil i pentru array-uri n-domensionale, ns expresia, fiind funcie de n indici i de dimensiunile declarate, aa cum rezult din modul de liniarizare, prezentat n capitolul referitor la acest tip de date, este mai dificil de utilizat Echivalena pune n eviden i posibilitatea de a scdea doi pointeri de acelai tip, dac, n plus, ei au i aceeai adres de segment, aa cum este cazul a doi pointeri ncrcai cu adresele unor elemente din acelai array. Dac se presupune c q=&tab[k] i p=&tab[k+n], atunci se deduce succesiv: p-q = *(tab+k+n)- *(tab+k) = *(tab+k+n-tab-k) = n. Se observ cum diferena, n acest caz, produce ca rezultat un numr natural, reprezentnd numrul de componente care se gsesc n array ntre cele dou ranguri. Trebuie semnalat aici c pointerii de tip array fiind pointeri constani, nu pot fi modificai prin operaii de adunare cu constante i nici prin atribuire, dar pot s fie supui la acele operaii care nu le afecteaz valoarea. 1.1.4 Pointerii i parametrii funciilor In multe situaii, transferul parametrilor la funcii se realizeaz prin adres, adic prin intermediul pointerilor. Dup cum se tie, o astfel de metod de transfer este obligatorie n cazurile n care funcia trebuie s modifice valoarea parametrului actual corespunztor, dar ea se utilizeaz uneori i n cazul stucturilor de date, pentru a evita multiplicarea datelor prin copiere i ncrcarea suplimentar a timpului de execuie. In aceste condiii, protecia datelor i a pointerilor mpotriva modificrilor accidentale este esenial. In scrierea funciilor care se gsesc n astfel de situaii, programatorul poate s utilizeze facilitile pe care le ofer limbajul pentru a declara date constane i pointeri constani, prin utilizarea corespunztoare a modificatoruli const. Modificatorul const poate fi plasat, ntr-o declaraie cu pointeri, n patru poziii, cu semificaia care este prezentat cu ajutorul declaraiilor care urmeaz: int* pv = 100; // pointer non-const la data non-const int* const pv = 100; // pointer const la data non-const const int* pv = 100; // pointer non-const la data const const int* const pv = 100; // pointer const la data const Dac transferul prin adres este fcut pentru structuri voluminoase, n vederea eliminrii copierilor costisitoare, parametrul actual se recomand a fi protejat declarnd parametrul formal corespunztor ca o dat constant. Declaraia trebuie s fie precedat de modificatorul const, aa cum se observ n secvena care urmeaz, unde, n funcia sum(), arrayul x este declarat constant i orice ncercare de modificare a componentelor sale va fi semnalat ca eroare de ctre compilator. double sum(const double* x, int n) { int k; double s; for(s=1, k=0; klink; free(*top); *top = p; return 0; } /* Apelul functiei */ . . . . . NOD *cap; . . . . . int r = stergenod(&cap); . . . . . In aceast secven, variabila pointer cap trebuie s se actualizeze ca urmare a tergerii nodului din vrful stivei. In acest scop, parametrul formal top este declarat pointer la pointer i trebuie s se supun regulii de indirectare discutate mai sus, pentru a accesa valoarea, aa cum se observ n instruciunile funciei. La apel, pentru variabila pointer cap, se transmite subprogramului adresa, la fel ca pentru oricare variabil obinuit. Tipul NOD, construit de programator, este un struct ce descrie structura unui element al stivei. De regul, un element are cel puin un cmp pentru informaie i o adres care puncteaz spre elementul urmtor (link). In multe cazuri, este convenabil ca o funcie s ntoarc un pointer la o variabil n care funcia a construit rezultatul, n locul rezultatului nsui. Trebuie, ns, acordat atenie validitii pointerului, dup revenirea din funcie n apelator, avnd n vedere existena variabilei pe care o desemneaz. Dup cum se tie, variabilele declarate ntr-o funcie sunt variabile locale, de clas automatic, crora li se aloc memorie pe stiva sistem n momentul intrrii n funcia respectiv i memoria ocupat de acestea este automat eliberat nainte de rentoarcerea la apelator. In aceste condiii, un pointer la o variabil local nu are sens n apelator, deoarece zona de memorie pe care o adreseaz nu mai exist. O prim modalitate de rezolvare a acesteri situaii, este aceea a schimbrii clasei de memorie pentru variabila n cauz, prin declararea ei de clas static. In acest mod, variabilei respective i se aloc spaiu n segmentul de date al programului i aceasta rmne alocat pe toat durata execuiei programului. In secvena care urmeaz, se schieaz un astfel de caz i se sugereaz modul de utilizare a rezultatului. double* func(...) {static double x; double* px = &x; . . . . . . . . return px;


9

} . . . . . . . . double* d, y, z=5.25; d = func(...); y = *d + z; . . . . . . . . O alt modalitate este aceea a construirii unei variabile dinamice n funcia respectiv, deoarece zona de memorie alocat ei este persistent, adic aceasta este accesibil, pe baz de adres i dup ntoarcerea la apelator. In secvena care urmeaz se sugereaz acest mod de rezolvare, considernd cazul de mai sus. double* func(...) {double* px; px = (double*)malloc(sizeof(double)); . . . . . . . . return px; } . . . . . . . . double* d, y, z=5.25; d = func(...); y = *d + z; . . . . . . . . In aceast secven, pointerului px i se atribuie adresa unei zone de memorie dinamic, solicitat sistemului de alocare prin funcia malloc(). Rezultatul se construiete n aceast zon i adresa ei este cea care se transmite apelatorului. Pe baza discuiei de mai sus, se pot face urmtoarele recomandri pentru transferul parametrilor i a rezultatului la funcii: pentru variabile scalare nemodificabile, transfer prin valore; pentru structuri voluminoase, transfer prin adres. Arrayul se transfer implicit prin adres; pentru variabile modificabile, indiferent de mrime, transfer prin adres; pentru rezultat ca variabil local retunare prin valoare: pentru rezultat n heap, returnare prin pointer; pentru structuri voluminoase nemodificabile, ca parametru sau ca rezultat, se declar pointer la dat constant i/sau rezultat constant aa cum se sugereaz n declaraia: const tip* func(const tip* pv); 1.1.5 Declaraii cu pointeri i interpretarea lor Utilizarea pointerilor, benefic altminteri, poate s aduc i neajunsuri, printre care semnalm dificultatea de a descifra programe surs. Un caz tipic, l constiuie interpretarea declaraiilor complexe, pentru care, n cele ce urmeaz se d, sub form de algoritm, un ndrumar. In continuare, se dau cteva exemple, succesiunea entitilor care se analizeaz fiind marcate prin numere de ordine 1. Se ncepe cu identificatorul din declaraie. 2. Se merge spre dreapta cutnd o entitate sub forma unei perechi de paranteze rotunde ( ) sau drepte [ ]. O succesiune de dou sau mai multe perechi de paranteze drepte se considerat ca o entitate unic. 3. Dac s-a selectat o entitate, se interpreteaz ca funcie, respectiv array. 4. Se schimb sensul de deplasare nspre stnga cutnd o entitate *, dat de cel mai apropiat caracter de acest fel care nu a fost nc analizat. Dac * este precedat de modificatorul const, atunci aceast sucsesiune formeaz o entitate. Se interprezeaz entitatea ca indicaie de pointer sau pointer constant i se continu cu deplasare spre stnga.


10

5. Dac n cutarea spre stnga, se ntlnete o parantez rotund deschis (, atunci entitatea care este cuprins ntre aceast parantez i perechea ei dreapta este considerat tratat i algoritmul se reia de la pasul 2. 6. Dac n cutarea spre dreapta, se ajunge la o parantez rotund nchis ), atunci algoritmul se reia de la pasul 4. 2. Dac n cutarea spre dreapta, se ajunge la sfritul declaraiei, atunci se ncheie cutarea i se interpreteaz declaraia de tip.

Exemplul 1: char* (* ( * var )(int))[10]4 2

7

6

1

3

5

1. Identificatorul var este declarat ca 2. un pointer la 3. o funcie care are un parametru ntreg i care returneaz 4. un pointer la 5. un array de 10 elemente care sunt 6. pointeri la 2. tipul char

Exemplul 2: double ( * var (double (*)[3])) [5]

5

3

1

2

4

1. Identificatorul var desemneaz o funcie care are un parametru i returneaz 2. un pointer la 3. un array cu 3 componente 4. de tip double Parametrul funciei esteun pointer la un array cu 5 componente de tipul double


11

Exemplul 3:

struct s * (* var[5])[5]6 5 1 4

3

2

1. Idetificatorul var este 2. un array cu 5 componente care sunt 3. pointeri la 4. un array cu 5 componente care sunt 5. pointeri la 6. tipul struct s

Exemplul 4: unsigned int * ( * const* var [5][10])(void)7 6 4 3 1 5

2

1. Identificatorul var este 2. o matrice cu 5 linii i 10 coloane 3. pointeri constani la 4. un pointer la 5. o funcie care nu are parametrii i returneaz 6. un pointer la 2. un ntreg fr semn Declaraiile de funcii, incluse, se analizeaz n acelai mod, depinznd de poziia lor. In exemplul care urmeaz sunt trei funcii, analiza ncepe cu funcia intermediar. De remarcat prezena parantezelor care o delimiteaz, fr care scrierea ar fi fost eronat sintactic.


12

Exemplul 5:

void ( * var (int,double(*)(int) ) )(int)5 3 1

2

4

1. Identificatorul var este 2. o funcie 1 care are doi parametri i returneaz 3. un pointer la 4. o funcie 2 cu un parametru ntreg care returneaz 5. un void Funcia 1 are un parametru ntreg i un parametru care este pointer la o funcie -3 care are un parametru intreg i returneaz un double

1.2 Variabile dinamiceLa fel ca i alte limbaje, limbajul C implementeaz posibilitatea utilizrii spaiului de memorie disponibil, denumit spaiu de memorie dinamic sau spaiu heap, potrivit unui model prestabilit pentru memoria intern. Utilizarea acestui spaiu se bazeaz pe pointeri, ca variabile prin care se pot accesa locaii de memorie, denumite blocuri. In plus fa de cazul static, blocurile de memorie pot s fie controlate - alocate i eliberate - la momentul execuiei programului, prin sistemul pe care limbajul l ofer, denumit sistem de gestiune a memoriei heap. Datorit posibilitiilor de utilizare i a posibilitilor de control, un cuplu (pointer, bloc heap) este denumit variabil dinamic. Variabilele dinamice pot fi utilizate independent sau pot fi asamblate n structuri de variabile, prin care se pot implementa structuri complexe de date, cunoscute ca structuri dinamice de date. In fig. 1.2, este redat modelul logic al memoriei interne n sistemele de operare DOS (UNIX, MS-DOS), de referin pentru implementarea sistemului de gestiune heap.


13

Spaiul heap Spaiul pentru stiva sistem Spaiul de date statice ale programului Spaiul pentru codul programului Spaiul pentru antetul programului

Fig. 1.2 Modelul logic al memoriei interne pentru un program C Sistemului de gestiune pentru heap pune la dispoziia programatorului o mulime de funcii, prin care programul poate aloca i elibera, la momentul execuiei programului, blocuri de memorie, de lungimi variabile, la care s se refere prin pointeri. Mulimea de funcii, conform standardului ANSI, conine un nucleu obligatoriu, la care o anumit implementare a limbajului poate aduga i alte funcii. In acest capitol, se face referire numai la sistemul de gestiune heap recomandat de standard, pentru a asigura construirea de programe portabile. Prototipurile funciilor sistemului de gestiune a memorie heap, la fel ca n cazul altor biblioteci, sunt declarate n fiierul header alloc.h care trebuie s fie inclus n programul surs, atunci cnd se face uz de acest spaiu. Alocarea de blocuri de memorie presupune apelul uneia din funciile de alocare/realocare urmtoare: void * malloc(size_t blocksize); void * calloc(size_t nitem, size_t blockitemsize); void * realloc(void* pblock, size_t blocksize); In aceste prototipuri, size_t este tipul intreg, ntlnit i la alte funcii, definit n mai multe fiiere header, printre care i fiierul alloc.h. Acest tip permite declararea unor ntregi foarte mari, ntregi care ar putea fi necesari n exprimarea unor cereri de blocuri, avnd n vedere c lungimile acestora se exprim n bytes. Lungimea blocului cerut este dat prin parametrul blocksize, n cazul funciei malloc() sau este produsul dintre numrul de elemente nitem i lungimea unui element, n cazul funciei calloc(). Ultima funcie este utilizat, mai ales, n legtur cu alocarea spaiului pentru array-uri cu numr variabil de componente (array dinamic). Ambele funcii de alocare ntorc adresa blocului, ca pointer nelegat de un tip de dat, pointer void, care poate fi NULL, dac spaiul heap liber nu are disponibil un bloc de mrimea cerut. In acest mod, programatorul poate controla, testnd valoarea pointerului, dac alocarea s-a realizat sau nu i poate decide n consecin. Trebuie, de asemenea, remarcat faptul c programatorul trebuie s rein adresa returnat de alocator, ntr-o variabil pointer, legat de tipul de date pe care urmeaz s-l conin blocul, pentru utilizare ulterioar. Rezult, de aici, necesitatea de a converti, prin cast, pointerul void la tipul dorit, ceea ce, poate nsemna utilizarea unei alocri de forma:


14

tip * pblock; if(pblock = (tip*)functiealocare(parametri)) {/* Spatiu alocat. Utilizare pointer pblock */} else { /* Rezolvare situatie de lipsa de spatiu */ } In textul care urmeaz, se aloc spaiu pentru un real dublu, pentru un articol, care urmeaz a fi utilizat ca nod al unei liste, i pentru un array intreg cu n componente, utiliznd o secven fr testare de reuit: #include #include void main() {......................... /* Definiri de tipuri si de variabile */ double* predab; typedef struct art {char info[50]; art* next; } NOD; NOD* cap; int* arrayint; .......................... /* Alocare de blocuri */ predab = (double*)malloc(sizeof(double)); cap = (NOD*)malloc(sizeof(NOD)); n = 80; arrayint = (int*)calloc(n, sizeof(int)); .......................... /* Utilizarea blocurilor alocate */ *predab = -5.75L; strcpy(cap->info, " "); cap->next = NULL; for(int k = 0; k < n; k++) arrayint[k] = 0; } Aa cum rezult din text, se recomand ca lungimea blocului sau a elementului de bloc, n funciile de alocare, s se indice prin operatorul sizeof(), pentru a evita specificarea eronat a lungimii. Se remarc, de asemenea, modul de conversie i utilizare, avnd n vedere tipurile blocurilor i a cmpurilor pe care acestea le conin. Funcia realloc() este utilizat n cazul n care un bloc alocat anterior trebuie s fie reajustat ca mrime, potrivit parametrului blocksize specificat. Funcia ntoarce pointer nul, dac nu este posibil realocarea. Dac se utilizeaz valoarea NULL, ca parametru pentru pointerul la bloc, atunci aceast funcie este echivalent cu malloc(). Noul bloc poate fi obinut prin prelungirea vechiului bloc sau poate fi alocat pe un spaiu nou. In ambele cazuri, coninutul blocului este conservat pn la minimum ditre cele dou lungimi. Eliberarea blocurilor alocate se realizeaz prin funcia free() care are un prototip simplu: void free(void* pblock); Pentru exemplele de mai sus, eliberarea se face sub forma: free(predab); free(cap); free(arrayint);


15

In ncheierea acesui paragraf, se face precizarea c implementrile limbajului C utilizeaz, n general o metod de gestiune a spaiului heap, denumit garbage collection (colectarea rezidurilor). Potrivit acestei metode, evidena spaiului liber i ocupat se ine pe mai multe liste, cu blocuri de mrimi diferite. Alocarea unui bloc, nseamn scoaterea lui din lista de spaiu disponibil i trecerea lui ntr-o list de spaiu ocupat. Atunci cnd programul cere o eliberare de bloc, blocul respectiv este, de regul marcat ca disponibil, fr s fie returnat unei liste de spaiu liber. La anumite intervale de timp, sistemul de gestiune declaneaz procesul de eliberare proriu-zis, comasnd blocuri adiacente, marcate ca disponibile, pentru a construi blocuri libere de lungime ct mai mare, pe care le evideniaz n liste corespunztoare. Acest proces se aplic i atunci cnd, la o cerere de alocare, nici una din listele de spaiu liber nu poate oferi un astfel de bloc. Alocarea eueaz, dac, i dup colectare (de reziduri), cererea nu poate fi satisfcut. Prin acest sistem, se asigur o funcionare, ct mai ndelungat posibil, a programelor care utilizeaz memoria heap fr a a ncrca exagerat timpul de execuie al programului cu timp necesar procesului de gestiune a acestui spaiu. In fine, menionm c n C++, au fost introdui operatorii (new, dispose), pentru a facilita utilizarea spaiului heap, legat, mai ales, de tehnica programrii orientate pe obiecte, care sunt prezentai n lucrare, n capitolul de faciliti ale acestui limbaj.

1.3 Array-uri dinamiceAa dup cum se cunoate, n limbaj exist posibilitatea declarrii i referirii, prin indexare, a array-urilor uni i multidimensionale. Acestea sunt variabile de clas automatic al cror spaiu de memorie le este atribuit n segmentul de date al programului sau pe stiva sistem, la dimensiunile maxime declarate i acest spaiu, n timpul execuiei programului, nu mai poate fi ajustat (mrit sau micorat) i nici nu poate fi eliberat, atunci cnd rolul acelui array a ncetat. In programele mari, n condiiile n care determinarea spaiului maxim necesar pentru astfel de structuri este dificil, utilizarea eficient a memoriei trebuie s fie o preocupare a programatorului. O soluie posibil este aceea a construirii de structuri array n memoria heap care s poat fi dinamic ajustate dimensional i s poat fi eliberate n timpul execuiei programului. Structurile array construite n heap poart denumirea de array dinamic. Acestea pstreaz proprietatea de spaiu compact, dar pierd, cu excepia celor unidimensionale, posibilitatea referirii directe prin indexare. Pentru array-urile unidimensionale, pe baza echivalenei ntre expresia de indexare, cu un indice, i expresia de indirectare asociat, aa cum s-a artat mai nainte n acest capitol, exist posibilitatea utilizarii alternative a celor dou modaliti. O prim abordare este aceea a construirii unui array cu spaiu la dimensiuni efective, care, n timpul execuiei programului nu mai trebuie ajustat dimensional, denumit array dinamic neajustabil. Formal, un asfel de array este un tuplu de forma (n, psp, bloc), unde n este numrul efectiv (maxim) de elemente, iar psp este pointerul la blocul de spaiu din heap. Dup cum se observ, un astfel de array este o variabil dinamic i utilizarea lui revine la realizarea urmtoarei secvene de aciuni: - declararea unui pointer la tipul de dat pe care urmeaz s l conin elementele: tip* psp; - preluarea spaiului din heap: psp = (tip*)malloc(n*sizeof(tip)); - utilizarea elementelor, fie prin indexare psp[k] , fie prin indirectare *(psp +k), unde k este poziia( rangul) elementului, n convenia de referire cu indice ntreg, cu valori ncepnd zero. Controlul ncadrrii n blocul de spaiu se realizeaz prin raportarea la valoarea n-1 sau la adresa (psp + n-1), ca adres a ultimului element ; - eliberarea spaiului, atunci cnd array-ul nu mai este necesar: free(psp);


16

In listingul 1.1, utiliznd un array dinamic neajustabil, funcia main() introduce un ir de n date ntregi, utiliznd adresarea cu indexare i le nsumeaz, folosind referirea prin indirectare. Listingul 1.1 Utilizarea unui array dinamic neajustabil #include #include void main() {int n, k, s; int *psp, *p; printf(" Numarul de componente: "); scanf("%d", &n); psp = (int*)malloc(n*sizeof(int)); printf("Componentele: "); for(k=0; k < n; k++) scanf("%d", &psp[k]); s = 0; for(p = psp; p < (psp + (n-1)*sizeof(int)); p++) s = s + (*p); printf("Suma este %d ", s); } Cazul general este cel al unui array dinamic ajustabil. Un astfel de array este un tuplu de forma (nelem, pozelem, psp, bloc), unde nelem este numrul maxim de elemente care pot fi nserate n array la dimensiunea curent a blocului de memorie alocat, iar pozelem d rangul ultimului element efectiv ncrcat. Iniial, este necesar ca aceste variabile s aib valorile: nelem = 0; pozelem = -1; psp = NULL; Lucrul cu un astfel de array este ceva mai complicat, deoarece operaiile de inserare a unui elemente n array pot cere o cretere a spaiului pe care acesta l posed la un anumit moment, inclusiv momentul iniial, cnd un asfel de spaiu nu exist. De aceea, pentru un asfel de array este necesar s se construiasc funcii care s poat realiza nserri, cu realocare de spaiu, precum i alte operaii, cum ar fi preluarea elementului de un anumit rang, cu controlul ncadrrii n limita numrului de elemente efectiv prezente n array. In cele ce urmeaz, se sugereaz o list de astfel de funcii care ar putea asigura o funcionalitate ct mai complet: - funie pentru nserarea unui element la sfrit, dup ultimul element efectiv prezent; - funcie pentru nserarea unui element pe o poziie interioar k, cu deplasarea spre dreapta a elementelor pentru a face loc; - funcie de nlocuire a valorii unui element de rang k; - funcie de preluare a valorii ultimului element; - funcie de preluare a valorii elementuli de rang k; - funcie de ncrcare de array prin citire de la consol; - funci de afiare de array pe monitor, - funcie de sortare de array etc. In continuare, cu titlu de exemplu, n listingul 1.2 este redat o funcie de nserare a unui element pe poziia k i una de preluare a valorii elementului de rang k. Aici s-a fcut ipoteza, care va fi discutat mai n detaliu ntr-un paragraf urmtor, c tuplu care definete un


17

array dinamic ajustabil se definete ca un tip de dat struct, pentru date de tip double, de forma: typedef struct {int nelem; int pozelem; double *psp; } DINARRAY; In aceste condiii, programul apelator declar variabile de tip DINARRAY, atunci cnd dorete o astfel de structuri, le iniializeaz cum s-a artat mai sus i transfer funciilor de lucru cu array pointeri de acest tip. De exemplu, aceste aciuni, cu apelul funciei de nserare, sunt sugerate de secvena de instruciuni care urmeaz: DINARRAY vectdin, *pvect; vectdin.nelem = 0; vectdin.pozelem = -1; vectdin.psp = NULL; pvect = &vectdin; . . . . . . . . . . . . . . . . . . . . int err = setitemat(pvect, 5, -200.75); Listingul 1.2 Funcia de nserare i funcia de preluare pentru un array dinamic ajustabil /* Functia de inserare a unui element pe pozitia k */ int setitemat(DINARRAY* pa, int k, double x) {double *r; if(kpa->pozelem) return 2; if(pa->pozelem +1 > pa->nelem) {r = (double*)realloc(pa->psp, (pa->nelem +50)*sizeof(double)); if(!r) return 1; pa->psp = r; pa->nelem += 50; } for(int i= pa->pozelem + 1; i > k; i--) p[i]=p[i-1]; pa->psp[k] = x; pa->pozelem++; return 0; } /* Functia de preluare a valorii elementului de rang k */ int getitemat(DINARRAY* pa, int k, double *x) {if(kpa->pozelem) return 2; *x = pa->psp[k]; return 0; } Se observ c funcia de nserare verific, mai nti, corectitudinea indicelui k i dac acesta este n afara limitelor, returneaz codul 2. Cnd nserarea este corect definit, se verific dac mai este spaiu pentru a putea deplasa spre dreapta elementele. Dac blocul nu are cel puin un element neocupat, se face o realocare, cu suplimentare a blocului cu 50 de elemente. Dac realocarea eueaz, funcia returneaz codul 1, pentru a arta c inserarea nu s-a putut realiza, din lips de spaiu. Dac blocul a fost realocat, se rencarc corespunztor pointerul la spaiu, deoarece blocul ar fi putut s fie alocat pe alt amplasament i se modific numrul maxim de elemente posibile, n noile condiii. Apoi, se face deplasarea, din poziia k, spre dreapta cu o poziie, se nscrie, n poziia k, valoarea x, se actualizeaz


18

informaia cu privire la poziia ultimului element prezent i funcia returneaz codul 0, pentru a marca reuita. Funcia de preluare a elementului de rang k, verific indicile k. Dac acesta ete incorect, operaia de preluare eueaz, funcia ntoarce codul 2 i valoarea lui x este nedeterminat. Dac preluarea reuete, funcia returneaz codul 0 i x conine valoare corect.

1.4 Liste nlnuite i arboriFrecvent, n programele scrise n C, sunt necesare liste nlnuite i arbori binari, ca structuri dinamice de date care s faciliteze rezolvarea diferitelor clase de probleme. Cu scopul de a fixa elementele necesare nelegerii mecanismelor de implementare n limbaj, n acest paragraf, se face o scurt trecere n revist a acestor tipuri de structuri. 1.4.1 Liste nlnuite Listele de date sunt compuse din articole, denumite noduri, dispuse ntr-o anumit ordine. In fiecare nod, rezid informaia propriu-zis, la care se adaug o informaie special, care s materializeze legtura nodului respectiv cu vecinii si. Aceasta nseamn c lista de date trebuie s se construiasc ntr-un spaiu adresabil, de exemplu heap, informaia de legtur fiind adresa (adresele) blocului (blocurilor) vecinului (vecinilor). Dac se noteaz cu P = {p1, p2, , pn} mulimea adreselor din spaiul de construcie, la care se adaug valoarea NULL, pentru a desemna adresa vid i se noteaz cu D = {d1, d2,, dn} mulimea informaiilor care vor fi coninute de de nodurile listei, atunci se pot defini formal listele simplu i dublu nlnuite, dup cum urmeaz. O list simplu nlnuit sau list asimetric este cuplu (cap, La) unde La este mulimea { (di, pi) | di D, pi P }, pe care s-a definit o relaie de ordine, cu cap = p0, ca adres a blocului care conine perechea (d1, p1), cu pi, 1 i n-1 ca adres a blocului care conine perechea (di+1, pi+1) i cu pn = NULL, pentru perechea (dn, pn). O list dublu nlnuit sau list simetric este tripletul (prim, Ls, ultim), unde Ls este mulimea { (pi, di, si) | di D, pi, si P }, pe care s-a definit o relaie de ordine direct, cu Prim = p0, ca adres a blocului care conine tuplul (p1, d1, s1), cu pi, 1 i n-1 ca adres a blocului care conine tuplul (pi+1, di+1, si+1) i cu pn = NULL, pentru (pn, dn, sn) i o relaie de ordine invers, cu ultim = pn+1, ca adres a blocului care conine tuplul (pn, dn, sn), cu si, unde n i 2, ca adres ablocului (pi-1, di-1, si-1) i cu s1 = NULL. Convenind s se figureze nodurile prin dreptunghiuri i legturile prin sgei, cu valoarea NULL ca legare la pmnt, cele dou tipuri de liste se pot reprezenta grafic aa cum se arat n fig.1.3.


19

d1 cap

d2

dn-1

dn

d1

d1

d1

d1

prim Fig.1.3 Liste nlnuite

ultim

Figura sugereaz c nodurile unei liste simplu nlnuite pot fi "vizitate" numai ntr-un singur sens, de la nodul de pointer cap spre nodul cu legtur la pmnt (ultimul nod), deoarece, pentru fiecare nod se cunoate numai succesorul su imediat. O adtfel de list, prin convenie, este vid, adic nu are nici un nod, atunci cnd pointerul cap = NULL. Similar, pentru o list dublu nlnuit, vizitarea se poate face de la nodul dat de pointerul prim spre nodul ultim, dar i invers, de la nodul dat de pointerul ultim spre primul nod, deoarece fiecare nod interior are legtur spre succesorul imediat, n ordine direct i spre predecesorul imediat, n ordine invers. Dac lista dublu nlnuit este vid, atunci prim = ultim =NULL. Listele cresc dinamic, plecnd de la situaia de list vid, adugnd mereu cte un nod i se micoreasz dinamic, tergnd cte un nod. Cele dou operaii tipice, denumite adugare/tergere sau nserare/tergere, fac ca, n timpul execuiei programului respectiv, structura i numrul de noduri ale listei s sufere o permanent schimbare. Astfel, o list poate trece de mai multe ori ntre situaia de list vid i nevid, n general, pe alt amplasament, datorit faptului c, la nserare se solicit un nou bloc, iar la tergere se elibereaz cte un bloc, care, pn la o nou nserare, poate fi ocupat de alt structur. Dup locul unde se fac cele dou operaii tipice, se disting stivele i cozile, ca liste particulare, deosebit de utile n programare. Stiva nlniut (stack) este o list asimetric la care operaia de nserare i operaia de tergere se fac numai la primul nod (nodul de cap), care, n acest caz este denumit vrful stivei sau top. Datorit acestui comportament sau disciplin de lucru, bine sugerat de modul n care se gareaz i se scot vagoanele ntr-o linie nchis la un capt, stivele se mai numesc liste LIFO (Last-In-First-Out = ultimulintratprimul-ieit). La o stiv, de regul se viziteaz numai nodul top, dar nu este exclus vizitarea i a altor noduri, caz n care vizitarea presupune o operaie de traversare a stivei, total sau parial. Datorit acestui comportament, stiva este o structur frecvent utilizat n diferite probleme care presupun o atare disciplin n lucrul cu datele. Coada nlnuit (queue) este o list asimetric la care operaia de nserare se face la captul dat de pointerul ultim, iar operaia de tergere se face la captul dat de pointerul prim. Coada este denumit list FIFO (First-In-First-Out=primul-intratprimul-ieit), deoarece materializeaz comportamentul obinuit pentru tratarea cozilor cotidiene: cozi de persoane, cozi de automobile etc. Prin analogie cu aceste cozi, captul la care se face tergerea este denumit faa cozii, operaia de tergere este denumit servire, iar pointerul spre acest nod este notat fata. Similar, nodul dup care se poate face o nserare


20

este este denumit spatele cozii i pointerul se noteaz spate. Tratarea corect a unei cozi presupune totdeauna doi pointeri, pentru oricare din operaiile care modific coada i este suficent cunoaterea unui singur pointer, pointerul de fa, n cazul unei operaii de traversare. 1.4.2 Arbori binari Pstrnd notaiile introduse n paragraful anterior, se poate defini formal un arbore binar sau arbore de ordinul doi, utiliznd o schem recursiv. Un arbore binar este cuplul (cap, A2), unde A2 este o mulime de forma { (pi, di, si) | di D, pi, si P } care ndeplinete urmtoarele condiii: 1) exist unic nodul de adres p0 care conine tripletul (p1, d1, s1), numit nod rdcina al arborelui i cap = p0; 2) diferena A2 {( p1, d1, s1)} se descompune n mulimile A21 i A22, cu A21 A22 = ; 3) dac A21 = , atunci p1=NULL, iar dac A21 , atunci exist unic (pk, dk, sk) n A21 astfel nct p1 s fie adresa blocului acestui element, numit succesor stnga al lui ( p1, d1, s1) ; 4) dac A22 = , atunci s1=NULL, iar dac A22 , atunci exist unic (pr, dr, sr) n A22 astfel nct s1 s fie adresa blocului acestui element, numit succesor dreapta al lui ( p1, d1, s1) ; 5) A21 i A22 sunt arbori binari. Dac se reprezint nodurile arborelui binar la fel ca la liste, se poate obine o imagine de forma celei din fig.1.4, situaia de arbore vid fiind marcat convenional prin valoarea NULL a pointerului cap. Se observ c, ntr-un arbore binar, fiecare nod are cel mult doi succesori direci, iar structura de noduri care deriv din acesta poate fi considerat un arbore, numit subarbore, a crui rdcin este nodul considerat. Nodurile arborelui binar care nu au succesori direci sunt denumite frunze. De asemenea, trebuie remarcat faptul c n tehnica lucrului cu abori binari se utilizeaz adesea o terminologie mprumutat din structurile de tip arbore genealogic. Astfel, se vorbete de nod tat i copii si, pentru a desemna un nod i succesorii si direci, noduri frai i noduri veri, descendeni i ascendeni etc. La fel ca la liste, operaiile la arbori se refer la nserarea i tergerea de noduri care fac ca un arbore s creasc sau s descreasc dinamic, dar, din punctul de vedere al realizrii, acestea sunt mai complicate. Ambele operaii solicit o operaie de traversare parial, pentru a depista nodul dup care trebuie fcut nserarea sau nodul care trebuie ters, operaie care, de regul se bazeaz, pentru identificare, pe informaia coninut n noduri. Aceast categorie de arbori binari, pentru care structura este dat prin relaia care exist ntre informaiile distincte pe care nodurile le conin sunt denumii arbori binari de cutare. In continuare, pentru exemplificarea modului de implementare, se consider, n detaliu, numai aceast categorie.


21

cap d1

d2

d3

d4

d5

d6

d7 Fig.1.4 Arbore binar

Dac se noteaz cu info partea din structura unui nod care conine informaia, cu llink cmpul de legtur spre succesorul stnga, iar cu rlink cmpul de legtur spre succesorul dreapta, atunci un arbore binar este arbore de cutare dac, pentru oricare nod de adres p, diferit de o frunz, sunt adevrate urmtoarele relaii de dominare: p->info > p->llink->info; p->info < p->rlink->info. Relaiile de mai sus trebuie interpretate astfel: oricare nod i domin subarborele stnga i este dominat de subarborele su dreapta. In fig.1.5 este reprezentat un exemplu de astfel de arbore, n care, pentru simplitate, informaia, de tip caracter, este nscris n cerculee, iar legturile sunt redate prin sgei.


22

f

d

h

b

e

g

i

a

c

Fig.1.5 Arbore binar de cutare

Dac un astfel de arbore este traversat n ntregime, adic se viziteaz, ntr-o anumit ordine, fiecare nod, se poate obine o list liniarizat a informaiilor coninute n arbore. Traversarea complet a unui arbore binar, inclusiv a arborilor binari de cutare, se poate face n mai multe moduri, dup ordinea n care se selecteaz sucesorii direci, n raport cu momentul selectrii nodului respectiv ca rddcin de subarbore. Teoretic, este comod s se defineasc traversarea n mod recursiv, pe baza subarborelui stnga S, a subarborelui dreapta D i a rdcinii R a acestuia, astfel: traversare n preordine (RSD) pentru fiecare subarbore se viziteaz rdcina R, se traverseaz n preordine subarborele stnga S i apoi se traverseaz n preordine subarborele dreapta D; traversare n ordine simetric (SRD) pentru fiecare subarbore se traverseaz n ordine simetric subarborele stnga S, se viziteaz rdcina R, i apoi se traverseaz n ordine simetric subarborele dreapta D; traversare n postordine (SDR) pentru fiecare subarbore se traverseaz n postordine subarborele stnga S, se traverseaz n postordine subarborele dreapta D i apoi se viziteaz rdcina R. Pentru exemplul din fig.1.5 se obin urmtoarele liste liniare: f, d, b, a, c, e, h, g, i pentru preordine (RSD); a, b, c, d, e, f, g, h, i pentru ordine simetric (SRD); a, c, b, e, d, g, i, h, f pentru postordine (SDR). Se obsrv c lista care se obine printr-o traversare n ordine simetric este o list sortat, de aceea un arbore de cutare traversat complet, n aceast ordine, poate reprezenta o metod de sortare, denumit sortare pe arbore binar.

1.5 Realizarea operaiilor de baz pe liste nlnuiteAsupra listelor se pot realiza diferite operaii, dar, n cele ce urmeaz, prezentarea se limiteaz la operaiile de traversare, nserare i tergere, pentru care este recomandabil i comod s se construiasc funcii cu parametri.


23

Oricare program care trebuie s implementeze astfel de operaii trebuie s defineasc un tip de dat pentru nodul listei. In modul cel mai simplu, tipul NOD este un articol n care, pentru simplitate, informaia este considerat ca string. Pentru o list simplu nlnuit, tipul poate fi definit astfel: #define n 50 typedef char informatie[n]; typedef struct art {informatie info; struct art* succesor; }NOD; Depinznd de situaie, definiia se poate adapta pentru liste dublu nlnuite i diferite tipuri de informaie, inclusiv pentru cazul n care informaia este un alt articol sau un array dinamic. In ultimul caz, blocul de informaie fiind variabil, nodul trebuie s conin un pointer spre spaiul heap al blocului. 1.5.1 Traversarea unei liste Operaia de taversare este o operaie de vizitare a nodurilor listei, n ordinea specific acesteia. Aceasta se poate realiza, printr-o funcie, numit funcie de traversare, ca o traversare total sau poate fi o traversare parial de cutare. Traversarea total presupune vizitarea tuturor nodurilor, de la captul ales, pn la sfritul listei, fr ieire din funcia de traversare. Cu fiecare nod localizat, se pot executa prelucrri general valabile, pentru toate nodurile, i/sau prelucrri specifice, condiionate, de informaia coninut de noduri. Prelucrrile care se fac asupra unui nod constituie operaia de tratare de nod. Dac este necesar, n raport de informaia coninut n nod, nodurile care sunt supuse operaiei de tratare pot fi alese, operaia de traversare, n acest caz, fiind denumit traversare total cu selecie. In listingul 1.3 este redat, pentru exemplificare, structura unei funcii de traversare total cu selecie, pentru o list sumplu nlnuit, n care operaia de tratare s-a presupus c este realizat de o alt funcie, denumit tratare(). Listingul 1.3 Structura general a funciei de traversare a unei liste sumplu nlnuit cu selecie int traversare(NOD* inceput, char * infsel) {NOD* p; /* Rezolvarea situatiei de lista vida */ if(!inceput) return 1; /* Traversarea listei nevide */ p = inceput; do {if(conditie-de-selectie) tratare(p); p = p->succesor; } while (p); return 0; } In structura funcie de traversare, trebuie remarcat, n primul rnd, lista de parametri. Parametrul, denumit inceput este un pointer spre nodul cu care se ncepe traversarea, de regul, nodul de nceput - dat de pointerul cap al listei. Inceputul traversrii poate fi i un alt nod, atunci cnd este necesar o traversare total a unei subliste terminal a acesteia. Parametrul pointer primit aici este un parametru prin valoare i este conservat de funcia de


24

traversare din motive de semantic, mai ales dac acesta este pointerul de cap i, n consecin, este introdus un pointer de lucru p, numit pointer de traversare. Parametrul infsel este destinat primirii informaiei de selecie, adic a informaiei cu care se stabilete, prin expresia denumit conditie-de-selectie, dac nodul curent va fi tratat sau nu. Condiia de selectie este specific, dar aici s-a meinut presupunerea c informaia din noduri este un text i, prin urmare, parametrul trebuie s fie un pointer la char. In al doilea rnd, trebuie observat modul n care este conceput codul funciei de traversare, din punctul de vedere al asigurrii caracterului general al acestei funcii i anume tratarea strii listei. Aici, funcia distinge cele dou cazuri, prin rezultatul ntreg pe care l returneaz apelatorului: valoarea 1, pentru situaia de list vid i valoarea 0, dac lista este nevid, avnd cel puin un nod i a fost traversat. In al treile rnd, se remarc bucla de ciclare do, pentru controlul traversrii, cnd lista este nevid. Nodul curent, accesat prin pointerul de traversare p, este livrat sau nu funciei tratare(), n raport de valoarea de adevr a condiiei de selectie. Apoi, indiferent de caz, se trece la un alt nod, prin linia de avans p = p->succesor care obine adresa nodului succesor sau valoarea NULL, dac lista s-a terminat. Funcia de tratare, prin pointerul p primit, i acceseaz informaiile din nod i realizeaz tratamentul adecvat. Dac, n listingul 1.3, se renun la selecie, se obine o funcie de traversare total normal, eventual de la ultimul nod spre nceput, dac lista este dublu nlnuit i se nlocuiete legtura succesor cu legtura predecesor. Traversarea parial este, de regul, conceput ca o traversare de cutare i presupune vizitarea n ordine a nodurilor, de la captul ales, spre sfritul listei, pentru a localiza un nod care ndeplinete o condiie dat, n raport cu informaia coninut. Traversarea listei se termin cu succes, atunci cnd s-a localizat un astfel de nod (primul, dac pot exista mai multe noduri care ndeplinesc codiia impus) sau fr succes (insucces), dac un astfel de nod nu exist i a fost atins sfritul listei. In listingul 1.4, este redat, pentru exemplificare, structura unei funcii de cutare, pe o list simplu nlnuit, n ipoteza c informaia din noduri este de tip text. Funcia returneaz apelatorului o adres sau pointer, prin care l informeaz asupra situaiei ntlnite, pe baza urmtoarei convenii: - rezultat = NULL lista vid sau insucces; - rezultat NULL succes i rezutatul este adresa nodului gsit. Listingul 1.4 Structura general a funciei de traversare pentru cutare pe o list simplu nlnuit NOD* cutare(NOD* inceput, char * infsel) {NOD *p, *s; s = NULL; p = inceput; /* Rezolvarea situatiei de lista vida */ if(!inceput) return s; /* Traversarea listei nevide */ do {if(conditie-de-cautare) {s = p; break; } else p = p->succesor; } while (p); return s; }


25

Parametrii au aceeasi semificaie ca la procedura anterioar, iar conditie-decautare este expresia pe care trebuie s o ndeplineasc informaia din nodul curent, n raport cu informaia dat de parametrul infsel. Rezultatul cutrii se pregtete prin pointerul ajuttor s care, atunci cnd lista este nevid, n bucla do, rmne pe valoarea NULL, dac nu exist un nod care s satisfac cerina impus sau primete valoarea pointerului p, numit pointer de traversare, dac nodul curent este cel corespunztor. Traversarea parial cu pointer de urmrire este o variant a traversrii de cutare, necesar, de multe ori, n lucrul cu listele simplu nlnuite cnd intereseaz nu numai adresa nodului care ndeplinete criteriul de cutare ci i adresa predecesorului imediat al acestuia. Aa, de exemplu este cazul tergerii unui nod, cnd refacerea legturilor nu este posibil, dac nu se posed i adresa predecesoruuli nodului care se terge. In acest tip de traversare, fa cazul anterior, funcia de cutare trebuie s prevad nc un parametru, de tip pointer la pointer la nod, prin care s se returneze adresa predecesorului. In listingul 1.5, este redat structura funciei de traversare cu urmrire, unde acest pointer, denumit pointer de urmrire, este parametrul r, declarat sub forma NOD** r. In listingul model, s-au utilizat urmtoarele convenii, cu privire la valorile pointerilor: - rezultat NULL, r = NULL lista vid; - rezultat NULL, r NULL insucces, r conine adresa ultimului nod a listei; - rezultat NULL, r = NULL succes, rezultatul este adresa primului nod al listei i acesta ndeplinete criteriul de cutare, nu exist predecesor; - rezultat NULL, r NULL succes, rezultatul este adresa nodului care ndeplinete criteriul de cutare, iar r conine adresa predecesorului su. Listingul 1.5 Structura general a funciei de traversare pentru cutare, cu pointer de urmrire, pe o list simplu nlnuit NOD* traversarecuurmarire(NOD* inceput, char * infsel, NOD** r) {NOD *p, *s, *pr; s = pr = NULL; p = inceput; /* Rezolvarea situatiei de lista vida */ if(!p) return s; /* Verificarea primului nod */ if(conditie-de-cautare) {s = p; *r =pr; return s; } /* Traversarea listei care are cel putin doua noduri */ pr = p; p = p -> succesor; do {if(conditie-de-cautare) {s = p; break; } else {pr = p; p = p->succesor; } } while (p); *r = pr; return s;


26

} In funciile de cutare, conditie-de-cautare este o expresie care trebuie scris pentru nodul curent, adic n raport de pointerul de traversare p. In ipotezele fcute aici, trebuie utilizat funcia de comparare de iruri de caractere i aceast condiie se scrie sub forma: strcmp(p->info, infsel) 0; unde operatorul relaional se nlociuete cu unul din operatorii ==, , depinznd de cerina pe care trebuie s o indeplineasc informaia din nod fa de informaia de selecie: - informaia din nod == informaia de selecie; - informaia din nod < informaia de selecie; - informaia din nod > informaia de selecie; Trebuie acordat atenie apelului unei astfel de funcii care, pe poziia parametrului r, trebuie s transfere o adres unei variabile pointer, aa cu sugereaz secvena urmtoare: NOD *inceput, *p, *r; ....... p = traversarecuurmarire(inceput, "textde informatie", &r); 1.5.2 Inserarea ntr-o list Inserarea unui nod nou se poate realiza la unul din capetele listei sau n interiorul listei, dup sau naintea unui nod dat. Pentru ndeplinirea unei astfel de sarcini, pentru fiecare caz, se recomand construirea unei funcii, numit funcie de nserare. O astfel de funcie trebuie s cunoasc pointerul sau pointerii care definesc lista, informaia care trebuie s fie pus n nod i, adresa nodului referin, dac nserarea nu se face la un capt. De regul, apelatorul are sarcina s posede informaiile cerute de funcia de nserare, iar, dac este necesar apelatorul va realiza traversarea prealabil a listei, cu cutare, pentru a construi unele din aceste informaii. Funcia de nserare trebuie s actualizeze pointerii caracteristici ai listei, dac nserarea i afecteaz, i s realizeze corect nserarea i n situai n care lista este vid. La nserare, n general, trebuie avut n vedere situaia n care se modific pointerii caracteristici. De aceea, toi pointerii care vor suferii modificri n funcia de nserare, modificri care trebuie s se regseasc ca atare n apelator, trebuie s fie declarai de tipul pointer la pointer la nod. Corespunztor, la apel, argumentele trebuie s fie adrese de variabile pointeri. Inserarea n capul listei este specific stivelor nlnuite, dar poate fi aplicat i la o list oarecare. Din punct de vedere algoritmic, nu ridic probleme deosebite, aa cum se poate deduce din listingul 1.6, n care se construiete un model de funcie pentru o list simplu nlnuit, cu informaie de tip text. Grafic, nserarea n fa se ilustreaz ca n fig.1.6 a. Listingul 1.6 Structura general a funciei de nserare n capul unei liste simplu nlnuit int inserareinceput(NOD** inceput, char * infnod) {NOD *p; /* Alocare si pregatire nod */ p = (NOD*)malloc(sizeof(NOD)); if(!p) return 1; strcpy(p->info, infnod); p->succesor = NULL; /* Legarea nodului nou, cu actualizarea pointerului de inceput*/ if(!*inceput) *inceput = p; /* Lista a fost vida */ else { p->succesor = *inceput;


27

*inceput = p; }; return 0; }

/* Lista a avut cel putin un nod */

In acest listing, parametrul infnod aduce informaia de pus n nod care, dup alocarea de spaiu - adresa n p - se copiaz n nod, legtura acestuia spre succesor fiind iniializat NULL. Dac lista este vid, atunci acest nod devine cap al listei i pointerul inceput devine egal cu p. Dac lista are cel puin un nod, atunci nodul nou p, trebuie s puncteze spre nodul dat de pointerul inceput i acest pointer se actualizeaz cu adresa lui p, pentru a arta noul cap al listei. De remarcat faptul c funcia testeaz situaia de lips de spaiu i ntoarce, ca rezultat, valoarea 1 (adevrat), pentru a marca lipsa de spaiu i valoarea 0, dac alocarea a reuit. Dac lista este dublu nlnuit, atunci funcia de nserarea are doi pointeri caracteristici (inceput i sfarsit) care trebuie s figureze n lista de parametri. Funcia trebuie s iniializeze la NULL ambele legturi ale nodului nou i s fac legarea acestuia sub forma: /* Lista a fost vida */ *inceput = p; *sfarsit = p; /* Lista a avut cel putin un nod */ p->succesor = *inceput; (*inceput)->predecesor = p; *inceput = p; Dac lista dublu nlnuit a fost vid, funcia actualizeaz ambii pointeri caracteristici, pentru a puncta spre nodul nou, ca unic nod al listei. Atunci cnd lista are cel puin un nod, trebuie ca fostul nod de inceput s puncteze, prin legtura sa predecesor spre nodul nou p, dar numai pointerul inceput trebuie actualizat, pointerul sfarsit trebuind s rmn cu vechea sa valoare. Inserarea la sfritul listei este specific cozilor, dar poate fi aplicat i la o list oarecare. Din punct de vedere algoritmic, nu ridic probleme deosebite, aa cum se poate deduce din listingul 1.7, n care s-a construit un model de funcie pentru o list simplu nlnuit, cu informaie de tip text. Grafic, nserarea n fa se ilustreaz ca n fig.1.6 - b. De remarcat aici faptul c funcia trebuie s primeasc pointerii caracteristici ai listei, de inceput i sfrit, pe care trebuie s i actualizeze corespunztor. Dac lista a fost vid, ambii pointeri puncteaz spre noul nod. Dac lista a avut cel puin un nod, ultimul su nod trebuie s trimit spre nodul nou, iar pointerul de sfrsit trebuie s arate spre nodul nserat.


28

a) Inserare n capul listei p 1

inceput

inceput

b) Inserare la sfarsitul listei 1

p

inceput

sfarsit

sfarsit

c) Inserare dup un nod dat dupanod

inceput

2

p

1

Fig.1.6 Inserare n list asimetric

Listingul 1.7 Structura general a funciei de nserare la sfritul unei liste simplu nlnuit int inseraresfarsit(NOD** inceput, NOD** sfarsit, char * infnod) {NOD *p; /* Alocare si pregatire nod */ p = (NOD*)malloc(sizeof(NOD)); if(!p) return 1; strcpy(p->info, infnod); p->succesor = NULL; /* Legarea nodului nou, cu actualizarea pointerului de inceput*/ if(!*inceput) /* Lista a fost vida */ {*inceput = p; *sfarsit = p; } else /* Lista a avut cel putin un nod */ { (*sfarsit)->succesor = p; *sfarsit = p; }; return 0; }


29

Pentru liste dublu nlnuite, este necesar s se modififice corespunztor secvenele de instruciuni date n cazul nserrii la nceput, modificnd captul de referin, adic nlocuind pointerul spre predecesor cu pointerul spre succesor, astfel: /* Lista a fost vida */ *inceput = p; *sfarsit = p; /* Lista a avut cel putin un nod */ (*sfarsit)->succecesor = p; p->predecesor = *sfarsit; *sfarsit = p; Inserarea dup un anumit nod al listei se aplic la o list oarecare. In acest caz, funcia de nserare trebuie s cunoasc, n plus fa de pointerii caracteristici, adresa nodului dup care se face nserarea. In cele ce urmeaz, cu titlu de exemplu, se presupune c funcia primete un pointer dupanod, cu adresa nodului dup care se face nserarea i pe care apelatorul o poate obine, de exemplu, prin traversare cu pointer de urmrire. Este recomandabil ca funcia de nserare s considere, de asemenea, situaia n care se solicit nserarea dup un nod dar lista este vid, adic o situaie pentru care parametrii inceput =NULL i dupanod NULL. In listingul 1.8, n ipoteza c pointerul dupanod este adresa unui nod al listei, este construit funcia model de nserare, iar situaia este ilustrat grafic n fig.1.6 c. Listingul 1.8 Structura general a funciei de nserare dup un nod dat la o list simplu nlnuit int inseraredupa(NOD** inceput, NOD* dupanod, char * infnod) {NOD *p; /* Alocare si pregatire nod */ p = (NOD*)malloc(sizeof(NOD)); if(!p) return 1; strcpy(p->info, infnod); p->succesor = NULL; /* Legarea nodului nou */ if(!*inceput) *inceput = p; /* Lista a fost vida */

else /* Lista a avut cel putin un nod */ {p->succesor = dupanod->succesor; dupanod->succesor = p; }; return 0; } Dac nu exist sigurana c pointerul dupanod conine o adres corect a unui nod al listei cnd aceasta este nevid, se poate introduce o secven de verificare prin traversare. Dac, n traversare, adresa nodului dupanod nu este egal cu adresa nici unui nod al listei, se refuz nserarea i funcia rentoarce valoare 2, ca mesaj de eroare. Dac lista este dublu nlnuit, atunci funcia trebuie s primeasc ambii pointeri specifici. In cazul de list nevid, de exemplu, cnd nserarea nu se face dup ultimul nod, legturile trebuie modificate astfel:


30

p->succesor = dupanod->succesor; p->predecesor = dupanod; dupanod->succesor->predecesor = p; dupanod->sucecesor = p; 1.5.3 Stergere ntr-o list La fel ca la nserare, tergerea poate s se refere la nodul din capul listei, la nodul ultim al listei sau la un nod oarecare din interiorul listei. Se pot construi funcii de tergere, pentru fiecare caz, eventual cu obligaia funciei de a returna informaia pe care o conine nodul ce este ters. In continuare, se presupune aceast situaie i se consider c informaia este de tipul text. La fel ca la nserare, tergerea poate modifica valorile pointerilor caracteristici. De aceea, toi pointerii care vor suferii modificri n funcia de tergere, modificri care trebuie s se regseasc ca atare n apelator, trebuie s fie declarai de tipul pointer la pointer la nod. Corespunztor, la apel, argumentele trebuie s fie adrese de variabile pointeri. Stergerea nodului din capul listei este tipic pentru stive i cozi, dar se poate utiliza i n cazul listelor oarecare. Funcia de stergere trebuie s primeasc, ca parametri, pointerul sau pointerii caracteristici ai listei i un pointer la char pentru un spaiu al al apelatorului n care s primeasc informaia din nodul care se terge. Pentru a distinge dac informaia returnat este semificativ, adic lista nu a fost vid, funcia trebuie s ntoarc un rezultat 1, dac lista a fost vid i un rezultat 0, n caz contrar. In listingul 1.9 este redat o astfel de funcie, pentru o list simplu nlnuit. Listingul 1.9 Structura general a funciei de tergere n capul unei liste simplu nlnuit int stergecap(NOD** inceput, char* infodinnod) {NOD *p; if(!*inceput) return 1; /* Lista a fost vida */ /* Stergere nod de cap, lista nu este vida */ p = (*inceput)->succesor; strcpy(infodinnod, (*inceput)->info); free(*inceput); *inceput = p; return 0; } Soluia ca apelatorul s i aloce spaiu pentru a primi informaia din nodul care se terge este recomandabil, pentru ca blocul de memorie s nu rmn ne eliberat dup utilizare, aa cum, de regul, se ntmpl dac funcia de tergere aloc n heap spaiul i returneaz la apelator numai adresa acestuia. In acest caz, apelul s-ar putea realiza ca n secvena care urmeaz: char t[10]; int r; . . . . . r = stergecap(&cap, t); Stergerea nodului ultim al listei este tipic pentru cozi, cnd funcia de tergere trebuie s primeasc ambii pointerii caracteristici, dar se poate utiliza i n cazul listelor oarecare. Dac lista este simplu nlnuit, funcia de tergere trebuie s cunoasc i adresa nodului predecesor al ultimului nod. Pentru a simplifica sarcinile apelatorului, funcia de


31

tergere nsi poate s execute o traversare care s depisteze predecesorul nodului ultim. Dac lista este dublu nlnuit, aceast adres este coninut n structura nodului ultim, n legtura denumit predecesor. Deoarece cozile solicit operaii frecvente de tergere, ele se pot proiecta ca liste dublu nlnuite (decozi - dequeue), pentru ca operaia de tergere s se realizeze uor, fr traversare. In continuare, pentru a arta n ce const, din punct de vedere algoritmic, o traversare de stabilire a acestei adrese, se presupune o list simplu nlnuit. Listingul 1.10 red structura funciei de tergere, n acest caz. Listingul 1.10 Structura general a funciei de tergere a nodului ultim al unei liste simplu nlnuit int stergesfarsit(NOD** inceput, char * infdinnod) {NOD *p, *r; infodinnod = NULL; /* Lista a fost vida */ if(!*inceput) return 1; /* Lista are un singur nod si devine vida */ strcpy(infdinnod, (*inceput)->info); free(*inceput); *inceput = NULL; return 0; /* Lista are cel putin doua noduri si se traverseaza */ r = *inceput; p = (*inceput)->succesor; while (p != NULL) /* Traversare */ {r =p; p = p->succesor; } /* Se sterge nodul sfarsit si lista ramane nevida */ strcpy(infdinnod, p->info); free(p); r->succesor = NULL; return 0; } In aceast funcie, r este pointerul de urmrire care rmne n urma pointerului de traversare p i, n final, d adresa predecesorului nodului de sfrit. Pe baza lui, se actualizeaz la NULL legtura, nodul r devenind nod ultim. Stergerea unui nod oarecare, de regul, presupune c nodul de ters se d prin informaia pe care o conine. In acest caz, funcia de tergere trebuie s realizeze o traversare cu pointer de urmrire, pentru a obine adresa nodului de ters i a predecesorului su. In listingul 1.11, se apeleaz funcia traversarecuurmarire(), n care se presupune o condiie de selecie pe egal. Se observ modul de apel al acestei funcii care primete pointerul de nceput (*inceput), informaia pentru selecie i adresa variabilei pointer r (&r). Listingul 1.11 Structura general a funciei de tergere a unui nod oarecare al unei liste simplu nlnuit int stergeoarecare(NOD** inceput, char* infsel, char * infdinnod) {NOD *p, *r; p = traversarecuurmarire(*inceput, infsel, &r); if((p==NULL) && (r==NULL))return 1; /* Lista este vida */ if((p==NULL) && (r!=NULL))return 2; /* Nu exista nodul de sters */ if((p!=NULL) && (r==NULL)) /* Se sterge primul nod */ {strcpy(infdinnod, p->info);


32

*inceput = p->succesor; free(p); return 0; } if((p!=NULL) && (r!=NULL)) {strcpy(infdinnod, p->info); r->succesor = p->succesor; free(p); return 0; }

/* Se sterge nodul p */

In aceast funcie, s-a extins codificarea rezultatului ntors, pentru a sesiza i situaia cnd nodul care se cere a fi ters nu exist n list, situaie ce poate apare, mai ales, datorit informaiei greite ce o conine parametrul infsel. De remarcat corecia care se aplic asupra pointerului inceput, n cazul n care se terge primul nod. De asemenea, trebuie acordat atenie modului n care se apeleaz funcia, potrivit unei secvene de forma: char t[10]; int n; . . . . . . n = stergeoarecare(&cap,"text", t); Dac, pentru o astfel de list, se ine i un pointer de sfarit, denumit sfarsit, atunci funcia trebuie s l primeasc n lista de parametri i trebuie s disting cazul cnd nodul care se terge este ultimul. In mod corespunztor, secvena situaiei, marcat prin comentariul /* Se sterge nodul p */, trebuie modificat astfel: if(p!=NULL && r!=NULL) /* Se sterge nodul p */ {strcpy(infdinnod, p->info); r->succesor = p->succesor; if(p->succesor==NULL)*sfarsit = r; free(p); return 0; Pentru cazul listelor dublu nlnuite, funciile de tergere se realizeaz uor, lista coninnd informaii de legtur care faciliteaz accesarea nodurilor n ambele direcii. Lsm cititorului, ca exerciiu, realizarea funciilor corespunztoare, avnd ca model funciile scrise la liste simplu nlnuite. 1.5.4 Distrugerea unei liste Dup cum se poate uor constata, la terminarea lucrului cu o list, aceasta poate s fie nevid i, n consecin, programul trebuie s elibereze spaiul ocupat. Aceast operaie este denumit distrugere de list i ea trebuie s elibereze spaiul nod cu nod. Operaia poate fi programat printr-o funcie adecvat, aa cum rezult din listingul 1.12. Listingul 1.12 Distrugerea unei liste void ditrugelista(NOD* inceput) {NOD* p; while(!inceput) {p = inceput; inceput = inceput->succesor; free(p); } }


33

1.6 Realizarea operaiilor de baz pe arbori binari de cutareLa fel ca i la liste, un program care trebuie s implementeze operaiile pe arbori binari trebuie s defineasc un tip de dat pentru nodul arborelui. In modul cel mai simplu, tipul NOD este un articol n care, pentru simplitate, informaia este considerat ca string i definete cele dou legturi spre succesorii direci (stnga = llink, dreapta = rlink): #define n 50 typedef char informatie[n]; typedef struct art {informatie info; art *llink, *rlink; }NOD; Depinznd de situaie, definiia se poate adapta pentru diferite tipuri de informaie, inclusiv pentru cazul n care informaia este un array dinamic. In ultimul caz, nodul trebuie s conin un pointer spre spaiul heap care se aloc array-ului. In cele ce urmeaz, avnd n vedere numai tratarea modului n care se pot implementa operaiile, se insist asupra operaiilor de traversare, cutare i nserare, considernd arborii binari de cutare. Problema distrugerii unui astfel de arbore se abordeaz n legtur cu exemplul de la sfritul capitolului. 1.6.1 Traversarea arborilor binari Traversarea arborilor binari se realizeaz ca o traversare total, n una din ordinile definite anterior: preordine, ordine simetric i postordine. Traversarea parcurge nodurile, potrivit metodei respective, indiferent de informaia pe care acestea o conin. In acest proces, fiecare nod este diponibil, pe rnd, pentru a i se aplica operaiile de tratare dorite. La fel ca n cazul listelor, se presupune c aceste operaii sunt realizate de funcia tratare(p), unde p este pointerul la nodul curent disponibil. Traversarea poate fi programat ntr-o funcie traversare() care poate fi realizat iterativ sau recursiv. In cele ce urmeaz se dicut, n detaliu, numai traversarea n ordine simetric. Pentru celelalte tipuri de traversri, se pot implementa funcii, ntr-o manier analog, modificnd corespunztor funcia pentru traversare simetric Traversarea iterativ n ordine simetric presupune o funcie care primete un pointer spre rdcina arborelului i, la fiecare nod vizitat, apeleaz funcia de tratare pe care o ofer programul. Deoarece legturile n arbore sunt totdeauna de la un nod printe spre succesorii si direci, o traversare n ordine simetric (SRD) presupune ca dup ce s-a vizitat, n ordine simetric, subarborele stnga, s se revin la rdcina acestuia, adic s se fac o revenire n sens invers direciei legturii lleft. Acest lucru nu este posibil, dect dac rdcinile subarborilor, n ordinea n care se trece prin ele nainte, sunt memorate. Dac memorarea acestora se realizeaz ntr-o stiv nlnuit, atunci drumul napoi se poate reconstitui extrgnd adresele de noduri n ordine invers memorrii, adic exact aa cum lucreaz o astfel de list. In listingul 1.13, n care se prezint codul funciei de traversare, stiva de lucru are partea de informaie de tip adres, denumit adrnodarbore, partea de legtur este denumit urmator, iat vrful stivei este gestionat prin pointerul top. Pentru a distinge cele dou tipuri de noduri, tipul pentru nodul arborelui este denumit NODABORE, iar cel al stivei de lucru este NODSTIVA. In fine, se face ipotez simplificatoare, c exist spaiu heap suficient pentru a putea construi stiva i pentru cea mai lung ramur a arborelui. Dealtfel, ipoteza este plauzibil, dac se are n vedere c la o ramur de 10000 de noduri, sunt necesari 80000 de bytes sau cca. 80 KB, ceea ce, pentru memoriile actuale este un spaiu mic.


34

Listingul 1.13 Structura funcie de traversare iterativ n ordine simetric a unui arbore binar void traversareSRD(NODARBORE* cap) {NODSTIVA *top, *r; NODARBORE *p; p=cap; top=NULL; do { while(p!=NULL) /* Pune adresa nodului arborelui in stiva */ {r = (NODSTIVA*)malloc(sizeof(NODSTIVA)); r->adrnodarbore = p; r->urmator = top; top = r; p = p->llink; /* Deplasare spre stanga */ } /* Extrage o adresa de nod al arborelui din stiva */ if(!top) {p = top->adrnodarbore; top = top->urmator; r = top; free(r); tratare(p); /* Tratare nod p */ p = p->rlink; /* Deplasare spre dreapta */ } } while(p != NULL || top != NULL); } Dac se urmrete codul funciei, se constat c stiva crete, iniial de la stiv vid, pe msur ce se face o deplasare spre stnga n arbore (p = p->llink), pn la un nod care are succesor stnga vid. In momentul cnd un astfel de nod a fost introdus n stiv, deplasarea stnga se oprete, se extrage nodul din vrful stivei, acesta se trateaz, prin funcia tratare(p) i apoi se face o schimbare a direciei de deplasare (p = p->rlink), spre subarborele dreapta al nodului tratat. Ciclul este reluat cu punerea n stiv a nodului rdcin al acestui subarbore i acesta este traversat spre stnga, pn la un nod cu succesor stnga vid etc, atta timp ct cel puin unul dintre pointerul p i pointerul top sunt nenuli, adic mai exist noduri ne vizitate. Traversarea recursiv n ordine simetric poate fi o tratare mai simpl, din punct de vedere algoritmic, aa cum rezult din listingul 1.14. O astfel de abordare, dei extrem de simpl, poate s nu dea satisfacie, pentru arbori voluminoi, avnd n vedere spaiul de memoriei al stivei sistem, mult mai redus dect spaiul heap i necesarul de memorie mai mare pentru a memora n stiv strile de ntrerupere, potrivit tehnicii de execuie a funciilor recursive. Listingul 1.14 - Structura funcie de traversare recursiv n ordine simetric a unui arbore binar void traversareSRD(NODARBORE* k) {if(k->llink != NULL) traversareSRD(k->llink); tratare(k); if((k = k->rlink)!= NULL) traversareSRD(k); }


35

1.6.2 Cutarea n arbori binari Aa dup cum s-a artat ntr-un paragraf anterior, la arborii binari de cutare, structura este definit de o relaie de dominare definit pe informaia coninut n noduri. Acest tip de arbore i gsete utilizarea n programele care stocheaz iniial informaii care posed o astfel de structur i apoi, la diferite momemte de timp, verific dac o anumit informaie este deja achiziionat. Datorit modului de memorare, pentru mulimi mari de informaii, un arbore de cutare poate fi mai eficient, ca timp mediu de cutare, dect o stocare a acestor informaii ca un array, la care trebuie adugat i facilitatea ca arborele s creasc dinamic, prin inserare, atunci cnd o informaie nu se gsete, dar se vrea adugarea ei. In acest paragraf, se consider cutarea ca un proces pur, ceea ce presupune c arborele este deja creat i o funcie, denumit funcie de cutare, stabilete dac o informaie, dat ca parametru, este sau nu n arborele de cutare. In listingul 1.15 este redat o astfel de funcie, n ipoteza cunoscut cu privire la structura de nod. Funcia primete pointerul cap la rdcina arborelui i intoarce ca rezultat un pointer valid p la ultimul nod vizitat. Din punct de vedere algoritmic, cutarea se realizeaz prin deplasare alternativ, cu pointerul p, fie n subarborele stnga fie n subarborele dreapta, n raport de relaia informaiei dat de parametrul infodat cu informaia info, coninut de nodul curent. Se constat cu uurin c informaia nu exist n arbore, dac n procesul deplasrii prin subarbori s-a ajuns prima dat la un nod frunz (terminal). Listingul 1.15 - Structura funcie de cutare pe un arbore binar de cutare int cautarearb(NODARBORE* cap, char* infodat, NODARBORE** pp) {NODARBORE *p; int terminat, succes, rel; terminat = succes = 0; p = cap; do {rel = strcmp(infodat, p->info); if(rel == 0) /* Informatia s-a gasit */ {succes = 1; terminat = 1; } else /* Informatia inca nu s-a gasit */ {if(rel < 0) /* Deplasare stanga sau terminat*/ {if(p->llink != NULL) p = p->llink; else terminat = 1; /* Informatia nu exista */ } else /* Deplasare dreapta sau terminat */ {if(p->rlink != NULL) p = p->rlink; else terminat = 1; /* Informatia nu exista */ } } } while(!terminat); *pp = p; return (succes); } In codul funciei, s-a utilizat o ciclare pe baza variabilei boolene terminat care pleac pe 0 (fals) i primete valoare 1 (adevrat), fie atunci cnd s-a gsit nodul ce conine informaia, fie atunci cnd se ajunge la un nod terminal. Variabila succes, de acelai tip, evideniaz eecul cutrii (valoarea 0) sau succesul acestui proces (valoarea 1). In final, funcia ntoarce valoarea variabilei succes i pointerul p al ultimului nod vizitat. In acest fel,


36

procedura de cutare poate fi utilizat n operaii de nserare (vezi paragraful urmtor), nodul ultim vizitat va fi cel de care se va lega un nod nou, atunci cnd informaia nu s-a gsit. Se atrage atenia asupra modului de declarare a parametrului pp, ca pointer la pointer la nod, adic sub forma NODARBORE** pp, pentru ca adresa nodului ultim vizitat s poat ajunge n apelator. In consecin, pentru apel, parametrul actual corespunztor trebuie decarat sub forma NODARBORE *p i transferat prin adres, sub forma &p. 1.6.3 Inserare n arbori binari de cutare Operaia de nserare este mecanismul general prin care se construiete, din aproape n aproape, un arbore binar de cutare. Operaia de nserare se poate programa ca o funcie de nserare care, la fiecare apel, adaug la arborele existent un nod nou. Inserarea unui nod nou trebuie s implementeze relaia de dominare specific. In listingul 1.16 este prezentat o astfel de funcie care primete, n lista de parametri, pointerul la rdcina arborelui, la primul apel pointer NULL, i un pointer la informaia de pus n nod. La fel ca alte funcii de nserare, funcia ia n considerare situaia spaiului heap i elimin situaia cnd aceeai informaie se repetat. Situaiile acestea sunt codificate ctre apelator, prin rezultatul ntreg pe care funcia l ntoarce: valoarea 1, dac spaiul s-a epuizat, valoarea 0, dac a existat spaiu pentru nod i nserarea s-a realizat i valoarea 2, dac informaia respectiv exist deja ntr-un nod. Listingul 1.16 - Structura funcie de nserare n arbore binar de cutare int inserarearb(NODARBORE** cap, char* infodat) {NODARBORE *p, *q; int s; q = (NODARBORE*)malloc(sizeof(NODARBORE)); if(!q) return 1; /* Lipsa spatiu */ /* Pregatire nod nou */ strcpy(q->info, infodat); q->llink = q->llink = NULL; /* Inserarea nodului q */ if(!*cap) *cap = q; /* Arbore vid, prima inserare */ else /* Inserare dupa o cautare */ {s = cautarearb(*cap, infodat, &p) ; if(s == 1) /* Informatia exista deja */ {free(q); return 2; } /* Legarea nodului nou */ if(strcmp(infodat, p->info)p->llink = q; else p->rlink = q; return 0; } } Trebuie remarcat faptul c, n funcia de nserare s-a apelat funcia de cutare cautarearb(). Variabila s recepioneaz rezultatul cutrii i, n cazul n care aceasta are valoarea 1, informaia exist deja n nod, de aceea, nodul q pregtit deja se elibereaz, deoarece inserarea nu se face. Dac informaia nu exist, nodul p este cel la care trebuie legat nodul q, fie ca succesor stnga, fie ca succesor dreapta, pe baza relaiei de comparare a informaiei infodat cu informaia info din p.


37

1.7 Realizarea programelor care utilizeaz structuri dinamicePentru a putea manipula, cu mai mult uurin, diferitele structuri de date, inclusiv n situaiile n care se utilizeaz mai multe structuri de aceali fel, n programul respectiv, este recomandabil s se construiasc tipuri de date: list arbore, array etc. Un astfel de tip de dat, n tehnica programrii procedurale, poate fi conceput ca un articol, descris prin struct, care s defineasc elemntele caracteristice drept cmpuri: pointeri, numr de noduri (elemente), unitatea de alocare i realocare etc. In aceste condiii, utiliznd aceleai funcii, se pot manevra structuri de acelai fel, prin declararea de variabile de acest tip. Fiecare astfel de structur dinamic este perfect identificat de o variabil i, prin notaia prefixat cu punct, cu numele acelei variabile, se disting elementele, fr confuzie. Tipurile struct definite pot s fie extinse ulterior, n tehnica programrii cu tipuri abstracte sau n tehnica programrii orientat pe obiecte, astfel nct s ncorporeze i funciile de manipulare, prin utilizarera limbajului C++. Mai mult, se poate depi specificitatea impus de tipul de dat al informaiei din noduri, dac se utilizeaz proprietatea de genericitate evitnduse constucia sistemului de funcii pentru fiecare caz. In concluzie, pentru a construi un program bun pentru lucrul cu o structur dinamic de date, cu informaii de un anumit fel, este necesar s se in seama de urmtoarele recomandri: s se defineasc un tip de dat pentru nodul (elementul) structurii care s introduc tipul de dat al elementelor i, dac este cazul, legturile; s se defineasc un tip de dat pentru structura respectiv care s cuprind elementele caracteristice ale acelui fel de structur; s se declare i s se defineasc funciile necesare, pentru utilizarea structurii respective. In paragrafele anterioare, s-a artat cum se definete tipul de dat pentru nod i cum trebuie abordat construcia funciilor necesare manevrrii structurii dinamice respective. In acest punct, exemplificm definirea tipului prin dou astfel de structuri dinamice. Pentru un array dinamic se poate declara un tip de forma: typedef struct {informatie* pblock; int nelem; int pozelem} DINARRAY; unde pblock este pointerul la spaiul heap compact alocat, la un anumit moment, acelei structurii, nelem reprezint numrul de elemente care pot fi coninute n spaiul alocat, iar pozelem arat poziia ultimului element prezent n array, potrivit conveniei de numerotare dat de limbaj. Pe baza tipului declarat, se poate defini o variabil vectdin, sub forma: DINARRAY vectdin; i pot fi referite aceste elemente ca vectdin.pblock, vectdin.nelem, vectdin.pozelem. La momentul de nceput, stuctura trebuie s fie vid, adic este necesar s se iniializeze structura declarat, sub forma: vectdin.pblock = NULL; vectdin.nelem = 0; vectdin.pozele = -1; In aceste condiii, funciile asociate structurii dinamice trebuie s primeasc valorile sau adresele elementelor caracteristice, dup cum acestea nu vor fi sau vor fi modificate n funciile respective. Ele pot s fie transferate individual, aa cum s-a artat ntr-un paragraf


38

anterior sau, mai comod, global, ca un unic parametru, sub forma unui pointer la aceea structur. In acest ultim caz, se recomand o declaraie de forma: DINARRAY vectdin, * pvectdin; ceea ce impune o iniializare a pointerului sub forma pvectdin = &vectdin. In funciile respective, dac se face ipoteza denumirii la fel a parametrului formal corespunztor, elementele necesare trebuie referite n notaia prefixat cu sgeat, pe baza acestui parametru, sub forma: pvectdin->numeelement. Pentru o coad, de exemplu, tipul este definit de mai puine elemente caracteristice i se poate declara sub forma: typedef struct {NODCODA* fata; NODCODA* spate;} COADA; unde fata i spate sunt pointeri la nceputul i respectiv ultimil nod. Corespunztor, se poate declara o variabil, vcoda iniial vid: COADA vcoda; vcoada.fata = NULL; vcoada.spate = NULL; La fel ca mai sus, i n acest caz, se poate alege una din variante, pentru transferul parametrilor la funciile asociate. Fiind numai dou elemete, se poate utiliza, fr complicaii de scriere, transferul individual, de pointeri. Se recomand ca tipurile care trebuie declarate, mpreun cu prototipurile funciilor de lucru cu structura dinamic respectiv, s se constituie sub forma unui fiier header *.h, iar definirele de funcii s se construiasc ntr-un alt fiier *.c. In felul acesta, se obin structuri cu un grad mai ridicat de reutilizare care s poat fi folosite i n alte programe, cu modificri minime. In fine, pentru a avea o viziune mai complet asupra acestui mod de lucru, se poate urmrii exemplul din paragraful care urmeaz. Se atrage atenia c tehnica de mai sus poate fi aplicat cu succes n cazul n care funciile care utilizeaz tipul respectiv nu sunt recursive. In cazul funciilor recursive, este nevoie s se construiasc replici ale structurii dinamice, pentru fiecare apel, ceea ce poate conduce foarte repede la epuizarea stivei sistem.

1.8 Un exemplu de utilizare a structurilor dinamicePentru a ilustra modul n care se pot utiliza structurile dinamice n rezolvarea de probleme, se consider urmtorul caz: S se realizeze un program care s furnizeze o list alfabetic, pentru o mulime de termeni (cuvinte) care se dau de la tastatur. Rezolvare: Deoarece este vorba de o mulime de cuvinte, a construi lista cerut revine la a realiza o sortare a acestora, pe baza ordinii lexicografice. Cum mulimea are un numr nedefinit de cuvinte, de lungimi diferite, este preferabil s se utilizeze un arbore de sortare, aa cum s-a artat n paragraful referitor la arbori binari. Arborele binar de sortare ofer posibilitatea de a stoca cuvintele n heap, pe un spaiu strict necesar, ceea ce poate asigura sortarea unui mare numr de termeni. Aceasta nseamn c n structura nodului arborelui nu se nscrie informaia, ci un pointer la blocul unde se memoreaz cuvntul respectiv. Se tie c, dup construcia arborelui, prin traversare n ordine simetric, se obine o list sortat a cuvintelor. Trebuie inut seama c aceast list poate fi mare i, n plus, trebuie


39

s fie redat pe hrtie. De aceea, lista sortat trebuie s fie nscris pe un fiier care, ulterior s poat fi listat, ntr-un anumit format. Inlisingul 1.17 este redat coninutul fiierului header al aplicaiei, denumit arbsort.h. Acesta se presupune c se gsete pe directorul curent i cuprinde declararea tipurilor de date i prototipurile funciilor necesare. Aici trebuie remarcat faptul c nodul arborelui nu conine cuvntul, ci un pointer la spaiul din heap, strict necesar, unde se memoreaz cuvntul respectiv. De asemenea, se observ c tipul pentru arborele de sortare posed, pe lng pointerul cap i un pointer la fiierul pe care se va gsi lista de cuvinte. Listingul 1.17 Fiierul antet arbsort.h /* Definirea nodului arborelui */ typedef struct nod {char* pinf; struct nod* llink; struct nod* rlink; } NODARBORE; /* Definirea arborelui de sortare */ typedef struct {NODARBORE* cap; FILE* fc;} ARBORESORTARE; /* Definirea prototipurilor functiilor pentru arbore */ int cautarearb(ARBORESORTARE* pa, char* infodat, NODARBORE** p); int inserarearb(ARBORESORTARE* pa, char* infodat); void traversareSRD(NODARBORE* k, FILE *f); void traversareRSD(NODARBORE* p); In listingul 1.18 este redat fiierul funciei principale. Funcia main() declar variabilele necesare, iniializeaz variabilele de tip structur i construiete arborele de sortare, prin conversaie la consol, apelnd funcia de nserare. Dup ce arborele a fost construit, se apeleaz funcia de traversare, pentru a crea, pe un fiier deja deschis n directorul curent, lista sortat a cuvintelor, fiecare cuvnt fiind scris pe un rnd distinct. In final, este apelat funcia care distruge arborele, ptin traversare n postordine. Listingul 1.18 Fiierul programului principal, pentru sortarea de cuvinte pe arbore #include #include #include "arbsort.h" /* Functia principala main() */ void main() {ARBORESORTARE as; char cuv[80]; int sp; /* Introducerea cuvintelor. Constructia arborelui */ as.cap = NULL; as.fc = NULL; printf("\nDati cate un cuvant.\n" "Terminati prin cuvant vid (ENTER):\n"); scanf("%s", cuv); while(strlen(cuv)!= 0) {sp = inserare(&as, cuv); if(!sp) {printf("\nNu mai pot fi introduse cuvinte; lipsa spatiu !\n"); break;


40

} /* Traversarea arborelui pentru sortarea cuvintelor */ as.fc = fopen("Listacuv.txt", "w"); traversareSRD(as.cap, as.fc); fclose(as.fc); printf("\nLista sortata a cuvintelor se gaseste in fisierul\n " "Listacuv.txt, pe directorul curent.\n"); /* Distrugerea arborelui, pentru eliberarea spatiului */ traversareRSD(as.cap); } Funciile sunt implemetate n listingul 1.19, considernd fiierul surs arbsort.c, pe directorul curent. Funciile care se utilizeaz aici sunt cele discutate anterior, la care s-au adus unele modificri i la care s-a adugat funcia de distrugere de arbore, prin treaversare n postordine. Funcile de cutare i de nserare sunt legate ntre ele, funcia de nserare apelnd, pentru fiecare cuvnt, funcia de cutare. Dac se urmrete codul surs al acestor funcii, se constat c exist o modificare, impus de structura nodului arborelui care conine pointer la informaia din nod. Atunci, la nserare este necesar s se aloce spaiu att pentru nod ct i pentru informaie i spaiile respective s se iniializeze corespunztor, aa cum rezult din secvena: q = (NODARBORE*)malloc(sizeof(NODARBORE)); t = (char*)malloc(sizeof(infodat)+1); . . . . . . . . . . . . . /* Pregatire nod nou */ q->pinf = t strcpy(t, infodat); q->llink = q->llink = NULL; Atunci cnd cutarea este fr succes, pointerul p aduce adresa nodului dup care trebuie s aib loc nserarea. Subarborele n care se leag nodul nou este dat de comparaia ntre informaia din nod i cuvntul dat. Relaia de comparare a informaiei dat cu cea din nod este de forma strcmp(infodat, p->pinf), avnd n vedere pointerul pinf la informaie. La funcia de cutare, s-a modificat numai modul de comparare a informaiilor, avnd n vedere structura nodului, aa cum arat instruciunea: rel = strcmp(infodat, p->pinf). Listingul 1.19 Funciile programului de sortare pe arbore- fiierul arbsort.c #include #include #include #include "arbsort.h" /* Functia de cautare pe un arbore binar de cautare */ int cautarearb(ARBORESORTARE* pa, char* infodat, NODARBORE** pp) {NODARBORE *p; int terminat, succes, rel; terminat = succes = 0; p = pa->cap;

} printf("\nDati cate un cuvant.\n" "Terminati prin cuvant vid (ENTER):\n"); scanf("%s", cuv);


41

if(!p) return succes; /* Arbore vid. Informatia nu exista */ do {rel = strcmp(infodat, p->pinf); if(rel == 0) /* Informatia s-a gasit */ {succes = 1; terminat = 1; } else /* Informatia inca nu s-a gasit */ {if(rel < 0) /* Deplasare stanga sau terminat*/ {if(p->llink != NULL) p = p->llink; else terminat = 1; /* Informatia nu exista */ } else /* Deplasare dreapta sau terminat */ {if(p->rlink != NULL) p = p->rlink; else terminat = 1; /* Informatia nu exista */ } } } while(!terminat); *pp = p; return (succes); } /* Functia de inserare in arbore binar de cautare */ int inserarearb(ARBORESORTARE* pa, char* infodat) {NODARBORE *p, *q; char *t; int r; q = (NODARBORE*)malloc(sizeof(NODARBORE)); if(!q) return 1; /* Lipsa spatiu pentru nod */ t = (char*)malloc(sizeof(infodat)+1); if(!t) return 1; /* Lipsa spatiu pentru informatie */ /* Pregatire nod nou */ q->pinf = t; strcpy(t, infodat); q->llink = q->rlink = NULL; /* Inserarea nodului q */ if(!pa->cap) {pa->cap = q; /* Arbore vid, prima inserare */ return 0; } /* Inserare dupa o cautare */ p = pa->cap; r = cautarearb(pa, infodat, &p) ; if(r == 1) /* Informatia exista deja */ {free(q); free(t); return 2; } /* Legarea nodului nou */ r = strcmp(infodat, p->pinf); if(r < 0) p->llink = q; else p->rlink = q; return 0; }

Prof

Date post:	14-Jul-2015
Category:	Documents
Upload:	ionut-oprisan
View:	968 times
Download:	1 times

Programare Procedurala

Documents