Stabilirea legăturii telefonice între n localități

Introducere

1. Introducere

Introducere

Tema de baza a lucrarii de an este “Stabilirea legaturii telefonice intre N localitati.”, cu utilizarea a citorva algoritmi de cautare si sortare ca: Bucket-sort - algoritm principal, Metoda injumatatirii intervalului- algoritm secundar si a algoritmilor de sortare Bucket-sort.Pe parcursul elaborarii programului am folosit listele dubluinlantuite, introducerea in fisier si extragerea din fisier cu ajutorul functiilor fprintf si fscanf observind eficienta acestor functii standart “C”, eficienta consta in faptul de rapiditae si volumul de cod pentru implementare. Dupa tesrtarea a celor doua algoritme de cautare Hash-search si Metoda injumatatirii intervalului am observat eficienta algoritmului Hash-search in cautarea intro baza de date cu un volum mai mare de date.Chiar si citind teoria asupra celor doua algoritme se poate de observat avantajul principal al algoritmului hash search, pe cind algoritmul de cautare injumatatirii intervalelor are eficienta in nr. de pasi pe care ii face.

ALGORITMI

1.Hashing

Tabele de dispersie (HASH Table)

Tabelul este o colecţie de elemente de acelaşi tip, identificabile prin chei. Elementele sale se mai numesc înregistrări.

Tabelele pot fi :

- fixe, cu un număr de înregistrări cunoscut dinainte şi ordonate;

- dinamice

Tabelele dinamice pot fi organizate sub formă de:

- listă dinamică simplu sau dublu înlănţuită;

- arbore de căutare;

- 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 în ordine alfabetică. Căutarea utilizată este cea binară.

Tabelele dinamice organizate sub formă de liste au dezavantajul căutării liniare. Arborele de căutare reduce timpul de căutare. În cazul în care cheile sunt alfanumerice, comparaţiile sunt mari consumatoare de timp. Pentru astfel de situaţii, cele mai potrivite sunt tabelele de dispersie.

Funcţia de dispersie ( hashing )

Funcţia de dispersie este funcţia care transformă o cheie într-un număr natural numit cod de dispersie:

f: K -> H

unde K este mulţimea cheilor, iar H este o mulţime de numere naturale.

Funcţia f nu este injectivă Două chei pentru care f(k1)=f(k2) se spune că intră în coliziune, iar înregistrările respective se numesc sinonime.

Asupra lui f se pun două condiţii:

- valoarea ei pentru un k K să rezulte cât mai simplu şi rapid;

- să minimizeze numărul de coliziuni.

Un exemplu de funcţie de dispersie este următoarea:

f(k)=(k) mod M

unde (k) este o funcţie care transformă cheia într-un număr natural, iar M este un număr

natural recomandat a fi prim.

Funcţia (k) se alege în funcţie de natura cheilor. Dacă ele sunt numerice, atunci (k)=k. În cazul cheilor alfanumerice, cea mai simplă funcţie (k) este suma codurilor ASCII ale caracterelor din componenţa lor; ca urmare funcţia f de calcul a dispersiei este următoarea:

#define M

int f(char *key)

{

int i,suma;

suma=0;

for(i=0;i<length(key);i++)

suma=suma+*(key+i);

return suma%M;

}

Tabela de dispersie