Cuprins
- • Generalitati despre ARBORII B+ si TRIE
- • Modul de rezolvare
- • Codul sursa al programului realizat in limbajul C
- • Bibliografie
Extras din proiect
Gestiunea unui magazin de piese auto
Se va realiza un program care va permite accesul la operatii specifice gestionarii unui magazin de piese auto.Produsele vor fi reprezentate in doua structuri de date arborescente, arbori B+ si arbori Trie, asupra carora se vor produce operatiile cerute.Informatiile despre piesele auto vor fi citite din fisierul text ‘piese.in’.
Fiecare produs va avea urmatoarea structura
- Cod
- Numar bucati
- Denumire
- Producator
- Pret
Pe arborele B+ care va avea 3 chei si 4 descendenti la fiecare nod, se implementeaza urmatoarele oparatii:
- 1 Inserare din fishier
- 2 Afisarea produselor
- 3 Afisarea arborelui B+
- 4 Adaugare produs
- 5 Cautare dupa codul produsului
- 6 Modificare informatie
- 7 Stergere informatie
- 8 Afisare in fisier
- 9 Transformare in arbore Trie
Din arb B+ se creeaza un arbore Trie cu urmatoarele operatii:
- 1 Afisarea produselor in forma arborelui Trie
- 2 Adaugare produs
- 3 Eliminare produs
- 4 Cautare dupa denumirea produsului
- 5 Afisare in fisier
- 7 Iesire
Generalitati despre ARBORI B+ si TRIE
Modul de rezolvare
Un ARBORE B de ordinul n este un arbore multicai perfect echilibrat, care are urmatoarele caracteristici:
- fiecare pagina are cel mult 2n-1 chei;
- fiecare pagina cu excepţia radacinii are cel puţin n chei;
- fiecare pagina cu excepţia celei terminale are m+1 descendenţi direcţi, unde m este numarul de chei efective din pagina;
- toate paginile terminale apar la acelasi nivel (perfect echilibrat).
Diferenta dintre un arbore B si unul B+ apare la nivelul frunzelor.La arborele B+, cand se executa splitul unei frunze, cheia care urca in radacina ramane si in frunza. De asemenea, frunzele arborelui B+ au intre ele o legatura dinamica.
Campurile unui Arbore B+ vor fi :
- 2n-1 chei ;
- 2n descendenti ;
- un contoar pentru chei ;
- un pointer care indica spre frunza din dreapta (folosit doar la frunze)
In implementarea de fata, n=2. Asadar fiecare nod are cel mult 3 chei si cel putin 1.
Structura unui nod va avea forma :
typedef struct ppag
{ int nrc;
int k[4];
struct ppag *des[4];
struct ppag *f;
struct textile *c[4];
} pag;
Iar structura unui produs :
struct textile {
int cod, nr_buc;
char den[30];
float pret;
};
Preview document
Conținut arhivă zip
- PROIECTT.CPP
- Structuri de Date si Algoritmi - Gestionarea unui Magazin de Piese Auto.doc