Capitolul 6.5. Structuri cu autoreferire

Vezi subiectul anterior Vezi subiectul urmator In jos

Capitolul 6.5. Structuri cu autoreferire

Mesaj  zooky la data de Mier Mar 18, 2009 1:54 pm

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 { /* the basic node */
char *word; /* points to the text */
int count; /* number of occurrences */
struct tnode *left; /* left child */
struct tnode *right; /* right child */
};

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 */
{
struct tnode *root, *tree();
char word[MAXWORD];
int t;
root = NULL;
while ((t = getword(word, MAXWORD)) != EOF)
if (t == LETTER)
root = tree(root, word);
treeprint(root);
}

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;
{
struct tnode *talloc();
char *strsave();
int cond
if (p == NULL) { /* a new word has arrived */
p = talloc(); /* make a new node */
p->word = strsave(w);
p->count = 1;
p->left = p->right = NULL;
} 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;
{
if (p != NULL) {
treeprint(p->left);
printf("%4d %s\n", p->count, p->word);
treeprint(p->right);
}
}

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()
{
char *alloc();
return((struct tnode *) alloc(sizeof(strusct tnode)));
}

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.
avatar
zooky
Moderator
Moderator

Numarul mesajelor : 147
Data de inscriere : 15/03/2009
Varsta : 24
Localizare : Cernatesti City

Vezi profilul utilizatorului http://e-learning.forumhit.ro

Sus In jos

Vezi subiectul anterior Vezi subiectul urmator Sus


 
Permisiunile acestui forum:
Nu puteti raspunde la subiectele acestui forum