Algoritmy pre rozptyľové tabuľky so zreťazeným rozptyľovaním
|
|
Vyhľadávanie pri metóde separate chaining
|
Popis |
|
Pri tejto metóde riešenia kolízií sa pre každú položku tabuľky vytvára samostatný zoznam prvkov a prvky sú ukladané mimo priestor tabuľky. Ak rozptylová funkcia priradí rovnakú adresu uloženia v tabuľke dvom prvkom, oba prvky budú uložené do samostatných záznamov a zreťazené v zozname. Položka v tabuľke bude potom obsahovať ukazovateľ na začiatok tohto zoznamu. Pri vkladaní ďalších prvkov sa vždy vytvorí nový záznam a ten sa zapojí do odpovedajúceho zoznamu. Podľa implementácie to môže byť na začiatok alebo na koniec zoznamu, vždy však do priestoru mimo rozptylovú tabuľku.
|
Vstupy algoritmu |
|
Vstupmi sú vyhľadávaná hodnota a rozptylová tabuľka s určeným počtom riadkov.
|
Princíp činnosti |
|
Pri vyhľadávaní sa prechádza zreťazený zoznam odpovedajúci položke, v ktorej by mal byť umiestnený hľadaný prvok. Vyhľadávanie v zreťazených zoznamoch bolo popísané v kapitole 2. Bližšie o metóde separate chaining sa môžeme dozvedieť v [3] alebo [4].
|
Výstupy algoritmu |
|
Ak v prislúchajúcom zreťazenom zozname nájdeme hľadanú hodnotu, výstupom je ukazovateľ na tento záznam. Ak vypočítanému riadku nie je zatiaľ priradený žiaden zoznam alebo sa v odpovedajúcom zozname nenachádza zadaná hodnota, výstupom je nulový ukazovateľ.
|
Vývojový diagram |
 |
Implementácia |
| |
//najdenie zadanej hodnoty "hodnota" v rozptylovej tabulky "tabulka"
//s poctom riadkov "p_riadkov" so zretazenym rozptylovanim metodou separate chaining
//funkcia vracia index polozky do ktorej bola hodnota vlozena
CZaznam_JZ* najdi_ZR_SCH(CRiadok_ZR_SCH* tabulka, int p_riadkov, int hodnota) {
int riadok = hodnota % p_riadkov;
if (tabulka[riadok].nasl_z()==0) {
return 0;
}
else {
CZaznam_JZ* aktualny=tabulka[riadok].nasl_z();
if (aktualny->hodnota()==hodnota) return aktualny;
while (aktualny->dalsi()!=0) {
aktualny=aktualny->dalsi();
if (aktualny->hodnota()==hodnota) return aktualny;
}
}
return 0;
} |
| Ďalšie implementácie |
Vizualizácie |
| Príklad úspechu |
|
| Príklad neúspechu |
|
