Laboratorium 5a: Wyszukiwanie binarne — doskonalenie aplikacji

W zależności od tego co zostało już zrobione „doskonalenie” polegać będzie na wykonywaniu czynności z listy w punkcie 2. Zrobić należy tyle na ile starczy sił i/lub umiejętności!

1. Wprowadzenie

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

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.
Usunięcia wszystkich wydruków poza pętle. W tej chwili część przedstawionych programów drukuje sprzeczne informacje (lub nie drukuje nic).
Ewentualnie doprowadzenie do sytuacji, w której do „algorytmu” wyszukiwania jest tylko jedno wejście i jedno wyjście.
Próba uwzględnienia przekazanych uwag

Otworzyłem dostęp do złożonych prac.

Istotna uwaga

Ponieważ w najbliższy piątek od godziny 9 ogłoszono godziny dziekańskie, dla jednej z moich grup zajęcia nie odbędą się,

Zgodnie z wszelkimi znakami na niebie i ziemi nie oznacza to, że godziny dziekańskie zwalniają z obowiązku przerabiania zaplanowanego materiału. Ci studenci, będą musieli zadanie wykonać samodzielnie, w domu.

Oczywiście jestem dostępny na konsultacjach czy stacjonarnych czy on-line po ustaleniu terminu via e-mail.

Aby wyrównać sytuację pozostali studenci wykonują pracę z minimalnym moim udziałem w trakcie zajęć.

2. Zadania do wykonania

W zależności od tego co zostało dotychczas przedstawione należy

Zastąpić wszystkie instrukcje goto poleceniami strukturalnymi do tworzenia pętli (do, while¹)
Przeniesienie algorytmu wyszukiwania binarnego do funkcji
- w pierwszym etapie funkcja ma zwracać informację na którym miejscu w tablicy znaleziono szukaną wartość lub o tym, że wartości nie znaleziono.
- w drugim etapie należy tak przetworzyć algorytm, żeby funkcja zwracała informację na którym miejscu znajduje się znaleziona liczba; gdy liczba nie może być znaleziona — funkcja ma podpowiedzieć, gdzie ją wstawić.
  I to jest absolutne minimum, do którego należy dążyć!
Gdy program wie na którym miejscu wartość trzeba wstawić powinien wstawić szukaną wartość do tablicy i wypisać zmodyfikowaną tablicę.

W zależności od tego co zostało już zrobione „doskonalenie” polegać będzie na wykonywaniu czynności z powyższej listy. Zrobić należy tyle na ile starczy sił i/lub umiejętności!

3. Podpowiedzi

3.1 `goto` i pętle

Konstrukcja programistyczna

poczatek:
    if (costam)
    {
        goto koniec;
    }
    ...
    ...
    goto poczatek;
koniec:
    ...

może być zastąpiona

while(!costam)
{
    ...
    ...
}

Uwaga: !costam oznacza negację warunku oznaczonego jako costam

3.2 Przeniesienie algorytmu do funkcji…

…opisane zostało na przykładzie algorytmu połowienia.

3.3 Jak funkcja ma poinformować o tym gdzie w tablicy powinna znaleźć się szukana wartość?

Najłatwiej poinformować gdzie wartość znaleziono używając polecenie

return C;

(zmienna C przyjmuje wartości od 0 do N-1)

lub o tym, że nie znaleziono

return -1;

Zwrócenie informacji o tym w którym miejscu uzupełnić tablicę o nieznalezioną, szukaną wartość trzeba jakoś zakodować wskazując na przedział gdzie powinna się znaleźć. Możliwe sytuacje są następujące:

przed zerowym elementem
między zerowym, a pierwszym,
między pierwszym, a drugim,
…
między $N - 2$ a $N - 1$ ,
na miejscu $N$ (po $N - 1$ ).

Zwracane przez funkcję wartości nieujemne (zero i dodatnie) zarezerwowane są do informowania na którym miejscu wartość znaleziono

Do dyspozycji zostają nam liczby ujemne:

$- 1$ — przed zerowym² elementem‚
$- 2$ — przed pierwszym elementem‚
$- 3$ — przed drugim elementem‚

i tak dalej.

3.4 Jak znaleźć miejsce w którym trzeba wstawić wartość?

Tu trzeba troszkę pokombinować. Moja podpowiedź jest następująca:

Na samym początku pętli trzeba dodać polecenie drukujące informacje o początku i końcu przedaiłu

printf("A = %d B = %d\n", A, B)

I zobaczyć jakie będą drukowane wartości podczas poszukiwania wartości nie występujących w tablicy na końcu przebiegu, czyli szukając

wartości mniejszej niż najmniejszy element tablicy
wartości, która powinna znaleźć się między pierwszym, a drugim³,
…
wartości większej niż największy element tablicy.

Uwierzcie mi — da się wyciągnąć sensowne wnioski.

3.5 Jak „rozszerzyć” tablicę?

Można to zrobić na dwa sposoby: elementarny i bardziej zaawansowany 😄

3.5.1 Sposób elementarny

Deklarujemy dwie tablice:

pierwszą, D o rozmiarze N zawierającą szukane dane

int D[] = {1, 5, 7, 12, …};
N = sizeof(D) / sizeof(int);

i drugą D1 o rozmiarze N + 1

int D1[N + 1];

Pierwsza zawiera dane wejściowe programu, druga zawierać będzie dane po modyfikacji.

Modyfikacja polegać będzie na odpowiednim przepisaniu wszystkich danych z jednej tablicy do drugiej i uzupełnieniu tablicy o brakującą wartość.

Pamiętamy, żeby na koniec programu wydrukować obie tablice, żeby zobaczyć, czy rzeczywiście szukana wartość dopisana została we właściwym miejscu.

3.5.2 Sposób zaawansowany

Ten sposób wymaga skorzystania z funkcji malloc() i pamięci dynamicznej oraz wskaźników. Pozwala ona nie tylko na utworzenie tablicy, ale również zmianę jej rozmiaru podczas pracy programu.

Utworzenie tablicy i przydział miejsca w pamięci operacyjnej:
```
#include <stdlib.h>   // NIEZBĘDNE
int * D;   // to będzie adres początkowy naszej tablicy
int N;     // rozmiar tablicy
T = malloc(N * sizeof(int)); // prośba o przydział pamięci
if ( T == 0) // sprawdzenie czy pamięć przydzielono
{
    print("Brak pamięci!\n"); // komunikat o błędzie
    return -1;
}
```
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ą!
Rozszerzenie tablicy.
Gdy okaże się, że szukanej danej nie ma w tablicy trzeba ją dopisać. Aby daną dopisać do tablicy trzeba ją rozszerzyć. Służy do tego funkcja realloc():
```
int * D1;  // tymczasowy adres rozszerzonej tablicy
D1 = realloc(D, (N + 1) * sizeof(int));
// D to "stara" tablica
// N + 1 to rozmiar nowej tablicy (wiiększy o  jeden od starej)
if (D1 == 0)
{
    printf("Brak pamięci!\n");
    return -1;
}
else
{
    D = D1;
}
```
funkcja realloc() zadba o to, aby wszystkie „stare” dane znalazły się w „nowej” tablicy; natomiast w przypadku gdyby się okazało, że pamięć nie może być przydzielona — funkcja realloc() zwraca zero i żeby nie stracić dostępu do dotychczasowych danych —adres nowej tablicy wpisujemy do D1, a gdy upewnimy się, że nie jest on równy zeru — przepisujemy do D.

3.6 Przepisywanie wartości tablic

Algorytm nie jest specjalnie skomplikowany, niech sytuacja wygląda tak jak na poniższym rysunku

Zaczynamy od końca i przebiegamy tablicę D1 o elementach 0, 1, …, N-1, N.
Ostatni (o numerze N - 1) i większy od wstawianego/szukanego (X) element tablicy D przepisujemy do tablicy D1 na pozycję o jeden większą (N).
Postępujemy tak ze wszystkimi większymi od X elementami tablicy D.
gdy dotrzemy do pierwszego elementu mniejszego od X na odpowiednie miejsce tablicy D1 wstawiamy X
Kolejne elementy tablicy D przepisujemy bez zmian do D1.

W przypadku tablic dynamicznych sytuacja jest nieco prostsza:

również zaczynamy od tyłu
wszystkie większe od X elementy tablicy przesuwamy w prawo o jedną pozycję
gdy dojdziemy do pierwszego mniejszego elementu wstawiamy X na odpowiednie miejsce

(W idealnym przypadku) Algorytm przepisywania tablic powinien być zrealizowany jako funkcja!

4. Idealny program

Dla bardzo zaawansowanych; wymaga użycia malloc() i realloc().

Po każdym dodaniu wartości do tablicy drukujemy ją (kolejna funkcja!).

4.1 Koniec pętli

Można się umówić, że wprowadzenie jakiejś magicznej wartości (-1 albo 0) kończy pętlenie się.

4.2 Wczytywanie X

O tym niby nie było, ale i tak wielu z Państwa z tego korzysta.

Aby przeczytać wartość int do zmiennej X używamy polecenia

scanf("%d", &X);

Teoretycznie można użyć również pętli for (pamiętając że jest to jakaś dziwna wersja while.) ↩︎
Tu wyraźnie przydaje się numeracja elementów tablicy od zera! ↩︎
Pamiętamy, żeby pomiędzy elementami tablicy było wolne miejsce. ↩︎