Structuri de Date Si Algoritmi - Managementul Unui Magazin de Haine
of 27
description
Magazin Haine
Transcript of Structuri de Date Si Algoritmi - Managementul Unui Magazin de Haine
Structuri de Date si Algoritmi - Managementul unui Magazin de Haine
Facultatea de Automatica, Calculatoare si ElectronicaUniversitatea din Craiova
Sectia Calculatoare Engleza
Proiect
Structuri de date si algoritmi
Profesor indrumator:
Student:
Cristian Mihaiescu
Cuprins:1. Descrierea temei..3
2. Consideratii teoretice...4
2.1. Arbori AVL...........................................................................4
2.2. Arbori B.................................................................................83. Listing cod sursa..........................................................................144. Bibliografie..................................................................................271. Descrierea temei:
S se realizeze managementul unui magazin de haine cu o structura de tip arbore AVL. In structura informatiei apar urmatoarele campuri: Id- cheia dupa care se creeaza structura Model haine Pret Culoare Marime Data vanzarii
Pentru aceasta structura se implementeaza urmatoarele operatii:
I. Operatii de baza
1. creare structura arbore din fisier
2. inserare inregistrare
3. modificare informatie(orice camp in afara de cheie)
4. cautare inregistrare in functie de cheie
5. stergere inregistrare in functie de cheie
6. afisare
a) pe nivele - se afiseaza numai cheile
b) completa - se afiseaza toate datele din structura sub forma tabelara
II. Operatii specifice
1.creare arbori folosind alte campuri din structura informatiei
2. adaugare date din alt fisier
3. prezentarea de situatii ale stocului in functie de diverse criterii4. crearea de scenarii pentru testarea functiilor de inserare si stergere
5.salvarea datelor in fisier
Datele din structura de tip arbore AVL referitoare la model sunt trecute intr-o structura arborescenta de tip B. Pentru arborele B se implementeaza urmatoarele operatii:
1. inserare inregistrare
2. cautare inregistrare
3. afisare structura arborescenta pe nivele
4. salvare date in fisier
5. incarcare date din fisier
Consideratii teoretice
Arbori AVL
O solutie interesanta privind mentinerea unui arbore de cautare avantajos a fost descoperita de catre matematicienii G.M. Adelson-Velskii si E.M. Landis, care au conceput o structura arborescenta in care subarborii unei radacini nu difera in inaltime prea mult(arbori AVL). Solutia foloseste un camp in plus pentru nodurile arborilor, dar limiteaza foarte mult numarul mediu de operatii pentru cautarea unui element in arbore. In plus, metoda lor conduce la o metoda generala, convenabila pentru reprezentarea listelor liniare cu un numar determinat de elemente, imbinand avantajele alocarii secventiale si inlantuite a elementelor.
Definitie: se numeste inaltimea unui arbore ca fiind lungimea celui mai lung drum de la nodul radacina la unul din nodurile terminale.
Definitie: un arbore binar se numeste echilibrat daca inaltimea subarborelui din stranga nu difera cu mai mult de o unitate fata de inaltimea celui din dreapta. Se numeste factor de echilibrare diferenta dintre inaltimea subarborelui drept si a celui stang.
Atasand fiecarui nod un camp care reprezinta factorul de echilibrare al sau, un arbore binar inseamna ca este echilibrat cand toti factorii de echilibru ai nodurilor sunt -1, 0 sau +1.
In exemplul urmator, in noduri s-au figurat factorii de echilibrare, iar alaturi informatia utila atasata nodurilor. Exemplu de arbore echilibrat:
F
N
Q
B
E
G
J
A
C D
M
I
K
L
Sa observam acum ce se intampla daca dorim sa inseram un nou nod in arbore. Echilibrul arborelui nu se schimba daca s-ar atasa un nod dupa nodurile C,D,M,G,J. Acest echilibru se destrama daca s-ar atasa acesta dupa unul din nodurile K,L,I. In ultimul caz este necesara o reajustare a nodurilor.
Aceasta problema se pune atunci cand se va insera un nou element in subarborele din stanga al unui nod cu factorul de echilibru -1, sau in subarborele drept al unui nod cu factorul de echilibru +1.
In principal sunt doua cazuri cand se pune problema reajustarii nodurilor:
Primul caz este prezentat in figura urmatoare:
A
B
h
h
h+1
Am notat cu h, h, h+1 inaltimile celor trei subarbori.
Din diferitele variante de reajustare a nodurilor, una foarte simpla presupune lasarea neschimbata a celor trei subarbori si inversarea nodurilor A si B:
B
A
h+1
h
h
In acest fel, factorii de echilibrare ai nodurilor A si B au devenit zero.
Al doilea caz de reechilibrare este prezentat in urmatoarea figura:
A
A
B
B
h
sau h
C
C
h
h
h-1
h
h
h-1
Acest caz apare cand inserarea noului nod a dus la cresterea inaltimii subarborelui din stanga nodului B (in ambele variante), spre deosebire de primul caz, cand inserarea nodului a dus la cresterea subarborelui din dreapta lui B.
Putem reajusta nodurile intr-un mod asemanator, pastrand neschimbati cei patru subarbori si ordinea lor, permutand nodurile A,B,C astfel:
C
A
B
h
h-1
h
h
Sau
C
B
A
h
h
h-1
h
In ambele cazuri trebuie modificat un numar mic de legaturi, tot restul arborelui ramanand neschimbat. Singurul lucru care trebuie schimbat il reprezinta coeficientii de exhilibrare ai subarborelui unde se insereaza nodul. Cu aceste observatii se poate scrie un algoritm de cautare intr-un arbore echilibrat si inserarea unui nod in acesta, parasind caracterul de arbore echilibrat al nodului arbore.
Algoritmul functioneaza si in cazul unui arbore initial vid, constituind o metoda de construire a arborilor echilibrati.
Cautarea si inserarea in arborii echilibrati
Algoritmul presupune trei parti distincte:
cautarea unui nod in arbore dupa o cheie data
inserarea noului nod in cazul cand acesta nu a fost gasit
reechilibrarea noului arbore dupa inserarea in cazul in care acesta s-a dezechilibrat. Luand in considerare si campul pentru factorul de exhilibrare a nodurilor, structura elementelor unui arbore echilibrat poate fi reprezentat astfel:
typedef struct tag_arbechi
{
int key;
int echi;
tag_arbechi *left, *right;
} arbechi;
typedef arbechi *parbe;
Algoritmul efectueaza cautarea intr-un arbore echilibrat al nodului cu cheia de identificare k. Daca acesta nu se gaseste in arbore se va insera un nod nou cu cheia k, in locul potrivit pentru a pastra structura de arbore de cautare, iar daca este nevoie, arborele este reechilibrat pentru a pastra structura de arbore echilibrat. Vom folosi notatia lin_k(a,p) pentru simplificarea descrierii algoritmului:
-p->left daca a=-1
-p->right daca a=1.
Eliminarea nodurilor din arborii echilibrati
Problema stergerii se poate reduce la stergerea unui nod P pentru care campul left sau right este NULL, la fel ca in cazul stergerii unui nod intr-un arbore de cautare. Deosebirea fata de acesta consta in faptul ca trebuie memorata traiectoria pe care se ajunge din nodul radacina la nodul care se va sterge, adica trebuie memorata in prealabil:
(P0,a0),(P1,a1),........., (Pk,ak)
Unde: P0=rad, a0=1, Pi+1=lin_k(a,P1), Pk=P si lin_k(ak,Pk)=NIL.
Aceasta kista de perechi se poate pastra folosind o stiva auxiliara pe durata cautarii in arbori, in sensul descendent.
Procesul de stergere al nodului P stabileste:
lin_k(ak-1,pk-1)echi
Sunt trei cazuri:
1. Pi->echi=ai. In acest caz se stabileste pk-echi, se micsoreaza i cu 1 si se repeta procedura de ajustare.2. pi->echi=0; se stabileste pk->echi( ai si algoritmul se termina.
3. pi->echi=-ai; este necesara reechilibrarea.
Situatiile care necesita reechilibrarea sunt aproape aceleasi cu cele intalnite la algoritmul de inserare. In acest caz, nodul pi este nodul A din figura din crearea anterioara, nodul B este lin_k(-ai,pi), adica ramura opusa fata de nodul unde s-a produs stergerea. Deosebirea consta in faptul ca nodul B trebuie echilibrat. Aceasta conduce la un nou caz 3, asemanator cu cazul 1, dar cu inaltimea subarborelui h+1.
In cazurile 1 si 2din algoritmul de inserare se stabileste lin_k(ai-1,pi) corespunzator radacinii, se micsoreaza icu 1 si se reinitializeaza procedura de ajustare in cazul 3din algoritmul precedent, apoi se stabileste ca lin_k(ai-1,pi-1) sa indice spre nodul 3 si algoritmul se termina. Datorita necesitatii folosirii unei stive pentru memorarea drumului parcurs , putem folosi o procedura recursiva. Pentru scrierea acesteia, se folosesc doua proceduri: una de echilibrare si una pentru stergerea propriu-zisa a nodului.
Procedura echil1 este folosita pentru reechilibrarea in cazul cand subarborele stang a devenit mai mic, iar procedura echil2 pentru cazul cand subarborele drept mai mic.
Procedura supr suprima nodul cu cheia specificata in cazul in care cesta este nod terminal sau are un singur descendent , iar daca acesta are doi subarbori, va fi inlocuit cu cel din dreapta nod al subarborelui stang.
Se va utiliza variabila booleana M pentru specificarea reducerii inaltimii subarborelui. Cand M are valoarea logica TRUE, se executa reechilibrarea. Variabila M se va pozitiona pe TRUE dupa suprimarea unui nod sau daca reechilibrarea reduce inaltimea subarborelui. Arbori BUn B-arbore este un arbore echilibrat, destinat cautarii de informatii memorate pe disc magnetic sau pe un alt tip de suport adresabil direct. B-arborii sunt similari cu arborii rosu-negru, dar ei minimizeaza operatiile de intrare/iesire disc.
Diferenta esentiala fata de arborii rosu-negru este aceea ca fiecare nod dintr-un B-arbore poate avea un numar mare de fii, pana la ordinul miilor. Astfel, factorul de ramificare poate fi foarte mare si este, de regula, determinat doar de caracteristicile unitatii de disc utilizate. Similaritatea cu arborii rosu-negru consta in faptul ca ambii au inaltimea O(lg n), unde n este numarul de noduri, desi inaltimea unui B-arbore poate fi considerabil mai mica din cauza factorului de ramificare foarte mare. Din aceasta cauza, B-arborii, pot fi, de asemenea, folositi pentru a implementa in timp O(lg n) diverse operatii pe multimi dinamice. B-arborii sunt o generalizare naturala a arborilor binari. Daca un nod x al unui B-arbore contine n[x] chei, atunci x are n[x]+1 fii. Cheile nodului x sunt folosite pentru a separa domeniul de chei vizibile din x in n[x]+1 subdomenii, fiecare dintre acestea fiind vizibile prin unul dintre fiii lui x. Cand se cauta o cheie in B-arbore exista n[x]+1 posibilitati de parcurgere, in functie de rezultatul compararii cu cele n[n] chei memorate in nodul x.Definitia B-arborelui.
Pentru a simplifica lucrurile, vom presupune, ca si la arborii binari si la cei rosu-negru ca informatia aditionala asociata unei chei este memorata in acelasi loc cu cheia. In practica fiecarei chei ii este atasat un pointer care repereaza informatia aditionala atasata cheii. De asemenea, la B-arbori se obisnuieste, tocmai pentru a creste factorul de ramificare, ca in nodurile interne sa se memoreze numai chei si pointeri catre fii, iar informatia aditionala (pointeri la ea) sa fie inregistrata doar in frunze.
Un B-arbore este un arbore cu radacina care are urmatoarele proprietati:
1. Fiecare nod x are urmatoarele campuri:
a) n[x], numarul curent de chei memorate in x
b) cele n[x] chei memorate in ordine nedescrescatoare, cheie1[x] cheie2[x] cheie3[x] cheien[x][x].
c) Valoarea booleana frunza[x] care este ADEVARAT daca nodul x este frunza si FALS daca nodul este nod intern.
2. Daca x este un nod intern, el mai contine n[x]+1 pointeri spre fiii lui c1[x], c2[x],... cn[x]+1[x]. Nodurile frunza nu au fii, astfel campurile lor ci sunt nedefinite.
3. Cheile cheiei[x] separa domeniile de chei aflate in fiecare subarbore: daca ki este o cheie oarecare memorata intr-un subarbore cu radacina ci[x] atunci:
k1 cheie1[x] k2cheie2[x] ....cheien[x][x] kn[x]+1
4. Fiecare frunza se afla la aceeasi adancime, care este inaltimea h a arborelui.
5. Exista o limitare inferioara si una superioara a numarului de chei ce pot fi continute intr-un nod. Aceste margini pot fi exprimate printr-un intreg fixat t>1, numit grad minim al B-arborelui.
a) Fiecare nod cu exceptia radacinii trebuie sa aiba cel putin t-1 chei si in consecinta fiecare nod intern, cu exceptia radacinii trebuie sa aibe t fii. Daca arborele este nevid, atunci radacina trebuie sa aiba cel putin o cheie.
b) Fiecare nod poate sa contina cel mult 2t-1 chei. De aceea orice nod intern poate avea cel mult 2t fii. Un nod cu 2t-1 chei se va numi nod plin.
Cel mai simplu B-arbore apare cand t=2. Orice nod intern poate avea 2, 3 sau 4 fii, motiv pentru care i se mai spune 2-3-4 arbore. Cu toate acestea in practica se folosesc valori mult mai mari pentru t.
Inserarea unei chei in arborele B
Pentru a aduga o cheie inexistent ntr-un arbore B, facem o cutare n arbore pentru a gsi frunza n care cheia trebuie inserat si dac putem o inserm. Ce nseamn dac putem? O frunz nu poate contine mai mult de m chei. Dac numrul de chei din frunza n care trebuie adugat cheia este mai mic dect m, atunci cheia poate fi inserat. Acesta este cazul din figura 1. n care este ilustrat inserararea cheii 28.
Dar dac dorim s inserm cheia 2. Urmnd algoritmul anterior descris, inserarea cheii 2 ar trebui fcut n prima frunz din stnga, care deja contine numrul maxim de chei. Solutia acestei probleme const n divizarea frunzei respective n dou frunze avnd cte dou chei fiecare si actualizarea informatiei din nodul printe, asa numitaEXPLOZIE, dupa cum este prezentat n figura urmtoare.
Ce se ntmpl ns dac nodul printe contine deja numrul maxim de descendenti? De exemplu, dac n arborele din figura 2. dorim s inserm cheia 90. Aceasta ar trebui inserat n cea mai din dreapta frunz. Cum aceast frunz contine deja numrul maxim de chei, ea va trebui divizat, iar nodul printe ar trebui s primeasc un nou fiu, ceea ce nu este posibil, pentru c are deja numrul maxim admisibil de subarbori. Asa cum se observ problema s-a mutat un nivel mai sus. Este logic ca si cu solutia s se ntmple acelasi lucru. Intrebarea este, desigur, pn cnd. Rspunsul este de data aceasta imediat, respectiv pn se ajunge la rdcin, iar efectul este crearea unui nou nod rdcin. Solutia inserrii cheii 90 n arborele din figura 2. este prezentat n figura 3.
Dac n acest din urm arbore dorim s inserm cheia 29, explozia nodurilor se va propaga pn la rdcin, obtinndu-se arborele urmtor:
Trebuie remarcat c atunci cnd este introdus o cheie n arbore, singurele schimbri ale nodurilor interne care pot apare sunt de a lungul cii de acces. Aceasta nseamn c schimbrile pot fi fcute n timp proportional cu lungimea cii.n general, n cazul arborilor de ordin m, atunci cnd se insereaz o cheie, problemele apar doar dac aceasta trebuie inserat ntr-un nod care are deja m chei. n acest caz numrul de chei din nod devine m+1 , caz n care nodul respectiv este divizat n dou noduri avnd (m+1)/2 respectiv (m+1)/2 chei fiecare. Asa cum am artat deja, nodul printe primeste un nou fiu si trebuie verificat dac nu este depsit numrul maxim admisibil de subarbori m, caz n care procesul de spargere a nodurilor continu, pna cnd se ajunge la un nod care poate accepta un nou fiu sau se creeaz o nou rdcin.Cautare cheie in arborele B
Pentru a regsi o cheie ntr-un arbore B, se porneste de la rdcin si se alege o anumit ramur n functie de relatia n care se afl cheia respectiv cu cheile din rdcin. Procesul continu n acelasi mod pe nivelurile urmtoare, pn se ajunge la o frunz, n care se face o cutare ordonat.
Din descrierea strategiei de cutare, ne asteptm ca durata operatiei de cutare s fie proportional cu nltimea arborelui. ntr-adevr, nltimea unui arbore B de ordin m este , iar operatia de selectie a ramurii pe care trebuie s continue cutarea dureaz O(log m) (n cazul cutrii binare). Deci n cazul cel mai defavorabil, cutarea unei chei ntr-un arbore B dureaz.
tergerea unei chei in arborele B
Un B-arbore se micoreaz (se restrnge) atunci cnd se terg chei. Pentru a terge o cheie, mai nti se efectueaz o operaie de cutare pentru a localiza nodul care o conine (n cazul n care cheia nu este gsit, tergerea nu mai are rost).
Dac cheia cutat se afl ntr-un nod care nu este frunz, se caut cheia urmtoare (conform relaiei de ordine definite peste mulimea valorilor cheilor), i ele i vor schimba locurile. ntr-un B-arbore, cheia urmtoare este ntotdeauna prima cheie din cel mai din stnga nod frunz al sub arborelui din dreapta. Mergem tot timpul spre stnga, urmrind cel mai din stnga pointer n fiecare nod pn cnd ntlnim nodul frunz. Interschimbnd cele dou chei, putem muta cheia pe care dorim s o tergem ntr-un nod frunz, dup care operaia de tergere se simplific. n felul acesta nu se afecteaz ordinea cheilor dat de pointeri n ntregul B-arbore.
Odat ce cheia cutat se afl ntr-o frunz, aceasta poate fi tears. Dac n nod rmn cel puin n chei, totul este n regul, n caz contrar se produce o subdepire (a limitei inferioare - underflow).
Dac ntr-un nod se produce o subdepire, putem redistribui cheile mprumutnd cteva chei de la nodul vecin. n acest caz, cheile din nodul vecin stng se deplaseaz prin nodul printe i sunt redistribuite.
Dar dac nodul curent i cel vecin au mpreun mai puin de 2n chei pentru redistribuire, cele dou noduri se vor combina i vor forma unul singur. n acest caz un nod este eliberat, i o cheie din nodul printe coboar un nivel pentru a umple singurul nod rmas:
Dar dac nodul printe are din start doar n chei, atunci i n acest caz se produce subdepire cnd cheia se deplaseaz n jos pentru a intra n componena nodului imediat inferior. Observm c subdepirea i combinarea nodurilor se poate propaga pn la nodul rdcin. Dac i nodul rdcin produce subdepire (acesta rmnnd gol), atunci nlimea arborelui (numrul de nivele) scade cu unu iar nodurile aflate pe al doilea nivel se combin pentru a forma o nou rdcin. Observaie: Dac nodul frunz curent este cel mai din stnga dintre nodurile fii, n caz de necesitate se mprumut chei de la vecinul din dreapta. Trebuie s existe un vecin n dreapta deoarece orice nod care nu este frunz are cel puin dou noduri fii. Ca o strategie general, n cazul tergerii unei chei dintr-un nod frunz care nu se afl pe margine, se va alege cea mai bun soluie atunci cnd se impune un "mprumut". Cea mai bun soluie este aceea care conduce la un numr minim de operaii (cel puin la nivelul nodurilor frunz). Evident, n cazul nodurilor aflate pe margine nu exist alternative. Listing Cod Sursa
#include
#include
#include
#include
#include
#include
#include
#include
#define nn 4
typedef char string[30];
typedef struct tip_inf
{
int id;
string denumire_comerciala;
int cantitate;
string producator;
float pret;
string data_expirare;
}tip_inf;
typedef struct avl_
{
tip_inf info;
avl_ *st,*dr;
int inalt;
int ech;
}avl_;
typedef struct pagina
{
int m;
tip_inf info[nn+1];
pagina *p[nn+1];
}pagina;
typedef struct triplet
{
pagina *p;
int i;
int nou;
}triplet;
typedef pagina * ref;
typedef avl_ * avl;
FILE *f;
avl rad_avl,q;
char opt;
int x;
int n=2,ok=0;
ref p_v,p_urc;
ref radacina;
triplet rez;
tip_inf urc,v;
int modif=0;
int gasit=0;
int height(avl p)
{
if (p==NULL) return(-1);
else return(p->inalt);
}
int max(int x1,int x2)
{
if (x1>x2) return(x1);
else return(x2);
}
avl rot_st(avl k2)
{
avl k1;
k1=k2->st;
k2->st=k1->dr;
k1->dr=k2;
k2->inalt=max(height(k2->st),height(k2->dr))+1;
k1->inalt=max(height(k1->st),height(k1->dr))+1;
k2=k1;
return(k2);
}
avl rot_dr(avl k2)
{
avl k1;
k1=k2->dr;
k2->dr=k1->st;
k1->st=k2;
k2->inalt=max(height(k2->dr),height(k2->st))+1;
k1->inalt=max(height(k1->dr),height(k1->st))+1;
k2=k1;
return(k2);
}
avl d_rot_st(avl k2)
{
k2->st=rot_dr(k2->st);
k2=rot_st(k2);
return(k2);
}
avl d_rot_dr(avl k2)
{
k2->dr=rot_st(k2->dr);
k2=rot_dr(k2);
return(k2);
}
avl insert(tip_inf x, avl t)
{
if (t==NULL)
{
t=new avl_;
if (t==NULL)printf("Iesire din spatiul de memorie");
else
{
t->info=x;
t->st=NULL;
t->dr=NULL;
t->ech=0;
t->inalt=0;
return t;
}
}
else
{
if (x.idinfo.id)
{
t->st=insert(x,t->st);
if (height(t->st)-height(t->dr)==2)
{
if (x.idst->info.id) t=rot_st(t);
else t=d_rot_st(t);
}
else t->inalt=max(height(t->st),height(t->dr))+1;
}
else
if (x.id>t->info.id)
{
t->dr=insert(x,t->dr);
if (height(t->dr)-height(t->st)==2)
{
if (x.id>t->dr->info.id) t=rot_dr(t);
else t=d_rot_dr(t);
}
else t->inalt=max(height(t->dr),height(t->st))+1;
}
}
return t;
}
void afis(avl p,int sp)
{
int i;
if (p!=NULL)
{
afis(p->dr,sp+7);
for(i=0;iinfo.id,p->ech);
for (i=0;ist,sp+7);
}
}
void afisare(avl q)
{
printf(" Arborele AVL \n\n");
afis(q,5);
printf("\n");
getch();
}
void afis2(avl p,int sp)
{
int i;
if (p!=NULL)
{
afis2(p->st,sp+7);
printf(" %-3d",p->info.id);
printf(" %-21s",p->info.denumire_comerciala);
printf("%-11d",p->info.cantitate);
printf("%-12s",p->info.producator);
printf("%-15.2f",p->info.pret);
printf("%s\n",p->info.data_expirare);
afis2(p->dr,sp+7);
}
}
void indic(avl p,int niv)
{
if (p!=NULL)
{
indic(p->dr,niv+1);
if (height(p->st)>height(p->dr)) p->ech=+1;
else
if (height(p->st)==height(p->dr)) p->ech=0;
else p->ech=-1;
indic(p->st,niv+1);
}
}
avl echil1(avl p,int * ok)
{
avl p1,p2;
int f1,f2;
switch (p->ech)
{
case +1 : p->ech=0; break;
case 0 : {
p->ech=-1;
*ok=0;
};break;
case -1 : {
p1=p->dr;
f1=p1->ech;
if (f1dr=p1->st;
p1->st=p;
if (f1==0)
{
p->ech=-1;
p1->ech=+1;
*ok=0;
}
else
{
p->ech=0;
p1->ech=0;
}
p=p1;
}
else
{
p2=p1->st;f2=p2->ech;
p1->st=p2->dr;p2->dr=p1;
p->dr=p2->st;p2->st=p;
if (f2==-1) p->ech=+1;
else p->ech=0;
if (f2==+1) p1->ech=-1;
else p1->ech=0;
p=p2;
p2->ech=0;
}
}
}
return(p);
}
avl echil2(avl p,int * ok)
{
avl p1,p2;
int f1,f2;
switch(p->ech)
{
case -1 : p->ech=0; break;
case 0 : {
p->ech=+1;
*ok=0;
};break;
case +1 : {
p1=p->st;f1=p1->ech;
if (f1>=0)
{
p->st=p1->dr;
p1->dr=p;
if (f1==0)
{
p->ech=+1;
p1->ech=-1;
*ok=0;
}
else
{
p->ech=0;
p1->ech=0;
};
p=p1;
}
else
{
p2=p1->dr;f2=p2->ech;
p1->dr=p2->st;p2->st=p1;
p->st=p2->dr;p2->dr=p;
if (f2==+1) p->ech=-1;
else p->ech=0;
if (f2==-1) p1->ech=+1;
else p1->ech=0;
p=p2;
p2->ech=0;
};
}
}
return(p);
};
avl sterge(avl r,int * ok)
{
avl r1;
if(r->dr!=NULL)
{
r->dr=sterge(r->dr,ok);
if(ok) r=echil2(r,ok);
}
else
{
q->info=r->info;
r1=r;r=r->st;*ok=1;
delete r1;
}
return(r);
}
avl sterge_avl(int x,avl p,int * ok)
{
if (p==NULL) *ok=0;
else
if (xinfo.id)
{
p->st=sterge_avl(x,p->st,ok);
if (*ok) p=echil1(p,ok);
}
else
if (x>p->info.id)
{
p->dr=sterge_avl(x,p->dr,ok);
if(*ok) p=echil2(p,ok);
}
else
{
q=p;
if(q->dr==NULL)
{
p=q->st;
*ok=1;
}
else
if(q->st==NULL)
{
p=q->dr;
*ok=1;
}
else
{
q->st=sterge(q->st,ok);
if(*ok) p=echil1(p,ok);
}
}
return(p);
}
void creare_avl(void)
{
FILE * f;
tip_inf x;
rad_avl= new avl_;
rad_avl->st=NULL;
rad_avl->dr=NULL;
rad_avl->inalt=0;
rad_avl->ech=0;
if ((f=fopen("in.txt","r+"))==NULL)
{
printf("NU exista fisierul 'in.txt'");
getch();
}
fscanf(f,"%d",&rad_avl->info.id);
fscanf(f,"%s",&rad_avl->info.denumire_comerciala);
fscanf(f,"%d",&rad_avl->info.cantitate);
fscanf(f,"%s",&rad_avl->info.producator);
fscanf(f,"%f",&rad_avl->info.pret);
fscanf(f,"%s",&rad_avl->info.data_expirare);
while (!feof(f))
{
if (feof(f)) break;
fscanf(f,"%d",&x.id);
fscanf(f,"%s",&x.denumire_comerciala);
fscanf(f,"%d",&x.cantitate);
fscanf(f,"%s",&x.producator);
fscanf(f,"%f",&x.pret);
fscanf(f,"%s",&x.data_expirare);
rad_avl=insert(x,rad_avl);
}
}
void insert_avl(void)
{
tip_inf x;
printf("Dati id-ul : ");
scanf("%d",&x.id);
printf("Dati denumirea comerciala : ");
scanf("%s",x.denumire_comerciala);
printf("Dati marimea : ");
scanf("%d",&x.cantitate);
printf("Dati culoarea: ");
scanf("%s",x.producator);
printf("Dati pretul : ");
scanf("%f",&x.pret);
printf("Dati data de expirare (zz/ll/aaaa) : ");
scanf("%s",x.data_expirare);
rad_avl=insert(x,rad_avl);
};
void modific(tip_inf x)
{
tip_inf x1;
int ok;
x1.id = x.id;
printf("Dati noua denumire comerciala : ");
scanf("%s",&x1.denumire_comerciala);
printf("Dati noua cantitate : ");
scanf("%d",&x1.cantitate);
printf("Dati noul producator : ");
scanf("%s",&x1.producator);
printf("Dati noul pret : ");
scanf("%f",&x1.pret);
printf("Dati noua data de expirare : ");
scanf("%s",&x1.data_expirare);
indic(rad_avl,1);
sterge_avl(x.id,rad_avl,&ok);
insert(x1,rad_avl);
}
void cauta_avl(avl q,int x)
{
if (q->info.id==x) modific(q->info);
else
if (xinfo.id)
if(q->st==NULL) printf("Produsul nu este in baza de date !!! ");
else cauta_avl(q->st,x);
else
if(q->dr==NULL) printf("Produsul nu este in baza de date !!! ");
else cauta_avl(q->dr,x);
}
void modificare_avl(int x)
{
cauta_avl(rad_avl,x);
getch();
}
void salvez_in_fisier(avl crt){
if(crt!=NULL){
salvez_in_fisier(crt->st);
fprintf(f,"%d\n",crt->info.id);
fprintf(f,"%s\n",crt->info.denumire_comerciala);
fprintf(f,"%d\n",crt->info.cantitate);
fprintf(f,"%s\n",crt->info.producator);
fprintf(f,"%f\n",crt->info.pret);
fprintf(f,"%s\n\n",crt->info.data_expirare);
salvez_in_fisier(crt->dr);
}
}
void salveaza(void){
f=fopen("out.txt","w+");
salvez_in_fisier(rad_avl);
fclose(f);
}
// Arborele B
void copiere(ref dest,ref r,int isursa,int idest,int n)
{
while(n>0)
{
n--;
dest->info[idest+n]=r->info[isursa+n];
dest->p[idest+n]=r->p[isursa+n];
}
}
void introdu(ref r,int k,tip_inf x)
{
if (r->m==nn)
{
p_v = new pagina;
p_v->m=n;
r->m=n;
if(k>n)
{
if(k==n+1)
{
copiere(p_v,r,n+1,1,n);
p_v->p[0]=p_urc;
}
else {
k=k-n-1;
copiere(p_v,r,n+2,1,k-1);
p_v->info[k]=urc;
p_v->p[k]=p_urc;
copiere(p_v,r,n+k+1,k+1,n-k);
p_v->p[0]=r->p[n+1];
urc=r->info[n+1];
};
}
else {
copiere(p_v,r,n+1,1,n);
p_v->p[0]=r->p[n];
v=r->info[n];
copiere(r,r,k,k+1,n-k);
r->p[k]=p_urc;
r->info[k]=urc;
urc=v;
};
p_urc=p_v;
}
else {
modif=0;
r->m+=1;
copiere(r,r,k,k+1,r->m-k);
r->p[k]=p_urc;
r->info[k]=urc;
if (urc.id==x.id)
{
rez.i=k;
rez.p=r;
}
}
}
void caut(ref r,tip_inf x)
{
int k;
if (r==NULL)
{
modif=1;
rez.nou=1;
urc=x;
p_urc=NULL;
}
else {
k=1;
gasit=0;
while((km)&&(!gasit))
{
if (r->info[k].idr->m) gasit=0;
else {
if (r->info[k].id==x.id) gasit=1;
else gasit=0;
}
if ( gasit) {
rez.nou=0;
rez.p=r;
rez.i=k;
modif=0;
}
else {
caut(r->p[k-1],x);
if( modif) introdu(r,k,x);
}
}
}
void insert_b(tip_inf x)
{
caut(radacina,x);
if(modif)
{
p_v = new pagina;
p_v->p[0]=radacina;
p_v->p[1]=p_urc;
p_v->info[1]=urc;
p_v->m=1;
radacina=p_v;
if (x.id==urc.id)
rez.p=radacina;
rez.i=1;
}
}
void tip(ref r, int nivel)
{
int j,k;
if (r!=NULL)
{
for (k=0;km/2);k++)
tip(r->p[k],nivel+1);
for(j=1;jm;j>=1;j--)
printf("%d ",r->info[j].id);
printf("\n");
for(k=(r->m/2);km;k++)
tip(r->p[k],nivel+1);
}
}
void citeste_avl_in_b(avl p)
{
if (p!=NULL)
{
citeste_avl_in_b(p->dr);
insert_b(p->info);
citeste_avl_in_b(p->st);
}
}
void transforma(void)
{
citeste_avl_in_b(rad_avl);
printf("S-a creat arborele B\n");
getch();
}
void afisare_b(void)
{
printf(" Arborele B : \n");
tip(radacina,1);
printf("\n");
getch();
}
void main()
{
int k;
char ch;
do
{
printf("Alegeti operatia : \n");
printf(" 1. Creare arbore AVL\n");
printf(" 2. Adaugare inregistrare\n");
printf(" 3. Stergere inregistrare\n");
printf(" 4. Modificare informatii intr-o inregistrare \n");
printf(" 5. Afisare AVL dupa id \n");
printf(" 6. Salvare date in fisier \n");
printf(" 7. Afisare completa \n");
printf(" 0. Trecerea din AVL in B \n");
ch=getch();
if (ch == '1')
{
creare_avl();
}
if (ch == '2')
{
insert_avl();
}
if (ch == '3')
{
printf("Dati id-ul inregistrarii care se sterge : ");
scanf("%d",&x);
indic(rad_avl,1);
sterge_avl(x,rad_avl,&ok);
}
if (ch == '4')
{
printf("Dati id-ul inregistrarii care se modifica : ");
scanf("%d",&x);
modificare_avl(x);
}
if (ch == '5')
afisare(rad_avl);
if (ch == '6')
salveaza();
if (ch == '7')
{
f=fopen("in.txt","r+");
printf("Afisare completa : \n\n");
printf(" Id Denumire comerciala Cantitate Producator Pret Data expirare\n\n");
afis2(rad_avl,5);
printf("\n");
}
if (ch == '0')
transforma();
}
while (ch != '0');
do
{
printf("Alegeti operatia : \n");
printf(" 1. Afisare B\n");
printf(" 0. Iesire\n");
ch=getch();
if (ch == '1')
afisare_b();
}
while (ch != '0');
}
Bibliografie
1. Introducere in algoritmi Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest.
2. Arta programarii calculatoarelor Donald E. Knuth.
-1
0
-1
0
1
0
0
0
0
0
0
0
-1
-1
+2
+1
0
0
-1
+2
+1
+2
-1
+1
0
0
-1
0
0
0
- 4 -
