structuri de date – subiecte · pdf filestructuri de date – subiecte examen 1...

STRUCTURI DE DATE – Subiecte examen

1

Biletul nr. 2

1. Opera ii pe liste dublu înl uite.

Lista este o structur secven ial de date, fiecare element con inând informa ia propriu-zis i adresa de leg tur cu lat nod.Lista este dublu înl uit dac între nodurile ei suntdefinite dou rela ii de ordine (figura 1).

Figura1. Lista dublu înl uit

Definirea comun a structurii de tip list dublu înl uit este:struct nod { int inf;

nod *urm, *pred; };

Pentru gestionarea lista se utilizeaz variabila pointer cap, iar pentru parcurgere, sefolosesc pointerii urm i pred.Opera ii pentru liste dublu înl uite:

- crearea unei liste;- afi area listei;- accesul la un element al unei liste;- inserarea unui nod într-o list ;- tergerea unui nod dintr-o list ;- tergerea unei liste.

Func iile membre ele clasei list care reprezint implement ri ale opera iilor de mai sussunt:1) Costructorul clasei lista(): se ini ializeaz capul listei cu NULL.

lista(){cap=NULL;}

2) Destructorul clasei ~lista(): se terge lista.

lista::~lista(){

cap

info info info

NULL NULL


2

nod *p; while(cap!=NULL) {p=cap; cap=cap->urm; delete(p); } cap=NULL;}

3) Func ia membru lista& adaugsf(int info): se insereaz un nod la sfâr itul listei.

lista& lista::adaugsf(int info){ nod *p,*pt; p=new nod; p->inf=info; p->urm=p->pred=NULL; if(!cap) cap=p; else {pt=cap; while(pt->urm!=NULL) pt=pt->urm; pt->urm=p; p->pred=pt; } return *this;}

4) Func ia membru void listare(): se afi eaz lista.

void lista::listare(){ nod *tp; if(cap){cout<<"\nLista: "; tp=cap; while(tp) {cout<<tp->inf<<" "; tp=tp->urm; } } else cout<<"\nLista vida"; cout<<"\n\n";}

5) Func ia membru lista& push(int info): se insereaz un nod la începutul listei.


3

lista& lista::push(int info){ nod *p; p=new nod; p->inf=info; p->urm=p->pred=NULL; if(!cap) cap=p; else {p->urm=cap; cap=p; } return *this;}

6) Operatorul – supraînc rcat cu ajutorul func iei membru lista& opertator - (int info):se terge un nod dup o cheie.

lista& lista::operator - (int info){ int bol=1; nod *pt,*p; if(!cap) bol=0; else if(info<cap->inf) bol=0; else if(info==cap->inf) {p=cap; cap=cap->urm; cap->pred=NULL; delete p; } else {pt=cap; while((pt->inf!=info)&&(pt->urm)) pt=pt->urm; if(info!=pt->inf) bol=0; else if((info==pt->inf)&&(pt->urm==NULL)){p=pt; pt->pred->urm=NULL; delete p; } else {p=pt; pt->pred->urm=pt->urm; pt->urm->pred=pt->pred; delete p; } } if (!bol) cout<<"\n "<<info<<" nu se afla in lista"; else cout<<"\n Stergere cu succes";


4

return *this;}

7) Func ia membru int pop(): se terge primul nod din list .

int lista::pop(){ nod *p; int x=0; if(cap){p=cap; x=p->inf; cap=cap->urm; cap->pred=NULL; delete p; } return x;}

8) Func ia membru lista& sterge(): se terge lista.

lista& lista::sterge(){ nod *p; while(cap!=NULL) {p=cap; cap=cap->urm; delete(p); } cap=NULL; return *this;}

9) Operatorul [] supraînc rcat cu ajutorul func iei membru int& operator [](int i):accesul la elementele listei dup un indice.

int& lista::operator [] (int i){ nod *tp=cap; while((i>1)&&(tp)) {tp=tp->urm; i--; } if(tp) return tp->inf; return tp->inf;


5

}

2. Dac num rul telefonic con ine cifrele fiecare în câte un element al listei,proceda i la definirea func iilor care efectueaz trecerea la noul sistem din 14numere. Generaliza i.

Solu ia problemei const în transformarea num rului de telefon din 7 cifre într-unul de 14cifre, prin ad ugarea prefixelor necesare. Cum num rul este memorat prin intermediulunei liste simplu înl uite sau dublu înl uite, solu ia informatic a problemei serezum la implementarea opera iilor de ad ugare de noi noduri în cap tul unei liste.Astfel se ad ug în ordine invers în cap tul listei curente care con ine num rul detelefon, cifrele prefixului. De exemplu pentru num rul 1234567 memorat ca în listasimpl de mai jos:

Num rul de telefon memorat într-o list simplu înl uit .

Opera ia de transformare într-unul de 14 cifre este format din 7 ad ug ri succesive denoduri, adic 7 apeluri succesive ale func iei adaug _început(), de fiecare dat nodulad ugat devenind noul cap t al listei.

nod* aduga_inceput(nod* cap,int info){ nod *p; p=new nod; p->inf=info; p->urm=p->pred=NULL; if(!cap) cap=p; else {p->urm=cap; cap=p; } return cap;}

Transformarea num rului de telefon într-unul de 14 cifre prin ad ug ri succesive

O solu ie general a problemei care necesit mai pu ine opera ii este dat de utilizareaopera iei de concatenare a dou liste. Astfel, având cele 2 liste, cea a num rului de telefonexistent i cea a prefixului, ob inem num rul de telefon din 14 cifre concatenând primalista la cea de-a dou .

1 2 3 4 5 6 7

prefix prefix

1 2 3 4 5 6 7…..


6

Concatenarea a dou liste

3. Compresa i irul anilor de domnie ai lui tefan cel Mare.

Biletul nr. 1 – 12 Dec. 2000

1. Func ia de concatenare pentru structuri de date dinamice.

Opera ia de concatenare este folosit pentru rezolvarea unor probleme ce necesitformarea de noi structuri de date prin compunerea altora de acela i tip. Indiferent de scopul si semnifica ia specific fiec rei aplica ii în care sunt folosite,definirea din punct de vedere al algoritmului este una singura. Fie X de un anumit tip de structur de date dinamic (liste simplu i dublu înl uite,arbore sau graf, ultimele dou structuri fiind privite ca implement ri particulare a listelor)i Y de acela i tip ca X.

X are elementele x 1 , x 2 ,x 3 ,…, x n (care pot fi nodurile unei liste, ale unui arbore sau

ale unui graf), iar Y are elementele y 1 , y 2 , y 3…, y m , cu n i m finite. Dac X se concateneaz cu Y, atunci la elementele lui X se vor ad uga elementele luiY formând o nou structur de date de acela i tip ca X i Y i care are elementele x 1 ,

x 2 , x 3 ,.., x n , y 1 , y 2 , y 3 ,…, y m . Foarte important de re inut sunt urm toarele :

- Opera ia de concatenare nu este comutativ- Opera ia de concatenare nu altereaz elementele (informa iile memorate de

ele) structurilor ci doar leg turile dintre ele- Structurile care se concateneaz trebuie s fie de acela i tip.- Structurile ob inute prin concatenare au acela i tip cu cele din care s-au

ob inut.

Concatenarea listelor simplu înl uite:

Structura de tip list este de forma :struct listas {

int info; //informa ia listas * next; //leg tura la elementul urm tor };

1 2 3 4 5 6 7

0 4 0 0 0 2 1


7

Concatenarea a dou liste duble este opera ia prin care una din cele doua liste ( ordinealistelor este aleas de utilizator) se adaug la sfâr itul celeilalte. Acest lucru se facepunând pointerul spre elementul urm tor al ultimului element al primei liste, care aveavaloarea NULL, s con in adresa cap tului celei de-a doua listFunc ia care realizeaz aceast opera ie este concatenlistas(listas * cap,listas * cap1),care primind ca date de intrare adresele capetelor celor doua liste simple va returnacap tul primei liste.

listas * concatenlistas(listas * cap1,listas * cap2){listas * p, * cap3; //parcurge prima list pân la sfâr itfor(p=cap1;p->next!=NULL;p=p->next) { }p->next=cap2; //face leg tura cu cap tul listei a douareturn cap1;}

Concatenarea listelor : 1 -> 2 -> 3 -> 4 -> 5 -> 6 i 7 -> 8 -> 9 ->0are ca rezultat lista simpl 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 ->0

Concatenarea listelor dublu înl uite:

Structura de tip list dubl con ine pe lâng informa ie i doi pointeri la aceea i structur :struct listad {

int info; listad * d; // legatura la dreapta listad * s; // legatura la stanga };

Concatenarea a dou liste duble este opera ia prin care una din cele doua liste seadaug la sfâr itul celeilalte. Acest lucru se face punând pointerul spre elementul anterioral cap tului celei de-a doua liste, care avea valoarea NULL, s con in adresa ultimuluielement din prima list , iar pointerul spre elementul urm tor al acestui ultim element valua valoarea adresei cap tului. Func ia care realizeaz aceast opera ie este concatenlistad(listad * cap,listad * cap1),ea primind ca date de intrare adresele capetelor celor doua liste duble i va returnacap tul primei liste.

listad * concatenlistad(listad * cap,listad * cap1){listad * cap2, *p, *q;//parcurge prima lista pân ajunge la ultimul elementfor(p=cap;p->d!=NULL;p=p->d) { }


8

cap2=cap;q=cap1;p->d=q;//face leg tura între nod final i cap t lista a douaq->s=p;//faceleg tura cap t lista a doua i nod final prima listreturn cap2;}

Luând de exemplu listele : 1<->2<->3<->4<->5<->6 i 7<->8<->9<->10, rezultatulconcaten rii lor este lista dubl : 1<->2<->3<->4<->5<->6<->7<->8<->9<->10

Concatenarea arborilor:

Reprezentarea unei astfel de structuri în aplica iile pentru calculator se poate face prindefinirea unei structuri de forma:

struct nod { int info; //informa ia din nod nod * * fii; //list a fiilor unui nod int nrfii; //num rul de fii ai nodului };

Este în esen o list de liste în care fiecare nod p rinte creaz o list a nodurilor fii ifiecare nod fiu care este p rinte creaz i el o list a nodurilor fii i tot a a.

Concatenarea a doi arbori ordona i este opera ia de ad ugare a celui de-al doilea arbore laprimul arbore legând r cina arborelui care se adaug la un nod al primului arbore.Astfel r cina acelui arbore devine fiu al nodului la care se concateneaz .Singura regul a acestei opera ii este c trebuie s se introduc de la tastatur nodul lacare se concateneaz al doilea graf. Acest nod se alege introducând pozi ia sa relativ înirul care reprezint parcurgerea în preordine a arborelui.

Nodul fiind ales, func ia nod * cautnod(nod * p,int n) se va pozi iona pe acel nod iîntoarce adresa nodului.Odat nodul g sit, concatenarea este ca i terminat pentru c adresa r cinei arboreluial doilea se adaug la lista nodurilor fii ale acelui nod iar num rul de fii cre te cu 1.Func ia care face acest lucru este:

nod * concatenarbori(nod * cap,nod * cap2){int n,x;nod *p;//se afi eaz arborele la care se concateneaz , în preordineprintf("\n Arborele la care se concateneaza este :\n");n=afisare(cap);


9

printf("\n La al catelea nod se face concatenarea ? (intre 1 si %d)",n);x=citire(); //se gase te nodul c utat;p=cautnod(cap,x);// se m re te num rul de fii cu 1;p->nrfii=x+1;//se adug r cina arborelui 2 la lista de fii ai noduluip->fii[x]=(nod *)malloc(sizeof(struct nod));p->fii[x]=cap2;return cap;}

Pentru a exemplifica, lu m doi arbori :

1

2 3

4 75 6

1 ( 2 ( 4 ) 3 ( 5 6 7 ) )

8

9 30

4 7

8 ( 9 ( 4 7 ) 0 3 )

1

2 3

4 75 6

09

8

4

3

7 1( 2 ( 8 ( 9 ( 4 7) 0 3 ) 4) 3 ( 5 6 7))

Figura 10. Concatenarea a doi arbori

Pentru a concatena arborele cu r cina egal cu 8 la primul arbore la nodul cuvaloarea 2 alegem al doilea nod din afisarea lui în preordine (adic nodul cu valoarea 2),iar arborele rezultat va fi: De re inut este faptul c nu conteaz ce informa ii au nodurile pentru c nodul îlalegem prin pozi ia sa din preordine.


10

Concatenarea grafurilor reprezentate prin structuri de date dinamice:

În acest caz graful este reprezentat printr-o re ea de liste înlan uite. Graful apare ca unansamblu format dintr-o mul ime de noduri i una de arce. De asemenea existposibilitatea de preciza informa ia de orientare a arcului i dupa caz cea privind greutateaarcului.Definesc structura arcs care se asociaz elementelor din mul imea arcelor:

struct arc { struct nodgraf * destina ie; /*adresa nodului c tre care exist arc;*/ struct arcs* next_arc; //referin c tre elementul urm tor; int greutate; //greutatea arcului; }

Tipul de structura nodgraf este tot o structur de list . Ea va con ine, pe lâng informa iade baz i pe cea de înl uire i trimiterea c tre o parti ie din mul imea arcelor, i anumelista cuprinzând arcele descendente din nodul respectiv.

struct nodgraf { int info; //informa ia nodului; struct nodgraf* next; //referin c tre urm torul nod; struct arc *capat; //cap tul listei de arce; }

Definesc concatenarea a doua grafuri ca fiind opera ia de ad ugare a altui graf la unul dinnodurile grafului ini ial respectând urmatoarele reguli:

- Nodul cap t al grafului al doilea se va lega printr-un arc de un nod al primuluigraf. Arcul este orientat pe direc ia nod graf 1 ->cap t graf 2.

- Se introduce de la tastatur informa ia nodului unde se va ad uga graful al doilea.- Dac nodul cap t al grafului 2 este nod în graful 1 i concatenarea se face în acel

nod nu se va mai face nici un arc, completându-se lista de arce a nodului dingraful 1 cu arcele nodului din graful 2.

- Dac nodul final al grafurilor difer , atunci între nodul final al grafului 2 i cel alprimului graf se va forma un arc a c rui informa ie se va citi de la tastatur .

- Dac al doilea graf se leag la nodul final al grafului 1 atunci nodul final algrafului 2 devine nod final al noului graf ob inut prin concatenarea celor dougrafuri.

- Dac în graful al doilea se afl minim 2 noduri care se afl i în primul graf, ocondi ie esen ial de a face concatenarea celor dou grafuri este c , dac exist înambele grafuri arc în acela i sens între cele dou noduri, acesta s aib aceea igreutate.

Func ia care verific aceast ultima condi ie este urm toarea: int verificare(nodgraf*cap,nodgraf *cap2)


11

Func ia care realizeaz concatenarea celor dou grafuri prime te ca date de intrare doipointeri la capetele celor dou grafuri i returneaz 0 dac nu se poate face concatenareai l dac a reu it. Func ia respectând condi iile de mai sus, adaug la lista nodurilor

grafului 1 i nodurile care nu sunt comune ale grafului 2, iar listele de arce ale acestornoduri sunt i ele copiate. În cazul nodurilor comune, listele arcelor sunt doar completatecu arce noi. Exist i cazuri când este nevoie s se creeze arce noi (când se leaga deexemplu nodurile finale ale grafurilor) iar atunci greutatea lor este citit de la tastatur .Func ia este:

int concatenaregraf(nodgraf *cap,nodgraf *cap2){int k;nodgraf *p,*q,*aux,*ultim1,*ultim2;arc *r; //verifica dac se poate face concatenareaif(verificare(cap,cap2)==0) return 0;

printf("\n La ce nod are loc concatenarea ?");/*se introduce nodul unde se face concatenarea i se verific dac el exist în primulgraf*/k=citire();

ultim1=cauta_nodgraf_final(cap);// memorez ultimul nod al grafului 1ultim2=cauta_nodgraf_final(cap2);//memorez ultimul nod al grafului 2

/*se insereaz în lista nodurilor primului graf nodurile necomune din al doilea graf*/for(q=cap2;q!=NULL;q=q->next){ p=cauta_nodgraf(cap,q->info); if(p==NULL) cap=ins_nodgraf(cap,q->info);}/* se copiaz pentru noduri i lista arcelor, iar pentru acele noduri care existau secompleteaz aceast list */for(q=cap2;q!=NULL;q=q->next){ p=cauta_nodgraf(cap,q->info); if(p!=NULL) for(r=q->capat;r!=NULL;r=r->next_arc)/*functia ins_arc(nod cap,int surs ,int destina ie,int greutate) insereaz un nou arc catrenodul cu informa ia destina ie de greutate greutate în lista arcelor nodului cu informa iasurs din graful cu cap t cap */ ins_arc(cap,p->info,r->destinatie->info,r->weight);}


12

/* dac nodul unde se face concatenarea nu este cap t al grafului 2 atunci se face arcîntre cele dou cu citirea informa iei de la tastatur */if(cap2->info!=aux->info){printf("\n Distanta dintre nodul ales si capatul grafului 2 este ?");k=citire();ins_arc(cap,aux->info,cap2->info,k);}/* dac al doilea graf nu se leag la nodul final al primului graf i dac nodurile finalenu sunt acelea i, atunci ele se leag printr-un arc */if(aux->info!=ultim1->info) if(ultim1->info!=ultim2->info) if(cauta_nodgraf(cap,ultim2->info)==NULL)/* func ia cauta_nodgraf(nod * cap,int k) cauta un nod cu informa ia k în graful cu cap tcap, return nd adresa nodului sau NULL */ {printf("\n Distanta dintre nodul final al grafului 2 si cel al lui 1 este ?"); k=citire();//se creaz arc intre nod final al grafului 1 si cel al grafului 2 ins_arc(cap,ultim2->info,ultim1->info,k); }return 1;}

Pentru a exemplifica procesul de concatenare, lu m grafurile :

7 1 9 8

5 3

0

1

2

3 4

Graf 1

4 62 5 6

Graf 2


13

7 1 9 8 10

5 3

4 6

0

1

2

3 4

6

5

Figura 14. Concatenarea a dou grafuri

Dac se dore te concatenarea grafului 2 la graful 1 în nodul cu valoare 2 atunci grafulcare va rezulta va fi:Informa ia arcului dintre nodul cu informa ia 6 i cel cu informa ia 4 a fost introdus de latastatur fiind ceruta de func ia de concatenare.

2. Scrie i func iile pentru num rarea elementelor din structurile de date prinrecursivitate.

- num rarea elementelor listei simplu înl uite;

int nr_nod (lista* cap){ if(cap) return 1 + nr_nod (cap->next); else return 0;}

- num rarea elementelor listei dublu înl uite;

int nr_nod_listad (listad* cap){ if(cap) return 1 + nr_nod_listad (cap->next); else return 0;}

- num rarea elementelor arborelui binar;

int nr_nod(nod_arbore *rad){ if (rad) return 1+ nr_nod (rad->st) + nr_nod (rad->dr);else return 0;}


14

3. Calcula i gradul de compresie a datelor din fi ierul ce con ine elementeleunei matrice p tratice cu elementele propor ionale pe linii.

Consider m c un element al matricei p tratice ocup 1 octet de memorie fizic , i cmatricea este de dimensiune nXn. Deci fi ierul necompresat ocup n2 octe i.O metod de a compresa fi ierul este aceea în care fiecare linie a matricei în afar deprima o reprezent m doar prin num rul care reprezint propor ia elementelor sale fa decele ale primei linii. Astfel cele n-1 linii vor fi reprezentate de n-1 numere. Fi ierulcompresat are în acest caz o dimensiune de n+n-1 octe i.

Biletul nr. 1 – 11 Sept. 1999

1. Utilizarea variabilelor pointer în definirea i referirea structurilorarborescente.

Structurile arborescente reprezint structuri neliniare de date cu multe aplica ii înprogramarea i utilizarea calculatoarelor. Într-un limbaj simplist, structurile arborescenteexprim rela ii de ramificare între noduri, asem toare configura iei arborilor dinnatur , cu deosebirea c , în informatic , în mod tradi ional, arborii cresc în jos. Conformdefini iei matematice un arbore este un graf conex i f cicluri, iar un arbore ordonateste un arbore care are un vârf special numit r cin iar celelalte noduri pot fi repartizateîn m mul imi disjuncte X1, X2, …,Xm ,cu m>0 astfel încât în fiecare din aceste mul imiexist un nod adiacent cu r cina iar subgrafurile generate de acestea sunt la rândul lorarborescente.Reprezentarea grafic a unui arbore ordonat este:

1

2 3

4 75 6

Figura 8. Un arbore

Reprezentarea unei astfel de structuri în aplica iile pentru calculator se poate face prindefinirea unei structuri de forma:

struct nod { int info; //informa ia din nod nod * * fii; //list a fiilor unui nod int nrfii; //num rul de fii ai nodului };

Este în esen o list de liste în care fiecare nod p rinte creaz o list a nodurilor fii ifiecare nod fiu care este p rinte creaz i el o list a nodurilor fii i tot a a. Astfel arboreleordonat de mai sus va ar ta în memorie a a:


15

4

2

32

1

765

1

0

3

0 0 0

NULL

NULL NULL NULL NULL

NULLNULL

Figura 9. Memorarea unui arbore în memorie

Aceast modalitate de reprezentare a arborelui este eficient deoarece ocup atât spa iucât este nevoie spre deosebire de modalit ile în care fii unui nod sunt reprezenta i printr-un vectori de pointeri la ace tia, vectorul fiind definit cu un num r limitat de elemente. Încazul în care un nod nu ar avea fii iar num rul maxim de noduri fii al unui nod este 10,atunci acel vector al adreselor fiilor ocup spa iu f s -l foloseasc .La crearea arborelui se va cere introducerea informa iei nodului i a num rului de fii pecare acest nod îi are. Dup aceasta se ia fiecare fiu în parte i se cere introducerea ainforma iei i a numarului de fii. Definirea arborelui se termin când nici un nod nu maiare nici un fiu.Afi area arborelui pe ecran se va face citind arborele în preordine (R cin – Fiu – Fiu –Fiu …) iar cu ajutorul parantezelor ( i ) vor specificate nodurile de la acela i nivel(nodurile dintre o pereche de paranteze ( ) se vor afla la acela i nivel) . Deci arborele demai sus va fi afi at pe ecran astfel : 1 ( 2 ( 4 ) 3 ( 5 6 7 ) ).

Un graf orientat este o pereche ordonat de mul imi G=(X,U) unde X este o mul imefinit i nevida numit mul imea vârfurilor (nodurilor), iar U este o mul ime format dinperechi ordonate de elemente distincte din X numit mul imea arcelor. Orice arc u care apar ine mul imii U va fi notat cu u=(x,y) i spunem c x esteextremitate ini ial iar y este extremitate final a arcului u. Arcul (x,y) difera de arcul(y,x). Reprezentarea prin matrice de adiacen a a grafurilor este ineficient când num rulmediu de arce dintre noduri este mic (gradul de umplere al matricei de adiacen estesc zut). Cea mai mare parte a memoriei necesar stoc rii matricei de adiacen estenefolosit . Exist apoi situa ii în care nu se cunoa te aprioric num rul maxim de noduriale grafului, apelându-se la construirea dinamic a grafului, pe parcursul rezolv riiproblemei, deci nu se cunoa te dimensiunea matricei de adiacen . În aceste situa ii grafulse poate reprezenta printr-o re ea de liste înlan uite. i în aceast reprezentare, graful apare ca un ansamblu format dintr-o mul ime denoduri i una de arce. De asemenea trebuie s existe posibilitatea de preciza informa ia deorientare a arcului i dupa caz cea privind greutatea arcului. Definesc structura arcs care se asociaz elementelor din mul imea arcelor: struct arc {


16

struct nodgraf * destina ie; /*adresa nodului c tre care exist arc;*/ struct arcs* next_arc; //referin c tre elementul urm tor; int greutate; //greutatea arcului; } Este vorba în esen , de o list a arcelor, ce va fi construit dinamic. Reg sim îndescriere “informa ia propriu-zis ”, precum i cea necesar înl uirii în list . Cu toate cnodgraf * destina ie de i este un pointer, face parte din informa ia de baz i nu din ceadestinat reg sirii în list . Nu toate arcele vor fi grupate într-o singur list , ci vor exista mai multe liste,organizate pe principiul descenden ei dintr-un nod. Un arc nu poate figura în mai multeliste, pentru c exist un singur nod rinte, originea arcului. Tipul de structura nodgraf este tot o structur de list . Ea va con ine, pe lânginforma ia de baz i pe cea de înl uire i trimiterea c tre o parti ie din mul imeaarcelor, i anume lista cuprinzând arcele descendente din nodul respectiv. struct nodgraf { int info; //informa ia nodului; struct nodgraf* next; //referin c tre urm torul nod; struct arc *capat; //cap tul listei de arce; } La crearea grafului se vor introduce inti ial informa iile nodurilor, creându-se astfellista lor. Dup aceasta se vor crea listele de arce introducându-se informa ia noduluisurs , a nodului destina ie i greutatea arcului.

7 1

8 9

5 3

0

1

2

3 4

Figura 12. Un graf orientat

Pentru graful din figura de mai sus reprezentarea sa în memorie este:

@2

@2@1

0

@4@3

@3

7

5

8

1

3 9

NULL

NULL NULL

NULL

NULL

4321

NULL

@ i – reprezint adresa lui „i”

Figura 13. Reprezentarea în memorie a unui graf


17

, iar cea de pe ecran este realizat cu ajutorul matricei de adiacen : 0 7 5 0 0 0 0 8 1 0 0 0 0 3 0 0 0 0 0 9 0 0 0 0 0 De men ionat este faptul c informa ia de baz a unui nod este unic pentru fiecarenod, dou noduri neavând aceea i valoare.

2. Scrie i func ia de transpunere a unei matrice rare, definit cu liste dubluînl uite.

Matricele rare sunt acele masive bidimensionale ale c ror elemente nenule reprezint opondere de mai pu in 1/3 din num rul total de elemente. Astfel de matrice suntreprezentate în memorie în moduri neconven iale, memorându-se doar elementelenenegative, restul având valoarea 0.O astfel de metod este i cea care utilizeaz pentru acest lucru o list dublu înl uit .Astfel, fiecare element al listei con ine 3 informa ii: indicele liniei i coloanei elementuluidiferit de 0, i valoarea acestuia. Structura general a acestei liste este:Struct lista_matr_rara{ int linie; int coloana; tip valoare_elem; lista_matr_rara * next; lista_matr_rara *pred;}

Cap tul listei re ine informa ii despre dimensiunea matricei rare, elementele linie icoloana reprezentând num rul de linii respectiv coloane, iar valoare_elem are valoarea 0.Transpunerea matricelor rare este similar celei efectuate pe structur tablou, constând îninversarea indicilor de linie i coloan între ei. În cazul de fa se inverseaz pointerii lamasivele de întregi reprezentând liniile, respectiv coloanele elementelor nenule:

lista_matr_rara * transpunere(lista_matr_rara * capat){ int temp; lista_matr_rara * vb; *n = capat->linie; *m = capat->coloana; for (vb = capat->next ; vb != NULL ; vb = capat->next) { temp = vb->linie; vb->linie = vb->coloana; vb->coloana = temp;


18

} return capat;}

3. Scrie i func ia care deconcateneaz o list simpl .

Structura de tip list este de forma :

struct listas { int info; //informa ia listas * next; //leg tura la elementul urm tor };

Deconcatenând o list simpl , aceasta se rupe rezultând astfel dou liste simple. Cum înlist exist sau nu mai multe elemente cu aceea i valoare, elementul de unde sedeconcateneaz este ales prin indicarea pozi iei sale în list .Fiind ales nodul de unde se deconcateneaz , acesta devine cap tul noii liste, iar pointerulelementului anterior lui va lua valoarea NULL i elementul va deveni sfâr itul primeiliste.Func ia care realizeaz acest lucru pime te ca date de intrare cap tul primei liste i vareturna cap tul listei simple nou formate.

listas * deconcatenlistas(listas * & cap){int i,x;listas * p, * cap2;for(i=1,p=cap;p->next!=NULL;p=p->next) {i++;}//i num câte elemente are listaprintf("\n\t De la al catelea element are loc deconcatenarea ?");x=citire();//se alege elementul de unde se deconcateneazif(x==1) {/*dac lista se deconcateneaz de la primul element noua list va fi exact lista ini ial */ cap2=cap; cap=NULL; } else { for(i=1,p=cap;i<x-1;p=p->next,i++) { } cap2=p->next;// se desfac leg turile p->next=NULL; }return cap2;}

Aplicarea deconcatenarii asupra listei simple


19

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

de la elementul al 6-lea se vor ob ine listele simple:

1 -> 2 -> 3 -> 4 -> 5 i 6-> 7 -> 8

Observa ie : deconcatenând lista de la primul element, noua lista va fi chiar lista ini ial .

4. Defini i i exemplifica i opera ia de interschimb a elementelor din structurilede date cunoscute.

Pentru vectorul din figura de mai jos:

v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7]

Opera ia de interschimbare a elementelor cu valorile v[1] i v[5] implic :- definirea i crearea unui element, temp, de tipul elementelor vectorului;- temp ia valoarea elementului v[5];- v[5] ia valoarea elementului v[1];- elementul v[1] ia valoarea lui temp;

Aceste ecua ii transpuse în limbaj de programare au ca rezultat func ia:

void interschimbare (int vect[1], int vect[5]){ int temp = vect[5]; vect[5] = vect[1]; vect[1] = temp;}

Pentru lista simpl din figura de mai jos:

NULL

Opera ia de interschimbare a elementelor cu valorile B i F implic :- definirea i crearea unui element de tip nod list numit temp;- temp ia valoarea elementului F (inclusiv valorile pointerilor);- F ia valoarea elementului B, inclusiv valoarea pinterului;- elementul B ia valoarea lui temp, iar pointerul b->next i ia valoarea lui temp-

>next.


void interschimbare (lista * elemB, lista * elemF){


20

lista * temp = (lista*) malloc(sizeof(lista));

temp = elemF;

elemF->info = elemB->info; elemF->next = elemB->next;

elemB->info = temp->info; elemB->next= temp->next;}

Pentru lista dubl din figura de mai jos:

NULL NULL

Opera ia de interschimbare a elementelor cu valorile B i F implic :- definirea unui element de tip nod list numit temp;- temp ia valoarea elementului F (inclusiv valorile pointerilor);- F ia valoarea elementului B, inclusiv valorile opinterilor;- elementul B ia valoarea lui temp, iar pointerii b->dr i b->st iau valorile lui temp-

>dr i temp->st.


void interschimbare (listad * elemB, listad * elemF){ listad * temp; temp = elemF;

elemF->info = elemB->info; elemF->dr = elemB->dr; elemF->st = elemB->st;

elemB->info = temp->info; elemB->dr = temp->dr; elemB->st = temp->st;}

Biletul nr. 2 – 11 Sept 1999

1. Utilizarea variabilelor pointer în definirea i referirea structurilor omogenede date.


21

Variabilele pointer reprezint tipuri de date al c ror con inut reprezint adrese dememorie unde se afl valorile diferitelor variabile utilizate de program.Avantajele utiliz rii pointerilor se concretizeaz în definirea dinamic a zonei dememorie de lucru, eliminându-se irosirea nejustificat de spa iu, precum i în accesulimediat la un element anume al structurii de date, pentru c în caz contrar este necesarparcurgerea acesteia pân la elementul respectiv.În cazul structurilor de date de tip vector:

- definirea se realizeaz prin sinataxa tip * nume_vector;- referirea elementului k al vectorului de n elemente este *(pointer_vector + (k-1)),

unde k variaz de la 1 la n.

De exemplu, elementul al 5-lea al vectorului definit int * vect, este *(vect + 4).

În cazul structurilor de date de tip masiv bidimensional:- definirea se realizeaz prin sinataxa tip ** nume_matrice;- referirea elementului a[i][j] al matricei a[n][n] de n2 elemente este

*(pointer_matrice + n * i + j), unde i i j variaz de la 0 la n-1.

De exemplu, elementul de pe linia 1 i coloana 2 al matricei a[3][3] definit int * matr,este (matr + 3 * 1 + 2).

În cazul structurilor de date de tip list simplu sau dublu înl uit :- definirea se realizeaz prin sintaxa

struct lista //pentru lista simplu înl uit{ int info; lista * next;}

struct listad //pentru lista dublu înl uit{ int info; listad * urmat; listad *predec}

- referirea elementului urm tor cap tului listei este cap->next;

2. Scrie i func ia de normalizare dintr-o list simpl asociat unei matrice rare.

Matricele rare sunt acele masive bidimensionale ale c ror elemente nenule reprezint opondere de mai pu in 1/3 din num rul total de elemente. Astfel de matrice suntreprezentate în memorie în moduri neconven iale, memorându-se doar elementelenenegative, restul având valoarea 0.


22

O astfel de metod este i cea care utilizeaz pentru acest lucru o list simpl . Astfel,fiecare element al listei con ine 3 informa ii: indicele liniei i coloanei elementului diferitde 0, i valoarea acestuia. Structura general a acestei liste este:Struct lista_matr_rara{ int linie; int coloana; tip valoare_elem; lista_matr_rara * next;}

Cap tul listei re ine informa ii despre dimensiunea matricei rare, elementele linie icoloana reprezentând num rul de linii respectiv coloane, iar valoare_elem are valoarea 0.Opera ia de normalizare, reprezint procesul construirii matricei rare ini iale pornind dela un tip ca acesta de reprezentare eficient a ei. Subrutina de normalizare const îngenerarea unei matrice ini iale de dimensiunile [nr_linii][nr_coloane] cu toateelementele 0, i apoi parcurgând lista în ordine ini ializarea elementelor acesteia date de[linie][coloana] cu [valoare_elem].

int ** normalizare(lista_matr_rara * capat, int *n, int *m){ int **pmat; pmat=(int **)malloc(n*sizeof(int*)); for (int i=0;i<n;i++) pmat[i]=(int*)malloc(m*sizeof(int));

for(i=0;i<n;i++) for (j=0;j<m;j++) pmat[i][j]=0; *n = capat->linie; *m = capat->coloana; for (capat=capat->next ; capat != NULL ; capat = capat->next) pmat [capat->linie][capat->coloana] = capat->valoare_elem; return pmat;}

3. Scrie i func ia care terge k elemente consecutive dintr-o list simpl .

Func ia care terge k elemente consecutive dintr-o list simpl , este o func ie careapeleaz de k ori metoda de tergere a unui element. Pentru a terge un element e dintr-olist simplu înl uit este suficient ca leg tura lista * next a elementului precedent lui e

nu mai con in adresa loca iei de memorie unde se afl elementul e, ci adresa zonei dememorie asociat succesorului lui e. În concluzie, solu ia se rezum la a schimba valorileunor variabile pointer.


23

De i elementul e nu mai apar ine listei, el ocup în mod nejustificat spa iu de memoriepân la terminarea aplica iei, i de aceea o rezolvare complet a tergerii unui elementinclude i dealocarea zonei de memorie ocupat de acesta.

void stergere_k_elem (lista *pred_nod_start, int k){ lista * temp; lista * nod_de_sters; for(temp = pred_nod_start->next, i=1 ; i <= k && temp != NULL ; i++) { nod_de_sters = temp; temp = temp->next; delete(nod_de_sters); }

if ( i>k) pred_nod_start->next = temp else cout<<” Nu s-a putut sterge k elemente ”;}

Func ia prime te ca parametrii elementul listei de la care în continuare se terg k elemente(f el) i num rul k. Pentru a nu face k ini ializ ri de variabile pointer, la ie irea dinbucla for( ) se realizeaz atribuirea pred_nod_start->next = adresa celui de-al k+1-leaelement.

4. Defini i i exemplifica i opera ia de inserare elemente în structuri de datecunoscute.

Opera ia de inserare elemente în structuri de date cunoscute este opera ia prin care seadaug un nou element la o structur de date definit i ale c rei elemente sunt cunoscute.Aceast procedur se realizeaz respectând reguli care caracterizeaz structura existent ,de exemplu elementele sale sunt într-o anumit regul , sau în func ie de necesit ileprogramului, de exemplu se însereaz elemente noi la început, la sfâr it sau dup unelement specificat.În func ie de structura de date folosit , opera ie de inserare respect anumite condi ii:

- în cazul vectorilor, inserarea unui nou element duce la crearea unui nou vectorcare s con in i elementul inserat;

int * inserare_vector_inceput (int *vector_initial, int n, int * lungime_vector_nou, int nr){ * lungime_vector_nou = n+1; int * vector_nou = (int*)malloc(n * sizeof (int)); vector_nou[0] = nr; for(int i = 0 ; i<n ; i++) vector_nou[i+1] = vector_initial[i]; return vector_nou;


24

}

- în cazul masivelor bidimensionale, inserarea unui nou element duce la creareaunei noi matrice care s aib o coloan , o linie în plus sau ambele i care deasemenea s con in elementul inserat;

- în cazul listelor simplu sau dublu înl uite, inserarea însemn atribuirea unorvariabile pointer cu adresele elementului predecesor (numai la liste duble) isuccesor;

nod* aduga_inceput(nod* cap,int info){ nod *p; p=new nod; p->inf=info; p->urm=p->pred=NULL; if(!cap) cap=p; else {p->urm=cap; cap=p; } return cap;}

- în cazul arborilor i în special în cazul arborilor binari de c utare, inserarea esteechivalent cu ad ugarea unui nou nod frunz ;

nod_arbore* inserare(nod_arbore *radacina, int k){ if(radacina) { if (k < radacina->inf) radacina->ss = inserare (radacina->ss, k); else if (k > radacina->inf) radacina->sd = inserare (radacina->sd, k); else cout<<"Nod existent!"<<endl; return radacina; } else return creaza_nod(k, NULL, NULL);}

- în cazul grafului, opera ia de inserare este cea mai complex dintre celeenumerate pentru c implic modific ri la nivelul multor structuri folosite (listanodurilor, lista arcelor, listele predecesorilor etc.).

Biletul nr. 4 – 18 Ian 2000

1. Opera ia de dezactivare în arbore ternar.


25

2. Conceptul de list peral .

Nu exist o astfel de list în literatura de specialitate. Fiecare programator este liber s idefineasc un astfel de concept, în func ie de necesit ile sale.

3. Scrie i func ia pentru traversarea structurii de date asociat ADN-ului.

Structura ADN-ului este descris în figura de mai jos:

i cu precizarea c este în spiral , lucru care nu este reprezentat în memoriacalculatorului.Astfel, structura de date asociat ADN-ului este format din 2 liste compuse din elementecare con in informa ia nodului i 3 variabile pointer care îl leag de nodurile vecine.struct adn{ int info; adn * stanga; adn * dreapta; adn * jos;}

Traversarea listelor se face în func ie de rezultatul urm rit, existând mai multeposibilit i: fie se parcurge una dintre liste i pentru fiecare element citit se g se te inodul asociat din ce de-a doua list (prin intermediul pointerului c tre el), fie se parcurgîn paralel ambele liste.Implementarea primului procedeu conduce la realizarea procedurii urm toare:

Void citire_adn ( adn * capat_lista_1){ adn * temp; for (temp = capat_lista_1 ; temp != NULL ; temp = temp->dreapta ) cout<<”\n Elementul ”<< temp->info << ” este pereche cu ”<<temp->jos->info;}

4. Compresa i textul :

Ziua ninge, noaptea ningeDiminea a ninge iarZiua ninge, noaptea ningeDiminea a ninge iarZiua ninge, noaptea ninge


26

Diminea a ninge iar . Cum se observ ca primele dou versuri se repet de 3 ori, textul este compresat astfel:3 Ziua ninge, noaptea ninge Diminea a ninge iar. Astfel textul este mic orat de 3 ori.

5. Defini i i evalua i gradul de referire a structurilor de date.

Gradul de referire a structurilor de date este un indicator care descrie modul de folosire adiferitelor structuri de date definite în interiorul unui program. Avantajul utiliz rii acestuiindicator const în realizarea unei analize a aplica iei care s conduc în final la alegereastructurii de date optime care s aib eficien maxim .De exemplu într-un program care implementeaz lista simpl i dublu înl uit , unvector i o matrice gradul de referire a structurilor de date este definit ca fiind procentulnum rului de instruc iuni care refer elementele unei structuri, din totalul instruc iunilor.Astfel, se analiza dac structura care are un grad de referire mic este indicat pentruprogramul respectiv sau dac problemele care duc la acest procent mic pot fi sau nuînl turate.

Biletul nr. 1 – 17 Ian 2000

1. Noi opera ii pe structuri de date.

În produc ia de aplica ii software, structurile de date folosite sunt obiectul numeroaselorprelucr ri care în final conduc la rezultatul dorit. În func ie de aceste obiective, precum ide metoda general de abordare a problemei sunt folosite în lucrul cu structurile de date,opera iile tradi ionale ca inserare, tergere de elemente, interschimbare, sortare etc. însprogramatorul nu este limitat doar la acestea, el putând defini noi opera ii care s -imaximizeze eficien a algoritmului precum i rezultatele ob inute. Singura limit este datde viziunea sa.

2. Defini i conceptul de ingineria datelor.

Conceptul de ingineria datelor este modul în care programatorul combin tipurilefundamentale de date (integer, real, boolean, pointer etc) dând na tere unor structuri dedate complexe care s -i permit transpunerea problemei reale în limbaj de programare.

3. Scrie i func ia pentru desortarea unei liste simple.

Func ia de desortare este opera ia prin care termenii unui ir ce sunt a eza i ini ial înordine cresc toare sau descresc toare sunt amesteca i astfel încât s nu mai aibproprietatea de la început.De exemplu func ia urm toare prime te ca date de intrare o list simplu înl uit sortatcresc tor i fiecare 2 elemente le interschimb între ele.Lista * desortare (lista * cap){ lista * temp;


27

lista * cap_nou; if (cap && cap->next) { temp = cap->next; cap->next = temp->next; temp->next = cap; cap_nou = temp; for(cap = cap->next ; cap->next != NULL && cap->next->next != NULL ;cap = cap->next) { temp = cap->next; cap->next = temp->next; temp->next = cap; }

} else return cap;return cap_nou;}

4. Compresa i o matrice unitate de 102 X 102 elemente.

Aceast matrice, considerând c fiecare element al s u este scris pe un octet ocup caspa iu 1022 octe i. O modalitate de compresie este scrierea ei ca : #102 unde simbolul #semnific matrice p tratic unitate, ob inând astfel o compresie foarte bun . Totu imetoda descris anterior nu este realist , ea fiind un caz particular (merge aplicat doarpe matrice p tratice unitate), îns o alt metod prone te de la ideea c o matrice poate fiscris ca un vector.În cazul nostru, aceast matrice este scris ca un vector de 1022 elemente, în care primulelement este 1, urm toarele 102 elemente sunt 0, apoi iar 1 i înc 102 elemente cuvaloarea 0,etc. Acest vector este compresat astfel : 1 1 102 0 1 1 102 0 ………102 0 1 1,lucru care se traduce : 1 element de 1, 102 elemente de 0……….Vectorul astfel compresat are 2 X 102 de elemente 1, 101 elemente de 102 i 101elemente de 0, adic 406 octe i.

5. Defini i i evalua i gradul de neomogenitate a datelor.

În majoritatea programelor întâlnim mai multe tipuri fundamentale de date (integer, real,bool, pointer, etc), lucru care prezint atât avantaje cât i dezavantaje. Avantajul este datde faptul c astfel fiec rei variabile i se aloc atât spa iu cât este necesar, neexistândsitua ii când acesta este irosit. Dar acest lucru implic o urm rire atent a opera iilordintre variabile pentru c exist posibilitatea pierderii de informa ie datorit trecerii de laun tip la altul.Pentru a m sura diversitatea de tipuri de date dintr-un cod surs , se define te gradul deomogenitate a datelor calculat pentru fiecare tip în parte ca num rul de operatori de aceltip pe num rul total de operatori.


28

Biletul nr. 1 – 7 Dec 1999

1. Ecua iile de interschimb elemente în liste dublu înl uite.

Opera ia de interschimbare a elementelor în liste dublu înl uite const în schimbareapozi iilor între cele dou elemente în list . Dificultatea procesului const în gestionareavalorilor variabilelor pointer asociate fiec rui element, la stânga i la dreapta, astfel încât

nu fie pierdut nici o adres , în caz contrar fiind afectat structura întregii liste.Pentru lista dubl din figura de mai jos:

NULL NULL

opera ia de interschimbare a elementelor cu valorile B i F implic :- definirea unui element de tip nod list numit temp;- temp ia valoarea elementului F (inclusiv valorile pointerilor);- F ia valoarea elementului B, inclusiv valorile opinterilor;- elementul B ia valoarea lui temp, iar pointerii b->dr i b->st iau valorile lui temp-

>dr i temp->st.





2. Obiectul arbore B. Metode.

3. Scrie i func ia care realizeaz traversarea unui arbore de c utare în vedereaconstruirii unei liste duble sau a unei liste simple.


29

Func ia care realizeaz traversarea unui arbore binar de c utare în vederea unei listesimplu înl uite are la baz o metod de traversare a arborelui, preordine, inordine saupostordine, i func ia inssf ( ) care insereaz un element nou la sfâr itul listei.

lista *inssf(lista *cap,int info){lista *nou=(lista*) malloc(sizeof(lista)),*temp;nou->info=info;nou->next=NULL;if (cap==NULL) return nou;temp=cap;while (temp->next) temp=temp->next;temp->next=nou;return cap;}

De exemplu func ia care creeaz o list simpl , list, din parcurgerea arborelui binar înpreordine con ine instruc iunile:

void vector_to_lista( arb_bin *rad){ if (rad) { lista = inssf (lista, rad->inf); vector_to_lista (rad->stanga); vaetor_to_lista (rad->dreapta); }}

Biletul nr. 2 – 12 Dec 2000

1. Func ia de inserare elemente în structuri de date dinamice.

Structurile de date dinamice sunt: lista simplu sau dublu înl uit , arborele i graful. Elesunt numite dinamice pentru c dimensiunea lor nu este constant din momentul definiriilor i pân în momentul termin rii programului, ci variaz prin ad ug ri sau scoateri deelemente.Opera ia de inserare este opera ia prin care se adaug noi elemente la structura existent .

- în cazul listelor, inserarea de elemente are loc la începutul listei, în interiorul eisau la sfâr it, alegerea tipului depinzând de rezultatul urm rit;

Func ia care insereaz un element la sfâr itul listei:

lista *inssf(lista *cap,int info){lista *nou=(lista*) malloc(sizeof(lista)),*temp;


30

nou->info=info;nou->next=NULL;if (cap==NULL) return nou;temp=cap;while (temp->next) temp=temp->next;temp->next=nou;return cap;}

Func ia care insereaz un element la începutul listei:

lista *insincep(lista *cap,int info){lista *nou=(lista*) malloc(sizeof(lista)),*temp;nou->info=info;nou->next=NULL;if (cap==NULL) return nou;else nou->next=cap;return nou;}

Func ia care insereaz un element dup un element al listei:

lista *ins_dupa_elem(lista *cap,lista *element, int info){lista *nou=(lista*) malloc(sizeof(lista)),*temp;nou->info=info;nou->next=element->next;element->next=nou;return cap;}

- în cazul arborilor binari de c utare, inserarea unui element verific regulile cecaracterizeaz structura de acest tip;

nod_arbore* ins(nod_arbore *r, int k){ if(r) { if(k<r->inf) r->ss=ins(r->ss,k); else if(k>r->inf) r->sd=ins(r->sd,k); else cout<<"Nod existent!"<<endl; return r; } else return creare_nod(k,NULL,NULL);


31

}

- în cazul grafului, inserarea unui nou nod implic numeroase opera ii deactualizare a listelor de noduri i de arce.

2. Scrie i func iile pentru c utarea unui element dup cheie în structuri de date.

Procedura de c utare a unui element dup cheie în structuri de date se reduce la opera iade comparare a termenilor structurii lua i pe rând cu valoarea cheii.

- în cazul vectorilor func ia returneaz fie pozi ia elementului în vector, fie valoarea–1;

int caut_elem(int *vect, int n, int cheie){int i=0;while (i<n && vect[i] != cheie) i++;if(i<n) return i; else return –1;}

- în cazul listelor simplu sau dublu înl uite, func ia returneaz adresa elementuluisau valoarea NULL;

lista *caut_elem_lista(lista *cap, int cheie){lista * tempif (cap==NULL) return NULL;temp=cap;while (temp && temp->info != cheie) temp=temp->next;if(temp) return temp; else return NULL}

- în cazul arborilor binari, func ia returneaz adresa nodului sau valoarea NULL;

nod_arbore* caut_nod(nod_arbore *rad, int cheie){ if (rad) if ( cheie = = rad->info) return rad; else { caut_nod(rad->stg,cheie); caut_nod(rad->drt,cheie); }}


32

3. Calcula i gradul de compresie a datelor din fi ierul ce con ine elementeleunei matrice p tratice cu elemente identice.

Dac consider m c matricea are n elemente, fiecare element fiind scris pe un octetatunci fi ierul ocup n2 octe i. Metoda de compresie aplicat în aceast situa ie pleac dela ipoteza c matricea este scris în fi ier sub forma unui ir de n2 elemente identice.Astfel, acest ir compresat devine num rul de elemente al irului urmat de simbolul carese repet , el ocupând în final 3 octe i (presupunem c n2 este un num r care se scrie pe 2octe i)

Biletul nr. 1 – 29 Mai 2000

1. Scrie i ecua iile pentru realizarea opera iilor de: inserare, interschimb itergere în liste duble.

Pentru lista dubl din figura de mai jos:

NULL NULL

Opera ia de inserare a unui element între C i D implic :- crearea elementului nou cu elem_nou->info = val_elem_nou;- ruperea leg turii între C i D i realizarea leg turilor între C i elementul nou i

între acesta i D, prin rela iile C->dr = elem_nou, elem_nou->st = C, D->st =elem_nou, elem_nou->dr = D;


void inserare (listad * elemC, listad * elemD, int val_elem_nou){ listad *nou=(listad*) malloc(sizeof(listad)); nou->info = val_elem_nou;

elemC->dr = nou; nou->st = elemC; nou->dr = elemD; elemD->st = nou;}

Opera ia de interschimbare a elementelor cu valorile B i F implic :- definirea unui element de tip nod list numit temp;- temp ia valoarea elementului F (inclusiv valorile pointerilor);- F ia valoarea elementului B, inclusiv valorile opinterilor;


33

- elementul B ia valoarea lui temp, iar pointerii b->dr i b->st iau valorile lui temp->dr i temp->st.





Opera ia de tergere a unui element al listei implic :- verificarea faptului dac elementul de ters nu este chiar cap tul listei sau sfâr itul

acesteia (dac pointerul la stânga sau la dreapta are sau nu valoarea NULL);- ruperea leg turii între element i vecinii s i i realizarea leg turilor între aceste

elemente vecine, prin rela iile vecin_stanga->dr = elem_sters->dr,vecin_dreapta->st = elem_sters->st;


void tergere (listad * cap, listad * elem_sters){ listad * temp;

if (elem_sters->st == NULL) { delete (elem_sters); return elem_sters->dr; } else if (elem_sters->dr == NULL) { temp = elem_sters->st; temp->dr = NULL; delete (elem_sters); return cap; } temp = elem_sters->st;


34

temp->dr = elem_sters->dr;

temp = elem_sters->dr; temp->st = elem_sters->st;}

2. Scrie i func iile pentru num rarea elementelor listei simple, listei duble iarbori binari.

- num rarea elementelor listei simplu înl uite;

int nr_nod (lista* cap){ int nr = 0; while(cap) { nr++; cap = cap->next; } return nr;}

- num rarea elementelor listei dublu înl uite;

int nr_nod_listad (listad* cap){ int nr = 0; while(cap) { nr++; cap = cap->dr; } return nr;}

- num rarea elementelor arborelui binar;

int nr_nod(nod_arbore *rad){ if (rad) return 1+ nr_nod (rad->st) + nr_nod (rad->dr);else return 0;}


35

3. Lua i un text oarecare, compresa i-l folosind doi algoritmi diferi i i efectua ianaliza rezultatelor.

Fie textul: Dintre sute de catarge

Care leag malurileCâte oare le vor spargeVânturile, valurile

A fost odat c-n pove ti A fost ca niciodat Din rude mari împ te ti O prea frumoas fat .

Care va fi compresat prin identificarea de sub iruri repetitive.În acest sens pentru cele 27 litere ale alfabetului, se construie te matricea frecven elor deapari ie a grupurilor de câte dou litere, X. Astfel, xij reprezint num rul de apari ii alliterei cu pozi ia i, urmat de liter cu pozi ia j din alfabet.Construirea matricei X se realizeaz , prin parcurgerea unei diversit i de texte ifrecven ele depind de particularit ile fonetice ale fiec rei limbi ea fiind fixat pentrutoate opera iile de compresie asemenea unei reguli generale. Dintre grupurile de câtedou litere, vor fi extrase acelea cu frecven ele cele mai mari i vor fi dispuse pe linii într-un tabel, ale c rui coloane con in literele alfabetului.Se vor considera cele 27 litere ale alfabetului, cele 10 simboluri ale cifrelor i caracterele:spa iu, plus, minus, egal, punct, virgul , dou puncte, punct i virgul , semnul mir rii,semnul întreb rii i asteriscul. În total sunt 48 de caractere. Din analizele statistice efectuate pe texte, se re in grupurile de litere alc tuind omul ime format din 64 de elemente dispuse în tabloul de mai jos, care au în dreptulliniilor i coloanelor combina ii de bi i care alc tuiesc codul asociat fiec rui ir.

1000 1001 1010 1011 1100 1101 1110 11111000 u1 1e pr mb mp ni in lui1001 lor se ut re tr te ta nu1010 it la ea ta ti ca oi au1011 am ar ei ra ne un ns nt1100 cr sc st os ti at ri oa1101 sa ma ne tre ist tri urile ind1110 nstr eau eam esti ndu u-se ati nul1111 asera res tit ros oasa isem tit art

Aceste grupuri de litere sunt puse în coresponden cu codul unui caracter, altul decâtcele 48 considerate.Astfel, versurile eminesciene care însumeaz 177 caractere incluzând i spa iile caresepar cuvintele, sunt compacte astfel:


36

Dx x sux de x x rge 17 64 26 36 27

x x x aga x lux x 26 24 12 62 57 12

Cix x x x vor spx ge 26 58 24 12 42

Vix ux x , valux x 48 57 12 57 12A fox odat c-an povex

53 73

A fox x x ciodat 53 26 16

Dx rude x x ix aratx 17 62 57 15 74o x x frumx fata. 13 33 85

ceea ce conduce la un indice de performan :

22%100*177

137177p =−

=

Construirea matricei generale a sub irurilor, are avantajul c este unic pentru orice textcare se compacteaz , dar poate apare situa ia ca frecven ele grupurilor în textul decompact, s nu urmeze nivelurile de frecven a textelor care au stat la baza ob inerii ei.

Dac pentru fiecare compactare, se construie te o matrice de sub iruri proprie,performan a este cu totul alta. Pentru textul analizat, sub irurile identificate seorganizeaz într-un tabel, c ruia i se ata eaz o matrice C a codurilor, ce conduce la untext de 116 caractere, având un indice de performan :

34%100*177

116177p =−

=

Dac pornim de la ideea c acest text este memorat folosind succesiuni de 6 bi i, pentru el con ine 25 de combina ii de bi i, corespunz toare grupurilor de litere i cele 27 de

litere, comparativ cu memorarea ca text având fiecare caractere câte 8 bi i, indicele deperforman este:

52%100*8*177

6*1168*177p =−

=


37

Observ m c algoritmii de compactare, vizeaz atât lungimea codului sub care sereprezint un caracter din text, cât i modul în care se identific elementele invariante întexte.


1. Scrie i ecua iile pentru realizarea opera iilor de: inserare, interschimb itergere în liste simple.

Pentru lista simpl din figura de mai jos:

NULL

Opera ia de inserare a unui element între C i D implic :- crearea elementului nou cu elem_nou->info = val_elem_nou;- ruperea leg turii între C i D i realizarea leg turilor între C i elementul nou i

între acesta i D, prin rela iile C->next = elem_nou, elem_nou->next = D;


void inserare (lista * elemC, lista * elemD, int val_elem_nou){ lista *nou=(lista*) malloc(sizeof(lista)); nou->info = val_elem_nou;

elemC->dr = nou; nou->dr = elemD;}

Opera ia de interschimbare a elementelor cu valorile B i F implic :- definirea i crearea unui element de tip nod list numit temp;- temp ia valoarea elementului F (inclusiv valorile pointerilor);- F ia valoarea elementului B, inclusiv valoarea pinterului;- elementul B ia valoarea lui temp, iar pointerul b->next i ia valoarea lui temp-

>next.


void interschimbare (lista * elemB, lista * elemF){ lista * temp = (lista*) malloc(sizeof(lista));

temp ->info = elemF->info; temp ->next = elemF->next;

elemF->info = elemB->info;


38

elemF->next = elemB->next;

elemB->info = temp->info; elemB->next= temp->next;}

Opera ia de tergere a unui element al listei dup valoarea acestuia implic :- verificarea faptului dac elementul de ters nu este chiar cap tul listei (dac

elementul cap t are valoarea c utat );- ruperea leg turii între element i vecinii s i i realizarea leg turilor între aceste

elemente vecine, prin rela iile vecin_stanga->dr = elem_sters->dr,vecin_dreapta->st = elem_sters->st;


void sterg_nod(lista* &cap, int k){

if(cap) if(cap->inf==k) { lista *temp=cap; cap=temp->next; free (temp); sterg_nod(cap,k); } else sterg_nod(cap->next,k);}

2. Scrie i func iile pentru afi area unui anumit element din lista simpl , listadubl i arborele binar.

- afi area unui anumit element din lista simplu înl uit (al k-lea element);

void afi are_elem_lista(lista *cap, int k){lista * tempif (cap==NULL) return NULL;temp=cap;while (temp && k!=0) temp=temp->next, k--;if(temp) cout<<” Al k-lea element are valoarea :”<<temp->info; else cout<<”NU exista”;}

- afi area unui anumit element din lista dublu înl uit (al k-lea element);


39

void afi are_elem_lista(listad *cap, int k){listad * tempif (cap==NULL) return NULL;temp=cap;while (temp && k!=0) temp=temp->next, k--;if(temp) cout<<” Al k-lea element are valoarea :”<<temp->info; else cout<<”NU exista”;}

- afi area unui anumit element din arborele binar (dac pe lâng informa ia utilfiecare nod con ine i o cheie de c utare);

void caut_nod(nod_arbore *rad, int cheie){ if (rad) if ( cheie = = rad->cheie) { cout<<”Nodul cu cheia ”<<cheie<< ” are informatia : ”<<rad->info ; return; } else { caut_nod(rad->stg,cheie); caut_nod(rad->drt,cheie); }}

3. Lua i un text oarecare, compresa i-l folosind doi algoritmi diferi i i efectua ianaliza rezultatelor.

Fie textul: Dintre sute de catarge

Care leag malurileCâte oare le vor spargeVânturile, valurile


Care va fi compresat prin identificarea de sub iruri repetitive.În acest sens pentru cele 27 litere ale alfabetului, se construie te matricea frecven elor deapari ie a grupurilor de câte dou litere, X. Astfel, xij reprezint num rul de apari ii alliterei cu pozi ia i, urmat de liter cu pozi ia j din alfabet.


40

Construirea matricei X se realizeaz , prin parcurgerea unei diversit i de texte ifrecven ele depind de particularit ile fonetice ale fiec rei limbi ea fiind fixat pentrutoate opera iile de compresie asemenea unei reguli generale. Dintre grupurile de câtedou litere, vor fi extrase acelea cu frecven ele cele mai mari i vor fi dispuse pe linii într-un tabel, ale c rui coloane con in literele alfabetului.Se vor considera cele 27 litere ale alfabetului, cele 10 simboluri ale cifrelor i caracterele:spa iu, plus, minus, egal, punct, virgul , dou puncte, punct i virgul , semnul mir rii,semnul întreb rii i asteriscul. În total sunt 48 de caractere. Din analizele statistice efectuate pe texte, se re in grupurile de litere alc tuind omul ime format din 64 de elemente dispuse în tabloul de mai jos, care au în dreptulliniilor i coloanelor combina ii de bi i care alc tuiesc codul asociat fiec rui ir.


Aceste grupuri de litere sunt puse în coresponden cu codul unui caracter, altul decâtcele 48 considerate.Astfel, versurile eminesciene care însumeaz 177 caractere incluzând i spa iile caresepar cuvintele, sunt compacte astfel:

Dx x sux de x x rge 17 64 26 36 27

x x x aga x lux x 26 24 12 62 57 12

Cix x x x vor spx ge 26 58 24 12 42

Vix ux x , valux x 48 57 12 57 12A fox odat c-an povex

54 73


Dx rude x x ix aratx 17 62 57 15 74


41

o x x frumx fata. 13 33 85


22%100*177

137177p =−

=

Construirea matricei generale a sub irurilor, are avantajul c este unic pentru orice textcare se compacteaz , dar poate apare situa ia ca frecven ele grupurilor în textul decompact, s nu urmeze nivelurile de frecven a textelor care au stat la baza ob inerii ei.

Dac pentru fiecare compactare, se construie te o matrice de sub iruri proprie,performan a este cu totul alta. Pentru textul analizat, sub irurile identificate seorganizeaz într-un tabel, c ruia i se ata eaz o matrice C a codurilor, ce conduce la untext de 116 caractere, având un indice de performan :

34%100*177

116177p =−

=

Dac pornim de la ideea c acest text este memorat folosind succesiuni de 6 bi i, pentru el con ine 25 de combina ii de bi i, corespunz toare grupurilor de litere i cele 27 de

litere, comparativ cu memorarea ca text având fiecare caractere câte 8 bi i, indicele deperforman este:

52%100*8*177

6*1168*177p =−

=

Observ m c algoritmii de compactare, vizeaz atât lungimea codului sub care sereprezint un caracter din text, cât i modul în care se identific elementele invariante întexte.


1. Stiva; exemple de utilizare.

Stiva este tot o structur de tip list simplu înl uit , îns ceea ce o deosebe te deaceasta este proprietatea c scoaterea elementelor se fac totdeauna la acela i cap t allistei, conform principiului LIFO (ultimul intrat, primul ie it).

c

← bazaaNULL

vârf de stiv →


42

Opera iile cele mai utilizate pe stiv sunt:

- tergerea unei stive, revine la dealocarea componentelor care formeaz stiva. Serealizeaz prin parcurgerea integral a stivei, cu dealocarea fiec rui vârf;

stiva* sterg (stiva *vs){ stiva *p; if(vs == NULL) cout<<"\n Stiva este vida!"; else { p = vs->prec; free(vs); while(p !=NULL) { vs=p; p=p->prec; free(vs); } vs = NULL; } return vs;};

- Ad ugarea unui element în stiv , se face de regul cu mutarea pozi iei vârfuluistivei pe componenta ad ugat .

stiva* inser(stiva *vs, int elem_nou){ stiva* p; p = new(stiva); p->info = elem_nou; p->prec = vs; vs = p; return vs;};

- tergerea unui element din stiv , se efectueaz de regul asupra elementului dinvârful stivei, aceasta coborând pe componenta ce îl precede.

int extrag(stiva * &vs){


43

stiva* p; int el; if (vs == NULL) return -1; else { p = vs->prec; el = vs->info; free(vs); vs = p; return el; }};

- Parcurgerea stivei, se efectueaz de la vârf c tre baz .

void tiparire (stiva * vs){ stiva * p; if(vs == NULL) cout<<"\n Stiva este vida!"; else { p = vs; while(p !=NULL) { cout<<p->info; p=p->prec; } }};

- Opera iile de inserare, de concatenare, de sortare a stivelor, nu difer mult deacelea i opera ii din interiorul unei liste, dar frecven a lor de utilizare este multmai redus .

2. Scrie i func ia de tergere a unui element dintr-o list dublu înl uit .

Opera ia de tergere a unui element al listei nu este o opera ie dificil , îns ea implic ogestiune atent a variabilelor pointer care leag elementele în list .Func ia descris mai jos, verific prima dat dac elementul dorit nu este chiar cap tullistei, caz în care succesorul acestuia devine noul cap t. Urm toarele dou situa iiabordate sunt cele în care elementul de ters este ultimul din list sau în interiorulacesteia.

listad * stergere_dupa_cheie (listad *cap, int info){


44

int bol=1;listad *pt,*p; if(!cap) bol=0; else if(info==cap->inf) { p=cap; cap=cap->urm; cap->pred=NULL; delete p; } else { pt=cap; while((pt->inf != info)&&(pt->urm)) pt=pt->urm; if(info!=pt->inf) bol=0; else if((info==pt->inf)&&(pt->urm==NULL)) { p=pt; pt->pred->urm=NULL; delete p; } else { p=pt; pt->pred->urm=pt->urm; pt->urm->pred=pt->pred; delete p; } } } if (!bol) cout<<"\n "<<info<<" nu se afla in lista"; else cout<<"\n Stergere cu succes"; return cap;}

3. Compresa i prima strof a poemului „Luceaf rul”.

Prima strof a poemului „Luceaf rul” este :


Pentru a rezolva metoda compresiei se folose te metoda compactarii prin identificarea desub iruri repetitive.Pentru cele 27 litere ale alfabetului, se construie te matricea frecven elor de apari ie agrupurilor de câte dou litere, X.


45

Astfel, xij reprezint num rul de apari ii al literei cu pozi ia i, urmat de liter cu pozi ia jdin alfabet.Construirea matricei X se realizeaz , prin parcurgerea unei diversit i de texte ifrecven ele depind de particularit ile fonetice ale fiec rei limbi.Dintre grupurile de câte dou litere, vor fi extrase acelea cu frecven ele cele mai mari ivor fi dispuse pe linii într-un tabel, ale c rui coloane con in literele alfabetului.Se construie te matricea Y, ale c rei elemente yij, con in frecven ele de apari ie alegrupului de dou litere de pe linia I, urmat de litere de pe coloana j a tabelului.Se are în vedere c totalitatea grupurilor de litere ce vor fi selectate în ordineadescresc toare a frecven elor de apari ie, s nu dep easc un num r K a a fel încât:

K + L < 256unde, L reprezint num rul de caractere considerat necesar pentru introducerea unui textîntr-un fi ier.În continuare, se vor considera cele 27 litere ale alfabetului, cele 10 simboluri ale cifrelori caracterele: spa iu, plus, minus, egal, punct, virgul , dou puncte, punct i virgul ,

semnul mir rii, semnul întreb rii i asteriscul. În total sunt 48 de caractere.Din analizele statistice efectuate pe texte, se re in grupurile de litere alc tuind o mul imeformat din 64 de elemente dispuse în tabloul de mai jos, care au în dreptul liniilor icoloanelor combina ii de bi i care alc tuiesc codul asociat fiec rui ir.


Aceste grupuri de litere au fost puse în coresponden cu codul unui caracter, altul decâtcele 48 considerate.Astfel, versurile eminesciene care însumeaz 94 caractere incluzând i spa iile caresepar cuvintele i versurile, vor fi compacte astfel:

A fox odat c-an povex55 73


Dx rude x x ix aratx 17 62 57 15 74

O x x frumx fata. 13 33 85


46


13%100*94

8194p =−

=

Construirea matricei generale a sub irurilor, are avantajul c este unic pentru orice textcare se compacteaz , dar poate apare situa ia ca frecven ele grupurilor în textul decompact, s nu urmeze nivelurile de frecven a textelor care au stat la baza ob inerii ei.Dac pentru fiecare compactare, se construie te o matrice de sub iruri proprie,performan a este cu totul alta.

4. Scrie i func ia pentru calculul produsului scalar a dou masiveunidimensionale stocate ca frunze ale unui arbore binar.

Cei doi vectori reprezint frunzele unui arbore binar, adic fiecare nod frunz alarborelui, frunz [i], con ine 2 informa ii: valoarea elementului i al primului vectorrespectiv celui de-al doilea.Solu ia acestei probleme const în g sirea nodurilor frunz ale arborelui i în calcululsumei celor n produse (elementul i al primului vector înmul it cu elementul i al celui de-al doilea masiv).Structura unui nod al arborelui este:

struct nod_arbore{ nod_arbore *st; nod_arbore *dr; int val_elem_vect2; int val_elem_vect2;}

i în cazul de fat ne intereseaz doar valorile din nodurile frunz .

int prod_vect(nod_arbore rad){ if(rad) if(rad->st==NULL && rad->dr==NULL) return (rad-> val_elem_vect1 * rad-> val_elem_vect2); else return prod_vect (rad->st) + prod_vect (rad->dr); else return 0;}


1. Liste duble; exemple.


47

Lista dubl este i ea asemenea listei simplu înl uite tot o structur secven ial dedate, fiecare element con inând informa ia propriu-zis i, aici este deosebirea între celedou liste, adresele de leg tur cu alte doua noduri, elementul urm tor i cel anterior dinlist . Primul element din list are întotdeauna pointerul spre nodul anterior pus pe NULL, iarultimul element are NULL, pointerul spre elementul anterior. Structura de tip list dubl va con ine pe lâng informa ie i doi pointeri la aceea istructur : struct listad { int info; listad * d; // legatura la dreapta listad * s; // legatura la stanga };

Reprezentarea în memorie sub forma unei liste duble a urm torului ir de elemente : 1, 2,3, 4, 5, 6 este:

61 2 3 4 5

NULL NULL

i cu listele dublu înl uite se efectueaz opera ii precum:- inserarea unui element;- ad ugarea unui element;- tergerea unui element;- inversarea a dou elemente;- tergerea listei;- parcurgerea într-un sens i în sensul opus;- transformarea listei în list circular dublu înl uit .

Func iile membre ele clasei list care reprezint implement ri ale opera iilor de mai sussunt:1) Costructorul clasei lista(): se ini ializeaz capul listei cu NULL.

lista(){cap=NULL;}

2) Destructorul clasei ~lista(): se terge lista.

lista::~lista(){


48

nod *p; while(cap!=NULL) {p=cap; cap=cap->urm; delete(p); } cap=NULL;}

3) Func ia membru lista& adaugsf(int info): se insereaz un nod la sfâr itul listei.

lista& lista::adaugsf(int info){ nod *p,*pt; p=new nod; p->inf=info; p->urm=p->pred=NULL; if(!cap) cap=p; else {pt=cap; while(pt->urm!=NULL) pt=pt->urm; pt->urm=p; p->pred=pt; } return *this;}

4) Func ia membru void listare(): se afi eaz lista.

void lista::listare(){ nod *tp; if(cap){cout<<"\nLista: "; tp=cap; while(tp) {cout<<tp->inf<<" "; tp=tp->urm; } } else cout<<"\nLista vida"; cout<<"\n\n";}

5) Func ia membru lista& push(int info): se insereaz un nod la începutul listei.


49

lista& lista::push(int info){ nod *p; p=new nod; p->inf=info; p->urm=p->pred=NULL; if(!cap) cap=p; else {p->urm=cap; cap=p; } return *this;}

6) Operatorul – supraînc rcat cu ajutorul func iei membru lista& opertator - (int info):se terge un nod dup o cheie.

lista& lista::operator - (int info){ int bol=1; nod *pt,*p; if(!cap) bol=0; else if(info==cap->inf) {p=cap; cap=cap->urm; cap->pred=NULL; delete p; } else {pt=cap; while((pt->inf!=info)&&(pt->urm)) pt=pt->urm; if(info!=pt->inf) bol=0; else if((info==pt->inf)&&(pt->urm==NULL)){p=pt; pt->pred->urm=NULL; delete p; } else {p=pt; pt->pred->urm=pt->urm; pt->urm->pred=pt->pred; delete p; } } if (!bol) cout<<"\n "<<info<<" nu se afla in lista"; else cout<<"\n Stergere cu succes"; return *this;}


50

7) Func ia membru int pop(): se terge primul nod din list .

int lista::pop(){ nod *p; int x=0; if(cap){p=cap; x=p->inf; cap=cap->urm; cap->pred=NULL; delete p; } return x;}

8) Func ia membru lista& sterge(): se terge lista.

lista& lista::sterge(){ nod *p; while(cap!=NULL) {p=cap; cap=cap->urm; delete(p); } cap=NULL; return *this;}

2. Scrie i func ia care traverseaz un arbore binar.

Traversarea unui arbore binar se realizeaz în 3 moduri.

- în preordine (Radacin – Stânga – Dreapta);

void preord(nod_arbore* rad){ if(rad) { cout<<rad->inf<<"\t"; preord(rad->ss); preord(rad->sd); }}


51

- în inordine (Stânga – R cin – Dreapta);

void CArbBin::inord(Nod_arbore*rad){ if(rad) { inord(rad->ss); cout<<rad->inf<<"\t"; inord(rad->sd); }}

- în postordine (Stânga – Dreapta – R cin )

void postord(Nod_arbore*rad){ if(rad) { postord(rad->ss); postord(rad->sd); cout<<rad->inf<<"\t"; }}

3. Scrie i func ia pentru calculul salariului net folosind un vector de structur .

În termeni financiari, salariul net se calculeaz ca diferen între salariul brut i :impozitul pe salariu, contribu ia la asigur rile sociale, contribu ia la ajutorul de omaj.Pentru a informatiza acest proces de calcul al salariului net se creeaz un program careprimind toate aceste variabile sub forma unui vector de structur returneaz valoarea netce revine persoanei.În aceste sens se utilizeaz un vector al c rui elemente con in urm toarele informa ii:

- semnifica ia sumei;- valoarea sumei.

struct elem_vect{ char semnifica ie[10]; float valoare;}

Func ia implementat este:

Float calc_sal_net ( elem_vect v[4]){ float sal_net; sal_net = v[0].valoare;


52

for(int i = 1 ; i<4 ; i++) sal_net - = v[i].valoare; return sal_net;}

Biletul nr. 2 - 12 Feb 2000

1. Arbori binari. Model analitic. Func ii de c utare i reg sire.

Structurile arborescente reprezint structuri neliniare de date cu multe aplica ii înprogramarea i utilizarea calculatoarelor. Într-un limbaj simplist, structurile arborescenteexprim rela ii de ramificare între noduri, asem toare configura iei arborilor dinnatur , cu deosebirea c , în informatic , în mod tradi ional, arborii cresc în jos.Un arbore binar este format dintr-o mul ime finit de elemente, numite noduri, mul imecare poate fi vid , poate avea un element (numit în acest caz r cin ), sau poate aveamai multe noduri (ce sunt aranjate în 2 submul imi numite subarbore stâng i subarboredrept).Reprezentarea grafic a unui arbore binar este:

5

2 8

1 97

În programele C/C++, pentru implementarea structurilor de date necontigue, arborelebinar se define te prin urm torul tip de baz derivat.

struct arbore_binar { int valoare; arbore_binar *stanga; arbore_binar *dreapta; };

Func iile de c utare i reg sire includ:- func ia ce determin num rul de nivele ale unui arbore;

int nr_nivele (arbore_binar *rad){ if (rad) return 1 + max (nr_nivele (rad->stanga), nr_nivele (rad->dreapta)) else return 0}, unde func ia max returneaz maximul dintre 2 numere.

- func ia care afi eaz nodurile de pe un anumit nivel;


53

void afis_nivel (arbore_binar, int nivel){ if (rad) if(!nivel) cout<<” ”<<rad->inf; else { afis_nivel (rad->stanga, nivel-1); afis_nivel (rad-.dreapta, nivel-1) }}

- func ia care caut un nod dup cheie.

arbore_binar caut_nod(arbore_binar *rad, int cheie){ if (rad) if ( cheie = = rad->info) return rad; else { caut_nod(rad->stanga,cheie); caut_nod(rad->dreapta,cheie); }}

2. Scrie i func ia pentru compararea a dou liste simple.

Func ia care compar dou liste simplu înl uite prime te ca date de intrare capetelelistelor i verific care lista are mai multe elemente. Dac prima list este mai marefunc ia returneaz valoarea 1, dac este mai mic returneaz valoarea 2 i dac listelesunt egale returneaz valoarea 0.

Int comparare_liste (lista *cap1, lista *cap2){ if(cap1 && cap2) comparare_liste(cap1->next,cap2->next) else if(cap1) return 1; else if(cap2) return 2; else return 0;}

3. Prezenta i comparativ compresia textului:

„Ziua ninge, noaptea ningeDiminea a ninge iar


54

Ninge, ninge, ninge, ningeIar i iar i iar ”

Acest text este compresat folosind dic ionarul {ziua, ninge, noaptea, diminea a, iar }, alerui elemente sunt înlocuite cu simbolurile {#, $, %, ^,&}. Deci textul arat compresat

astfel: # $, % $ ^ $ & $, $, $, $ & i & i &

, ob inându-se o compresie de %5698

4398=

− , dar s nu uit m c fi ierul compresat

trebuie s includ i biblioteca pentru ca apoi s fie decompresat. Deci fi ierul compresatcon ine i caracterele : ziua ninge noaptea dimineata iar 0 # $ % ^&. În final compresia

este de %0,498

514398=

−− .

O alt metod de compresie este aceea în care g sim secven e repetitive în text i leînlocuim cu o singur apari ie a secven ei precedat de indicele de repeti ie. Astfelob inem textul:

1 Ziua 1 ninge, 1 noaptea 1 ninge1 Diminea a 1 ninge 1 iar4 Ninge

2 Iar i 1 iar

cu o compresie de: %0.698

9298=

− .

În nici unul din cazuri nu s-a ob inut o compresie bun , lucru datorat în mare parte ifaptului c textul este foarte mic.

structuri de date – subiecte · pdf filestructuri de date – subiecte examen 1...

Documents