ALG8

198 Rozdział 7. Algorytmy przeszukiwania

pod indeks ///, stwierdzimy, że już wcześniej ktoś się tam „zameldował”, wystarczy doczepić ,v na koniec listy, której głowa jest zapamiętana w T[mj.

Analogicznie działa poszukiwanie: szukamy elementu v i H(x) zwraca nam pewien indeks m. W przypadku, gdy T[mJ zawiera NULL, możemy być pewni, że szukanego elementu nie odnaleźliśmy - w odwrotnej sytuacji, aby się ostatecznie upewnić, wystarczy przeszukać listę TfmJ. (Warto przy okazji zauważyć, że listy będą na ogół bardzo krótkie).

Opisany powyżej sposób jest zilustrowany na rysunku 7-1.

Obrazuje on sytuację powstałą po sukcesywnym wstawianiu do tablicy Trekordów A, B. ( ', D, E, F i G, którym funkcja H przydzieliła adresy (indeksy): 7, 5, 2, 5, 3, I i 0. Indeksy tablicy, pod którymi nie ukrywają się żadne rekordy danych, są zainicjowane wartością NULL - patrz np. komórki 4 i 6. Na pozycji 7 marny do czynienia z konfliktem dostępu: rekordy A i F otrzymały ten sam adres! Odpowiednia funkcja wstaw (którą musimy przewidująco napisać!) wykrywa tę sytuację i wstawia element F na koniec listy T[1J.

Rys. 7- /.

Użycie list do obsługi konfliktów dostępu.

Obrazuje on sytuację powstałą po sukcesywnym wstawianiu do tablicy T rekordów A. B, C, D, E, F i G', którym funkcja 77 przydzieliła adresy (indeksy): 7, 3, 2. 5, 3, 1 i 0. Indeksy tablicy, pod którymi nic ukrywają się żadne rekordy danych, są zainicjowane wartością NULL - patrz np. komórki 4 i 6. Na pozycji 1 mamy do czynienia z konfliktem dostępu: rekordy A i 7*' otrzymały ten sam adres! Odpowiednia funkcja wstaw (którą musimy przewidująco napisać!) wykrywa tę sytuację i wstawia element F na koniec listy T[l].

Podobna sytuacja dotyczy rekordów B i E. Proces poszukiwania elementów jest zbliżony do ich wstawiania - Czytelnik nie powinien mieć trudności z dokładnym odtworzeniem sposobu przeszukiwania tablicy T w celu odpowiedzi na pytanie, czy został w niej zapamiętany dany rekord, np. E.

Wyszukiwarka

Podobne podstrony:
ALG8 88 Rozdział 4. Algorytmy sortowania Jest chyba dość oczywiste, że wywołania rekurencyjne zatrz
ALG8 158 Rozdział 5. Struktury{ if (p->t[rio_indeksu{słowo[i])]==NULL) test=0; // bidk odgałęzie
ALG0 190 Rozdział 7. Algorytmy przeszukiwania Odnalezienie liczby .1 w tablicy tub jest sygnalizowa
ALG2 192 Rozdział 7. Algorytmy przeszukiwani; gdy maksymalna ilość elementów należących do pewnej d
ALG4 194 Rozdział 7. Algorytmy przeszukiwania •    powinna być tatwo obliczalna, tak
ALG8 138 Rozdział 5. Struktury danych • „prawy” potomek /-tego węzła jest „schowany” pod indeksem 2
ALG8 48 Rozdział 2. Rekurencja W celu dokładniejszego przeanalizowania algorytmu posłużymy się kilk
ALG8 68 Rozdział 3. Analiza sprawności algorytmów3.6. Nowe zadanie: uprościć obliczenia! Nic sposób
ALG8 78___Rozdział 3 Analiza sprawności algorytmówZad. 3-4 Proszę rozwiązać następujące równanie
ALG6 Rozdział 7. Algorytmy przeszukiwania r > dzielenie modulo RmM: H(v) = v% Rmax Przykład: Dla
ALG 0 200 Rozdział 7. Algorytmy przeszukiwania Rekordy E i F zostały zapamiętane w momencie stwierdz
ALG 2 202 Rozdział 7. Algorytmy przeszukiwani! gdzie a jest współczynnikiem zapełnienia tablicy T. A
ALG 4 204 Rozdział 7. Algorytmy przeszukiwania i (gdzie a jest, tak jak poprzednio, współczynnikiem
ET8 198 Rozdział 11. Turystyka międzynarodowa turystycznych. Misją WTTC jest zwiększanie świadomośc
ALG
8 18 Rozdziali. Zanim wystartujemy dopóki a>0 wykonuj; podstaw za c resztę z dzielenia a prze
ALG6 86 Rozdział 4. Algorytmy sortowania zamiany sąsiadujących ze sobą elementów, a druga będzie wy
ALG 0 90 Rozdział 4. Algorytmy sortowania 90 Rozdział 4. Algorytmy sortowania Rys. 4 - 8. Sortowanie
ALG 8 98 Rozdział 5. Struktury danych W następnych paragrafach zostaną przedstawione wszystkie metod

więcej podobnych podstron