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.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



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

©2017 mgr Jerzy Wałaszek

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