Cautare in tabele

Cautare in tabele

In aceasta sectiune vom da continutul unui pachet de cautare

in tabel ca o ilustrare a mai multor aspecte legate de

structuri. Amcest pachet este tipic pentru modul de explorare

a unui tabel de simboluri pentru rutinele de management ale

unui macroprocesor. De exemplu sa consideram declaratia din C,

'#define'. Cind o linie ca

#define YES 1

este luata in considerare, numele YES si textul corespunzator 1

sint memorate intr-un tabel. Mai tirziu, cind numele YES apare

intr- declaratie ca

inword = YES;

trebuie inlocuit cu 1.

Exista doua rutine majore care manipuleaza numele si textele

de inlocuire corespunzatoare. 'install(s, t)' inregistreaza

numele 's' si textul de inlocuire 't' intr-o tabela; 's'

si't' sint siruri de caractere. 'lookup(s)' cauta numele 's'

intr-o tabela si returneaza un pointer la locul unde afost gasit

ori NULL daca nu a fost gasit.

Algoritmul care se utilizeaza se bazeaza pe o cautare

fragmentara 'hash' un nume care se introduce este convertit

intr-un intreg pozitiv care apoi este utilizat ca index intr-un

tabloude pointeri. Un element al tablului pointeaza pe inceputul

unui lant de balncuri care descriiu avind respectiva valoare de

fragment ('hash'). Acesta este NULL daca nici un nume nu

corespunde acestei valori.

Un bloc din lant este o structura care contine: pointeri, la

nume, textul de inlocuire si urmatorul bloc din lant. Daca

pointerul pentru urmatorul bloc este nul marcheaza sfirsitul

lantului de blocuri.

struct nlist ;

Tabloul de poiunteri este:

#define HASHSIZE 100

static struct nlist *hashtab[HASHSIZE]; /* pointer table */

Functia de fragmentare ('hashing'), care este utilizata de

ambele rutine 'lookup' si 'install', aduna valorile carcterelor

din sirul nume si formeaza restul modulo dimensiunea tabloului.

(Aceasta nu este cel mai bun algoritm posibil, darare meritul

simplitatii. )

hash(s) /* form hash value for string s */

char *s;

Procesul de fragmentare ('hashing') produce un index de cautare

in 'hashtab'; sirul de carctere cautat se va gasi intr-un bloc

din sirul de blocuri a carui inceput este pointat de elementul

din tabelul 'hashtab'. Cautarea este efectuata de rutina

'lookup'. Dca 'lookup' gaseste in 'hashtab' intrarea deja

prezenta, returneaza un pointer; daca nu, returneaza NULL.

struct nlist *lookup(s) /* look for s in hashtab */

char *s

else /* already there */

free(np->def); /*free previous definition */

if ((np->def = strsave(def)) == NULL

return(NULL);

return(np);

}

'strsave' copiaza sirul furnizat de catre argumentul sasu

intr_un loc obtinut cu un apel la functia 'alloc'. Am

prezentat codul in capitolul 5 Deoarece apelurile la 'alloc' si

'free' pot sa apara in orice ordine si deoarece aici aliniamentul

conteaza, versiunea simpla a 'alloc' de la capitolul 5, nu este

adecvata aici vedeti capitolele 7 si 8.

Exercitiul 6.7. Scrieti o rutina care sa scoata un nume si

definitia dintr-o tabela mentinuta cu 'lookup' si 'install'.

Exercitiul 6.8. Implementati o versiune simpla a

procesorului '#define' utilizabila in programe C, folosind

rutinele din aceasta sectiune. Puteti gasi de ajutor si 'getch' si

'ungetch'.