Structuri cu autoreferire

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.