Konwersja tablicy wielowymiarowej do wskaźnika
Wcześniej mówiłem, że nazwa tablicy jest wskaźnikiem na jej pierwszy element, dlatego możemy przypisać tablicę na wskaźnik. Niestety dotyczy to tylko jednowymiarowych tablic, np. dwuwymiarowej tablicy na dwuwymiarowy wskaźnik przypisać nie można.
Przykład:
double liczby[10][10];
double** wsk_dwuwymiarowy = liczby;
wsk_dwuwymiarowy[2][5] = 6; /* bedzie warning + segmentation fault */
double* wsk = (double*)liczby; /* traktujemy tablice dwywymiarowa jako jedno
-zadziala i lubia to na rozmowach kwalifikacyjnych,
ale w zyciu osobistym polecam tego unikac */
Więc jak przekazać do funkcji tablicę dwywymiarową bez podania rozmiaru tablicy? A no tak (kluczowy jest tutaj nawias):
void f(double (*wsk)[])
{}
Tablice zmiennej długości w C99
Często rozmiar tablicy nie jest znany w trakcie kompilacji, dopiero w czasie wykonywania programu.
W C od wersji C99 są dostępne tablice o zmiennej długości:
int rozmiar;
scanf("%d", &rozmiar);
int tablica[rozmiar];
Są one bardzo wygodne, choćby ze względu na możliwość tworzenia wielowymiarowych tablic nawet na wejściu do funkcji:
/* void f(double liczby[][], unsigned rozmiar1, unsigned rozmiar2) {}
- to jest blad kompilacji */
void wypisz(unsigned rozmiar1, unsigned rozmiar2,
double liczby[rozmiar1][rozmiar2])
{
unsigned i, j;
for(j=0; j<rozmiar1; ++j)
for(i=0; i<rozmiar2; ++i)
printf("tab[%d][%d] = %lf\n", j, i, liczby[j][i]);
}
Niestety stosowanie tablic o zmiennej długości jest niebezpieczne z wielu powodów, główny jest następujący:
unsigned size = 4000000000; int array[size]; // segmentation fault, program sie wysypuje
Co prawda w powyższym programie alokujemy olbrzymią pamięć bo aż 4*4mld bajtów ~ 16mln kb ~ 16 tys MB ~ 16 GB.
Zapewne wyda się Państwu, że nie musimy na to zważać, bo nigdy nie będziemy chcieli aż tak dużej pojemności, ale kto powiedział, że innymi programami nie zapchamy całego RAMu, a może piszemy program na system wbudowany, który ma tylko 1 MB RAMu? Dlatego za wszelką cenę należy unikać sytuacji gdy ryzykujemy wywaleniem się programu!
Dynamiczna alokacja pamięci
http://jezykc.wordpress.com/2014/12/19/cwiczenia-10/
Co jeśli nie uda się zaalokować wystarczającej pamięci? Malloc zwróci 0 i możemy działać dalej:
#include <stdio.h>
#include <stdlib.h>
#include <errno.h> /* zmienna errno */
int main()
{
unsigned size = 4000000000u;
int* ptr = (int*)malloc(size);
if(NULL == ptr)
{
fprintf(stderr, "kod bledu = %d", errno);
perror(", a tresc bledu");
}
free(ptr);
return 0;
}
Inicjowanie wskaźnika
Jak inicjować wskaźnik pierwotną wartością? Istnieje specjalna makrodefinicja o nazwie NULL, której wartość wynosi 0, w ten sposób inicjujemy wskaźnik. Jeśli spróbujemy zwolnić taką pamięć program się nam nie wysypie, niemniej jednak przypisywanie do wyłuskanego adresu NULLowego nadal powoduje wysypanie się programu.
Zerowa długość i rozmiar wskaźnika
Allokowanie zerowego rozmiaru jest tym, czego powinniśmy się wystrzegać, gdyż jest to zachowanie niezdefiniowane, chociaż jak widać gcc akceptuje coś takiego.
Przykład allokacji i zwalniania pamięci:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int* ptr1 = (int*)malloc(0);
int* ptr2 = NULL;
free(ptr1);
free(ptr2);
puts("koniec:)");
return 0;
}
Alokacja tablicy wielowymiarowej
Tablice wielowymiarowe również da się allokować. Aby tego dokonać najpierw allokujemy tablicę wskaźników, następnie do każdego w niej wskaźnika kolejną tablicę, oto przykład:
#include <stdio.h>
#include <stdlib.h>
#define ROZMIAR 3
void wyswietlTablice(int** tablica)
{
int i, j;
for(j=0; j<ROZMIAR; ++j)
{
for(i=0; i<ROZMIAR; ++i)
printf("tab[%d][%d] = %d, ", j, i, tablica[j][i]);
puts("");
}
}
int main(void)
{
int** tablica = (int**)malloc(sizeof(int**) * ROZMIAR);
int i, j;
for(i=0; i<ROZMIAR; ++i)
tablica[i] = (int*)malloc(sizeof(int*) * ROZMIAR);
for(j=0; j<ROZMIAR; ++j)
for(i=0; i<ROZMIAR; ++i)
tablica[j][i] = i*j;
wyswietlTablice(tablica);
for(i=0; i<ROZMIAR; ++i)
free(tablica[i]);
free(tablica);
}
Niestety operacja allokacji jest operacją wolną -zwracamy się do systemu operacyjnego o przydzielenie nam pamięci, dlatego niektórzy mogą chcieć operować na tablicy jednowymiarowej jak na dwuwymiarowej. Jest to mniej czytelne, ale czemu by do tego nie zrobić sobie funkcji:
#include <stdio.h>
#include <stdlib.h>
const unsigned ROZMIAR1 = 5, ROZMIAR2 = 3;
int* element(int* tablica, unsigned index1, unsigned index2)
{
unsigned przesuniecie = index1*ROZMIAR2 + index2;
return tablica + przesuniecie;
}
void wyswietlTablice(int* tablica)
{
unsigned i, j;
for(j=0; j<ROZMIAR1; ++j)
{
for(i=0; i<ROZMIAR2; ++i)
printf("tab[%d][%d] = %d, ", j, i, *element(tablica, j, i));
puts("");
}
}
int main(void)
{
unsigned rozmiarDoAllokacji = sizeof(int) * ROZMIAR1*ROZMIAR2;
int* tablica = (int*)malloc(rozmiarDoAllokacji);
unsigned i, j;
for(j=0; j<ROZMIAR1; ++j)
for(i=0; i<ROZMIAR2; ++i)
*element(tablica, j, i) = i*j;
wyswietlTablice(tablica);
free(tablica);
return 0;
}
A teraz życiowy przykład na dynamiczną allokację -napiszmy program do sortowania, gdy nieznany jest rozmiar początkowy:
#include <stdio.h>
#include <stdlib.h>
void wyswietlTablice(double* tablica, unsigned rozmiar)
{
unsigned i;
for(i=0; i<rozmiar; ++i)
printf("%d)\t%lf\n", i+1, tablica[i]);
puts("");
}
void zamien(double* a, double* b)
{
double tmp = *a;
*a = *b;
*b = tmp;
}
int main(int argc, char* argv[])
{
unsigned iloscLiczb, i, j;
double *liczby;
if(argc < 2)
{
puts("!!! Za malo argumentow!!!");
return 1;
}
iloscLiczb = atoi(argv[1]);
liczby = (double*)calloc(iloscLiczb, sizeof(*liczby));
if(liczby == NULL)
return -1;
for(i=0; i<iloscLiczb; ++i)
scanf("%lf", &liczby[i]);
for(i=0; i<iloscLiczb; ++i)
for(j=0; j<iloscLiczb-1; ++j)
if(liczby[j]>liczby[j+1])
zamien(&liczby[j], &liczby[j+1]);
wyswietlTablice(liczby, iloscLiczb);
free(liczby);
}
I oto przykładowy wydruk:
$ gcc program.c && ./a.out 3 2 5 1 1) 1.000000 2) 2.000000 3) 5.000000
Dla dociekliwych -użycie powyższego programu w bashu
I załóżmy, że chcemy posortować ilości linii plików w danym katalogu, najpierw musimy pobrać ilość plików, żeby tego dokonać wystarczy w systemie Linux wpisać:
find . -type f -name '*.c' | wc -l
I wyjaśnienie: find wyszukuje pliki i katalogi, szukamy w bieżącej ścieżce, stąd ta kropka, zależy nam tylko na plikach więc dodajemy -type f, ale interesują nas tylko pliki z rozszerzeniem *.c.
wc -l zwraca ilość linii
pionowa kreska to potok, czyli tzn. przekierowanie standardowego wyjścia jednego programu do standardowego wejścia drugiego programu.
Jak mamy rozmiar to pozyskajmy ilość linii na każdy plik:
$ find . -name '*c' -type f | xargs wc -l 29 ./cw1_malloc.c 39 ./cw4_mallocVLA.c 51 ./cw3_malloc3.c 32 ./cw2_malloc2.c 37 ./cw2b_malloc2_dwuwymiar.c 188 razem
xargs na zawartości pliku wykonuje dane polecenie
Teraz przydało by się wziąć tylko te liczby.
$ find . -name '*c' -type f | xargs wc -l | tr -s ' ' | cut -d ' ' -f 2 29 39 51 32 37 188
Polecenie cut tnie linię na fragmenty, -d to separator, -f to numer pola między separatorami, niestety mamy różną ilość spacji, więc musimy doprowadzić do sytuacji w której sąsiaduje ze sobą maksymalnie jedna spacja, do tego jest tr.
Mając to wszystko możemy wykorzystać nasz program:
$ find . -name '*c' -type f | xargs wc -l | tr -s ' ' | cut -d ' ' -f 2 | ./cw3_malloc3 5 1) 29.000000 2) 32.000000 3) 37.000000 4) 39.000000 5) 51.000000
Oczywiście do naszego programu musimy podawać ścieżkę od bieżącej pozycji, lub bezwzględną, ewentualnie możemy ścieżkę do naszego programu dodać do zmiennej środowiskowej PATH.
Nasz program jest troszeczkę niewygodny w użyciu -gdyż musimy dwukrotnie wykonywać komendy systemowe, które przy dużej liczbie plików może być powolne, możemy więc zastosować funkcję realloc, do ponownego alokowania pamięci, gdy zabraknie zaallokowanej:
#include <stdio.h>
#include <stdlib.h>
void wyswietlTablice(double* tablica, unsigned rozmiar)
{
unsigned i;
for(i=0; i<rozmiar; ++i)
printf("%d)\t%lf\n", i+1, tablica[i]);
puts("");
}
void zamien(double* a, double* b)
{
double tmp = *a;
*a = *b;
*b = tmp;
}
int main(void)
{
unsigned iloscLiczb = 0, i, j;
unsigned aktualnyRozmiar = 10;
const unsigned przyrostRozmiaru = 5;
double *liczby = (double*)malloc(aktualnyRozmiar*sizeof(*liczby));
if(liczby == NULL)
return -1;
while(EOF != scanf("%lf", &liczby[iloscLiczb]))
{
++iloscLiczb;
if(iloscLiczb == aktualnyRozmiar)
{
double *liczby2;
aktualnyRozmiar += przyrostRozmiaru;
liczby2 = (double*)realloc(liczby, aktualnyRozmiar*sizeof(*liczby2));
if(NULL == liczby2)
{
puts("!!! Nie mozna dokonac realokacji!!!");
free(liczby);
return -1;
}
printf("[INFO] Realokacja, nowy rozmiar to %d\n", aktualnyRozmiar);
}
}
for(i=0; i<iloscLiczb; ++i)
for(j=0; j<iloscLiczb-1; ++j)
if(liczby[j]>liczby[j+1])
zamien(&liczby[j], &liczby[j+1]);
wyswietlTablice(liczby, iloscLiczb);
free(liczby);
}
Ten program wczytuje liczby do czasu podania mu EOF, czyli Ctrl+D na Linuxie.
Dla tych samych dociekliwych co wcześniej
Teraz możemy użyć naszego programu w taki sposób:
$ find . -name '*c' -type f | xargs wc -l | tr -s ' ' | cut -d ' ' -f 2 | ./cw3_realloc
Proszę się teraz nie zdenerwować, ale mamy wbudowany program sort, więc zamiast pisać naszego programu możemy użyć komendy tak:
$ find . -name '*c' -type f | xargs wc -l | tr -s ' ' | cut -d ' ' -f 2 | sort -n
Niemniej jednak wiedza bywa bezcenna.
Wskaźniki na funkcje
Również na funkcje możemy mieć wskaźniki. Możemy na nich operować w następujący sposób:
#include <stdio.h>
#include <math.h>
float kwadrat(int liczba)
{
return liczba*liczba;
}
float pierwiastek(int liczba)
{
return sqrtf(liczba);
}
int main(void)
{
float (*wsk)(int) = kwadrat;
printf("Wywoluje dla kwadratu z 3 i wynik = %f\n", wsk(3));
wsk = pierwiastek;
printf("Wywoluje dla pierwiastka z 3 i wynik = %f\n", wsk(3));
wsk = &kwadrat;
printf("Wywoluje dla kwadratu z 5 i wynik = %f\n", wsk(5));
wsk = &pierwiastek;
printf("Wywoluje dla pierwiastka z 5 i wynik = %f\n", (*wsk)(5));
return 0;
}
Fajną rzeczą ze wskaźnikami do funkcji jest to, że możemy je przekazywać jako argumenty funkcji, lub nawet zwracać z funkcji:
void wykonajOperacje(const char* nazwa, float (*operacja)(int), int liczba)
{
printf("Wykonuje operacje %s, dla wartosci %d, otrzymuje %f\n",
nazwa, liczba, operacja(liczba));
}
i używamy w taki sposób:
wykonajOperacje("pierwiasteczek", pierwiastek, 66);
Rzutowanie wskaźników do funkcji
Da się to zrobić, oto przykład:
#include <ctype.h> /* int isspace(int) */
int main(void)
{
char (*wsk_char)(char) = ( char(*)(char) )isspace;
wsk_char('g');
}
Niestety również da się rzutować na inny typ wskaźnika, ale to jest działanie bez sensu, a jak jest coś bez sensu to zdecydowanie odradzam stosowanie:
#include <stdio.h>
int f(int i1, int i2)
{
printf("wywoluje %d, %d\n", i1, i2);
return i1+i2;
}
int main(void)
{
void (*wsk_falszywy)(void) = ( void (*)(void) )f;
wsk_falszywy();
}
Rzutowanie funkcji na void* nie jest zachowaniem standardowym, dlatego zdecydowanie proszę go unikać, niemniej jednak kompilator gcc pozwala na coś takiego:
void* wsk_void = &kwadrat;
wsk = ( float(*)(int) )wsk_void;
printf("Wywoluje dla kwadratu z -2 i wynik = %f\n", wsk(-2));
Funkcje do sortowania i przeszukiwania binarnego
W ramach zadania mieli Państwo do napisania sortowanie. Co ciekawe sortowanie w języku C jest zaimplementowane. Poza tym jego złożoność ma być rzędu N*log2 (N). Do przeszukiwania binarnego musimy mieć posortowany zakres. Z tych funkcji można korzystać w taki sposób:
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
int porownaj(const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
void wyswietl(int tablica[], unsigned rozmiar)
{
unsigned i;
for(i=0; i<rozmiar; ++i)
printf("%d, ",tablica[i]);
puts("");
}
void znajdzElement(int tablica[], unsigned rozmiar, int szukany)
{
int* element = (int*)bsearch(&szukany, tablica, rozmiar,
sizeof(tablica[0]), porownaj);
if(element)
printf("Znaleziono element %d na pozycji %d\n",
szukany, element - tablica);
else
printf("Nie znaleziono elementu %d\n", szukany);
}
int main(void)
{
int tablica[] = { 4, 122, -122, 7, 90, 0 };
const unsigned ROZMIAR = sizeof(tablica)/sizeof(*tablica);
qsort(tablica, ROZMIAR, sizeof(*tablica), porownaj);
wyswietl(tablica, ROZMIAR);
znajdzElement(tablica, ROZMIAR, 7);
znajdzElement(tablica, ROZMIAR, 9);
return 0;
}
Wydruk będzie następujący:
-122, 0, 4, 7, 90, 122, Znaleziono element 7 na pozycji 3 Nie znaleziono elementu 9
Czytanie zmiennych
Jest to ważne zagadnienie, szczegółowo poćwiczymy na zajęciach.
Czytamy najpierw zmienną, potem idziemy w prawo tak długo dopóki nie ma ewentualnego nawiasu zamykającego:
Oto przykłady:
int f(int liczba); – f, jest funkcją, przyjmującą argument typu int, zwracającą int
void f2(void); – f2, jest funkcją, nie przyjmującą żadnych argumentów, nie zwracającą wartości
int (*wsk)(double, float); – wsk, jest wskaźnikiem, do funkcji, przyjmującej argumenty typu double i float, zwracającą wartość typu int.
char fc( char(*wsk)(const char*) ); -fc, jest funkcją, przyjmującą jako argument wskaźnik do funkcji przyjmującej argument typu const char* zwracający argument typu char, zwracającą argument typu char
Dla dociekliwych -funkcja zwracająca wskaźnik do funkcji
Tak, da się to zrobić, robi się to najczęściej stosując typedafa dla czytelności, ale jak ktoś nie chce typedefa, lub jest o to pytany na rozmowie kwalifikacyjnej, tak się to robi:
#include <stdio.h>
int kwadrat(int i)
{
return i*i;
}
int (*funkcjaZwracajacaWskDoFunkcji(char c))(int)
{
switch(c)
{
case 'k':
return kwadrat;
default:
return NULL;
};
}
int main()
{
printf("funkcjaZwracajacaWskDoFunkcji('k')(2) = %d\n", funkcjaZwracajacaWskDoFunkcji('k')(2));
return 0;
}
Jak widać zwracając wskaźnik do funkcji z funkcji można wywoływać funkje kaskadowo.
Dla funkcji zwracających wskaźnik do funkcji są też wskaźniki, rozumienie tego zagadnienia najlepiej zacząć od:
http://stackoverflow.com/questions/10758811/c-syntax-for-functions-returning-function-pointers
a oto przykład dla naszej, powyższej funkcji:
int (*(*wsk)(char))(int) = funkcjaZwracajacaWskDoFunkcji;
wsk('k')(3);
Można również napisać wskaźnik do funkcji ze zmienną liczbą argumentów, robi się to dokładnie tak samo:
int (*wskZmienny)(const char*, ...) = printf;
wskZmienny("dziala!\n");
Na następnych ćwiczeniach będzie przedstawione jak czytelniej pisać funkcje zwracające wskaźnik do funkcji -przy użyciu typedefa.
Dla dociekliwych -zwracanie wskaźnika do siebie samej
Tak, da się to zrobić, ale niestety nie wprost -przy użyciu struktury (o strukturach na następnych ćwiczeniach).
Mimo pozorów może coś takiego być przydatne -przy implementacji maszynki stanów, niestety nie udało mi się wymyślić prostego, a równocześnie życiowego przykładu, ale chodzi o wiedzę:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
struct Stan
{
struct Stan (*func)(char);
};
int znaleziono = 0;
struct Stan oczekujeLiteryA(char c);
struct Stan oczekujeLiteryL(char c);
struct Stan oczekujeLiteryE(char c);
struct Stan oczekujeBialegoZnaku(char c);
struct Stan oczekujeLiteryA(char c)
{
struct Stan nowyStan;
if('A' == toupper(c))
nowyStan.func = oczekujeLiteryL;
else
nowyStan.func = oczekujeLiteryA;
return nowyStan;
}
struct Stan oczekujeLiteryL(char c)
{
struct Stan nowyStan;
if('L' == toupper(c))
nowyStan.func = oczekujeLiteryE;
else
nowyStan.func = oczekujeLiteryA;
return nowyStan;
}
struct Stan oczekujeLiteryE(char c)
{
struct Stan nowyStan;
if('E' == toupper(c))
nowyStan.func = oczekujeBialegoZnaku;
else
nowyStan.func = oczekujeLiteryA;
return nowyStan;
}
struct Stan oczekujeBialegoZnaku(char c)
{
struct Stan nowyStan;
nowyStan.func = oczekujeLiteryA;
if(isspace(c))
++znaleziono;
return nowyStan;
}
int main(void)
{
const char* napis = "Wydaje mi sie ze Ala nie ma kota! Ale nie daje gwarancji, gdyz nie znam Ali, ale mi sie wydaje!\n";
unsigned i;
struct Stan (*wsk)(char) = oczekujeLiteryA;
for(i=0; i<strlen(napis); ++i)
wsk = wsk(napis[i]).func;
printf("Automat spasowal razy %d\n", znaleziono);
return 0;
}
ZADANIA
- Funkcja do dzielenia zdania na wyrazy.
- Funkcja przyjmująca wskaźnik zakresu od, do i sprawdzająca czy dany tekst jako całość spełnia podany predykat z ctype.h.
- Funkcja, która na podstawie podanych argumentów zwróci inną funkcję do wyświetlania tekstu.
- Funkcja alokująca wskaźnik do tablicy char* i centrująca podany tekst.
Zgodnie z obietnicą -za zrobienie wszystkich zadań o wskaźnikach (z dwóch ćwiczeń) jest to traktowane jak zrobienie zadań z 3 ćwiczeń.
programowaniec 