Laborator 6
Arbori de regăsire
OBS
Pentru a modela explicatiile aferente unui cuvant, se va tine cont ca intr-un arbore de regasire, fiecare cuvant are asociat un singur pointer terminator (pointer in bucla, de obicei) si fiecare astfel de pointer terminator (in bucla) are asociat un singur cuvant. Exista astfel o corespondenta biunivoca intre cuvintele din dictionar si pointerii lor terminatori. Astfel, pointerul terminator al unui cuvant (care este, de regula, un pointer in bucla) poate fi modificat in cadrul acestei aplicatii astfel incat sa pointeze spre o structura ce contine explicatii referitoare la cuvantul respectiv. Astfel, rolul pointerului terminator va fi si acela de a "referi" explicatiile unui cuvant, pe langa cel de marcare a sfarsitului cuvantului.
O alta modalitate de rezolvare ar putea lasa pointerul terminator (al 27-lea pointer din fiecare nod) sa-si "faca treaba" pentru care a fost conceput si ar putea prelungi fiecare nod cu inca un pointer (al 28-lea), care sa refere explicatiile pentru cuvant (in caz ca in respectivul nod se sfarseste vreun cuvant - sunt noduri in care nu se sfarseste vreun cuvant si aceste noduri nu vor trebui sa ofere explicatii).
Aplicatia 1
Sa se redacteze un program interactiv care implementeaza urmatoarele functii pentru prelucrarea unui dictionar de cuvinte implementat printr-un arbore de regasire:
o functie pentru initializarea dictionarului (nici un cuvant);
o functie pentru inserarea unui cuvant in dictionar, impreuna cu explicatiile aferente;
o functie pentru suprimarea unui cuvant din dictionar, impreuna cu explicatiile aferente, dezalocand memoria daca este cazul;
o functie pentru cautarea unui cuvant in dictionar si afisarea explicatiilor aferente;
o functie pentru afisarea inaltimii arborelui de regasire;
o functie care afiseaza toate cuvintele din dictionar ce incep cu o litera data;
o functie care returneaza numarul de noduri din arborele de regasire;
o functie care returneaza raportul dintre numarul de pointeri nenuli si numarul total de pointeri din dictionar;
o functie care afiseaza cuvantul cel mai lung din dictionar;
o functie care afiseaza primul cuvant din dictionar.
rezolvare
Sa se redacteze un program interactiv care implementeaza urmatoarele functii pentru prelucrarea unui dictionar de cuvinte implementat printr-un arbore de regasire:
o functie pentru initializarea dictionarului (nici un cuvant);
o functie pentru inserarea unui cuvant in dictionar, impreuna cu explicatiile aferente;
o functie pentru suprimarea unui cuvant din dictionar, impreuna cu explicatiile aferente, dezalocand memoria daca este cazul;
o functie care permite modificarea explicatiilor aferente unui cuvant dat;
o functie pentru cautarea unui cuvant in dictionar si afisarea explicatiilor aferente;
o functie pentru afisarea gradului arborelui de regasire;
o functie care returneaza raportul dintre numarul de cuvinte si numarul de noduri din dictionar;
o functie care afiseaza toate cuvintele din dictionar;
o functie care afiseaza cuvantul cel mai scurt din dictionar;
o functie care afiseaza ultimul cuvant din dictionar.
rezolvare
ArboreRegasire.h
#ifndef ARBORE_REGASIRE
#define ARBORE_REGASIRE
typedef struct NodArboreDeRegasire {
struct NodArboreDeRegasire *alfabet[27]; //alfabetul A B ... Z [
}NodArboreDeRegasire;
void Initializare(NodArboreDeRegasire *Nod);
void Atribuie(NodArboreDeRegasire *Nod, char c, NodArboreDeRegasire *p);
NodArboreDeRegasire *Valoare(NodArboreDeRegasire *Nod, char c);
void NodNou(NodArboreDeRegasire *Nod, char c);
typedef enum { false = 0, true = 1 }bool;
bool sfarsitCuvant(NodArboreDeRegasire *nod);
bool nodTerminal(NodArboreDeRegasire *nod);
int max(int a, int b)
void Adauga(char *cuvant, NodArboreDeRegasire *radacina);
void afisare(NodArboreDeRegasire *radacina, char *cuvant, int pozitieCurenta);
void cautare(NodArboreDeRegasire *nodcrt, char *cuvant);
int gradArbore(NodArboreDeRegasire *nodcrt);
#endif
ArboreRegasire.c
#include <stdlib.h>
#include <stdio.h>
#include "ArboreRegasire.h"
/*adaugare in arbore cuvinte
afisare alfabetica
cautare
gradul arborelui
*/
void Initializare(NodArboreDeRegasire *Nod)
{
//ATENTIE, aceasta functie trebuie apelata cu *Nod deja alocat
char c;
for (c = 'A'; c <= '['; c++)
Nod->alfabet[c - 'A'] = NULL;
}
void Atribuie(NodArboreDeRegasire *Nod, char c, NodArboreDeRegasire *p)
{
Nod->alfabet[c - 'A'] = p;
}
NodArboreDeRegasire *Valoare(NodArboreDeRegasire *Nod, char c)
{
return Nod->alfabet[c - 'A'];
}
void NodNou(NodArboreDeRegasire *Nod, char c)
{
Nod->alfabet[c - 'A'] = (NodArboreDeRegasire *)malloc(sizeof(struct NodArboreDeRegasire));
Initializare(Nod->alfabet[c - 'A']);
}
void Adauga(char *cuvant, NodArboreDeRegasire *radacina)
{
int i;
NodArboreDeRegasire *t;
t = radacina;
//TO DO: de adaugat cod pentru parcurgerea cuvantului, litera cu litera
//"for" adaugat
for(i=0; i<strlen(cuvant);i++)
{
if (Valoare(t, cuvant[i])==NULL) //nodul curent nu are fiu pentru caracterul x[i], deci se creaza unul nou
{
NodNou(t, cuvant[i]);
}
t = Valoare(t, cuvant[i]); //avansez in arborele de regasire
}
Atribuie(t, '[', t); //se face o bucla pentru '[', pentru a marca un nod terminal
}
bool sfarsitCuvant(NodArboreDeRegasire *nod)
{
if (nod->alfabet[26]!=NULL)
return true;
else
return false;
}
void afisare(NodArboreDeRegasire *radacina, char *cuvant, int pozitieCurenta)
{
if(sfarsitCuvant(radacina))
{
cuvant[pozitieCurenta]='\0';
printf("%s\n", cuvant);
}
if (cuvant==NULL)
{
cuvant=(char *)malloc(sizeof(char));
pozitieCurenta=0;
}
char j;
for (j='A';j<'[';j++)
{
if(Valoare(radacina,j)!=NULL)
{
cuvant[pozitieCurenta]=j;
afisare(Valoare(radacina,j), cuvant,pozitieCurenta+1);
}
}
}
bool nodTerminal(NodArboreDeRegasire *nod)
{
bool terminal = true;
int i;
for (i = 0; i < 26; i++)
if (nod->alfabet[i] != NULL)
{
terminal = false;
break;
}
return terminal;
}
int max(int a, int b)
{
if(a>b)
return a;
return b;
}
int gradArbore(NodArboreDeRegasire *nodcrt)
{
if (nodTerminal(nodcrt)) //toate literele sunt nule, mai putin ultima(26)
return 0;
char j;
int maxim = 0;
for (j = 0; j < 26; j++)
if (nodcrt->alfabet[j] != NULL)
maxim++;
for (j = 0; j < 26; j++)
if (nodcrt->alfabet[j] != NULL)
maxim = max(maxim, gradArbore(nodcrt->alfabet[j]));
return maxim;
}
void cautare(NodArboreDeRegasire *nodcrt, char *cuvant)
{
if (strlen(cuvant) == 0)
{
printf("Am gasit cuvantul %s\n", cuvant);
return;
}
if (nodcrt->alfabet[cuvant[0] - 'A'] != NULL)
cautare(nodcrt->alfabet[cuvant[0] - 'A'], cuvant + 1);
else
printf("Nu s-a putut gasi cuvantul cerut\n");
}
main.c
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}