Structuri cu autoreferire
Sa presupunem ca vrem sa tratam problema numararii aparitiei
cuvintelor in modul cel mmai general adica sa numaram fiecare
aparitie a fiecarui cuvint la o intrare. Deoarece lista de
cuvinte nu este cunoscuta in avans nu putem sa o sortam
convenabil si sa folosim o cautare liniara. Inca nu putem sa
efectuam o cautare liniara pentru fiecare cuvint in momentul
cind soseste pentru a vedea daca a mai aparut deoarece perogramul
ar dura foarte mult. (Mai precis, timpul de rulare ar creste
cu patratul numarului de cuvinte introduse. ) Cum putem organiza
datele pentru a face fata in mod eficient cu o lista de
cuvinte arbitrare?
O solutie ar fi sa pastram setul de cuvinte sortat in orice
moment plasind fiecare cuvint in pozitia adecvata in
momentul sosirii lui. Aceasta n-ar terebui facut prin mutarea
cuvintelor intr-un tablou linear deoarece si aceasta ia un timp
prea lung. In loc vom utiliza o structura de date numita "binary
tree" adica arborele binar.
Arborele contine un "node" pentru fiecare cuvint distinct; fiecare
nod contine:
un pointer la textul cuvintului
un contor al numarului de aparitii
un pointer la nodul-copil din stinga
un pointer la nodul-copil din dreapta
Nici un nod nu poate avea mai mult de doi copii. Ar trebui sa
aiba numai zero sau unu.
Nodurile sint astfel mentinute incit subarborele din stinga
contine numai cuvinte care sint mai mici decit cuvintele
din nodul considerat, iar subarborele din dreapta numai
cuvinte care sint mai mari. Pentru a afla daca un nou cuvint se
afla in arbore se incepe comparatia de la nodul radacina. Daca ele
sint egale chestiunea este rezolvata Daca noul cuvint este mai
mic decit cuvintul din nodul radacina cercetarea continua la
nodul copil din stinga; altfel este investigat nodul copil din
dreapta. Daca nu gasete nici un copil cu un continut egal noului
cuvint, inseamna ca noul cuvint nu se afla in vreun nod al
arborelui si deci trebuie creat unul. Procesul de cautare
este inerent recursiv deoa rece cautarea din orice nod este
legata de cautarea din unul din nodurile copii. In consecinta
rrutinele pentru insertie si tiparire vor fi cele mai naturale.
Intorcindu-ne la descrierea unui nod, este clar o
structura cu patru componente:
struct tnode ;
In general este ilegal ca o structura sa contina o parte a ei
insusi, dar
struct tnode *left;
declara "left" ca fiind un pointer al nodului si nu nodul insusi.
Codul pentru intregul program este surprinzator de scurt si
foloseste o multime de rutine ajutatoare pe care deja le-am
scris. Acestea sint 'getword' pentru a aduce fiecare cuvint de
la intrare si 'alloc' pentru a obinte spatiu pentru cuvinte in
avans.
Rutina principala citeste cuvinte cu ajutorullui 'getword' si le
instaleaza in arbore cu ajutorul lui 'tree'.
#define MAXWORD 20
main() /* word frequency count */
Un cuvint este prezentat de catre rutina "main" la
nivelul cel mai de sus(radacina) arborelui. La fiecare nivel
cuvintul este comparat cu cuvintul aflat deja in nod si apoi
este coborit in arbore fi e in subarborele din dreapta fie in
cel din stinga printr-o apelare recursiva la "tree". Cuvintul nou
fie are deja un corespondent in arbore in care caz
contorul este incrementat, fie se ajunge la un pointer nul
ceea ce indica necesitatea creearii unui nou nod in arbore. Daca
este creat un nou nod "tree" returneaza un pointer care este
instalatin nodul parinte.
struct tnode *tree(p, w) /* install w at or below p */
struct tnode *p;
char *w;
else if ((cond = strcmp(w, p->word)) == 0)
p->count++; /* repeated word */
else if (cond < 0) /* lower goes into left subtree */
p->left = tree(p->left, w);
else /* greater into right subtree */
p->right = tree(p->right, w);
return(p);
}
Memoria pentru noul nod este obtinuta de rutina "talloc" care este
o adaptare a rutinei "alloc" scrisa mai devreme. Aceasta
returneaza un pointer a unui spatiu liber utilizabil pentru un
nod. ANoul cuvint este copiat in locul pregatit de catre
"strsave", contorul este initializat si cei doi copii sint facuti
nuli. Aceasta parte a programului este executata numai la
"marginea" copacului cind un nou nod este de adaugat. Am omis
intentionat controlul erorilor la valorile returnate de rutinele
"strsave" si "talloc".
Rutina "treprint" tipareste arborele incepind in ordine cu
subarborele din stinga; in fiecare nod tipareste subarborele
sting (toate cuvintele mai mici decit cel actual ), apoi
cuvintul actual, apoi subarborele drept (toate cuvintele mai
mari). Daca va simtiti cam nesiguri pe recursiune imaginativa
singuri un arbore si tipariti-l cu "tree print"; este una dintre
cele mai pure rutine recursive pe care o puteti gasi.
treeprint(p) /* prnt tree p recursinely */
struct tnode *p;
}
O observatie practica; daca arborele devine dezechilibrat din
cauza cuvintelor care nu sosesc intr-o ordine aleatoare, timpul
de rulare al progarmului poate sa creeasca prea repede. In cel
mai rau caz, daca cuvtele sosesc deja sortate acest program
devinnnnn o alternativa neeconomicoasa a cautarii lineare. Exista
generalizari ale arborelui care nu sufera de acest neajuns, dar
pe care nu le putem descrie aici.
Inainte de a parasi acest exemplu merita o scurta digresiune
asupra problemelor legate de alocarea de memorie. Clar, este
dezirabil ca intr-un program sa fie folosit un singur alocator
de memorie chiar daca aloca diferite feluri de obiecte. Dar
daca un alocator trebuie sa satisfaca cereri pentru pointeri de
caractere "char" sau de "struct tnode", daca se pun intrebari.
Prima, cum se satisface cerinta celor mai multe masini reale ca
obiectele de diferite tipuri sa fie aliniate la adrese
satisfacatoare(de exemplu intregii adesea trebuie aliniati pare)?
A doua, ce declaratii pot satisface faptul ca "alloc" in mod
necesar returneaza diferite tipuri de pointeri ?
Cererile de aliniament pot fi usor satisfacute, cu pretul
unor spatii neutilizate, asigurindu-ne ca alocatorul
intodeauna returneaza pointeri care intrunesc toate restrictiile
de aliniament. De exemplu pentru PDP-11 este suficient ca
"alloc" intodeauna sa returneze un "even" point, din moment ce
orice tip de obiect poate fi memorat la o adresa "even". Masuri
asemanatoare se iau pe alte masini. Astfel implementarea
unui "alloc" poate sa nu fie portabila) dar usajul este.
"Alloc"-ul din capitolul 5 nu garanteaza nici un aliniament
particular. In capitolul 8 vom prezenta modul de a face corect.
In legatura cu intrebarea asupra declaratiei tipului pentru
"alloc"; i"c" cea mai buna metoda este aceea de a dlara ca
"alloc" returneaza un pointer la "char" si apoi sa se
converteasca ppoinerul in tipul dorit. Daca p este declarat
astfel:
char *p;
atunci
(struct tnode *)p
il converteste intr-unn "tnode" pointer dintr-o exepresie.
Astfel "talloc" devine:
struct tnode *talloc()
Aceasta este mai mult decit este nevoie pentru compilarile
curente dar reprezinta cel mai sigur mod pentru viitor.
Exercitiul 6.4. Scrieti un program care citeste un program "c" si
tipareste in ordine alfabetica fiecare grup al numelor de
variaile care sint identice in primele 7 caractere dar
diferite dupa aceea. (Asigurativa ca 7 este un parametru).
Exercitiul 6.5. Scrieti un porogram care tipareste o lista a
tuturor cuvintelor dintr-un text si pentru fiecare cuvint o lista
cu numerele liniei in care apar.
Exercitiul 6.6. Scrieti un program care tipareste cuvintele
distincte, care sint introdues, in ordinea frecventei lor de
aparitie. Fiecare cuvint sa fie precedat de numarul de aparitii.
