1 Wprowadzenie
Jak się wydaje większość stworzonych 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.
2 Zadania do wykonania
-
Wydzielenie algorytmu wyszukiwania binarnego jako osobnej funkcji, o przykładowym wywołaniu:
1int bin_szuk(int X, int N, int dane[N]);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 − 2 a N − 1,
- na miejscu N (po N − 1).
-
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 T i T1 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:
123456789101112#include <stdlib.h>...int * T; // To jest nasza tablicaint N; // W N jest rozmiar tablicy...T = malloc(N * sizeof(int)); // Prosba o przydzial pamieciif (T == 0) // Gdy pamiec nie może byc przydzielona// funkcja zwróci wartosc 0{printf("Brak␣pamieci!\n");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ą!
Gdy trzeba rozmiar tablicy zwiększyć używamy funkicji realloc. Używamy jej tak:
123456789101112131415int * T1; // To bedzie ,,nowa’’ tablica...T1 = realloc(T, (N + 1) * sizeof(int))// T to ,,stara.. tablica, a N + 1 to potrzebny rozmiar ,,nowej’’if (T1 == 0)// Oznacza to, ze ne udalo sie zwiekszyc rozmiaru tablicy{printf("Brak␣pamieci!\nEmergency␣exit");return -1;}else{T = T1;}...Używamy dodatkowej zmiennej T1 żeby w sytuacji, kiedy nie uda się przydzielić pamięci (realloc() zwraca zero!) nie stracić danych!
-
3 Wersja PDF tego dokumentu…
Wersja: 50 z drobnymi modyfikacjami! data ostatniej modyfikacji 2016-05-07 09:02:46 +0200