Structuri De Date.rtf

1. Structuri elementare de date Înainte de a elabora un algoritm, trebuie să ne gândim la modul în care reprezentăm datele. Structurile fundamentale de date cu care se poate opera sunt: fişier, tablou, listă, graf, arbore. În acest capitol ne vom ocupa de liste, arbori şi grafuri, întrucât primele două (tablou, fişier) au fost studiate anterior. O listă este o colecţie de elemente de informaţie (noduri) aranjate într-o anumită ordine. Lungimea unei liste este dată de numărul de noduri din listă. Structura listei trebuie să ne permită să determinăm eficient care este primul/ultimul nod în structură şi care este predecesorul/succesorul unui nod dat. Cea mai simplă listă este lista liniară. Un alt tip de listă este cea circulară, în care, după ultimul nod, urmează primul, deci fiecare nod are succesor şi predecesor. Operaţiile curente care se fac în liste sunt: inserarea unui nod, ştergerea (extragerea) unui nod, concatenarea unor liste, numărarea elementelor unei liste etc. Implementarea unei liste se poate face in principal în două moduri. Primul, constă în implementarea secvenţială, adică în locaţii succesive de memorie, conform ordinii nodurilor din listă, care conţin informaţia dorită. Avantajul acestei tehnici este accesul rapid la predecesorul/succesorul unui nod, inclusiv găsirea rapidă a primului/ultimului nod. Dezavantajele sunt inserarea/ştergerea relativ complicată a unui nod şi faptul că, în general, nu se foloseşte întreaga memorie alocată listei. Cel de-al doilea, implementarea înlănţuită. în care fiecare nod conţine două părţi: informatia propriu-zisă şi adresa nodului următor. Alocarea memoriei fiecărui nod se poate face în mod dinamic, în timpul rulării programului. Accesul la un nod necesită parcurgerea tuturor predecesorilor săi, ceea ce poate lua ceva mai mult timp. Inserarea/ştergerea unui nod este în schimb foarte rapidă. Se poate construi o listă dublu înlănţuită, care conţine două adrese în loc de una, astfel încat un nod să conţină pe lânăa adresa nodului următor şi adresa nodului anterior. Listele implementate înlănţuit pot fi reprezentate cel mai simplu prin tablouri. În acest caz, adresele sunt de fapt indici de tablou. O alternativă este să folosim tablouri paralele: să memoram informaţiile fiecărui nod într-un tablou INFO[n], iar adresele (indicii) nodurilor succesoare într-un tablou SUCC[n]. Indicele primului nod din listă (fie că este de tip coadă sau stivă) va fi păstrat într-o variabilă. Acest mod de reprezentare este simplu dar apare o problemă, şi anume cea a gestionării locaţiilor libere. O soluţie este să reprezentăm locaţiile libere tot sub forma unei liste înlănţuite. Atunci, ştergerea unui nod din listă implică inserarea sa într-o listă cu locaţii libere, iar inserarea unui nod în listă implică ştergerea sa din lista cu locaţii libere. Este interesant de remarcat că, pentru implementarea listei de locaţii libere, putem folosi aceleaşi tablouri, dar avem nevoie de o alta variabilă, care să conţină indicele primei locaţii libere din VAL şi LINK, în timp ce variabila cealaltă, iniţială, va conţine adresa primei locaţii din lista propriu-zisă. Vom exemplifica în continuare două tipuri de liste foarte des folosite, şi anume coada şi stiva, considerând implementarea ce utilizează alocarea statică (tablouri). O stivă (stack) este o listă liniară cu proprietatea că operaţiile de inserare/extragere a nodurilor se fac în/din coada listei, motiv pentru care stivele se mai numesc şi liste LIFO (Last In First Out). Cel mai natural mod de reprezentare pentru o stivă este implementarea secvenţială într-un tablou S[n], unde n este numarul maxim de noduri. Primul nod va fi memorat în S[0], al doilea în S[1], iar ultimul în S[n1]; sp este o variabila care conţine adresa (indicele) ultimului nod inserat. Iniţial, cand stiva este vidă, avem sp = -1 (sau poate fi 0). Iată funcţiile de inserare, extragere a unui nod, precum şi cele de afişare şi de semnalare a situaţiilor extreme (stivă goală sau stivă plină). /* stivatab.c - operatii cu o stiva realizata static intr-un tablou; operatii disponibile: inserare, extragere, afisare cap stiva, afisare stiva, afisare pointer la varful stivei */ 1

#include <stdio.h> #include #define MaxS10 typedef int ElTip; // ElTip - definire tip element din stiva typedef struct { ElTip elem [MaxS];// spatiu pentru elem. stivei int sp; /* index/ referinta la varful stivei (stack pointer) */ } TStiva, *AStiva; void eroare (char *meserr){ printf("%s\n", meserr); } void InitStiva (AStiva rs){ /* initializare stiva, sp nu refera un element (stiva goala) */ rs->sp=-1; } int StivaGoala (AStiva rs){ return (rs->sp == -1); } int StivaPlina (AStiva rs){ /* stiva este plina, index=MaxS-1, indice maxim, nu se mai pot introduce elemente in stiva */ return (rs->sp == MaxS-1); } void Push (AStiva rs, ElTip el){ /* introduce element in stiva, daca nu este plina */ if (StivaPlina (rs)) eroare ("Stiva Plina !!!"); else {rs->sp=rs->sp+1; rs->elem[rs->sp]=el; } } ElTip Pop (AStiva rs){ /* extrage element din stiva, daca nu este goala */ ElTip e; if (StivaGoala (rs)) {eroare ("Stiva Goala !!!"); return 0; } else {e=rs->elem[rs->sp]; rs->sp=rs->sp-1; return e; } } ElTip CapStiva (AStiva rs){ if (StivaGoala (rs)) {eroare ("Stiva Goala !!!"); 2

return 0; } else return rs->elem[rs->sp]; } void AfisareStiva (AStiva rs){ /* se creaza o copie a stivei curente, pentru a utiliza functiile definite pentru operare stiva (Pop, CapStiva, StivaGoala) */ TStiva s=*rs; AStiva pt=&s; int nvl=0; /* Numar de valori afisate pe linie */ if (pt->sp == -1) eroare("Stiva Goala !!!\n"); else while (!StivaGoala (pt)) {printf ("%d -> ", CapStiva (pt)); Pop (pt); if (++nvl % 10 == 0) printf("\n"); } printf("NULL\n"); } void Afisare_Poz_sp (AStiva rs){ printf("Referinta (indexul), sp: %d\n", rs->sp); if (!rs->sp) printf("\tSTIVA GOALA!!!\n"); else if (rs->sp == MaxS-1) printf("\tSTIVA PLINA !!! ELIMINATI ...\n"); } void main (void){ TStiva s, *rs; char optiune[20]; ElTip n; clrscr(); printf("Exemplu de stiva realizata utilizand un tablou.\n"); printf("Stiva este alcatuita din numere intregi.\n"); InitStiva (rs); printf("\nOptiuni Introduc, Extrag, Afis stiva, Cap stiva, Poz sp, Stop: "); gets(optiune); while (optiune[0] != '\0' && optiune[0] != 's' && optiune[0] != 'S'){ switch(optiune[0]){ case 'i': case 'I':if (StivaPlina(rs)){ eroare("\n\tSTIVA PLINA !!! ELIMINATI...\n"); break;} printf("Introd. nr. (CTRL-Z, Enter-Stop Introd): "); while (scanf("%d", &n) == 1 && !StivaPlina(rs)){ Push (rs, n); 3

if (StivaPlina (rs)){ eroare("Stiva PLINA !!! ELIMINATI.....\n"); break; } printf("Introd. nr. (CTRL-Z, Enter-Stop Introd): "); } fflush(stdin); break; case 'e': case 'E': optiune[0]='D'; while ( !StivaGoala (rs) && (optiune[0] == 'D' || optiune[0] == 'd') ) {printf ("Se extrage primul element din stiva: %d\n", CapStiva (rs)); Pop (rs); if (!StivaGoala (rs)){ printf("Continuati extragerea (Da/Nu): "); gets(optiune); fflush(stdin); } } if (StivaGoala (rs)) printf("Stiva Goala !!! INTRODUCETI ELEMENTE \n"); break; case 'c': case 'C': if (!StivaGoala (rs)) printf("Afisare element din capul stivei: %d\n", CapStiva (rs)); else eroare("Stiva Goala !!!\n"); break; case 'a': case 'A':AfisareStiva (rs); break; case 'p': case 'P': Afisare_Poz_sp (rs); break; } printf("\nOptiuni Int, Ext, Afis stiva, Cap stiva, Poz sp, Stop: "); gets(optiune); } } O coadă este o listă liniară în care inserările se fac doar în capul listei (prim), iar extragerile doar din coada listei (ultim). Cozile se numesc şi liste FIFO (First In First Out). O reprezentare secvenţială pentru o coadă se obţine prin utilizarea unui tablou C[n], pe care îl tratăm ca şi cum ar fi circular: după locatia C[n-1] urmează locaţia C[0]. Dacă cei doi indecşi (ultim şi prim) referă cele două locaţii, sau două locaţii în această ordine (k-1, respectiv k) coada este goală; dacă cei doi indecşi sunt 4

egali (k), atunci coada conţine un singur element, iar dacă ultim=k-2, iar prim=k, atunci coada este plină. /* coadatab.c - operatii cu o coada realizata static intr-un tablou; operatii disponibile: inserare, extragere, afisare cap coada, afisare coada, afisare pozitii referinte la primul si ultimul element din coada */ #include <stdio.h> #include #define MaxC 10 typedef int ElTip; // ElTip - definire tip element din coada typedef struct { ElTip elem [MaxC];// spatiu pentru elem. cozii int prim, ultim; /* indecsi/ referinte la primul/ ultimul element din coada */ } TCoada, *ACoada; void eroare (char *meserr){ printf("%s\n", meserr); } int IncIndexC (int i){ /* increment index element curent coada */ return ((i+1) % MaxC); } void InitCoada (ACoada pc){ /* initializare coada, referintele prim si ultim */ pc->prim=0; pc->ultim=MaxC-1; } int CoadaGoala (ACoada pc){ /* coada este goala: index (ultim+1) == index (prim) coada goala: x x x x u p x x x x , daca p si u ocupa aceeasi pozitie coada are un singur element: x x x x x p(u) x x x x , p si u au aceeasi valoare */ return (IncIndexC (pc->ultim) == pc->prim); } int CoadaPlina (ACoada pc){ /* coada este plina: index (ultim+2) == index (prim) coada goala: x x x u - p x x x x , pozitia - nu este element in coada*/ return (IncIndexC (IncIndexC(pc->ultim)) == pc->prim); } void AdaugElC (ACoada pc, ElTip el){ if (IncIndexC (IncIndexC(pc->ultim)) == pc->prim) eroare ("Coada Plina !!!"); else {pc->ultim=IncIndexC(pc->ultim); pc->elem[pc->ultim]=el; } } ElTip ScotElC (ACoada pc){ 5

ElTip e; if (CoadaGoala (pc)) {eroare ("Coada Goala !!!"); return 0; } else {e=pc->elem[pc->prim]; pc->prim=IncIndexC(pc->prim); return e; } } ElTip CapCoada (ACoada pc){ if (CoadaGoala (pc)) {eroare ("Coada Goala !!!"); return 0; } else return pc->elem[pc->prim]; } void AfisareCoada (ACoada pc){ /* se creaza o copie a cozii curente, pentru a utiliza functiile definite pentru operare coada (ScotElC, CapCoada, CoadaGoala) */ TCoada c=*pc; ACoada pt=&c; int nvl=0; /* Numar de valori afisate pe linie */ if (CoadaGoala(pt)) eroare("Coada Goala !!!\n"); else while (!CoadaGoala (pt)) {printf ("%d -> ", CapCoada (pt)); ScotElC (pt); if (++nvl % 10 == 0) printf("\n"); } printf("NULL\n"); } void Afisare_Poz_Prim_Ultim (ACoada pc){ printf("Cei doi indecsi (referinte), prim si ultim: %d(p), %d(u)\n", pc->prim, pc->ultim); } void main (void){ TCoada c, *pc; char optiune[20]; ElTip n; clrscr(); printf("Exemplu de coada realizata utilizand un tablou.\n"); printf("Coada este alcatuita din numere intregi.\n"); InitCoada (pc); 6

printf("\nOptiuni Int, Ext, Afis coada, Cap coada, Poz p/u, Stop: "); gets(optiune); while (optiune[0] != '\0' && optiune[0] != 's' && optiune[0] != 'S'){ switch(optiune[0]){ case 'i': case 'I':if (CoadaPlina(pc)){ eroare("\n\tCOADA PLINA !!! ELIMINATI...\n"); break;} printf("Introd. nr. (CTRL-Z, Enter-Stop Introd): "); while (scanf("%d", &n) == 1){ AdaugElC (pc, n); if (CoadaPlina (pc)){ eroare("Coada PLINA !!! ELIMINATI.....\n"); break; } printf("Introd. nr. (CTRL-Z, Enter-Stop Introd): "); } fflush(stdin); break; case 'e': case 'E': optiune[0]='D'; while ( !CoadaGoala (pc) && (optiune[0] == 'D' || optiune[0] == 'd') ) {printf ("Se extrage primul element din coada: %d\n", CapCoada (pc)); ScotElC (pc); if (!CoadaGoala (pc)){ printf("Continuati extragerea (Da/Nu): "); gets(optiune); fflush(stdin); } } if (CoadaGoala (pc)) printf("Coada Goala !!! INTRODUCETI ELEMENTE \n"); break; case 'c': case 'C': if (!CoadaGoala (pc)) printf("Afisare element din capul cozii: %d\n", CapCoada (pc)); else eroare("Coada Goala !!!\n"); break; case 'a': case 'A':AfisareCoada (pc); break; case 'p': case 'P': Afisare_Poz_Prim_Ultim (pc); break; 7

} printf("\nOptiuni Int, Ext, Afis coada, Cap coada, Poz p/u, Stop: "); gets(optiune); } } Structurile de date utilizate anterior (tablouri, sau structuri, uniuni) nu sunt structuri de date dinamice, deoarece ramân fixe în ce priveşte dimensiunea lor pe toată durata lor de viaţă, adică pe durata execuţiei funcţiei respective. Astfel de exemple sunt tablourile sau structurile, ale căror dimensiuni pot fi cunoscute de la declararea lor. Sunt însă situaţii în care structurile de date trebuie să se modifice ca formă sau ca mărime pe parcursul programului; astfel de structuri sunt listele, arborii, grafurile şi mulţimile disjuncte. Deoarece pentru astfel de structuri numărul de componente şi legăturile dintre acestea nu sunt dinainte fixate, ele se crează dinamic, pe durata execuţiei programului. Variabilele statice sunt toate variabilele declarate în secţiunile declarative ale unei funcţii sau ale unui bloc, având aceeaşi durată de viaţă cu cea a funcţiei sau blocului respectiv în care au fost declarate. Variabilele dinamice se generează şi se distrug dinamic pe parcursul execuţiei programului. Spre deosebire de variabilele statice, variabilele dinamice nu au un nume (identificator), referirea la ele făcându-se în mod indirect prin intermediul variabilelor pointer (referinţă). O variabilă referinţă (pointer) are ca valoare o adresă a unei variabile dinamice. Variabilele pointer se folosesc pentru a creea variabile dinamice (a aloca memorie pentru acestea) şi pentru a le distruge când nu mai sunt necesare (deci pentru a elibera memoria alocată). O structură de date dinamice este constituită dintr-un număr de elemente referite prin pointeri. Se pot introduce noi elemente sau suprima cele vechi, în timpul execuţiei programului. Adresele reale ale elementelor nu au importanţă, deoarece legăturiile logice dintre elemente sunt stabilite de pointeri şi nu prin poziţia lor relativă din memorie, ca în cazul tablourilor. Fiecare element al unei structuri dinamice poate conţine unul sau mai multe câmpuri cu referire (pointeri) la alte elemente, care pot fi de orice tip (simplu, tablou, structură sau pointer). De exemplu, componentele unei listei sunt structuri cu două câmpuri: o valoare de tip întreg şi un pointer la următoarea componentă: struct intrare { int valoare ; struct intrare *urmator ; }; Crearea efectivă a variabilei dinamice, deci alocarea de memorie, se face utilizând una dintre funcţiile malloc(), calloc() sau new (C++). Distrugerea unei variabile dinamice, deci eliberarea spaţiului de memorie ocupat de aceasta, se realizează cu una dintre funcţiile free() sau delete (C++). Aceste funcţii sunt definite după cum urmează. void *malloc(size_t dimensiune), alocă un spaţiu continuu de ‘dimensiune’ octeţi, returnând un pointer de tipul void la începutul blocului alocat, dacă s-a realizat alocarea cu succes, sau pointerul NULL dacă nu se poate aloca memorie; void *calloc (size_t n , size_t dim), alocă spaţiu continuu pentru n elemente de date, fiecare necesitând ‘dim’ octeţi. Spaţiul alocat este iniţializat cu zero. Dacă s-a alocat, returnează un pointer la începutul spaţiului alocat, altfel returnează pointerul NULL. Când se termină operarea cu memoria ce a fost alocată dinamic, cu funcţiile malloc() sau calloc(), spaţiul de memorie poate fi eliberat (cedat sistemului) prin aplicarea funcţiei free(): 8

void *free (void *pointer), eliberează blocul de memorie referit de pointer, ce a fost alocat de una dintre funcţiile calloc( ) sau malloc( ). Aceste funcţii se află în fişierul antet standard <stdlib.h> (şi ). În C++ pentru operaţii de alocare / eliberare de memorie se utilizează operatorii (funcţiile) new şi delete. Operatorul new încearcă să creeze un obiect de tipul specificat (nume) prin alocarea, dacă e posibil, de sizeof (nume) octeţi în memoria disponibilă (denumită “heap”). Durata de alocare e până la eliberare, cu operatorul delete sau până la sfârşitul programului. Dacă alocarea se face cu succes, new returnează un pointer către această zonă, altfel un pointer nul. Trebuie testat pointerul returnat, la fel ca la funcţia malloc. Dar, spre deosebire de aceasta, new calculează dimensiunea spaţiului de memorie necesar (sizeof(nume)) fără a fi nevoie de utilizarea explicită a operatorului. De asemenea pointerul returnat este de tipul corect, pointer la “nume”, fără să fie necesară prezenţa operatorului de conversie: (nume *)malloc( sizeof( nume)). Sintaxa sa de utilizare este: ptr_nume = new nume; Respectiv delete ptr_nume; Utilizarea variabilelor dinamice asigură o administrare eficientă a spaţiului de memorie.

1.1 Liste simplu înlănţuite (stive şi cozi) Aceasta este cea mai simplă structură de date dinamice. O listă este o colecţie de elemente de informaţie (denumite şi noduri) aranjate într-o anumita ordine. Lungimea listei este dată de numărul de noduri din listă. Operaţiile curente cu liste trebuie să permită, la un moment dat, să determinăm care este primul/ultimul nod în listă şi care este predecesorul/succesorul (dacă există) pentru un nod dat. Să considerăm următoarea listă înlănţuită de tip stivă (LIFO-Last In First Out, adică ultimul element introdus în listă este primul ce poate fi extras): primul NULL ‘Y’ ‘X’ ‘Z’ care porneşte de la o singură variabilă, pointerul primul şi trei elemente de tip st_litera. Într-o lista de tip stivă elementele se pot extrage în ordinea inversă introducerii în listă. Să vedem cum se poate creea prin program o astfel de structură. În primul rând declaraţiile pentru o astfel de structură vor fi: struct st_litera { char car; struct litera *urmator; }; struct st_litera *vr, *primul; Iniţial lista este vidă, deci putem scrie: primul = NULL; În continuare este nevoie să inserăm un element în această listă. În primul rând trebuie creat acest element: vr = (struct st_litera *) malloc ( sizeof ( struct st_litera)); primul vr

9

După aceasta trebuie actualizate câmpurile noului element: vr -> car = ‘Z’; primul

vr ‘Z’

vr -> urmator = primul; primul

vr NULL ‘Z’

Valoarea curentă pentru primul este NULL şi efectul acestei instrucţiuni este de a pune NULL la vr -> urmator. Pentru ca variabila primul să refere primul element din listă vom realiza atribuirea: primul = vr;/* acum şi variabila primul va referi adresa referită de vr */ vr NULL ‘Z’ primul

Pentru a insera un nou element (caracterul ‘Y’) în listă vom proceda în aceeaşi manieră: vr = (struct st_lista *) malloc ( sizeof ( struct st_lista )); vr -> car = ‘Y’; vr -> urmator = primul; şi se obţine: primul

vr NULL ‘Y’

‘Z’

iar după instrucţiunea: primul = vr; /* ‘primul’ va referi caracterul referit de ‘vr’, adică ‘Y’ */ primul

vr NULL ‘Y’

‘Z’

În mod asemănător se introduce în lista, de tip stivă, şi elementul următor pentru a obţine lista iniţială, prezentată la începutul paragrafului.

10

Să utlizăm, în continuare, această tehnică de inserare pentru a crea o listă înlănţuită cu o structură de tip stivă. Vom scrie programul pentru citirea unui şir de caractere, memorarea lor într-o astfel de listă şi tipărirea lor în ordine inversă. /* stivacar.c - programul construieste o stiva de caractere, pe care apoi o tipareste */ #include <stdio.h> struct st_lista { char car; struct st_lista *urmator; }; void main() { struct st_lista *vr, *primul; char c; primul = NULL; printf("\nProgramul construieste si afiseaza o stiva de caractere.\n"); printf("Introduceti caractere (CTRL-Z, Enter-pentru sfarsit):\n"); fflush(stdin); while ((c=getchar()) != EOF) if (c!='\n') {vr=(struct st_lista *) malloc(sizeof(struct st_lista)); if (vr == NULL) { /* daca pointerul returnat de functia malloc() este NULL */ printf("Memorie plina !!!!!!\n"); /* se tipareste un mesaj de eroare */ break; /* si se termina executia ciclului de citire caractere */ } vr->car=c; vr->urmator=primul; primul=vr; } vr=primul; /* initializare pointer curent, vr, pentru a referi primul caracter */ while (vr != NULL) { printf("%c -> ", vr->car); vr=vr->urmator; } printf(" NULL");/* tiparire sfarsit lista caractere sau lista vida daca primul era NULL */ } Să considerăm acum aceeaşi problemă, dar cu condiţia de a introduce în listă şi de a tipări numai caracterele distincte. Pentru această situţie vom defini o funcţie întreagă, pe care o vom numi distinct, care va returna valoarea 1 (adevărat) dacă caracterul este diferit de restul listei (deci nu apare 11

între caracterele introduse în listă până în acel moment) şi va returna 0 (fals) dacă caracterul este găsit în listă. /* stivcdif.c - programul construieste o stiva de caractere distincte, pe care apoi o tipareste */ #include <stdio.h> struct st_lista { char car; struct st_lista *urmator; }; void main() { struct st_lista *vr, *primul; char c; int distinct (struct st_lista *prim, char ch); primul = NULL; printf("\nProgramul construieste si afiseaza o stiva de caractere.\n"); printf("Introduceti caractere (CTRL-Z, Enter-pentru sfarsit):\n"); fflush(stdin); while ((c=getchar()) != EOF) if (c != '\n' && (distinct(primul, c))) { vr=(struct st_lista *) malloc(sizeof(struct st_lista)); if (vr == NULL) { /* daca pointerul returnat de functia malloc() este NULL */ printf("Memorie plina !!!!!!\n"); /* mesaj de eroare */ break; /* si se termina executia ciclului de citire caractere */ } vr->car=c; vr->urmator=primul; primul=vr; } vr=primul; /* initializare pointer curent, vr, pentru a referi primul caracter */ while (vr != NULL) { printf("%c -> ", vr->car); vr=vr->urmator; } printf(" NULL");/* tiparire sfarsit lista caractere sau lista vida daca primul era NULL */ } int distinct (struct st_lista *prim, char ch) { struct st_lista *ptr; 12

int gasit; ptr=prim; /* initializare pointer curent cu primul din lista */ gasit=0; /* presupunem ca nu l-am gasit inca */ while (ptr != NULL && !gasit) /* cat timp nu s-a terminat lista si nu l-am gasit */ { /* se continua parcurgerea listei */ gasit=(ptr->car == ch); ptr=ptr->urmator; } return (!gasit); } Să considerăm acum un alt tip de listă înlănţuită, şi anume una de tip FIFO (First In First Out), adică primul intrat în listă este şi primul care poate fi extras. O astfel de structură mai este denumită şi coadă sau coadă (şir) de aşteptare, întrucât elementele se introduc pe la un capăt şi sunt accesibile pe la celălalt capăt, deci la un moment dat este accesibilă numai prima componentă introdusă în listă. Vom considera de această dată problema construirii unei liste înlănţuită formată din cuvinte şi apoi tipărirea acestor cuvinte în ordinea în care au fost introduse. Vom defini două funcţii: una pentru ataşarea unui element (cuvânt) la sfârşitul listei, iar cea de-a doua pentru extragerea, adică afişarea cuvintelor din lista de tip coadă, cu eliberarea spaţiului de memorie alocat dinamic pentru această structură. /* coadacuv.c - programul construieste o coada de cuvinte, pe care o afiseaza, la terminarea introducerii de cuvinte, cu eliberarea spatiului alocat pentru aceasta structura */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include #define SIR_VID "" #define DIMCV 25 struct st_cuvant { char *cuvant; /* pointer la sirul de caractere (cuvant) */ struct st_cuvant *urmator; }; int ncl=0; /* numar de cuvinte afisate pe linie */ struct st_cuvant * atasare_coada (struct st_cuvant *ultim, char *sirc) { struct st_cuvant *vr; vr=(struct st_cuvant *) malloc(sizeof(struct st_cuvant)); if (vr) /* daca s-a putut crea un pointer se continua atasarea */ { vr->cuvant=strdup(sirc); vr->urmator=NULL; ultim->urmator=vr; } return (vr); 13

} void extragere ( struct st_cuvant * primu) { struct st_cuvant *ptr; while (primu) {ptr=primu; /* memorat pentru a elibera spatiul referit de el */ printf (" %s -> ", primu->cuvant); ncl++; if (ncl%5==0) printf("\n"); primu=primu->urmator; free(ptr); /* eliberarea spatiului alocat pointerului */ } printf ("NULL\n");/* sfarsit lista sau lista vida daca primu == NULL */ } void main() { struct st_cuvant *primul, *ultimul; char cuv[DIMCV]; clrscr(); printf("Programul construieste o lista de tip coada cu cuvinte de la" " tastatura\n"); printf("Programul ia sfarsit cu un cuvant vid, adica RETURN," " la inceput de linie.\n"); printf("Cuvant de introdus in lista:"); gets(cuv); primul=(struct st_cuvant *) malloc(sizeof(struct st_cuvant)); primul->cuvant=strdup(cuv); primul->urmator=NULL; ultimul=primul; printf("Cuvant de introdus in lista:"); gets(cuv); while (strcmp(cuv, SIR_VID)) { if(!(ultimul=atasare_coada (ultimul, cuv))) break; printf("Cuvant de introdus in lista:"); gets(cuv); } extragere (primul); } O altă operaţie necesară în aplicaţii cu liste înlănţuite este introducerea unui element în orice punct din listă, astfel încât elementele listei să respecte o anumită ordine. Vom defini o funcţie care inserează un nou element, marcat prin referinţa nou, după un element din listă, marcat prin variabila pointer curent. void insereaza_dupa (struct st_orice_tip *curent; struct st_orice_tip *nou) {nou -> urmator = curent -> urmator; 14

curent -> urmator = nou; } Această funcţie se utilizează când avem o variabilă pointer (cum este pointerul curent) după care se inserează noul (nou) element al listei. Inserarea se poate face şi înaintea unui element din listă, dar este mai dificilă deoarece lista este unidirecţională şi nu ne putem referi la predecesorul unui element, ci numai la succesorul său. Această problemă se poate rezolva în două moduri: fie prin parcurgerea listei de la început şi determinarea poziţiei unde se face inserarea, fie prin inserarea după elementul respectiv (curent), urmată de interschimbarea conţinuturilor celor două variabile, mai puţin a legăturilor (referinţelor). În primul caz funcţia pentru inseare va fi următoarea: void insereaza_inainte (struct st_orice_tip *curent, struct st_orice_tip *nou, struct st_orice_tip *primul) { /* se insereaza elementul ‘nou’ in fata celui ‘curent’ */ struct st_orice_tip aici; /* va reprezenta locul unde se insereaza ‘nou’ */ if ( curent == primul ) /* testeaza daca trebuie inserat in fata primului element */ { /* daca da, se pune primul in lista */ nou -> urmator = curent; /* deci ‘curent’ devine ‘primul’ */ primul = curent; } else {/* daca nu, i se determina pozitia de inserare in lista */ aici = primul; /* care va fi intre ‘aici’ si ‘curent’ */ while ( aici -> urmator != curent ) aici = aici -> urmator; /* ‘aici’ va fi predecesorul lui ‘curent’*/ aici -> urmator = nou; /* si se insereaza intre cei doi pointeri */ nou -> urmator = curent; } } Utilizând cea de-a doua metodă, rezută următorea funcţie: void insereaza_inainte (struct st_orice_tip *curent, struct st_orice_tip *nou) { /* se insereaza elementul ‘nou’ in fata celui ‘curent’ , prin inserarea lui ‘nou’ dupa ‘curent’ si apoi se inverseaza valorile referite de acesti doi pointeri, astfel incat valorea lui ‘nou’ sa fie in fata lui ‘curent’ */ tip_info val_info; /* variabila de acelasi tip cu tipul valorilor referite de pointeri */ nou -> urmator = curent -> urmator; /* se insereaza ‘nou’ dupa ‘curent’ */ curent -> urmator = nou; val_info = curent -> info; /* dupa care se interschimba valrile referite de cei */ curent -> info = nou -> info; /* doi pointeri, astfel ca in lista, valorile sa fie in */ nou -> info = val_info; /* ordinea dorita */ } Dacă lista este foarte mare, cea de-a doua funcţie este mai bună, deoarece nu parcurge lista, ceea ce ar lua destul timp. Dacă, însă, lista este scurtă, dar fiecare element are asociată multă informaţie, adică fiecare componentă este destul de mare, este preferabilă prima funcţie. Cea de-a doua metodă nu poate fi folosită dacă structurile asociate componentelor conţin şi alte variabile referinţă (pointeri). 15

Operaţia inversă celei de inserare este cea de eliminare din listă a unui element. Eliminarea elementului “curent”, chiar dacă este primul din listă, se face astfel: void eliminare_elem_curent (struct st_orice_tip *curent, struct st_orice_tip *primul) { struct st_orice_tip *elimin; /* pointer local la elementul de eliminat (curent)*/ if ( curent == primul ) /* daca trebuie eliminat chiar 'primul' */ primul = curent -> urmator; /* devine 'primul' campul 'urmator' */ else { /* altfel trebuie determinata pozitia elementului de eliminat */ elimin = primul; while ( elimin -> urmator != curent ) elimin = elimin -> urmator; elimin -> urmator = curent -> urmator;/* elimnarea propriu-zisa */ } free (curent); } Eliminarea unui element situat după un element marcat prin variabila referinţă ‘curent’ se face astfel: void eliminare_elem_dupa (struct st_orice_tip *curent) {struct st_orice_tip *elimin; /* elementul de eliminat */ elimin = curent -> urmator; /* salvarea referintei la urmatorul celui ce va fi eliminat */ curent -> urmator = elimin -> urmator;/* refacerea legaturii ocolind elementul eliminat */ free (elimin); /* eliberare spatiu de memorie ocpat de element */ } Să considerăm un alt exemplu, şi anume să construim o listă ordonată crescător de numere întregi, distincte (copiile nu se mai inserează în listă). Inserarea elementului curent în listă se va face înaintea primului element ce are în câmpul de informaţie o valoare mai mare decât cea din elementul de inserat, şi după cel ce conţine o valoare mai mică (dacă există, altfel valoarea de inserat va deveni prima). Inserarea înaintea elementului respectiv se poate face folosind una dintre metodele anterioare, sau întrucât tot parcurgem lista de la început pentru fiecare element nou, putem să utilizăm două variabile referinţă la două elemente succesive din listă, notat anterior şi curent, care vor referi elementul curent şi cel anterior lui. După afişarea listei, memoria alocată este eliberată (utilizând funcţia free()). /* listord.c - construiete o lista ordonata de numere intregi, distincte */ #include <stdio.h> #include <stdlib.h> #include struct st_numar { int numar; struct st_numar *next; }; int nvl=0; /* numarul de valori afisate pe linie */ void main() { struct st_numar *inserare (struct st_numar *, int ); 16

struct st_numar *prim, *vr; int nr; clrscr(); printf("Programul construieste o lista ordonata, de numere distincte.\n"); printf("Introducerea numerelor se termina cu o valoare nenumerica.\n"); printf("Numar de inserat in lista: "); prim=(struct st_numar *) malloc(sizeof (struct st_numar)); scanf("%d", &prim->numar); /* citire numar de introdus in lista */ prim->next=NULL; printf("Numar de inserat in lista: "); while (scanf("%d", &nr)==1){ prim=inserare (prim, nr); printf("Numar de inserat in lista: "); } /* tiparirea listei introduse cu eliberarea memoriei alocate */ printf("\nLista de numere ordonata este:\n"); while (prim) {vr=prim; /* variabila auxiliara pentru a apela functia free() */ printf("%d -> ", vr->numar); nvl++; if (nvl%8==0) /* daca s-au tiparit 8 valori pe linie */ printf("\n"); /* se trece pe o linie noua */ prim=prim->next; free(vr); /* eliberare memorie alocata pentru vr */ } printf("NULL\n"); /* tiparire sfarsit de lista */ } struct st_numar *inserare (struct st_numar *primul, int n){ /* daca nu se mai poate aloca memorie se rutrneaza poiterul NULL, altfel se returneaza pointerul la primul numar din lista, care se poate modifica daca se insereaza un numar mai mic decat primul din lista */ struct st_numar *anterior, *curent, *vr; vr=(struct st_numar *) malloc(sizeof(struct st_numar)); if (vr == NULL){ printf("\nNu mai introduceti numere!!!\nMEMORIE PLINA!!!\n"); return (primul); } else { vr->numar=n; anterior=NULL; /* initializare pointeri 'anterior' si 'curent' */ curent=primul; /* pentru det. pozitie element de inserat, vr */ while (curent != NULL && vr->numar > curent->numar) { anterior=curent; curent=curent->next; } /* vr trebuie inserat intre anterior si curent */ 17

if(vr->numar == curent->numar) /* daca numarul exista in lista */ {free(vr); /* elibereaza spatiul alocat variabilei 'vr' */ return (primul); /* nu mai insereaza si termina inserarea */ } vr->next=curent; if (anterior == NULL) /* se insereaza in fata primului din lista */ primul=vr; /* este pus primul in lista */ else anterior->next=vr; /* este pus dupa 'anterior' */ return (primul); } } Tratarea recursivă a unei liste Lista este un exemplu de structură de date recursivă (în exemplul anterior, struct st_numar), întrucât un câmp al ei (next) face referire la definiţia structurii ( struct st_numar * ). În al doilea rând o listă înlănţuită poate fi definită recursiv, astfel: lista poate fi vidă sau poate consta dintr-un element ce conţine o referinţă la listă. O altă caracteristică de recursivitate a unei liste este aceea că se pot scrie funcţii recursive pentru tratarea listelor. În acest caz corpul funcţiei conţine, în principiu, definiţia anterioară şi o instrucţiune if, care este necesară pentru a separa tratarea operaţiilor necesare unei liste vide, de cealaltă situaţie corespunzătoare tratării unui singur element al listei şi apoi apelul recursiv al funcţiei pentru tratarea restului listei. Vom relua problema citirii unui şir de cuvinte (un text) şi afişarea lor în ordinea citirii, utilizând pentru cele două operaţii, ataşare element în listă şi afişare un element din listă, două funcţii recursive. /* listrec1.cpp - programul construieste o lista de cuvinte, introduse de la tastatura, pe care apoi le afiseaza, utilizand functii recursive: atsare - pentru construire lista, si afisare - pentru afisare lista; Varianta 2: elementul din lista contine adresa cuvantului citit, pentru care se aloca spatiu (strdup) la citire; */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include #define SIR_VID "" #define DIMC 25 int nvl=0; struct st_cuvant { char *cuvant; /* pointer la sirul de caractere (cuvant) */ struct st_cuvant *urmator; }; int atasare (struct st_cuvant * vr) { /* citeste un cuvant, creaza o variabila dinamica vr si o ataseaza la lista */ char cuv[DIMC], *pc; if (vr->urmator==NULL) /* daca referinta este NULL se ceaza un pointer */ { 18

else

vr->urmator=(struct st_cuvant *)malloc(sizeof(struct st_cuvant)); if (vr->urmator==NULL) return (0); else { gets(cuv); if (!strcmp(cuv,SIR_VID)) {vr->urmator=NULL; return(0); } else {if(!(pc=strdup(cuv))) {vr->urmator=NULL; return(0); } else { vr=vr->urmator; vr->urmator = NULL; vr->cuvant=pc; return (1); } } } } /* daca s-a putut crea un pointer se continua atasarea */ return(atasare (vr->urmator));

} void afisare (struct st_cuvant * curent) { if (curent) { printf ("%s -> ", curent -> cuvant); nvl++; if(nvl%5==0) printf("\n"); afisare (curent -> urmator); } } void main() { struct st_cuvant *primul; char c[DIMC]; clrscr(); printf("Programul construieste o lista de tip coada cu cuvinte de la" " tastatura\n"); printf("Programul ia sfarsit cu un cuvant vid, adica RETURN," " la inceput de linie.\n"); 19

gets(c); primul->cuvant=strdup(c); primul->urmator=NULL; while (atasare(primul)); afisare (primul); printf("NULL\n"); } Alte operaţii uzuale asupra unei liste simplu înlănţuite, de tip coadă sau stivă, sunt descrise în continuare. Determinarea lungimii unei liste. typedef struct st_tip_info TINF; typedef struct st_lista { TINF info; struct st_lista* urm; } TEl, * TLista, ** ALista; /* tipurile: element lista, lista si adresa lista*/ size_t LungL (TLista L) {if (!L) return (0); return (1+LungL(L->urm)); } Afişarea conţinutului unei liste în ordine inversă: void AfisInv (TLista L) { if (!L) return; AfiInv (L->urm); printf ("%s, ", L->info); /* am presupus ca lista contine cuvinte*/ } Căutarea unui element în listă, care îndeplineşte o anumită condiţie descrisă de funcţia de prelucrare (f, de tipul TFPrelEl) care returnează o anumită valoare transmisă ca parametru (Gasit). TLista PrimEl (TLista L, TFPrelEl f, int Gasit) /* intoarce adresa primului gasit sau NULL */ { for (; L != NULL; L = L->urm) if ( f (L->info) == Gasit ) return L; return NULL; } TLista UltimEl (TLista L, TFPrelEL f, int Gasit) /* intoarce adresa ultimului gasit sau NULL */ { TLista ultim = NULL; for (; L != NULL; L = L->urm) if ( f (L->info) == Gasit ) ultim = L; return u; } 20

Prototipul funcţiei transmisă ca parametru (pointer la funcţie) este următorul: typedef int (* TFPrelEl)(const void *p,...); /* pointer la functie de prelucrare element lista - p - adresa element -*/ Căutarea unei legături (adrese) spre o celulă: ALista CautaEl (ALista aL, TFPrelEl f, int Gasit) /* intoarce adresa legaturii spre celulaş functia primeste adresa unei celule */ { TLista a = *aL, p = NULL; /* elementul actual, predecesor */ while (a) { if (f(&a->info) == Gasit) break; p = a; a = p-> urm; } if (!p) return aL; /* oprire la inceput */ return &(p->urm); /* oprire in interior */ }

1.2. Liste dublu înlănţuite Pentru a simplifica operaţia de inserare într-o listă înlănţuită, înainte sau după componenta curentă se poate utiliza o listă dublu înlănţuită. Într-o astfel de listă fiecare componentă conţine, pe lângă informaţia propriu-zisă, două referinţe: una la componenta anterioară şi una alta la componenta următoare; structura unei liste dublu înlănţuite de caractere va fi: struct st_tip_lista { st_tip_info info; struct st_tip_lista *anterior, *urmator; }; Pentru parcurgerea eficientă, în oricare din cele două sensuri, este necesar accesul la cele două extremităţi ale listei (primul şi ultimul). Pentru o astfel de listă putem defini un element (o celulă) care să conţină adresele primului şi ultimului element din listă (în câmpurile respective, anterior şi următor), pentru a permite accesul la cele două capete ale listei. În acest caz, elementul de acces la listă conţine cele două adrese (primul şi ultimul) iar câmpul informaţie nu este folosit; ultimul element din listă va conţine în câmpul urmator pointerul NULL, după cum primul element ca conţine în câmpul anterior pointerul NULL. Se observă că în această abordare există diferenţe de tratare în cazul operaţiilor asupra listei (inserare / eliminare) la extremităţi, deoarece acestea afectează fie câmpul primul, fie câmpul ultimul. Pentru o tratare uniformă se poate adopta soluţia de organizare ca listă circulară (cu santinelă). Câmpul info al celulei santinelă (de început, start, a listei circulare) poate fi utilizat pentru păstrarea adresei sau valorii unor informaţii cu caracter general, cum ar fi referinţa la funcţia de verificare a relaţiei de ordine în cazul în care elementele din listă sunt ordonate, după un anumit criteriu (funcţie). Dacă, prin construcţie, se leagă între ele, ultima componentă cu prima se obţine o listă dublu înlănţuită circulară. Lista circulară vidă se consideră formată dintr-un element legat la el însuşi, fără a conţine informaţie. 21

Pentru această structură funcţiile de inserare a unui element nou, înainte sau după elementul curent, devin: void inserare_dupa (struct st_tip *curent; struct st_tip *nou) {/* inserare element ‘nou’ dupa elementul ‘curent’ */ nou -> urmator = curent -> urmator; nou -> anterior = curent; curent -> urmator -> anterior = nou; curent -> urmator = nou; } void inserare_inainte ( struct st_tip *curent; struct st_tip *nou) {/* inserare element ‘nou’ inainte de elementul ‘curent’ */ nou -> urmator = curent; nou -> anterior = curent -> anterior; curent -> anterior -> urmator = nou; curent -> anterior = nou; } Iar procedura de eliminare a unui element, curent, dintr-o astfel de listă dublu înlănţuită va fi: void eliminare (struct st_tip *curent) { curent -> anterior -> urmator = curent -> urmator; curent -> urmator -> anterior = curent -> anterior; } Parcurgerea unei liste circulare nu este la fel de simplă ca în cazul parcurgerii unei liste înlănţuite în care există referinţa NULL şi care reprezintă o condiţie de oprire a parcurgerii listei (de terminare a ei). Parcurgerea listei circulare presupune memorarea punctului de plecare (santinela, denumită în continuare start), printr-un pointer, şi compararea pointerului curent din listă cu pointerul de start. Parcurgerea ia sfârşit când poziţia curentă ajunge în punctul de plecare. Parcurgerea listei de la început: for ( x = start->urmator; x != start; x = x->urmator ) {. . . .} Parcurgerea listei de la sfârşit: for ( x = start->anterior; x != start; x = x->anterior ) {. . . .} De exemplu, să definim o funcţie care determină de câte ori se repetă, într-o listă circulară ce conţine caractere, deja creată, caracterul aflat în câmpul respectiv al variabilei referinţă (pointer) start. Funcţia va primi caracterul căutat în santinelă (start->car) şi va returna caracterul căutat (referinţa acestuia) şi numărul său de apariţii în lista circulară (numar_aparitii_car). struct st_litera { char car; struct st_litera *urmator; }; int numar_aparitii_car (struct st_litera *start, char *pcar) { int numar = 0; 22

struct st_litera *curent; /* pointerul cu care se parcurge lista */ *pcar=start->car; /* se transmite prin adresa primita, caracterul cautat*/ curent=start->urm; while (curent != start) /* cat timp referinta la urmatorul din lista */ { /* nu a ajuns la santinela/ start */ if (start->car == curent->car) /* se numara daca este caracterul */ numar++; curent=curent->urm; } return (numar); } Se poate constata că listele circulare dublu înlănţuite sunt mai uşor de prelucrat (operaţii de eliminare, inserare etc.) decât listele simplu înlănţuite, deoarece pentru operaţii simple nu este necesară o parcurgere prealabilă. În schimb listele circulare sunt mai voluminoase (deoarece fiecare eleement conţine o referinţă în plus) şi gestionarea lor este mai lentă deoarece ea trebuie să actualizeze mai multe referinţe (pointeri).

1.3. Arbori Aceste structuri de tip arbore sunt foarte des întâlnite: - structura informaţiei înregistrată pe un suport magnetic (disc), cu directoare şi subdirectoare, este un arbore generalizat (sau multicăi, întrucât are mai mulţi descendenţi, subarbori); - cuprinsul unei cărţi (arbore multicăi); - organizarea administrativă a societăţilor comerciale, universităţi, etc.; - structura aparatelor de orice fel (acestea au unităţi funcţionale, compuse la randul lor din subansamble); - programul meciurilor dintr-un turneu eliminatoriu (arbore binar); - arborele unei expresii aritmetice (arbore binar); Variabilele referinţă pot fi folosite pentru reprezentarea de structuri mai generale decât listele. Astfel pot fi reprezentate grafurile orientate: nodurile grafului sunt reprezentate prin structuri iar arcele sunt reprezentate prin referinţe. un caz particula al grafurilor îl reprezintă arborii. Un arbore este format dintr-un nod radacină, căruia ii este ataşat un numar finit de subarbori. Orice nod dintr-un arbore poate fi privit ca rădacina a unui (sub)arbore. Arborele are două proprietăţi: substructurile legate la orice nod sunt distincte şi există un nod numit rădăcină din care este accesibil orice nod parcurgând un număr finit de arce. Dacă un nod a conţine o referinţă la un alt nod b, atunci a este ascendentul lui b, iar b descendentul lui a. Nodul rădăcină nu are ascendenţi, iar nodurile terminale, numite şi frunze, nu au descendenţi. Ca şi o listă un arbore este o structură recursivă, ce poate fi definit astfel: un arbore este fie vid, fie constituit dintr-un nod ce conţine referinţe la arbori disjuncţi. Iată un exemplu de arbore.

23

A D H G C B E FJI

Un arbore multicăi (denumit şi arbore generalizat) este un arbore în care nodurile pot avea mai mult de 2 subarbori; orice arbore multicăi poate fi transformat în arbore binar. Un caz particular al arborilor îl constituie arborele binar, caracterizat prin faptul că fiecare nod are cel mult doi descendenţi, deci are referinţe la cel mult doi subarbori. Exemple de arbori binari sunt: - arborele genealogic, având ca nod rădăcină om persoană, iar ca noduri descendente cei doi părinţi, nodurile descendente ale acestora cei patru bunici etc. - rezultatele unui turneu eliminator se reprezintă tot printr-un arbore binar, având ca nod rădăcină pe câştigător, nodurile descendente ale acestuia pe cei doi finalişti, următoarele noduri descendente sunt cei patru semifinalişti etc. Într-un arbore binar fiecare nod se reprezintă printr-o structură având minim trei câmpuri: un câmp ce conţine informaţia din nod şi cele două referinţe la cei doi subarbori, notaţi stâng (st) şi drept (dr). struct st_arbore { tip_informatie info; struct st_arbore *st, *dr; }TNod, *AArb; Parcurgerea unui arbore binar poate fi definită recursiv pentru fiecare nod al acestuia: prelucrarea informaţiei din nod; parcurgerea subarborele stâng; parcurgerea subarborele drept; Modificând ordinea acestor operaţii se pot defini 6 moduri diferite de parcurgere a unui arbore. Dacă însă impunem ca parcurgerea să înceapă întotdeauna cu subarborele stâng înaintea celui drept rămân numai 3 moduri de parcurgere (în adâncime): - parcurgere în preordine, denumită şi rădăcină-stângă-dreapta RSD, care prelucrează mai întâi informaţia din nod şi apoi parcurge subarborii (bineînţeles în ordinea stânga-dreapta); - parcurgere în inordine, sau SRD, în care ordinea este: parcurgere subarbore stâng, prelucrează nodul, parcuregere subarbore stâng; - parcurgere în postordine, sau SDR, în care ordinea este: parcurgere subarbori dreapta-stânga, prelucrează informaţia din nod. Să considerăm următoarea structură de arbore binar, pentru a exemplifica cele trei moduri de parcurgere (în adâncime) a unui astfel de arbore.

24

D A G H B C E FI

Cele trei moduri de parcurgere a arborelui vor parcurge arborele în următoarele secvenţe: - preordine (RSD)

E B A D C F H G I

- inordine (SRD)

A B C D E F G H I

- postordine (SDR)

A C D B G I H F E

Să considerăm o altă structură de arbore binar, reprezentând o expresie aritmetică, şi să percurgem (în adâncime) acest arbore (prin cele trei metode). + db*eca/

25

preordine (RSD): inordine (SRD): postordine (SDR):

+(*(a,+(b,c)),/(d,e)) ((a*(b+c))+(d/e)) ((a,(b,c)+)*,(d,e)/)+

Expresiile aritmetice pot fi reprezentate utilizând arbori binari, respectând următoarele reguli: - fiecare operaţie aritmetică corespunde unui nod neterminal, care conţine operaţia respectivă, iar subarborii săi reprezintă operanzii săi, în ordinea, primul operand este cel din stânga şi apoi cel din dreapta; - fiecare nod terminal conţine o variabilă sau o constantă; - rădăcina conţine ultima operaţie ce se efectuează. Parcurgerea arborelui în postordine va furniza forma poloneză asociată unei expresii aritmetice, ca în exemplul prezentat anterior. Se pot descrie funcţii recursive de parcurgere a unui arbore binar pentru oricare dintre cele trei moduri. Iată, de exemplu, funcţia pentru pacurgerea în preordine (RSD). void preordine (AArb arbore) { if (arbore != NULL) { prelucreaza ( arbore); preordine (arbore -> st); preordine (arbore -> dr) } } Modificând ordinea operaţiilor se pot obţine şi celelate două modri de parcugere. Vom descrie în continuare alte funcţii des utilizate în aceste aplicaţii. Prima este o funcţie de inserare a unei valori printre valorile unui arbore binar ordonat (sau de căutare, cum mai este denumit); informaţiile asociate nodurilor pot fi numere, scalari, şiruri de carctere ordonate alfabetic sau alte structuri ordonate după o anumită cheie. Inserarea unei noi valori presupune adăugarea unui nod frunză la arbore. Locul de inserare depinde de poziţia relativă a informaţiei acestui nod faţă de informaţiile deja existente în arbore. Dacă arborele este NULL înseamnă că am găsit poziţia corespunzătoare pentru noul nod, altfel se compară informaţia de inserat cu informaţiile referite de arbore: dacă sunt mai mici se continuă căutarea în subarborele stâng, dacă sunt mai mari se continuă căutarea în subarborele dreapta. int inserare (AArb arbore; tip_informatie val) { if ( val < arbore -> info ) if (arbore->st) /* exista aceasta ramura ? */ inserare ( arbore -> st , val ); /* exista, se continua cautarea pe ramura stanga */ else { /* se insereaza aici, intrucat ramura nu exista; se creaza nodul */ arbore->st = ( struct st_arbore ) malloc ( struct st_arbore); if ( arbore->st == NULL) /* nu mai este memorie disponibila */ return ( 0 ); else {arbore=arbore->st; /* daca nu este NULL se asociaza valoarea */ arbore -> st = NULL; /* si se initializeaza referintele */ arbore -> dr = NULL;/* stanga si dreapta cu NULL */ arbore -> info = val; return ( 1 ); } } 26

else if ( val > arbore -> info ) if (arbore->dr) /* exista aceasta ramura ? */ inserare ( arbore -> dr , val );/* exista, continua cautarea pe ramura dreapta */ else { /* se insereaza aici, intrucat ramura nu exista; se creaza nodul */ arbore->dr = ( struct st_arbore ) malloc ( struct st_arbore); if ( arbore->dr == NULL) /* nu mai este memorie disponibila */ return ( 0 ); else {arbore=arbore->dr; /* daca nu este NULL se asociaza valoarea */ arbore -> st = NULL; /* se initializeaza referintele subarbori */ arbore -> dr = NULL;/* stanga si dreapta cu NULL */ arbore -> info = val; return ( 1 ); } } else return ( 1 ); /* nodul exista deja; se poate adauga un camp care sa contorizez numarul de aparitii a valorii respective */ } O altă operaţie des utilizată este cea de căutare a unei informaţii (val) într-un arbore. Vom descrie o funcţie care caută, cauta, şi care returnează referinţa către un nod al arborelui ce conţine informţia căutată, sau returnează NULL dacă un astfel de nodnu se află în arbore. AArb cauta ( AArb arbore, tip_informatie val) {int gata = 0; do { if ( arbore == NULL) gata = 1; else { if ( val < arbore -> info) arbore = arbore -> st; else if ( val > arbore -> info) arbore = arbore -> dr; else gata = 1; } }while ( ! gata ); return ( arbore ); } Funcţia poate fi definită şi recursiv. AArb cauta ( AArb arbore, tip_informatie val) { if ( arbore == NULL) return ( NULL ); else 27

if ( val < arbore -> info) return ( cauta( arbore -> st) ); else if ( val > arbore -> info) return ( cauta( arbore -> dr) ); else return ( arbore ); } Operaţia de eliminare a unui nod, care nu este nod frunză, dintr-un arbore binar este mai dificilă, deoarece trebuie să ne asigurăm că arborele rămâne tot binar. Un arbore binar de căutare (ordonat) este o structură de date mult mai bună pentru memorarea şi căutarea datelor. Cu un astfel de arbore, cu N noduri, timpul necesar pentru inserarea sau eliminarea unui nod este proporţional cu log2N, în timp ce durata necesară aceloraşi operaţii într-un tablou, efectuând o căutare liniară este prporţională cu N. Să considerăm un alt exemplu, şi anume un program care citeşte un text şi afişează lista de cuvinte din text precum şi numărul de apariţii pentru fiecare cuvânt din text. Vom rezolva această problemă, utilizând pentru memorarea cuvintelor un arbore binar de căutare, în locul unui tablou. Căutarea într-un astfel de arbore este mult mai rapidă şi în plus va tipări cuvintele în ordine alfabetică fără să le mai sortăm, întrucât arborele este astfel construit încât ele sunt în ordine alfabetică. În schimb, această metodă va necesita mai mult spaţiu de memorie, deoarece fiecare nod va conţine, pe lângă cuvântul respectiv şi numărul său de apariţii şi două referinţe. /* arbrecc.c - arbore, construit recursiv, ce contine cuvinte, si numarul de aparitie a acestora, citite de la tastatura (cate un cuvant pe linie) introducerea cuvintelor se termina cu un cuvant vid (Enter la inceputul liniei), si apoi sunt afisate cuvintele in ordine alfabetica */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include #define LUNGMAX 20 struct st_arbore { char *cuvant; /* pointer la cuvantul citit */ int nrap; /* numarul de aparitii */ struct st_arbore *st, *dr; }; int nle=0; void actualizare (struct st_arbore * arb , char *cuv){ /* Functia actualizeaza arborele binar. Daca cuvantul nu a mai fost citit se creaza un nou nod, altfel se incrementeaza contorul de aparitii al nodului corespunzator cuvantului citit anterior. Se determina pe care ramura a arborelui se va insera cuvantul, sau daca exista deja */ if (strcmp(cuv, arb->cuvant) < 0) if (arb->st) actualizare (arb->st, cuv); 28

else

{ arb->st=(struct st_arbore *) malloc (sizeof(struct st_arbore)) ; arb=arb->st; arb->cuvant=cuv; arb->nrap=1; arb->st=NULL; arb->dr=NULL; } else if (strcmp(cuv, arb->cuvant) >0 ) if(arb->dr) actualizare (arb->dr, cuv); else { arb->dr=(struct st_arbore *) malloc (sizeof(struct st_arbore)) ; arb=arb->dr; arb->cuvant=cuv; arb->nrap=1; arb->st=NULL; arb->dr=NULL; } else arb->nrap=arb->nrap + 1; } void tiparire_arbore (struct st_arbore *arbo) /* functia afiseaza arborele de cautare ce contine cuvinte si numarul lor de aparitii */ { if (arbo!=NULL) { tiparire_arbore (arbo->st) ; /* tiparire arbore stanga */ printf ("%s (ap: %d)\n", arbo -> cuvant, arbo -> nrap ) ; nle++; if (nle%24==0){ printf("Apasati o tasta pentru a continua afisarea!\n"); getch(); } tiparire_arbore (arbo->dr) ; /* tiparire arbore dreapta */ } } void main () {struct st_arbore *arb; char cuvant[LUNGMAX] ; clrscr(); printf("Introduceti cuvinte, care vor fi apoi tiparite in ordine" " alfabetica:\n"); gets(cuvant) ; arb=(struct st_arbore *) malloc (sizeof(struct st_arbore)) ; /* am presupus ca nu se returneaza de catre malloc valoarea NULL */ 29

arb->cuvant=strdup(cuvant); arb->nrap=1; arb->st=NULL; arb->dr=NULL; gets(cuvant) ; while (strcmp(cuvant, "")) {actualizare (arb, strdup(cuvant)); gets(cuvant); } printf("Lista ordonata a cuvintelor (numar aparitii):\n"); tiparire_arbore (arb); } Alţi termeni utilizaţi în legătură cu arborii sunt:

30

ordinul (gradul) unui nod, reprezintă numărul de subarbori ataşaţi nodului; noduri interne, sunt nodurile care au subarbori; noduri externe (noduri terminale sau frunze), sunt nodurile fără subarbori (cu ordin 0); nivelul unui nod este distanşa la care se află faţă de rădăcină (rădăcina are nivelul 0); înălţimea unui arbore este nivelul maxim din arbore. arbore complet de ordin k – toate frunzele se află pe acelaşi nivel şi toate nodurile interne au ordinul k; un astfel de arbore, de înălţime h, are (k(h+1)-1)/(k-1) noduri, dintre care (kh-1)/(k-1) noduri interne si kh frunze; strămoş al unui nod x – orice nod aflat pe calea (unică) de la rădăcină până la nodul x (rădăcina este strămoşul tuturor celorlalte noduri); descendent al unui nod x – orice nod aflat în arborele cu rădăcina x; tată / fiu – noduri aflate la distanţa 1 (numite şi stramoş / descendent direct); fraţi – fiii aceluiaşi nod. Legat de aceste noţiuni se pot realiza operaţiile următoare. Numărul de noduri într-un arbore: int NrNoduri (AArb r) /* numarul de noduri din arborele r -*/ { if (!r) return 0; /* arbore vid => 0 noduri */ return 1 + NrNoduri(r->st) + NrNoduri(r->dr); } Numărul de niveluri într-un arbore (înălţimea = număr niveluri –1) int NrNiv (AArb r) /* numar niveluri (0 pentru arbore vid) */ { int ns, nd; if (!r) return 0; ns = NrNiv (r->st); nd = NrNiv (r->dr); return 1 + (ns >= nd ? ns : nd); } Numărul de frunze dintr-un arbore. #define Frunza(a) ((a)->st == NULL && (a)->dr == NULL) int NrFrunze (AArb a) { if (!a) return 0; if (Frunza(a)) return 1; return NrFrunze (a->st) + NrFrunze (a->dr); } Numărul de noduri de pe nivelul n int NNN (AArb r, int n) /* numar noduri de pe nivelul n */ { if (!r) return 0; if (n == 0) return 1; 31

return NNN(r->st, n-1) + NNN(r->dr, n-1); } Găsirea valorii maxime dintr-un arbore nevid int MaxArb (AArb a) { int m = a->info, t; if (a->st != NULL) { t = MaxArb (a->st); if (t > m) m = t; } if (a->dr != NULL) { t = MaxArb (a->dr); if (t > m) m = t; } return m; } Determinarea nivelului pe care se găseşte o anumită valoare x. int NivVal (AArb a, int x) /*(-1 daca nu exista)*/ { int r; if (!a) return -1; if (a->info == x) return 0; r = NivVal (a->st, x); if (r < 0) { r = NivVal (a->dr, x); if (r < 0) return -1; } return r + 1; } O problemă (operaţie) puţin mai delicată, decât cele prezentate anteror, este cea a eliminării unui nod dintr-un arbore binar de căutare. Problema constă în a determina poziţia în arbore a unei chei, x, ceea ce este simplu într-un arbore de căutare, iar apoi să se elimine nodul cu cheia respectivă. În principiu avem două situaţii, după cum nodul respectiv are ambii succesori (subarbori), sau numai pe unul dintre ei. Mai există şi cazul când nu are succesori, dar aici eliminarea nu este o problemă, doar se eliberează spaţiul de memorie alocat nodului respectiv şi se şterge referinţa din nodul precedent. În situaţia în care nodul de eliminat nu are decât subarborele drept (deci cel stâng este vid), dacă a este adresa nodului cu cheia x (cel de eliminat), atunci se atribuie lui a adresa descendentului drept, ceea ce permite păstrarea proprietăţii arborelui (cea de căutare). Se procedează similar şi pentru cazul în care nodul de eliminat nu are decât subarborele stâng (deci cel drept este vid), adică se atribuie lui a adresa descendentului stâng. Cele două situaţii sunt prezentate în figura următoare. 9426371

32

Din arborele iniţial (cel din stânga) a fost eliminat nodul cu cheia 6, şi se obţine arborele din dreapta. Să considerăm aceeaşi problemă pentru eliminarea nodului ce conţine valoarea 4, din arborele din figura următoare (în partea stângă înainte de eliminare, şi dreapta după eliminare). 94263715

Arborele s-a obţinut prin mutarea valorii maxime din subarborele stâng valorii 4, adică a valorii 3 în locul valorii 4, şi eliminarea frunzei pe care a fost valoarea 3. Mai există şi varianta în care valoarea minimă de pe subarborele drept al nodului ce conţine valoarea 4, adică valoarea 5 se mută în locul valorii 4, şi se elimină nodul în care a fost valoarea 5. Ambele variante vor furniza acelaşi arbore SRD, la listare. Dacă nodul de eliminat, a, cel ce conţine cheia x, are ambii subarbori nevizi, atunci procedeul de eliminare decurge după cum urmează. Se determină cea mai mare valoare din subarborele stâng, adică nodul (frunza) cel mai din dreapta din subarborele stâng, ce conţine valoarea maximă din acest subarbore, imediat mai mică decât cheia x, din arbore. Se va pune această valoare în locul lui x, iar frunza respectivă se şterge. Sau se poate proceda similar pentru subarborele stâng, adică să determinăm cea mai mică valoare din acesta, care va fi valoarea imediat mai mare decât x, din arbore. Întrucât algoritmul este recursiv vom defini o funcţie recursivă pentru eliminare. Întregul program este prezentat în continuare. /* arbelnod.cpp - programul construieste recursiv si tipareste un arbore de numere intregi, utilizand functiile recursive: 'inserare' si 'listare'. Arborele contine pe langa valorile intregi ordonate (SRD) si numarul de aparitii pentru valorile ce se repeta. Programul permite elimiarea unei anumite valori (chei), adica un nod din arbore ce contine cheia, pastrand arborele de cautare (SRD). */ #include <stdio.h> 33

#include <stdlib.h> #include typedef struct tnod {int nr; int ap; struct tnod *pstg; struct tnod *pdr; } ARB; int nel = 0; ARB *e; void inserare (ARB * &v, int val){ ARB *pc; int gasit; if (!v) {v = new ARB; v->nr=val; v->ap=1; v->pstg=NULL; v->pdr=NULL;} else if (v->nr > val) inserare(v->pstg, val); else if (v->nr < val) inserare(v->pdr, val); else v->ap++; } void inlocuire_nod(ARB * &n){ // n - nodul de eliminat // se inlocuieste cu maximul de pe subarborele stang (acum maximul din n), // care este pe ramura dreapta a lui 'n', // sau cu minimul de pe subarborele drept (adica minimul din arborele n), // rezultatul final fiind acelasi, adica un arbore de cautare if (n->pdr) inlocuire_nod(n->pdr); else {e->nr=n->nr; // e - nodul care se elimina (continutul sau) e->ap=n->ap; // se actualizeaza valorile lui 'e' cu maximul din e=n; // arborele nodului 'n' , ramura dreapta n=n->pstg; // pastrez legatura la ramura stanga a nodului free(e); // pentru care elimin ramura dreapta, a carei } // valori s-au mutat in nodul 'eliminat' (inlocuit) } void elimina_nod (ARB * &a, int x){// a-arbore, x-valoarea de eliminat if (!a) printf("\nCheia cautata %d nu este in arbore!\n", x); else if (x < a->nr) // se cauta pozitia valorii 'x' elimina_nod (a->pstg, x); else if (x > a->nr) elimina_nod (a->pdr, x); else // s-a gasit pozitia lui 'x' {e=a; if (!a->pstg){ // are subarborele stang vid a=a->pdr; // se conecteaza subarborele drept free(e); // si eliberez spatiul alocat } // nodului eliminat else if (!a->pdr){ // are subarborele drept vid 34

a=a->pstg; free(e); }

// se conecteaza subarborele stang // si eliberez spatiul alocat // nodului eliminat

else }

inlocuire_nod(a->pstg); // sau cu parametru 'a->pdr' // cu modificarile respective in functia de inlocuire

} void listare_SRD (ARB *v){ if (v) {if (v->pstg) listare_SRD (v->pstg); printf("%3d(%d) -> ", v->nr, v->ap); nel++; if (nel%7==0) printf("\n"); if (v->pdr) listare_SRD(v->pdr); } } main(){ ARB *pl; int valoare; pl = NULL; clrscr(); printf("Se construieste un arbore de cautare si permite elimarea unui nod.\n"); printf ("\nIntroduceti un sir de valori, terminat cu EOF.\n"); printf ("Valoare:"); while ( scanf ("%d", &valoare) != EOF) { inserare (pl,valoare); printf ("Valoare:"); } /* afisare arbore */ printf("\nListare arbore SRD:\n"); listare_SRD (pl); printf ("NULL\n"); printf("\nValoare de eliminat: "); scanf("%d", &valoare); elimina_nod(pl, valoare); /* afisare arbore dupa eliminare */ printf("\nListare arbore SRD, dupa eliminarea valorii %d:\n", valoare); nel=0; // initializare contor afisare pe ecran listare_SRD (pl); printf ("NULL\n"); printf("Terminare dupa apasarea unei taste!\n"); getch(); }

35

Arbori generalizaţi Să considerăm acum cazul arborilor generalizaţi, adică arbori în care fiecare nod poate conţine referinţe către mai mult de doi subarbori, fără ca numărul lor să fie constant. Dacă numărul subarborilor poate creşte cu o valoare finită, este comod de utilizat un tablou de referinţe care se referă către aceşti subarbori. Dacă însă fixăm numărul de noduri la o valoare prea mare, numeroase referinţe nu vor utiliza spaţiul de memorie rezervat. O soluţie a acestei probleme este de a ataşa fiecărui nod al arborelui o listă înlănţuită a descendenţilor săi. Fiecare nod conţine două referinţe, una către “fiul” său iar cealaltă către “fratele” său cel mai apropriat. Una din aceste referinţe poate fi NULL. Vom reprezenta, în acest mod, primul arbore, prezentat la începulul paragrafului; legăturile de descendenţă sunt reprezentate (desenate) vertical, iar cele de fraternitate, pe orizontală. Practic, în acest mod, s-a transformat un arbore generalizat într-unul binar: A D H G C B E FJI

36