Dynamiczny przydział pamięci

Dynamiczny przydział pamięci pozwala w czasie wykonywania programu uzyskać dostęp do obszaru pamięci o zadanej wielkości po to aby w tym obszarze przechowywać dane. Dostęp do tej pamięci możliwy jest przez wskaźnik, który uzyskujemy w wyniku wywołania funkcji malloc()' (nazwa funkcji to skrót od memory allocation). Uzyskany obszar pamięci można traktować jako tablicę o rozmiarze określonym w momencie żądania przydzielenia pamięci, czyli w czasie wykonywania programu. Pozwala to na tworzenie dynamicznych struktur danych w odróżnieniu od typowych tablic w języku C, których rozmiar jest z góry określony w deklaracji w momencie pisania kodu.

Funkcja malloc() i free()

Funkcja malloc() alokuje pamięć, zaś funkcja free() pozwala zwolnić przydzieloną wcześniej pamięć.
Funkcje te zadeklarowane są w pliku stdlib.h

#include <stdlib.h>
void *malloc(int rozmiar);
void free(void *wskaznik);

Argumentem funkcji malloc() jest ilość bajtów pamięci jaką chcemy uzyskać. W celu określenia ilość bajtów potrzebnych do pomieszczenia danych przydatny jest operator sizeof(), który wyznacza ilość bajtów zajmowanych przez zmienną danego typu. Przykładowo, tablica 100 liczb całkowitych potrzebuje sizeof(int)*100 bajtów. Wartością zwracaną funkcji malloc jest adres początku przydzielonej pamięci. Adres ten jest wskaźnikiem typu void*, jest więc adresem nieokreślonego typu. Chcąc uzyskać wskaźnik określonego przez nas typu (np. wskaźnik do liczb całkowitych int), należy wartość uzyskaną z malloc przetransformować za pomocą operatora rzutowania (typ). Na przykład, jeżeli potrzebujemy tablicy 100 liczb typu int to wywołanie funkcji malloc może wyglądać tak:

int *x = (int*)malloc( 100*sizeof(int) );

Jeżeli operacja alokacji pamięci się nie powiodła zwracana jest wartość NULL (adres 0)

Przykład
Poniższy program prezentuje w jaki sposób dynamicznie przydzielić pamięć dla n wartości typu float. Następnie uzyskana tablica jest wypełniana losowymi wartościami z zakresu od 0 do 1.

malloc.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int main()
{
   int n,i;
   float *dtab;
 
   printf("Podaj rozmiar :"); 
   scanf("%d",&n);
 
   /* alokacja pamieci */	
 
   dtab = (float *) malloc(n * sizeof(float));
 
   if(dtab == NULL) 
   {
      printf("Blad przydzialu pamieci\n");
      exit(1);
   }
 
   srand(time(0));  /* ustawienie ziarna generatora */
 
   for(i=0; i<n; i++)
   {
      dtab[i] = rand()/(RAND_MAX + 1.0);
   }
 
   while(--n >= 0) printf("%.4f %.4f\n",dtab[n],stab[n]);
 
   /* zwplnienie pamieci */
 
   free(dtab);
}

Zadanie - Sortowanie liczb z pliku

Napisz program, który posortuje liczby rzeczywiste umieszczone w pliku liczby.txt. Plik może zawierać dowolną ilość liczb rzeczywistych oddzielonych białymi znakami (spacją, tabulacją lub znakiem nowego wiersza). Ponieważ nie wiadomo jak wiele będzie wartości wejściowych, program najpierw wyznacza ilość liczb w pliku a następnie, za pomocą dynamicznego przydziału pamięci, tworzy tablicę o takim rozmiarze aby pomieścić wszystkie liczby zawarte w pliku, po czym dane są wczytywane do tablicy. Dopiero teraz można je posortować.

Dane wejściowe programu: plik tekstowy liczby.txt zawierający dowolnie długa serię liczb rzeczywistych. Zakładamy, że plik znajduje sie w bieżącym katalogu roboczym. W przypadku braku pliku wejściowego wypisywany jest stosowny komunikat błędu i program kończy swoje działanie.
Wynik: ciąg wszystkich liczb z pliku wejściowego wypisany w kolejności od najmniejszej do największej wartości

Algorytm sortowania umieść w stosownej funkcji.

Przykładowy plik danych wejściowych: liczby.txt

Zadanie - Odwracanie pliku

Napisz program, który odwróci kolejność wszystkich znaków w pliku tekstowym o nazwie input.txt. Plik może zawierać dowolnie długi tekst. Ponieważ nie wiadomo ile znaków umieszczonych jest w pliku, program najpierw wyznacza ilość znaków w pliku a następnie tworzy dynamicznie tablicę, o takim rozmiarze aby pomieścić całą zawartość pliku. Gdy cała zawartość pliku trafi do tablicy kolejność elementów zostaje odwrócona a uzyskany wynik jest wypisywany na ekranie.

Dane wejściowe programu: plik tekstowy input.txt. Zakładamy, że plik znajduje sie w bieżącym katalogu roboczym. W przypadku braku pliku wejściowego wypisywany jest stosowny komunikat błędu i program kończy swoje działanie.
Wynik: zawartość pliku wejściowego wypisana w odwrotnej kolejności

Przykładowo, dla pliku wejściowego o treści:

Lorem ipsum dolor
sit amet, consectetur
adipiscing elit.

na ekranie pojawi się taka treść

.tile gnicsipida
rutetcesnoc ,tema tis
rolod muspi meroL

Dynamiczna macierz

Dynamiczny przydział pamięci można użyć do tworzenia złożonych typów danych. Wykorzystamy ten mechanizm do reprezentowania macierzy o dowolnej liczbie wierszy i kolumn według schematu przedstawionego na poniższym rysunku.

Macierz reprezentowana jest przez wskaźnik m, który jest adresem do tablicy posiadającej w elementów typu float*, tzn. elementami tablicy są wskaźniki. Każdy z tych wskaźników pokazuje adres początku tablicy zawierającej k liczb rzeczywistych typu float. Tablice te tworzą wiersze macierzy.

Dowolny element macierzy, znajdujący się w i-tym wierszu i j-tej kolumnie, dostępny jest jako *(*(m+i)+j) lub m[i][j]. Inaczej mówiąc, macierz m to tablica zawierająca tablice liczb, gdzie m[i] to adres tablicy zawierającej elementy i-tego wiersza.

Poniżej znajduje się przykład funkcji, która dla danych liczb całkowitych w i k tworzy dynamicznie strukturę macierzy posiadającej w wierszy i k kolumn. Funkcja zwraca wskaźnik określający początek macierzy lub wartość NULL jeśli coś poszło nie tak przy alokacji pamięci.

float **utworz_macierz(int w, int k)
{
   float **m;
   int i;
 
   m = (float**)malloc( w * sizeof(float*));
   if ( m == NULL ) return NULL;
 
   for(i=0; i<w; i++)
   {
      m[i] = (float*)malloc( k * sizeof(float));
      if( m[i] == NULL ) return NULL;
   }
 
   return m;
}

Po wywołaniu funkcji utworz_macierz otrzymujemy adres do macierzy, którą możemy wypełnić wartościami. Poniżej znajduje się przykład funkcji, która pozwala wprowadzić do macierzy m wartości podane przez użytkownika.

float** wczytaj_macierz(float **m, int w, int k)
{
   int i,j;
   for(i=0 ; i<w ; i++)
   {
      for(j=0 ; j<k ; j++)
      {
         printf(" [%d,%d] = ", i,j);
         scanf("%f", *(m+i)+j); 
      }
   }
   return m;
}

Analogicznie, funkcja do wypisywania na standardowym wyjściu zawartość macierzy m o wymiarach w na k może wyglądac tak:

void wypisz_macierz(float **m, int w, int k)
{
   int i,j;
 
   printf("\nMacierz o wymiarach %dx%d\n\n", w, k);
   for(i=0; i<w; i++)
   {
      for(j=0; j<k; j++)
      {
         printf("%5.2f ",  m[i][j]   ) ;
      }
      printf("\n");
   }
   printf("\n");
}

Nie należy zapomnieć o tym, że zaalokowaną pamięć należy zwolnić, gdy już nie jest potrzebna. Stwórzmy w tym celu funkcję, która dla danej macierzy m o w wierszach zwolni wszystkie wiersze macierzy oraz tablicę zawierającą adresy wierszy.

void zwolnij_macierz(float **m, int w)
{
   int i;
   for (i = 0; i < w; ++i) free(m[i]);
   free(m);
}

Korzystając z tych funkcji możemy spróbować napisać program wykonujący operacje na macierzach. Poniższy fragment kodu prezentuje program, który wykonuje dodawanie dwóch macierzy. Najpierw zdefiniowana jest funkcja realizująca operację dodawania macierzy, która przyjmuje adresy dwóch macierzy m1 i m2 oraz ich wymiary (ilość wierszy i kolumn, odpowiednio w1, k1' , w2, k2). W przypadku, gdy wymiary macierzy nie pozwalają na wykonanie dodawania, zwracana jest wartość NULL. Jeżeli dodawanie jest możliwe do wykonania to tworzona jest nowa macierz o wymiarach w na k i wypełniania jest sumą elementów obu macierzy podanych w argumentach. Funkcja zwraca adres nowej macierzy.

float **dodaj_macierze(float **m1, int w1, int k1, float **m2, int w2, int k2)
{
   float **m3 = NULL;
   int i, j;
 
   if ( k1 != k2 || w1 != w2 )
   {
      printf("Niepoprawne wymiary\n");
      return NULL;
   }
 
   m3 = utworz_macierz(w1, k1);
 
   for (i=0; i<w1; i++) 
     for (j=0; j<k1; j++) 
        m3[i][j] = m1[i][j] + m2[i][j];
 
   return m3;
}
 
int main()
{
   float **m1;
   float **m2;
   float **m3;
   int w1, k1, w2, k2, w3, k3;
 
   printf("podaj rozmiary pierwszej macierzy w i k: ");
   scanf("%d", &w1);
   scanf("%d", &k1);
 
   m1 = utworz_macierz(w1, k1);
   if ( m1 == NULL )
   {
       printf("Problem alokacji macierzy\n");
       exit(1);
   } 
 
   wczytaj_macierz(m1, w1, k1);
   wypisz_macierz(m1, w1, k1);
 
   printf("podaj rozmiary drugiej macierzy w i k: ");
   scanf("%d", &w2);
   scanf("%d", &k2);
 
   m2 = utworz_macierz(w2, k2);
   if ( m1 == NULL )
   {
       printf("Problem alokacji macierzy\n");
       exit(1);
   }
 
   wczytaj_macierz(m2, w2, k2);
   wypisz_macierz(m2, w2, k2);
 
   m3 = dodaj_macierze(m1, w1, k1, m2, w2, k2);
   if ( m3!= NULL )
   {
      printf("Wynik dodawania\n");
      wypisz_macierz(m3, w1, k1);
      zwolnij_macierz(m3, w1);
   }
 
   zwolnij_macierz(m1, w1);
   zwolnij_macierz(m2, w2);
 
   return 0;
}

Pełen kod programu wykonujący dodawanie dwóch macierzy znajduje się tutaj: macierz.c

Zadanie - Mnożenie macierzy

Korzystając z funkcji dostępnych z programie macierz.c zaimplementuj program, który wykona mnożenie 2 macierzy. Operacja mnożenia powinna być zrealizowana za pomocą funkcji o następującej specyfikacji:

Funkcja o nazwie iloczyn_macierzy wykonuje operację mnożenia dwóch macierzy m1 i m2.
Argumenty funkcji: adres m1 oraz rozmiary w1 i k1 macierzy pierwszej oraz adres m2 i rozmiary w2 i k2 macierzy drugiej
Wartość zwracana: adres nowej macierzy o wymiarach w1 na k2 stanowiącej iloczyn macierzy pierwszej i drugiej.
W sytuacji, gdy mnożenie jest niemożliwe do wykonania ze względu na niepasujące wymiary lub w razie wystąpienia błędu alokacji pamięci zwracana jest wartość NULL'

Napisz program, który wczyta z terminala dwie macierze o dowolnych (podanych przez użytkownika) rozmiarach a następnie wypisze na ekranie macierz stanowiącą iloczyn obu macierzy lub informację o tym, że mnożenie jest niemożliwe do wykonania.

Przykładowe działanie programu:

podaj rozmiary macierzy
w=2
k=3
Podaj elementy macierzy:
 [0,0] = 1
 [0,1] = 2
 [0,2] = 3
 [1,0] = 4
 [1,1] = 5
 [1,2] = 6

Utworzono macierz o wymiarach 2x3

 1.00  2.00  3.00 
 4.00  5.00  6.00 

podaj rozmiary macierzy
w=3
k=2
Podaj elementy macierzy:
 [0,0] = 1
 [0,1] = 2
 [1,0] = 3
 [1,1] = 4
 [2,0] = 5
 [2,1] = 6

Utworzono macierz o wymiarach 3x2

 1.00  2.00 
 3.00  4.00 
 5.00  6.00 

Wynik mnozenia

Macierz o wymiarach 2x2

22.00 28.00 
49.00 64.00