Wyszukiwanie liniowe

Jedną z podstawowych operacji na zbiorze danych jest wyszukiwanie (ang. searching). Zadanie to definiujemy następująco:

W zadanym zbiorze danych wyszukać element v i zwrócić jego pozycję. Jeśli elementu nie ma w zbiorze, zwrócić niemożliwą pozycję (np. dla tablicy może to być indeks -1).

Aby rozwiązać zadanie, postępujemy w sposób następujący:

Rozpoczynamy od pierwszego elementu i przechodzimy kolejno przez poszczególne elementy zbioru. Każdy przeglądany element sprawdzamy, czy jest elementem v. Jeśli tak, zwracamy jego pozycję w zbiorze (dla tablicy będzie to indeks przeglądanego elementu) i kończymy przeglądanie. Jeśli zostały przeglądnięte wszystkie elementy zbioru i nie znaleziono w nim elementu v, zwracamy pozycję niemożliwą.

Opisany powyżej algorytm wyszukiwania liniowego (ang. linear search algorithm) posiada klasę złożoności obliczeniowej O(n), gdzie n jest ilością elementów w przeszukiwanym zbiorze.

 

Algorytm wyszukiwania liniowego

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: Dla i = 0,1,...,n-1: Jeśli T[i] = v, to zakończ zwracając i
K02: Zakończ zwracając -1

Program:

Ćwiczenie na lekcji

 

Ćwiczenia

Zad.1

Zmodyfikuj podany powyżej algorytm wyszukiwania liniowego tak, aby znajdował w tablicy T[] wszystkie wystąpienia v. Na podstawie algorytmu napisz odpowiedni program.

Zad.2

Zmodyfikuj podany powyżej algorytm wyszukiwania liniowego tak, aby rozpoczynał wyszukiwanie od pozycji p. Na podstawie algorytmu napisz odpowiedni program.

Zad.3

Zmodyfikuj podany powyżej algorytm wyszukiwania liniowego tak, aby zliczał w tablicy T[] elementy v i na końcu podawał ich ilość. Na podstawie algorytmu napisz odpowiedni program.

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2018 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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