Wprowadzenie

Zasadniczym tematem zajęć jest doskonalenie umiejętności operowania na jednowymiarowych tablicach dynamicznych (oraz używaniu ich jako parametrów funkcji).

Tematyka zadań nawiązuje do wcześniej rozpatrywanego problemu wyszukiwania binarnego. Tym razem program jest znacznie bardziej rozbudowany (wychodząc z założenia, że wszyscy ogarnęli problem odpowiedzi na pytanie Gdzie należy wstawić szukaną wartość, gdy program nie znajduje jej w tablicy?).

Wyszukiwaniu binarnemu poświęciłem sporo miejsca:

1. Laboratorium 5: Tablice. Wyszukiwanie binarne
2. Laboratorium 5a: Wyszukiwanie binarne — doskonalenie aplikacji
3. Tablice w czasach zarazy
4. Wyszukiwanie binarne dla bystrzaków

więc nie ma chyba sensu do problemu wracać ponownie.

Wyszukiwanie binarne z wstawianiem

Natomiast omówienia wymaga nowe postawienie zadania:

1. Program będzie czytał¹ kolejne wyszukiwane wartości z klawiatury.
2. Program startuje z pustą tablicą (która będzie rozszerzana dynamicznie):
   
   int * dane; int N = 0;

   1 2	int * dane; int N = 0;

3. Po przeczytaniu pierwszej wartości (x) program wykona następujące czynności:
   
   dane = malloc(1 * sizeof(int)) dane[N] = x; N++;

   1 2 3

   dane = malloc(1 * sizeof(int)) dane[N] = x; N++;

   
   Teraz tablica ma 1 element.
4. Dla każdej kolejnej czytanej wartości, program sprawdza, czy znajduje się ona w tablicy:
   • jeżeli tak — nie robi nic, przechodzi do czytania kolejnej wartości;
   • jeżeli nie — zwiększa długość tablicy o 1
     
     dane = realloc((N + 1) * sizeof(int));

     1	dane = realloc((N + 1) * sizeof(int));

   • przestawia tak elementy tablicy żeby na odpowiedniej pozycji pojawiło się miejsce na nowy element;
   • wstawia tam x i zwiększa N o jeden
5. Po każdym dodaniu, dla kontroli, program drukuje aktualną zawartość tablicy.

Proponuję następujący podział programu na funkcje:

1. Wyszukiwanie binarne.
2. Drukowanie tablicy.
3. Dodawanie elementu do tablicy (parametrami funkcji powinna być wstawiana wartość x, numer miejsca, na którym ma być wstawiona: 0 — na początku, N na końcu, rozmiar tablicy, tablica (adres jej początku))².

Parę wyjaśnień

Funkcja malloc() oraz spokrewnione z nią calloc(), realloc(), reallocarray() oraz free() służą do zarządzania pamięcią dostępną dla programu. Żeby z nich korzystać należy dołączyć do programu plik stdlib.h używając polecenia

Funkcja ta zwraca się do Systemu Operacyjnego z prośbą o przydział pamięci. Jej argument to liczba bajtów przydzielanej pamięci. Zwracam uwagę, że we współczesnych komputerach największa liczba całkowita 32-bitowa to 2147483647 (czyli 2 G); biorąc pod uwagę, że każda zmienna typu int zajmuje 4 bajty to tablica może mieć co najwyżej 536870912, sporo, ale komputer może mieć znacznie więcej niż 2 G bajtów pamięci. Z tego względu argument funkcji malloc() jest specjalnego typu size_t. W pewnym uproszczeniu jest to typ całkowity, bez znaku, zapisywany na 8 bitach. Trzeba o tym pamiętać gdy potrzebujemy baaardzo dużo pamięci.

Pamięć przydzielane z użyciem tej funkcji nie jest w żaden sposób kasowana — otrzymamy obszar o niezdefiniowanej, „przypadkowej” zawartości.

Gdy pamięć nie może być przydzielona funkcja zwraca wartość NULL (zero).

Zatem zamiast używać polecenia:

używać możemy:

Funkcja ta ma dwa argumenty (typu size_t): nmemb i size. Służy do przydzielenia wyzerowanego obszaru pamięci dla tablicy o nmemb elementach, zakładając, że każdy element zajmuje size bajtów.

Jeżeli chcemy stworzyć tablicę T typu double, o 1000 elementach powinniśmy użyć polecenia następującego:

(pierwsza wartość jest typu int ale zostanie automatycznie skonwertowana do typu size_t).

Gdy pamięć nie może być przydzielona funkcja zwraca wartość NULL (zero).

Zatem zamiast używać polecenia:

możemy napisać:

Funkcja ta, o dwu parametrach:

• pierwszy to, adres początku tablicy utworzonej za pomocą malloc(),
• drugi to nowy rozmiar pamięci (w bajtach)

zmienia przydział pamięci powiększając lub zmniejszając obszar tablicy. Dotychczasowa zawartość obszaru pamięci pozostanie niezmieniona, gdy tablica jest rozszerzana, dodawana pamięci nie będzie zmieniana w żaden sposób (czyli pojawią się tam jakieś „śmieci”). Funkcja zwraca adres obszaru pamięci o nowym rozmiarze lub wartość NULL gdy nie może zadania wykonać. Trzeba o tym pamiętać podczas zwiększania rozmiaru tablicy:

gdy żądanie nie będzie mogło być zrealizowane, T przyjmie wartość zero i stracimy dostęp do poprzedniej wartości tablicy T. Czyli powinno to być raczej robione inaczej

Funkcja ta to odpowiednik funkcji realloc() ale operujący liczbą (i wielkością) elementów tablicy, podobnie jak funkcja calloc(). Jej parametry to:

• dotychczasowy adres tablicy,
• nowa liczba elementów tablicy,
• wielkość jednego elementu w bajtach.

Mają zastosowanie wszystkie uwagi dotyczące funkcji realloc()

Funkcja ta zwalnia obszar pamięci przydzielony za pomocą malloc(). Jej argumentem jest wskaźnik (adres) używanej tablicy. Używając tej funkcji nie można zwolnić pamięci uzyskanej za pomocą „normalnej“ deklaracji zmiennej.

Funkcja nie zwraca żadnej wartości

Wszystkie funkcje zwracające wskaźnik zwracają wskaźnik bez określonego typu (void ). Podczas podstawienia dokonywane jest odpowiednie rzutowanie.

Wersja PDF tego dokumentu…

…pod adresem.

Wersja: data ostatniej modyfikacji

---

1. Tak. Tym razem czytamy kolejne wartości z klawiatury!↩
2. Przed wywołaniem tej funkcji tablica musi być już powiększona.↩