Home - qdidactic.com
Didactica si proiecte didacticeBani si dezvoltarea cariereiStiinta  si proiecte tehniceIstorie si biografiiSanatate si medicinaDezvoltare personala
referate stiintaSa fii al doilea inseamna sa fii primul care pierde - Ayrton Senna





Aeronautica Comunicatii Drept Informatica Nutritie Sociologie
Tehnica mecanica




Informatica


Qdidactic » stiinta & tehnica » informatica
Tabele de dispersie



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(k1)=f(k2) 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:



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









Contact |- ia legatura cu noi -| contact
Adauga document |- pune-ti documente online -| adauga-document
Termeni & conditii de utilizare |- politica de cookies si de confidentialitate -| termeni
Copyright © |- 2024 - Toate drepturile rezervate -| copyright

stiinta

Informatica



Access
Autocad
Baze de date
C
Calculatoare
Catia
Excel
Foxpro
Grafica design
Html
Internet
Java
Linux
Mathcad
Matlab
Oracle
Outlook
Photoshop
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word

Proiecte pe aceeasi tema


Algoritmi fundamentali de sortare
Tabele de dispersie
Aplicatii - nnmodel
Lucrare pentru atestarea competentelor profesionale la informatica - tablouri bidimensionale
Elemente fundamentale ale limbajului JavaScript



Ramai informat
Informatia de care ai nevoie
Acces nelimitat la mii de documente, referate, lucrari. Online e mai simplu.

Contribuie si tu!
Adauga online proiectul sau referatul tau.