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
|
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.
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
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 |
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