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".
