Laboratorium 5a: Wyszukiwanie binarne — doskonalenie aplikacji

 

1 Wprowadzenie

Jak się wydaje większość stworzonych aplikacji jest w miarę poprawna. To czego im zazwyczaj brakuje to:

  1. Dokładne przetestowanie. W szczególności sprawdzić należy:

    • tablice z danymi o długości 1 i 2 (warto też sprawdzić zachowanie algorytmu dla tablic o parzystej i nieparzystej liczbie danych),
    • sprawdzenie czy poprawnie znajdowane są pierwsza i ostatnia wartość z tablicy danych,
    • sprawdzenie czy poprawnie traktowane są szukane wartości mniejsze/większe od najmniejszej/największej wartości w tablicy.
  2. Usunięcia wszystkich wydruków poza pętle. W tej chwili część przedstawionych programów drukuje sprzeczne informacje (lub nie drukuje nic).
  3. Ewentualnie doprowadzenie do sytuacji, w której do „algorytmu” wyszukiwania jest tylko jedno wejście i jedno wyjście.

2 Zadania do wykonania

  1. Wydzielenie algorytmu wyszukiwania binarnego jako osobnej funkcji, o przykładowym wywołaniu:

    gdzie:

    • X — szukana wartość,
    • N — długość tablicy danych,
    • dane — tablica typu int zawierające uporządkowane dane.

    Funkcja zwraca wartości:

    • i ∈{0,1,…,N 1} — znaleziono wartość na pozycji i,
    • i < 0 — wartości nie znaleziono.

    Dodatkowo, zwracana wartość może zawierać zakodowaną informację gdzie należałoby wstawić wartość. Tu można zakodować numer przedziału, którym należy umieścić wartość:

    • przed zerowym elementem
    • między zerowym, a pierwszym,
    • między N 2N 1,
    • na miejscu N (po N 1).
  2. Kolejnym etapem jest taka modyfikacja funkcji, aby nieznalezioną wartość dopisywała do tabeli w takim miejscu aby dane ciągle były uporządkowane rosnąco (malejąco).

    Można to zrobić na dwa sposoby.

    • Oprócz tablicy z danymi (załóżmy, że nazywa się ona T i ma długość N deklarujemy tablicę T1 (tego samego typu co T) o długości N + 1.

      Tablice TT1 muszą być parametrami funkcji. Gdy wartość trzeba dodać przed wyjściem z funkcji dokonuje się odpowiedniego przepisania danych.

    • Drugi sposób jest nieco bardziej zagmatwany, ale ładniejszy. Skorzystamy z pamięci dynamicznej oraz funkcji malloc() oraz realloc().

      Funkcja malloc() wywoływana jest w sposób następujący:

      Funkcja zwraca adres (wskaźnik) początku obszaru pamięci przydzielonego tablicy z danymi. Użyjemy jej w funkcji main(). Niestety tablicom dynamiczny nie można nadawać początkowych wartości tak jak automatycznym. Nie jest to wielkim problemem, gdyż nasz program powinien teraz poradzić sobie z tablicą jednoelementową lub pustą!

      Gdy trzeba rozmiar tablicy zwiększyć używamy funkicji realloc. Używamy jej tak:

      Używamy dodatkowej zmiennej T1 żeby w sytuacji, kiedy nie uda się przydzielić pamięci (realloc() zwraca zero!) nie stracić danych!

szukanie_z_dodawaniem

3 Wersja PDF tego dokumentu…

pod adresem.

Wersja: 50 z drobnymi modyfikacjami! data ostatniej modyfikacji 2016-05-07 09:02:46 +0200