====== 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''

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

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:

<code C>
int *x = (int*)malloc( 100*sizeof(int) );
</code>

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.

<file C 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);
}
</file>

===== 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: {{zajecia:pp1_2020_1:dane: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:
<code>
Lorem ipsum dolor
sit amet, consectetur
adipiscing elit.
</code>
na ekranie pojawi się taka treść
<code>
.tile gnicsipida
rutetcesnoc ,tema tis
rolod muspi meroL
</code>


===== 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.

{{  zajecia:pp1_2019_1:macierz-wskazniki.png?300  }}

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.

<code C>
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;
}
</code>

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.

<code C>
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;
}
</code>

Analogicznie, funkcja do wypisywania na standardowym wyjściu zawartość macierzy ''m'' o wymiarach ''w'' na ''k'' może wyglądac tak:
<code C>
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");
}
</code>

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.

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

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.

<code C>
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;
}
</code>

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

===== Zadanie - Mnożenie macierzy =====


Korzystając z funkcji dostępnych z programie {{zajecia:pp1_2020_1: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**:\\

<code>
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 
</code>