Facultatea de Automatica si Calculatoare
Universitatea
“Politehnica” Bucuresti
PROIECT AA
DICTIONARE
amarfoaie.home.ro/paa.html
Amarfoaie Andrei – Sabin
Ghica Alexandru
334 CA
anul III
Proiectul are ca date de intrare un sir de cuvinte ‘c’ si doi întregi: ‘a’ si ‘b’. Se folosesc, pe rând, urmatoarele structuri de date:
I.BArbori
Fiecare cuvânt din ‘c’ este inserat într-un BArbore de coeficient ‘a’ (cu interpretarea ca fiecare nod poate retine cel mult 2*a-1 informatii).
Clasa ‘Barbore’ cuprinde cinci metode pentru inserarea si cautarea unei chei:
public
void insereazaBArbore(String k,...)
{
Nod r=radacina;
. . .
if (r.n==dt-1)
{
Nod s = new Nod();
radacina=s;
s.frunza=0;
s.n=0;
s.copii.add(1,r);
divideCopilBArbore(s,1,r);
. . .
insereazaBArboreNeplin(s,k,col);
}
else
{
insereazaBArboreNeplin(r,k,col);
}
. . .
}
private void divideCopilBArbore(Nod x, int i, Nod y)
{
int j;
Nod z=new Nod();
z.frunza=y.frunza;
z.n=t-1;
for (j=1;j<=t-1;j++)
z.cheie.add(j,y.cheie.elementAt(j+t));
if (y.frunza==0)
for (j=1;j<=t;j++)
z.copii.add(j,y.copii.elementAt(j+t));
y.n=t-1;
x.copii.add(i+1,z);
x.cheie.add(i,y.cheie.elementAt(t));
x.n=x.n+1;
}
private void insereazaBArboreNeplin(Nod x, String k,int col)
{
int i=x.n;
if (x.frunza==1)
{
while(i>=1&&k.compareTo((String)x.cheie.elementAt(i))<0)
i=i-1;
x.cheie.add(i+1,k);
x.n=x.n+1;
. . .
}
else
{
while (i>=1 &&
k.compareTo((String)x.cheie.elementAt(i))<0)
i=i-1;
i=i+1;
Nod cix=(Nod)x.copii.elementAt(i);
. . .
if (cix.n==dt-1)
{
divideCopilBArbore(x,i,cix);
if (k.compareTo((String)x.cheie.elementAt(i))>0)
i=i+1;
cix=(Nod)x.copii.elementAt(i);
. . .
}
insereazaBArboreNeplin(cix,k,col);
}
}
public int cautaBArbore(String k,int col)
{
return(cautare(radacina,k,col));
}
private int cautare(Nod x,String k,int col)
{
int i=1;
while ((i<=x.n) && (k.compareTo(x.cheie.elementAt(i))>0))
i=i+1;
if ((i<=x.n) &&
(k.compareTo(x.cheie.elementAt(i))==0))
{
return(1);
}
if (x.frunza==1)
return(0);
else
return(cautare((Nod)x.copii.elementAt(i),k,col));
}
La un moment dat
arborele poate fi descris astfel:
II.Arbori Trie
Literele cuvintelor din ‘c’ apar în nodurile arborelui trie începând de la cel de-al treilea nivel, primul fiind considerat radacina logica, si notat cu ‘*’.
Clasa ‘ArboreTrie’ cuprinde urmatoarele metode pentru inserarea si cautarea unei informatii:
private
char inf(String s,Nod n,int k)
{
if (s.length()==k)
return (1);
Nod aux = new Nod();
char cautat = s.charAt(k);
for (int i=0;i<n.v.size();i++)
{
aux = (Nod) n.v.elementAt(i);
char q[]={aux.cheie};
String afisat=new String(q);
int a=aux.x,b=aux.y;
. . .
if (cautat==aux.cheie)
return(inf(s,aux,++k));
}
return(0);
}
public int cauta(String s,int col)
{
if (s.length()!=0)
return(inf(s,radacina,0));
return(0);
}
private char inserare(String s,Nod n,int k)
{
char inserat= s.charAt(k);
Nod aux=new Nod();
if (!n.v.isEmpty())
for (int i=0;i<n.v.size();i++)
{
aux = (Nod) n.v.elementAt(i);
if (inserat == aux.cheie)
{
if (s.length()==k+1)
{
aux.inf = '1';
return('1');
}
else
return(inserare(s,aux,++k));
}
}
Nod nn = new Nod();
nn.cheie=inserat;
if (s.length()==k+1)
{
nn.inf='1';
n.v.addElement(nn);
return('1');
}
n.v.addElement(nn);
return(inserare(s,nn,++k));
}
public void adauga (String s,int col)
{
inserare(s,radacina,0);
. . .
}
In timpul executiei arborele trie poate ajunge la urmatoarea forma:
III.Tabele de dispersie
Fiecarei litere îi corespunde un numar calculat în functie de intregul ‘b’. Un cuvânt este evaluat prin realizarea operatiei SAU – logic pentru fiecare bit al valoarilor asociate literelor sale.
Secventa urmatoare corespunde unui exemplu de calcul al codului fiecarei litere (‘a’-‘z’):
for(i=0;i<26;i++)
{
d=new Double(Math.pow(2,i%c));
v1[i]=new Integer(d.intValue());
},
iar urmatoarea, calculului
codului (‘j’) al unui cuvânt ‘s’
for (i=0;i<s.length();i++)
if ((s.charAt(i)>='a')||(s.charAt(i)<='z'))
j=j|(v1[s.charAt(i)-97]).intValue();