Języki programowania - ćwiczenia 2

Temat zajęć: Język C - funkcje, zmienne globalne, lokalne, statyczne, automatyczne, wskaźniki, tablice.

Materiały dodatkowe:

• Opis standardowej biblioteki C (wersja on-line)

 Zmienne globalne i lokalne, statyczne i automatyczne.

Zmienne globalne definiowane są poza ciałem jakiejkolwiek funkcji i widoczne są w obrębie całego modułu (w pewnych sytuacjach - poznamy je później - nawet w innych modułach) od miejsca ich definicji w dół kodu (dlatego zwykle są one definiowane na początku modułu). Zmienne lokalne definiowane są wewnątrz funkcji i ich widoczność ograniczona jest do konkretnej funkcji (tzn. inne funkcje nie mogą skorzystać z takich zmiennych). Jeśli zmienna lokalna ma taką samą nazwę, jak zmienna globalna, mamy do czynienia z przesłanianiem. W wyniku przesłonięcia zmiennej globalnej przez zmienną lokalną danej funkcji, w tej funkcji nie ma możliwości odwołania się do takiej zmiennej globalnej (każde użycie nazwy zmiennej zostanie przez kompilator przetworzone na odwołanie do zmiennej lokalnej). Między innymi z tego powodu lepiej jest unikać (tam, gdzie jest to możliwe) stosowania zmiennych globalnych na rzecz dodatkowych parametrów funkcji.

 Przykład 1

Projekt Visual Studio  pobierz
Plik globlok.c  pobierz

#include <stdio.h>

int zmienna=2; /* zmienna globalna */

void f(void)
{
  int zmienna=4; /* zmienna lokalna */
  printf("%d\n",zmienna);
  zmienna++;
}

int main()
{
  printf("%d\n",zmienna);
  f();
  printf("%d\n",zmienna);
  return 0;
}

Pojęcie zmiennych statycznych i automatycznych odnosi się do zmiennych lokalnych funkcji. Zmienne automatyczne (częściej stosowane) są tworzone (jest im przypisywane miejsce w pamięci) przy każdym uruchomieniu funkcji, w której są zdefiniowane, oraz niszczone przy wyjściu z tej funkcji. Dlatego mówi się, że "żyją" one co najwyżej tak długo, jak konkretne wykonanie funkcji, do której należą. Z kolei zmienne statyczne (ich definicja poprzedzona jest słowem kluczowym static) istnieją przez cały czas działania programu (podobnie jak zmienne globalne), dzięki czemu zachowują swoją wartość pomiędzy wywołaniami funkcji, do której należą.

 Przykład 2

Projekt Visual Studio  pobierz
Plik stataut.c  pobierz

#include <stdio.h>

void f(void)
{
    static int x = 0; /* zmienna statyczna */
    int y = 0;        /* zmienna automatyczna */
    x++;
    y++;
    printf("X=%d, Y=%d\n",x,y);
}

int main()
{
  f();
  f();
  f();
  return 0;
}

 Tablice

Deklaracja tablicy:

typ_elementów nazwa_zmiennej[rozmiar]

Elementy tablicy są zawsze indeksowane od 0 do rozmiar-1. Odwołanie do k-tego (w kolejności) elementu tablicy wygląda następująco:

• jako LVALUE: tab[k-1] = x;
• jako RVALUE: x = tab[k-1];

Deklaracja tablic wielowymiarowych:

typ_elementów nazwa_zmiennej[rozmiar1][rozmiar2]...;

Tablice wielowymiarowe są w istocie tablicami tablic. Jeśli dana jest definicja:

int tab[10][5];

to każdy element tab[i] (dla i=0,...,9) jest typu int[5], czyli jest 5-cio elementową tablicą liczb całkowitych. Możemy więc wyobrażać sobie tablice dwuwymiarowe typ[w][k] jako macierze o w wierszach i k kolumnach, przy czym podając tylko jeden indeks dla zmiennej tablicowej jako wynik otrzymujemy cały wiersz (proszę zauważyć, że przy takiej interpretacji nie ma prostej metody otrzymania całej kolumny).

 Zadanie 1

Napisz program zawierający funkcję sortującą zadaną tablicę liczb całkowitych. Można skorzystać np. z algorytmu sortowania bąbelkowego dla tablicy t, który wygląda następująco:

powtarzaj rozmiar(t) razy:
dla i=0,...,rozmiar(t)-2 jeśli t[i]>t[i+1] to zamień miejscami t[i] z t[i+1]

Zakładamy, że sortowana tablica będzie miała 10 elementów. Program powinien umożliwić wprowadzenie z klawiatury 10 liczb całkowitych, umieścić je w kolejnych komórkach tablicy, a następnie posortować tablicę i wyświetlić ją (posortowaną) na konsoli.

 Wskaźniki

Deklaracja wskaźnika:

typ_wskazywanego_elementu *nazwa_zmiennej;

W manipulacji wskaźnikami przydatne są dwa operatory:

• * - dereferencja wskaźnika - umożliwia dostęp do danych wskazywanych przez wskaźnik (np. *x oznacza wartość przechowywaną w obszarze pamięci wskazywanym przez wzkaźnik x)
• & - pobranie adresu - wskaźnika do obszaru pamięci, gdzie mieści się wartość zmiennej (np. &a oznacza poberanie adresu obszaru pamięci przechowującego wartość zmiennej a)

Wartością wskaźnika jest adres obszaru pamięci i jako taki jest on mało użyteczny (zwykle nie interesuje nas czy dana wartość przechowywana jest pod adresem 0xf00cd05f czy np. 0x5cf0013e - zwykle nic nam ta informacja nie daje). Możliwe jest jednak przeprowadzanie operacji arytmetycznych na wskaźnikach (dodawanie i odejmowanie liczb całkowitych do/od wskaźnika), które działa tak jak indeksacja tablicy. Jeśli np. wskaźnik zadeklarowany jako int *p; wskazuje w danej chwili na początek obszaru pamięci, który zawiera kolejno n liczb całkowitych (int), to *p (równoważnie p[0]) umożliwia operacje na pierwszej liczbie całkowitej z sekwencji, *(p+1) (równoważnie p[1]) - na drugiej liczbie całkowitej, *(p+2) (równoważnie p[2]) - na trzeciej itd. Zatem wskaźniki i tablice jako konstrukcje języka C są w pewnych sytuacjach równoważne (mówiąc ściślej: możemy zwykle traktować wskaźnik jak tablicę i tablicę jak wskaźnik mimo, że są to wewnętrznie dwie różne konstrukcje języka C).

Załóżmy, że dane są następujące definicje:

int t[100];
int *w = t;

Arytmetykę wskaźników i tablic ilustruje poniższy schemat:

 Przykład 3

Projekt Visual Studio  pobierz
Plik refderef.c  pobierz

#include <stdio.h>

int main()
{
  int a;
  int *b;
  int c[3] = { 10, 20, 30 }; /* inicjalizacja tablicy literalami */
  int i;

  a = 3;
  b = &a;                    /* operacja pobrania adresu zmiennej a */
  printf("%d %d\n",a,*b);    /* dereferencja wskaznika b */
  
  b = c;                     /* teraz b wskazuje na pierwszy element tablicy c */
  for (i=0; i<3; i++)
      printf("c[%d] = b[%d] = %d\n",i,i,*(b+i)); /* arytmetyka wskaznika b */

  for (i=0; i<3; i++)
      printf("c[%d] = b[%d] = %d\n",i,i,b[i]);   /* arytmetyka wskaznika b */

  printf("c[1] = b[1] = %d\n", 1[b]);            /* A TO CO ???? Co to jest 1[b] ? */
                                                 /* Dziwne, ale dziala! */

  return 0;
}

Proszę zwrócić uwagę na ostatni (przed return) wiersz funkcji main. Znajduje się w nim dziwna na pierwszy rzut oka konstrukcja

1[b]

Co więcej, działa ona tak samo jak b[1]. Dlaczego? Odpowiedź jest prosta. Skoro b[1] jest równoważne *(b+1), to 1[b] jest równoważne *(1+b), a to dokładnie to samo, co *(b+1). Skoro więc dodawanie jest przemienne, możemy tworzyć takie dziwne konstrukcje opierając się na zasadach arytmetyki wskaźników. Nie jest to jednak zalecane (no, może jako metoda zabłyśnięcia w towarzystwie), gdyż powoduje zagmatwanie kodu źródłowego nie dając w zamian żadnych wymiernych korzyści. Dlatego podaję to jako ciekawostkę, a nie jako regułę godną naśladowania.

 Alokacja i zwalnianie pamięci

Korzystając ze wskaźników możemy sami decydować o tym, kiedy zmiennej przydzielana jest pamięć i kiedy jest ona zwalniana (przypomnijmy: zmienne globalne oraz lokalne zmienne statyczne tworzone są w pamięci w momencie uruchomienia programu i usuwane z niej w momencie jego zakończenia, zaś automatyczne zmienne lokalne alokowane są na stosie w momencie wejścia do funkcji i usuwane z niego w momencie wyjścia z funkcji). W bibliotece standardowej C (plik nagłówkowy stdlib.h) zdefiniowane są funkcje pozwalające "ręcznie" przydzielać i zwalniać obszary pamięci:

• void* malloc(size_t liczba_bajtów); - powoduje przydzielenie liczba_bajtów bajtów pamięci i zwraca wskaźnik do przydzielonego bloku
• void* calloc(size_t liczba_elementów, size_t rozmiar_elementu); - powoduje przydzielenie bloku pamięci o rozmiarze liczba_elementów * rozmiar_elementu i zwraca wskaźnik do przydzielonego bloku
• void free(void *wskaźnik); - powoduje zwolnienie bloku pamięci wskazywanego przez wskaźnik

UWAGA:
Ponieważ formalnie funkcja malloc zwraca void* (czyli wskaźnik na bufor pamięci bez konkretnej interpretacji), przypisując wynik zwracany przez malloc wskaźnikowi na konkretny typ, należy wykonać konwersję wskaźnika void* na wskaźnik typ*. Jest to prosta operacja i jej składnia jest następująca:

jakis_typ *wskaznik;
wskaznik = (jakis_typ*) malloc(rozmiar_bufora);

Od tego momentu kompilator będzie wiedział, że arytmetyka wskaźników na buforze wskazywanym przez wskaznik ma dotyczyć danych typu jakis_typ (dzięki temu kompilator wie, do którego konkretnie adresu odwołać się w przypadku napotkania konstrukcji w stylu *(wskaznik + przesuniecie)).

 Przykład 4

Projekt Visual Studio  pobierz
Plik wsktab.c  pobierz

#include <stdio.h>
#include <stdlib.h>

int main()
{
   int *t1;
   int t2[3];

   t1 = (int*) malloc(3*sizeof(int));
   t2[0] = 1;            /* tablica traktowana jak tablica */
   t1[0] = 1;            /* wskaźnik traktowany jak tablica */
   t2[1] = 2;            
   *(t1+1) = 2;          /* wskaźnik traktowany jak wskaźnik */
   *(t2+2) = 3;          /* tablica traktowana jak wskaźnik */
   *t1 = t2[2];          /* *t1 == *(t1+0) */

   printf("t1=[%d,%d,%d], t2=[%d,%d,%d]\n",
           *t1, *(t1+1), t1[2], *t2, *(t2+1), t2[2]); 
           /* wszystkie kombinacje razem */

   free(t1);             /* NIE WOLNO WYKONAĆ free(t2)!!! */
   return 0;
}

W powyższym przykładzie wykorzystaliśmy omówione wcześniej sposoby zamiennego traktowania wskaźników i tablic. Należy jednak zwrócić uwagę na jeden istotny element. Tablica t2 jest zmienną automatyczną funkcji main i pamięć jest jej przydzielana automatycznie w momencie wejścia do funkcji. Podobnie, pamięć przydzielona tablicy t2 jest automatycznie zwalniana przy wyjściu z funkcji main. Dlatego nie wolno stosować konstrukcji tablica = malloc(x) oraz free(tablica). Wskaźnik t1 jest również zmienną automatyczną i jest mu przydzielana pamięć przy wejściu do funkcji main. Jednak pamięć jest przydzielana wskaźnikowi (czyli tworzone jest miejsce w pamięci na przechowywanie adresu obszaru, na który będzie wskazywać t1), a nie obszarowi, na który będzie on wskazywał. Należy wyraźnie rozróżnić te elementy: sam wskaźnik i obszar, na który on wskazuje. Wskaźnik to zawsze adres - ma on taką samą wielkość niezależnie od tego, na jaki typ danych wskazuje. Wskazywane dane natomiast mają różny rozmiar w zależności od tego, jak inicjujemy wskaźnik (czy wskazuje on na inną zmienną, na tablicę czy też ma ręcznie przydzieloną pamięć za pomocą malloc).

UWAGA:
Proszę zwrócić uwagę na wartość t2[2] po uruchomieniu przykładu 4. Zauważmy, że jest to przypadkowa (przy kolejnych uruchomieniach programu może być inna) wartość. Dzieje się tak, ponieważ nigdzie w programie nie nadajemy wartości trzeciemu elementowi tablicy t2. Skoro jest to zmienna automatyczna, kompilator również nie nadaje jej żadnej początkowej wartości. Ma ona zatem taką wartość, jakie akurat dane znajdują się w obszarze stosu przydzielonym tablicy t2. Potraktujmy to jako zasadę: zawsze należy jawnie inicjować wartość zmiennej lokalnej przed jej użyciem w wyrażeniach. Uwaga ta w dotyczy również obszarów pamięci alokowanych przez malloc. Przydzielona pamięć nie jest automatycznie zerowana czy wypełniana jakąś początkową wartością i zawiera przypadkowe dane, które znajdowały się w komórkach pamięci przed jej przydzieleniem naszej aplikacji.

 Zadanie 2

Wczytać liczbę całkowitą (int), a następnie przedstawić jej reprezentację bajt po bajcie. Wskazówka: jeśli x jest typu int, to ((unsigned char*) &x)[0] jest pierwszym bajtem x, ((unsigned char*) &x)[1] jest jej drugim bajtem itd.
Powtórzyć procedurę dla liczby zmiennopozycyjnej (np. double).

 Zadanie 3

Dla wprowadzonego ciągu C zawierającego n liczb (n jest tutaj wartością wprowadzaną przez użytkownika, nie wiemy z góry ile liczb będziemy przetwarzać) wyświetlić jego medianę, czyli taki element m ciągu C, dla którego istnieje tyle samo elementów ciągu C mniejszych od m, co elementów większych od m. Jeśli dokładna mediana nie istnieje, należy poinformować o tym użytkownika. Proszę zastosować dynamicznie alokowane tablice.

 Zadanie 4

Przepisać program z zadania 1 tak, aby w kodzie źródłowym nie występował operator []. Proszę zastosować wskaźniki i dynamiczną alokację pamięci. Dodatkowo proszę uogólnić program tak, aby sortował tablice o dowolnej (podawanej przez użytkownika) długości. Schemat powinien być następujący:

1. Użytkownik podaje rozmiar tablicy.
2. Program alokuje dynamicznie tablicę o podanym rozmiarze.
3. Użytkownik wprowadza kolejno liczby, które umieszczane są w kolejnych elementach tablicy.
4. Program sortuje tablicę, wykorzystując algorytm z zadania 1.
5. Program wypisuje na konsoli posortowaną tablicę.