Tabele de dispersie

Tabele de dispersie

• Tabelele de dispersie au ca structuri de baza tablourile.
• Domeniul de valori ale cheilor este, de regula, mai mare decat dimensiunea tabelei.
• Valoarea unei chei este asociata unui indice din tablou, utilizand o functie de dispersie.
• Elementele asociate unei celule deja ocupate pot fi plasate in alte celule din tabela (metoda sondajului liniar, metoda dublei dispersii, etc) sau fiecare celula din tabela poate fi o lista inlantuita, iar elementele asociate acelei celule sa fie inserate in acea lista (metoda inlantuirii separate).
• Metoda sondajului liniar

elementele asociate unei celule deja ocupate vor fi plasate in alte celule din tabela;

pasul de deplasare este 1 (daca i este indicele calculat de functia de dispersie, secventa de sondaj este i, i+1,i+2, etc.).

• Metoda dublei dispersii:

pasul de deplasare depinde de chei, fiind obtinut prin utilizarea unei functii secundare de dispersie;

daca functia secundara de dispersie intoarce valoarea s, atunci secventa de sondaj este x, x+s, x+2s, x+3s, etc., unde valoare s depinde de cheie, dar ramane constanta pe parcursul sondajului.

Metoda sondajului liniar.

import java.io.*;

import java.lang.*;

//tabele de dispersie cu sondaj liniar

class Element

}

class tabelHash

public void afisare()

System.out.println();

}

public int functieHash(int cheie)

public void adauga(Element elem)

Vhash[valoareHash]=elem; //adauga elem

}

public Element sterge(int cheie)

++valoareHash; //deplasare la celula urmatoare

valoareHash%=dim_vect; //reia de la inceput dc e cazul

}

return null;

}

public Element cauta(int cheie)

return null; //elementul nu este in tabela

}

}

class tabeleDispersieAplicatie1

// introducere integer

public static int getInt() throws IOException

public static void main(String[] args) throws IOException

System.out.println('1. Afisare');

System.out.println(' ');

System.out.println('2.Inserare');

System.out.println(' ');

System.out.println('3.Stergere ');

System.out.println(' ');

System.out.println('4.Cautare ');

System.out.println(' ');

System.out.println('5.Exit ');

System.out.println(' ');

boolean var=true;

int opt,valoare;

while(var)

}

}

}

Metoda dublei dispersii.

import java.io.*;

import java.lang.*;

//tabele de dispersie - metoda dispersiei duble

class Element

}

class tabelHash

public void afisare()

System.out.println();

}

public int functieHash1(int cheie)

public int functieHash2(int cheie)

public void adauga(Element elem)

Vhash[valoareHash]=elem; //adauga elem

}

public Element sterge(int cheie)

//deplasare la celula urmatoare, conform pasului de deplasare

valoareHash+=pas;

valoareHash%=dim_vect; //reia de la inceput dc e cazul

}

return null;

}

public Element cauta(int cheie)

return null; //elementul nu este in tabela

}

}

class tabeleDispersieAplicatie2

// introducere integer

public static int getInt() throws IOException

public static void main(String[] args) throws IOException

System.out.println('1. Afisare');

System.out.println(' ');

System.out.println('2.Inserare');

System.out.println(' ');

System.out.println('3.Stergere ');

System.out.println(' ');

System.out.println('4.Cautare ');

System.out.println(' ');

System.out.println('5.Exit ');

System.out.println(' ');

boolean var=true;

int opt,valoare;

while(var)

}

}

}

3. Metoda inlantuirii separate

import java.io.*;

import java.lang.*;

//tabele de dispersie cu inlantuire separata

import java.io.*;

class Legatura

//afisare informatii

public void afisareLegatura()

}

class CListaSortata

//intoarce true daca lista este vida

public boolean esteVida()

//inserare in ordine

public void adaugaLista(Legatura nou)

if(anterior==null)

primul=nou;

else

anterior.urmator=nou;

nou.urmator=curent;

}

//sterge element

public void stergeLista(int cheie)

if(anterior==null)

primul=primul.urmator;

else

anterior.urmator=curent.urmator;

//parcurgere lista si afisare elemente

public void afisareLista()

System.out.println(' ');

}

//cauta element cu o valoare data, partea intreaga

public Legatura cautaLista(int caut)

temp=temp.urmator;

}

return null;

}

}

class tabelHash

public void afisare()

}

public int functieHash(int cheie)

public void adauga(Legatura elem)

public void sterge(int cheie)

public Legatura cauta(int cheie)

}

class tabeleDispersieAplicatie3

// introducere integer

public static int getInt() throws IOException

public static void main(String[] args) throws IOException

System.out.println('1. Afisare');

System.out.println(' ');

System.out.println('2.Inserare');

System.out.println(' ');

System.out.println('3.Stergere ');

System.out.println(' ');

System.out.println('4.Cautare ');

System.out.println(' ');

System.out.println('5.Exit ');

System.out.println(' ');

boolean var=true;

int opt,valoare;

while(var)

}

}

}