Structuri de date si algoritmi

Gestionarea unui magazin de piese auto

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

CUPRINS

. Generalitati despre ARBORII B+ si TRIE

. Modul de rezolvare 

Codul sursa al programului realizat in limbajul C . Bibliografie

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 exceptia radacinii are cel putin n chei;

Ø     fiecare pagina cu exceptia celei terminale are m+1 descendenti directi, 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

pag;

Iar structura unui produs :

struct textile ;

Ø   Inserarea unei chei in arborele b+

O cheie este inserata intr-un nod daca numarul de chei aflate in nod este mai mic decat numarul maxim de chei permise (n*2-1). In cazul in care pagina este plina, ea este impartita in 2 pagini, fiecare dintre ele cu n-1 chei, iar cheia din mijloc urca in nodul tata.

Daca pagina reprezinta frunza, cheia mediana ramane si intr-una din paginile nou formate.

In program, inserarea in arborele B+ este efectuata prin apelarea functiei Insert :

void insert(textile *c)

care foloseste alte doua functii :

void insert_neplin(pag **rad, textile *prod)

si

void split(pag **rad, int i, pag **nod_c)

Functia insert_neplin verifica daca radacina arborelui b+ este sau nu plina. In cazul in care este plina, declara o noua radacina, fara chei, al carei singur descendent este vechea radacina, apoi apeleaza divide_fiu pentru a divide fosta radacina in doua noduri.

In continuare, functia apeleaza insert cu parametri vechea radacina si produsul care doreste a fi introdus.

Insert cauta descendentul nodului curent catre care trebuie introdusa cheia, si apeleaza insert(descendent, produs), precedat, daca este cazul, daca descendentul are deja 3 chei, de split

Split are ca parametri un nod x neplin, unul plin, y si variabila intreaga i care indica care descendent al lui x este y. Functia creaza un nou nod z, in care se trece cheia 3 a lui y. Este urcata cheia 2 in x, si asezata astfel incat sa se pastreze ordinea crescatoare a cheilor. In cazul in care y este frunza, se introduce z in legaturile dintre frunze, si cheia mediana este pastrata la y (y->nk=2).

Ø   Cautare in B+

Cautarea se face incepand cu radacina, cautand in fiecare pagina cheia dorita. Daca cheia nu se afla printre cele prezente, se determina descendentul care va fi urmat.

Daca cheia este mai mica decat toate cheile paginii, atunci se reapeleaza pentru descendentul cel mai din stanga (des[0]). Daca valoarea cautata se afla intre doua chei, se porneste spre descendentul aflat intre ele (cheie[i]<val<cheie[i+1] --> des[i]) . Iar in cazul in care valoarea este mai mare decat toate cheile paginii, urmam descendentul din dreapta.

Daca acel descendent care trebuie urmat nu exista, nodul curent fiind frunza, se raspunde ca valoarea nu a fost gasita.

Cand se gaseste valoarea cautata, se afiseaza produsul cu toate proprietatile lui.

In program, functia care se apeleaza este void cautare_b (void este functia care cere utilizatorului codul produsului cautat, apeleaza functia find care returneaza produsul gasit, sau NULL daca acesta un face parte din arbore.

Functia find are ca parametrii nodul curent, si codul produsului cautat, si returneaza un produs, sau NULL, in cazul in care produsul nu este gasit.

Ø   Afisarea produselor din B+

Dupa mai multe adaugari, se doreste vizualizarea cheilor introduse in arborele B+. Din modul de creare - inserare, s-a vazut faptul ca o cheie poate aparea in arbore de mai multe ori, deoarece la dividerea unei frunze, o cheie se dubleaza. Se doreste evitarea tipariri unei chei de mai multe ori.

Tot din crearea arborelui b+ se observa ca toate cheile sunt inserate in frunze. Asadar, parcurgand frunzele de la stanga la dreapta se vor gasi toate cheile inserate in arbore, o singura data fiecare, si in ordine crescatoare.

Asadar, s-a implementat functia afisare_produse care parcurge in mod recursiv arborele pana la frunza cea mai din stanga, apoi tipareste la fiecare frunza cheile si produsele aferente cheilor, si trece la urmatoarea frunza, prin legatura dintre ele.

Ø   Afisare pe nivele a produselor din B+

Operatia este executata de functia afisare_arbore care porneste din nodul radacina si, la fiecare nod, afiseaza toate cheile continute, precum si nivelul la care se afla nodul in pagina. Apoi se reapeleaza recursiv functia pentru fiecare descendent nevid al nodului curent.

Ø   Transformarea arborelui B in Trie

Se doreste schimbarea structurii in care sunt introduse produsele, din arborele b+ in unul trie. Daca la arborele b+ s-au folosit codurile produselor ca chei, aici vom folosi denumirea acestora, deoarece arborele trie gestioneaza cuvinte, siruri de caractere.

Pentru a transforma arborele B+ in Trie se urmeaza pasii :

Ø     se creaza o radacina noua vida pentru arborele Trie ;

Ø     se parcurge arborele B+ pana la cea mai din stanga frunza ;

Ø     se parcurg frunzele, folosind legatura dinamica dintre ele, la fiecare frunza, fiecare cheie din respectiva, se apeleaza functia inserare_trie care adauga produsul in arborele trie.

ARBORII TRIE (arborii de regasire) sunt structuri de date speciale care pot fi utilizate in reprezentarea multimilor de caractere sau a tipurilor de date care sunt siruri de obiecte de orice tip sau siruri de numere.

Un arbore de regasire permite implementarea simpla a operatorilor definiti asupra unei structuri de date de tip multime, ale carei elemente sunt siruri de caractere (cuvinte) (inserare, stergere, cautare si tiparire).

Utilizarea e eficienta atunci cand numarul de prefixe distincte ale tuturor cuvintelor din multime e mult mai mic decat numarul total de cuvinte.

Intr-un arbore de regasire, fiecare drum de la radacina spre un nod terminal, corespunde unui cuvant al multimii. Nodurile arborelui corespund prefixelor cuvintelor. Pentru evitarea sitatiilor in care un cuvant este prefixul altuia deja introdus in arbore, si nu exista un loc in arbore pentru acel cuvant se foloseste in noduri un descendent special, fara vre-o litera asignata. Se pot face urmatoarele observatii:

Ø     fiecare nod are cel mult 27 de fii (26 litere ale alfabetului + descendentul special) ;

Ø     cele mai multe din noduri au mai putin de 27 de fii;

Ø     un nod la care se ajunge din descendentul special este intotdeauna frunza.

In program, declararea structurii arborelui trie :

typedef struct nod_trie

nodt;

unde cuv[30] reprezinta cuvantul cheie, de maxim 30 de caractere, *des[27] sunt descendentii nodului curent, int terminal este o variabila intreaga, a carei valoare este 1 daca nodul este frunza si 0 daca nodul este nod intern, iar *c este legatura dinamica la produsul pe care-l reprezinta cuvantul cheie.

Variabila globala rad_t reprezinta radacina arborelui trie.

Ø  Inserare in arbore Trie

Inserarea in abrorele trie se efectueaza cu ajutorul functiei inserare_trie care are ca parametrii nodul unde se incearca inserarea, produsul care trebuieste inserat, al carei denumire constituie cheie, si o variabila intreaga care reprezinta litera din cuvantul cheie care este selectata :

void inserare_trie(nodt **rad,textile *c,int lit)

Se apeleaza pentru radacina arborelui Trie, selectata considerandu-se prima litera din cuvant. La fiecare nod, trebuiesc examinate urmatoarele cazuri:

Ø     Daca s-au terminat literele cuvantului, adica acel cuvant este prefixul altor cuvinte introduse anterior in arbore. In acest caz, se creaza un nod frunza, caruia i se atribuie cuvantul dat, si produsul aferent acestuia. Acest nod devine descendentul special (des[26], 025 reprezentand literele alfabetului) al nodului curent.

Ø     Daca nu s-au terminat literele :

Descendentul corespunzator literei selectate nu exista : se creaza nodul frunza pentru noul produs, si se leaga ca fiind descendentul pe litera selectata a nodului curent.

Descendentul corespunzator literei selectate este nod intern : se reapeleaza functia de inserare pentru descendentul respectiv.

Descendentul corespunzator literei selectate este frunza : cuvantul si produsul din frunza se muta in variabile temporare, frunza este transformata in nod intern ( x->fr=0 ), apoi se apeleaza inserarea cuvantului din variabila temporara in nodul intern nou creat, si inserarea cuvantului dat in acelasi nod.

Functia trateaza toate aceste cazuri, si executa inserarea in arborele trie, pastrandu-i proprietatile si structura.

Ø   Eliminare din arbore Trie

Eliminarea unui cuvant cheie din arborele trie are trei parti componente :

Ø     Cautarea nodului frunza care contine cuvantul de sters ;

Ø     Eliminarea din arbore a nodului respectiv;

Ø     Refacerea structurii arborelui Trie.

In prima parte, cuvantul este cautat litera cu litera pana cand se

gaseste nodul frunza care-l contine. Daca ultima litera indica spre un nod intern, se cauta cuvantul in descendentul special. Daca nici acolo nu este gasit, inseamna ca nu exista in arbore, si deci nu poate fi eliminat.

Eliminarea se face simplu, nodul ia valoarea NULL.

Refacerea structurii este efectuata la revenirea din recursivitate, pentru nodurile prin care s-a executat cautarea, noduri interne. Unul din descendentii acestor noduri a fost eliminat. Se numara descententii.

In cazul in care nodul curent nu mai are nici un descentent, el este inutil si se sterge. Daca nodul mai are un singur descendent, de tip frunza, cuvantul din frunza este urcat in nod, care devine el frunza.

Functia elimina :

void elimina_trie(nodt **nc, char c[30],int i)

// Cautare si eliminare

else

else if (c[i]=='0')

if ((*nc)->des[26]!=NULL)

elimina_trie(&((*nc)->des[26]),c,i+1);

else

else {

if ((*nc)->des[c[i]-'a']!=NULL)

elimina_trie(&((*nc)->des[c[i]-'a']),c,i+1);

else

//Refacerea structurii

int j,nx=0,k;

for (j=0;j<=26;j++)

if ((*nc)->des[j]!=NULL)

if (nx==0)

(*nc)=NULL;

if ((nx==1)&&((*nc)->des[k]->terminal))

Ø   Cautarea in arbore Trie

Algoritmul de cautare este asemanator cu cel din stergere, diferenta aparand in momentul in care cheia este gasita.

Functia ceas *find(pag *nc,int cod)returneaza produsul al carei denumiri este cautata, iar void cauta_t(void citeste de la tastatura cuvantul cautat, apeleaza functia find_t, apoi, in cazul in care cautarea a avut succes, produsul este tiparit cu toate proprietatile sale.

Ø   Afisarea produselor din arborele Trie

Se porneste din radacina (rad_t), si la fiecare nod intern se reapeleaza pentru toti descendentii sai.

Nodurile frunza, care contin cuvinte, sunt afisate, cu deplasamentul corespunzator nivelului la care se afla.

Codul sursa al programului realizat in limbajul C

#include <conio.h>

#include <stdio.h>

#include <string.h>

struct textile ;

typedef struct ppag

pag;

typedef struct nod_trie

nodt;

pag *rad_b;

nodt *rad_t;

textile *find(pag *nc,int cod);

void split(pag **rad, int i, pag **nod_c)

else (*nod_c)->nrc=1;

z->nrc=1;

for (j=(*rad)->nrc;j>i;j--)

(*rad)->des[j+1]=(*rad)->des[j];

(*rad)->des[i+1]=z;

for (j=(*rad)->nrc;j>i;j--)

(*rad)->k[i+1]=(*nod_c)->k[2];

(*rad)->c[i+1]=(*nod_c)->c[2];

(*rad)->nrc=(*rad)->nrc+1;

void insert_neplin(pag **rad, textile *prod)

(*rad)->k[i+1]=k;

(*rad)->c[i+1]=prod;

(*rad)->nrc++;

}

else

insert_neplin(&(*rad)->des[i],prod);

}

void insert(textile *c)

else insert_neplin(&rad_b,c);

}

void insert_fis(void)

fclose(f);

void afisare_produse (void)

nc=nc->f;

}

while (nc!=NULL);

void afisare_fisier (void)

nc=nc->f;

}

while (nc!=NULL);

fclose(ff);

void afisare_arbore(pag *r, int niv)

void adauga_b(void)

textile *find(pag *nc,int cod)

void cautare_b (void)

else printf('nProdusul nu a fost gasit.');

textile *find_t(nodt *nc, char c[30],int i);

void inserare_trie(nodt **rad,textile *c,int lit)

else

if ((*rad)->des[c->den[lit]-'a']==NULL)

else if (((*rad)->des[c->den[lit]-'a'])->terminal)

else inserare_trie((&(*rad)->des[c->den[lit]-'a']),c,lit+1);

void sterge(pag *rad1,pag *rad,int kt)

else if(kt<rad1->c[j]->cod)

delete rad;

rad=0;

}

}

else

rad->nrc--;

}

}

else if(rad->des[i-1])

rad->c[i]->cod=temp->c[temp->nrc]->cod;

temp->nrc--;

if(!temp->nrc)

else rad->des[i-1]=temp->des[0];

}

}

else

rad->c[i]->cod=temp->c[1]->cod;

if(temp->nrc==1)

else rad->des[i]=temp->des[1];

}

else

temp->des[j-1]=temp->des[j];

temp->des[j]=0;

temp->nrc--;

}

}

}

}

void modificare(void)

else printf('nInformatia nu se afla in arboren');

}

void trecere(void)

nc=nc->f;

}

while (nc!=NULL);

void meniu_b2 (void)

}

void adauga_t(void)

void elimina_trie(nodt **nc, char c[30],int i)

else

else if (c[i]=='0')

if ((*nc)->des[26]!=NULL)

elimina_trie(&((*nc)->des[26]),c,i+1);

else

else

}

int j,nx=0,k;

for (j=0;j<=26;j++)

if ((*nc)->des[j]!=NULL)

if (nx==0)

(*nc)=NULL;

if ((nx==1)&&((*nc)->des[k]->terminal))

void elimina_t (void)

textile *find_t(nodt *nc, char c[30],int i)

void cauta_t(void)

else printf('nProdusul nu a fost gasit.');

void afisare_t(nodt *nc, int niv)

else for (i=0;i<=26;i++)

if (nc->des[i]!=NULL)

afisare_t(nc->des[i],niv+1);

void afisare_fisier(nodt *nc,int niv,FILE *f1)

else

for(i=0;i<=26;i++)

if(nc->des[i]!=NULL)

afisare_fisier(nc->des[i],niv+1,f1);

void meniu_trie (void)

}

void main(void)

BIBLIOGRAFIE

Ø      Prof. Burdescu Dumitru Dan - "TREE DATA STRUCTURES" (course)

Reprografia Universitatii din Craiova, 1997

Ø      Corman,Laiserson,Rivest-"INTRODUCTION TO ALGORITHM",M.I.T. Press, 1992

Ø      Prof. Burdescu Dumitru Dan,Brezovan,Cosulschi - "STRUCTURI DE

DATE ARBORESCENTE IN PASCAL SI C",Reprografia Universitatii din Craiova, 2000

Ø      Indrumar de laborator