Tabele de dispersie

TABELE DE DISPERSIE

Continutul lucrarii

In lucrare sunt prezentate principalele operatii asupra unei tabele de dispersie: construirea tabelei de dispersie, inserarea unei inregistrari, cautarea unei inregistrari, afisarea inregistrarilor. De asemenea se fac cateva consideratii asupra alegerii functiei de dispersie.

Consideratii teoretice

2.1.Tipuri de tabele

Tabelul este o colectie de elemente de acelasi tip, identificabile prin chei. Elementele sale se mai numesc inregistrari.

Tabelele pot fi :

- fixe, cu un numar de inregistrari cunoscut dinainte si ordonate;     

- dinamice

Tabelele dinamice pot fi organizate sub forma de:

- lista dinamica simplu sau dublu inlantuita;

- arbore de cautare;

- tabele de dispersie.

Din categoria tabelelor fixe face parte tabelul de cuvinte rezervate dintr-un limbaj de programare. Acesta este organizat ca un tablou de pointeri spre cuvintele rezervate, introduse in ordine alfabetica. Cautarea utilizata este cea binara.

Tabelele dinamice organizate sub forma de liste au dezavantajul cautarii liniare. Arborele de cautare reduce timpul de cautare. In cazul in care cheile sunt alfanumerice, comparatiile sunt mari consumatoare de timp. Pentru astfel de situatii, cele mai potrivite sunt tabelele de dispersie.

2.2.Functia de dispersie ( hashing )

Functia de dispersie este functia care transforma o cheie intr-un numar natural numit cod de dispersie:

f: K -> H

unde K este multimea cheilor, iar H este o multime de numere naturale.

Functia f nu este injectiva .Doua chei pentru care f(k₁)=f(k₂) se spune ca intra in coliziune, iar inregistrarile respective se numesc sinonime.

Asupra lui f se pun doua conditii:

- valoarea ei pentru un ke K sa rezulte cat mai simplu si rapid;

- sa minimizeze numarul de coliziuni.

Un exemplu de functie de dispersie este urmatoarea:

f(k)=g(k) mod M

unde g(k) este o functie care transforma cheia intr-un numar natural, iar M este un numar

natural recomandat a fi prim.

Functia g(k se alege in functie de natura cheilor. Daca ele sunt numerice, atunci g(k)=k. In cazul cheilor alfanumerice, cea mai simpla functie g(k este suma codurilor ASCII ale caracterelor din componenta lor; ca urmare  functia f de calcul a dispersiei este urmatoarea:

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

#define M .

int f(char *key)

2.3.Tabela de dispersie

Rezolvarea coliziunilor se face astfel: toate inregistrarile pentru care cheile intra in coliziune sunt inserate intr-o lista simplu inlantuita. Vor exista astfel mai multe liste, fiecare continand inregistrari cu acelasi cod de dispersie. Pointerii spre primul element din fiecare lista se pastreaza intr-un tablou, la indexul egal cu codul de dispersie .Ca urmare modelul unei tabele de dispersie este urmatorul:

Un nod al listei are structura urmatoare:

typedef struct tip_nod TIP_NOD;

Tabloul HT este declarat astfel:

TIP_NOD *HT[M];

Initial el contine pointerii nuli:        

for(i=0;i<M;i++)

HT[i]=0;

Cautarea intr-o tabela de dispersie a unei inregistrari avand pointerul key la cheia sa, se face astfel:

- se calculeaza codul de dispersie:

h=f(key);

- se cauta inregistrarea avand pointerul key la  cheia sa, din lista avand pointerul spre primul nod HT[h].

Cautarea este liniara:

p=HT(h);

while(p!=0)

return 0;

Inserarea unei inregistrari intr-o tabela de dispersie se face astfel:

- se construieste nodul de pointer p, care va contine informatia utila si pointerul la cheia inregistrarii:

p=(TIP_NOD*)malloc(sizeof(TIP_NOD));

citire_nod(p);

- se determina codul de dispersie al inregistrarii:

h=f(p->cheie);

- daca este prima inregistrare cu codul respectiv, adresa sa este depusa in tabelul HT:

if(HT[h]==0)

in caz contrar se verifica daca nu cumva mai exista  o inregistrare cu cheia respectiva. In caz afirmativ se face o prelucrare a inregistrarii existente ( stergere, actualizare) sau este o eroare (cheie dubla ). Daca nu exista o inregistrare de cheia respectiva, se insereaza in lista ca prim element nodul de adresa p:

q=cautare(p->cheie);

if(q==o)

else prelucrare(p,q);/* cheie dubla */

Construirea tabelei de dispersie se face prin inserarea repetata a nodurilor.

2.4.Listarea tuturor inregistrarilor

Listarea tuturor inregistrarilor pe coduri se face simplu, conform algoritmului urmator:

for(i=0;i<M;i++)

}

3.Mersul lucrarii

3.1. Se va crea o tabela fixa cu cuvintele rezervate din limbajul C. Se va scrie apoi o functie de cautare binara a unui cuvant in tabela.

3.2. Sa se implementeze algoritmii prezentati aferenti unei tabele de dispersie. Inregistrarea va contine datele aferente unui student. Cheia va fi numele si prenumele studentului. Scrieti in plus

fata de cele prezentate o functie de stergere a unei inregistrari de cheie data.

3.3. Scrieti un program care sa tipareasca identificatorii dintr-o tabela de dispersie in ordine alfabetica.

3.4. Sa se afiseze frecventa de aparitie a literelor dintr-un text utilizand o tabela de dispersie.