Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0
©2008 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0 |
©2008 mgr
Jerzy Wałaszek
|
Przedstawmy algorytm wyszukiwania liniowego w nieco inny sposób, który bardziej odpowiada jego realizacji w komputerze:
Dane wejściowe:
n - liczba elementów tablicy
T[] - tablica
v - poszukiwany element
Dane wyjściowe:
indeks elementu tablicy T[] zawierającego poszukiwany element v lub -1, jeśli elementu v nie znaleziono w tablicy.
Lista kroków:
K01: i ← 0
K02: Jeśli i ≥ n, to zakończ zwracając -1
K03: Jeśli T[i] = v, to zakończ zwracając i
K04: i ← i + 1
K05: Idź do K02
Zauważ, iż w każdym obiegu pętli przeszukującej algorytm wykonuje dwa porównania - w K02 oraz w K03. Pierwsze porównanie ma na celu sprawdzenie, czy indeks i wyszedł poza indeks ostatniego elementu w tablicy. Drugie porównanie sprawdza, czy element T[i] jest poszukiwanym elementem v. Otóż okazuje się, iż poprzez prostą modyfikację tablicy T[] możemy pozbyć się pierwszego porównania i w ten sposób przyspieszyć operację wyszukiwania. Zwróć uwagę, iż porównanie K02 staje się zbędne, jeśli poszukiwany element jest w zbiorze. Ma ono znaczenie tylko wtedy, gdy elementu v w zbiorze nie będzie.
Zatem wstawmy element v na koniec zbioru i usuńmy zbędne teraz porównanie K02. Musimy nieco zmodyfikować porównanie K03. Jeśli natrafimy na element v, to sprawdzamy w dalszej kolejności, czy leży on na pozycji mniejszej od n. Jeśli tak, to T[i] jest poszukiwanym elementem i kończymy zwracając jego pozycję. Jeśli pozycja elementu v wynosi n, to algorytm znalazł wstawiony przez nas element, zatem w zbiorze elementu v pierwotnie nie było - kończymy zwracając -1.
Wstawiony element nazywamy wartownikiem lub strażnikiem (ang. sentinel), a wyszukiwanie nosi nazwę wyszukiwania liniowego z wartownikiem (ang. sentinel linear search). Klasa złożoności algorytmu wciąż jest liniowa O(n), lecz wzrosła jego efektywność.
Dane wejściowe:
n - liczba elementów w tablicy
T[] - tablica n+1 elementowa
v - poszukiwany element
Dane wyjściowe:
indeks elementu tablicy T[] zawierającego poszukiwany element v lub -1, jeśli elementu v nie znaleziono w tablicy.
Lista kroków:
K01: T[n] ← v
K02: i ← 0
K03: Jeśli T[i] = v, to idź do K06
K04: i ← i + 1
K05: Idź do K03
K06: Jeśli i = n, to zakończ zwracając -1
K07: Zakończ zwracając i
Program:
Ćwiczenie na lekcji
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe