Wskaźniki, tablice, funkcje…

 

Wstęp

Wskaźniki są wredne. Wierzcie mi.

Oto prototyp prostej funkcji:

 

Co można o niej powiedzieć?

  • zwraca wartości całkowite;
  • ma dwa parametry:
    • pierwszy to wyrażenie całkowite,
    • drugi to wskaźnik na int.

Natomiast można sobie wyobrazić dwie zupełnie różne realizacje funkcji zgodne z tym prototypem:

Funkcja operująca na tablicy

Bardzo prosta funkcja, wyliczająca sumę wszystkich elementów n-elementowej tablicy całkowitej. Dla przypomnienia suma += t[i]; jest równoważne suma = suma + t[i];.

Użycie funkcji

 

Funkcja zwracająca dwie wartości

Jak wiadomo, polecenie return może być użyte do „wyprowadzenia” z wnętrza funkcji jedynie wartości jednej zmiennej.

Powyższy program to realizacja interesującego zagadnienia zwanego problemem Collatza. Był on omawiany przeze mnie na zajęciach z Technologii informacyjnych (ósmy zestaw slajdów: Zapis algorytmów (Algorytmy, Część II)). Program poprawnie działa tylko dla wartości x dodatnich i zwraca wartość 0 (fałsz) gdy x jest niedodatnie; 1 gdy argument jest poprawny. Drugi argument to liczba iteracji, którą trzeba wykonać aby program się zakończył.

Użycie funkcji

(Tak na marginesie: trzeba było 249 iteracji…)

Podsumowanie

Celem tych przykładów było uświadomienie, że wskaźnik może być użyty do przekazania adresu tablicy albo jakiejś zwykłej zmiennej: wskaźnik jest taki sam, ale jego sens i użycie zupełnie inne.

Tablice wielowymiarowe

Język C pozwala na deklarowanie tablic wielowymiarowych:

Tablica (dwuwymiarowa) T ma 10 wierszy i 20 kolumn.

Podobnie zadeklarujemy tablicę trójwymiarową:

 

Przekazanie tablicy do funkcji

Tablica jednowymiarowa

Możemy również zorganizować to inaczej:

 

Wywołując funkcję wpisujemy nazwę tablicy, czyli adres jej początku.

Zapis int [] jest poprawny, sugeruje, że drugim parametrem funkcji jest tablica czyli wskaźnik…

Ostatecznie mamy następujące możliwości zadeklarowania funkcji mającej tablicę jako jeden z parametrów:

  1. int funkcja(int n, int t[n])
  2. int funkcja(int n, int t[ ])
  3. int funkcja(int n, int * t)

Tablica wielowymiarowa

Skupimy się na dwu wymiarach. Pamiętamy cały czas, że

Najprawdopodobniej powinna zadziałać taka konstrukcja:

 

Trzecim jej argumentem jest tablica Tm wierszach i n kolumnach. Do funkcji musimy przekazać informację o rozmiarach tablicy.

W (opisanym wcześniej) przypadku tablic jednowymiarowych mieliśmy dwa równoważne (niewskaźnikowe) zapisy int t[n]int t[ ]. Czy coś takiego jest możliwe w przypadku tablic dwuwymiarowych? I tak i nie. Pominięcie rozmiaru tablicy w przypadku tablic jednowymiarowych nie jest problemem — język C nie sprawdza czy granice tablicy nie zostały przekroczone. Wystarczy znajomość początku (i zaufanie do programisty, że granic tablicy nie przekroczy).

W przypadku tablicy dwuwymiarowej, organizacja dostępu do poszczególnych elementów tablicy wymaga znajomości długości wiersza, bo miejsce elementu w pamięci można wyliczyć tylko gdy zna się długość wiersza. Tablica (4 wiersze, 4 kolumny) o następujących wartościach:

  0 1 2 3
0 00 01 02 03
1 10 11 12 13
2 20 21 22 23
3 30 31 32 33

zapisana będzie w pamięci tak:

0 1 2 3 4 5 6 7 8 9 10 15
00 01 02 03 10 11 12 13 20 21 22 33

Zatem, jedynie dopuszczalna, deklaracja tablicy dwuwymiarowej będącej parametrem funkcji wygląda tak:

(możemy pominąć jedynie pierwszy wymiar).

Skrajnie uproszczony prototyp będzie wyglądał tak:

Należy podać liczbę kolumn. Można to zrobić też tak:

(Jeżeli chcemy, żeby liczba kolumn mogła być zmienną — należy wcześniej tę zmienną zadeklarować…)

Przeglądając Internet można znaleźć różne porady jak zadeklarować tablicę dwuwymiarową. Pewna ich część sugeruje, żeby samemu zorganizować obsługę tablicy dwuwymiarowej używając jednowymiarowej i (niezbyt skomplikowanych, ale jednak) dodatkowych przeliczeń na indeksach.

Aby skorzystać z funkcji Funkcja() program może wyglądać tak:

 

Wywołując funkcję wpisujemy jedynie nazwę tablicy, czyli do funkcji przekazujemy adres jej początku.

Dynamiczna alokacja pamięci

Tablica jednowymiarowa

Jak wszyscy wiedzą, na potrzeby organizacji tablic, istnieje możliwość przydziału pamięci „od systemu operacyjnego”. Działą to jakoś tak:

 

Deklarujemy zmienną T typu wskaźnik na int. Funkcja malloc() przydziela 20 bajtów z zasobów pamięci operacyjnej komputera (czyli tworzymy tablicę o 50 elementach, gdyż każdy element tablicy int to 4 bajty.)

Później z tablicy korzystamy „w sposób normalny”.

Czyli gdy chcemy zadeklarować tablicę o N elementach, bardziej kompletny program będzie wyglądał tak:

Sprawdzenie czy przypadkiem T nie jest równe NULL (wskaźnik o wartości zero) ma nas ochronić przed sytuacją, w której system operacyjny nie mógł przydzielić pamięci. Funkcja malloc() informuje nas o tym zwracając wartość zero.

Tablica dwuwymiarowa

Można podobnie również w przypadku tablicy dwuwymiarowej. Ale wróćmy najpierw do „klasycznej” definicji. Co znaczy int t[20]? rezerwujemy obszar pamięci do przechowania 20 wartości int

Co zatem znaczy int T[20][30]? Czy można temu nadać taką interpretację, że deklarujemy najpierw tablicę o 20 elementach przechowującą informacje o adresach początków dwudziestu, trzydziesto-elementowych tablic jednowymiarowych?

Tym w istocie jest tablica dwuwymiarowa: każdy jej wiersz to tablica jednowymarowa…

Czy zatem można odpytać o adres drugiego wiersza tablicy?

  1. Deklaruję tablicę
  2. Drukuję wartość T[2] dokonując konwersji (rzutowania) na long int. (Adresy w komputerze są liczbami 64. bitowymi).
  3. Drukuję tę wartość jako wskaźnik (%p).

Wynik programu wygląda jakoś tak:

(Każde uruchomienie generuje inne wartości. Pierwsza liczba to wartosć adresu zapisana dziesiętnie, druga szesnastkowo.)

Czy zatem można zmajstrować sobie tablicę dwuwymiarową korzystając z funkcji malloc()?

Najpierw musimy zmajstrować jednowymiarową tablicę wskaźników (o dwudziestu elementach1)

(tablica ma dwadzieścia elementów ([20]), a jej wartościami są wskaźniki na int (int *)).

Teraz musimy poprosić system operacyjny, aby utworzy dla nas dwadzieścia tablic jednowymiarowych, po trzydzieści elementów; ich adresy wpiszemy do kolejnych komórek T:

Teraz trudne pytanie pomocnicze o typ wskaźnika wskazującego na tablicę wskaźników?

Gdy tablica jest typu int to jest łatwo: int *. Teraz tablica jest typu int * zatem wskaźnik na jej początek to int **.

Czyli jeżeli dodatkowo zadeklarujemy:

to będziemy mogli napisać

 

czyli do Tprim wstawić adres początku T i powinno być, tak, że Tprim[i] == T[i].

Jeżeli pójdziemy krok dalej i użyjemy funkcji malloc() do stworzenie dwudziestoelementowej tablicy T, to dostaniemy gotowca do deklaracji tablic dwuwymairowych:

Dodatkowo po każdym użyciu funkcji malloc sprawdzić trzeba czy nie zwróciła on a wartości zero! Gdy tak się zdarzy — program nie może być kontynuowany.

Tablica dwuwymiarowa i funkcja

Używając tak utworzonej tablicy w funkcji musimy zadbać o to żeby była zgodność typów parametrów w definicji funkcji i wywołaniu funkcji.

W funkcji o prototypie

trzeci parametr jest typu int (*)[30] stworzona powyższą metodą tablica/wskaźnik T jest typu int **. Jedno nie pasuje do drugiego. Dobra wiadomość jest taka, że można sobie zmajstrować taką funkcję:

i wszystko powinno być ok.

Zła wiadomość jest taka, że trzeba się zdecydować na jeden sposób deklaracji tablic wielowymiarowych:

  • albo automatyczny (int T[20][30]) ,
  • albo dynamiczny (znacznie dłuższy i bardziej zagmatwany).

Zaleta dynamicznego deklarowania pamięci

Wyobraźmy sobie taki prosty bardzo program:

Nie robi on nic specjalnego tylko w każdym obrocie pętli deklaruje coraz to większą tablicę i nadaje jej ostatniemu elementowi wartość zero.

Uruchomienie tego programu kończy się tak:

Jak widać największa tablica, którą udało się zadeklarować miała 524288 elementów. Całkiem to sporo, ale…

Gdy nasz program będzie wyglądał tak:

 

to znaczy za każdym razem tablica deklarowana jest dynamicznie, a następnie pamięć jest zwalniana, program kończy się tak:

Zadeklarowana tabela może być znaaaaacznie dłuższa.

Zadanie na ten tydzień

Zadanie na ten tydzień jest dosyć proste: macie Państwo stworzyć program, który:

  1. Tworzy tablicę dwuwymiarowa o zadanej liczbie kolumn i wierszy;
  2. Wypełnia ją danymi (odradzam wczytywanie — będzie to męczące; już lepiej wypełniać ją automatycznie)
  3. Program uzupełniają trzy funkcje:
    1. wyliczająca średnią z całej tablicy,
    2. wyliczająca średnią z zadanego wiersza,
    3. wyliczająca średnią z zadanej kolumny.
  4. Program powinien też wydrukować tablicę wejściową oraz wyniki. Te wydruki są po to, żeby można było sprawdzić działanie…

Podstawą jest instrukcja laboratoryjne numer 9: Tablice i funkcje.

Tekst w postaci pliku PDF…

jest również dostępny.


  1. Konsekwentnie nawiązuję do przykładu