Algoritmy pre rozptyľové tabuľky so zreťazeným rozptyľovaním
|
|
Vyhľadávanie pri metóde coalesced chaining
|
Popis |
|
Pri tejto metóde je vkladaný prvok vždy vkladaný do tabuľky. Ak ale nemôže byť vložený do položky, ktorú mu priradila rozptylová funkcia, sleduje algoritmus zreťazenie prvkov začínajúce v prislúchajúcej položke a až sa dostane na koniec zreťazenia, nájde voľné miesto v tabuľke do ktorého prvok vloží a do poslednej položky zreťazenia zapíše miesto, kde bol tento prvok vložený. Potom si ešte na miesto, ktoré je určené pre index nasledujúceho prvku poznačí, že vkladaný prvok je posledným v zreťazení.
|
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í algoritmus skontroluje vypočítanú pozíciu, kde by sa mal prvok nachádzať. Ak tam uložený prvok nie je, sleduje vzniknutú reťaz podľa zapísaných indexov nasledujúceho prvku. Ak pri prehľadávaní nenájde hľadaný prvok a index nasledujúceho prvku indikuje koniec zreťazenia prvkov, potom sa prvok v tabuľke nenachádza. Ak pri prehľadávaní reťaze prvkov nájde hľadaný prvok, algoritmus sa končí úspechom. Bližšie o metóde coalesced chaining sa môžeme dozvedieť v [4].
|
Výstupy algoritmu |
|
Výstupom je číslo riadku, v ktorom sa nachádzala hľadaná hodnota. Ak sa hľadaná hodnota v tabuľke nenachádzala, výstupom môže byť napríklad číslo -1 (riadok s poradovým číslom -1 sa v tabuľke určite nenachádza).
|
Vývojový diagram |
 |
Implementácia |
| |
//najdenie zadanej hodnoty "hodnota" v rozptylovej tabulke "tabulka"
//s poctom riadkov "p_riadkov" so zretazenym rozptylovanim metodou coalesced chaining
//funkcia vracia index polozky v ktorej bola hodnota najdena (v pripade neuspechu vracia -1)
int najdi_ZR_CCH(CRiadok_ZR_CCH* tabulka, int p_riadkov, int hodnota) {
int riadok = hodnota % p_riadkov;
if (tabulka[riadok].prazdna()) return -1;
else if (tabulka[riadok].hodnota()==hodnota) return riadok;
while ((riadok = tabulka[riadok].nasl_p())!=-1) {
if (tabulka[riadok].hodnota()==hodnota) return riadok;
}
return -1;
} |
| Ďalšie implementácie |
Vizualizácie |
| Príklad úspechu |
|
| Príklad neúspechu |
|
