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

{{https://sp-ao.shortpixel.ai/client/q_glossy,ret_img,w_900,h_500/https://codewindow.in/wp-content/uploads/2021/04/malloc.png?300|}}


**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\n",dtab[n];

   /* zwolnienie pamieci */

   free(dtab);
}
</file>

===== Lista jednokierunkowa ====

{{http://zsedabrowa.edu.pl/wp-content/uploads/2017/02/Lista-jednokierunkowa.gif|}}

Struktura dynamiczna, w której :
  * każdy element zawiera odnośnik (adres) następnego elementu
  * ostatni element posiada odnośnik do następnego równy ''NULL''
  * dostęp do listy możliwy przez wskaźnik głowy (wskaźnik do pierwszego elementu listy)
  * aby wydobyć element na pozycji ''k'' należy wykonać iterację od głowy (od początku) listy poprzez wszystkie kolejne elementy aż do elementu ''k'''

Przykład struktury:

<code C>
struct osoba
{
   char nazwisko[MAX];
   char imie[MAX];
   int wiek;
   struct osoba *nastepny;
};
</code>


===== Ćwiczenie: Baza danych =====

Zaimplementuj prostą bazę danych osobowych składającą się z sekwencji rekordów zawierających dane osobowe: imię, nazwisko i wiek osób umieszczonych w bazie danych. Struktury zawierające dane przechowuj w liście jednokierunkowej.
Program po uruchomieniu wypisuje menu z możliwymi akcjami do wykonania po podaniu liczby od 1 do 5:
  - ''wyswietl'' - wyświetlenie całej bazy danych
  - ''dodaj'' - dodanie nowego rekordu do bazy danych. Program przydziela pamięć dla pojedynczego rekordu, pozwala wypełnić zawartość rekordu i dodaje go do listy.
  - ''usun'' - usunięcie z bazy danych rekordu wskazanego przez użytkownika   
  - ''zamien'' - modyfikacja zawartości rekordu wskazanego przez użytkownika 
  - ''zamknij'' - zamkniecie programu (opróżnienie bazy danych)

Zaimplementuj wszystkie funkcjonalności opisane w powyższym menu. Zadbaj o obsługę sytuacji wyjątkowych, np. gdy podczas usuwania rekordu użytkownik poda niepoprawny numer.
Po wykonaniu akcji 1, 2, 3 lub 4 menu ponownie jest wyświetlane i użytkownik ponownie może wykonać jedną z akcji.
Wybranie pozycji nr 5 kończy działanie programu.

W zadaniu można skorzystać z implementacji z poprzednich zajęć  {{zajecia:pp1_2022_1:src:baza.c}}, gdzie baza danych realizowana była za pomocą tablicy rekordów a nie za pomocą listy.

===== Ćwiczenie: Dynamiczna macierz =====

Dynamiczny przydział pamięci można użyć do tworzenia złożonych typów danych. \\ 
Wykorzystamy ten mechanizm do reprezentowania macierzy posiadającej ''w'' wierszy i ''k'' 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>
/* Funkcja rezerwuje pamiec dla macierzy o rozmiarach w * k */
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>


===== Ćwiczenie: Macierz c. d. =====

Zaimplementuj program, służący do wykonywania operacji na macierzach, w którym macierze reprezentowane są strukturą zdefiniowaną w poprzednim przykładzie. Zaimplementuj w programie następujące funkcje:
    * ''**wczytaj_macierz**'' - funkcja wypełnia macierz wartościami podanymi przez użytkownika. Dla macierzy o wymiarach ''w'' na ''k'' wczytuje ''w*k'' liczb rzeczywistych ze standardowego wejścia i umieszcza je w kolejnych elementach macierzy  \\ **Argumenty:** adres macierzy oraz 2 wartości całkowite określające ilość wierszy oraz ilość kolumn macierzy\\ **Wartość zwracana:** adres macierzy wejściowej, wypełnionej wartościami\\ 
    * ''**wyświetl_macierz**'' - wyświetla macierz na ekranie \\ **Argumenty:** adres macierzy oraz 2 wartości całkowite określające ilość wierszy i ilość kolumn macierzy\\\\ **Wartość zwracana:** Brak. Funkcja wypisuje macierz na standardowym wyjściu.   \\ 
    * ''**zwolnij_macierz**'' - zwalnia pamięć zajętą przez macierz \\ **Argumenty:** adres macierzy ''m'' oraz ilość wierszy macierzy ''w''\\ **Wartość zwracana:** brak  \\ 
    * ''**suma_macierzy**'' - wykonuje operację dodawania dwóch macierzy. \\ **Argumenty:** adres macierzy pierwszej ''m1'', adres macierzy drugiej ''m2''' oraz rozmiary (liczba wierszy i kolumn) obu macierzy (obie macierze muszą mieć takie same rozmiary). \\ **Wartość zwracana:** adres nowej macierzy o takich samych wymiarach jak macierze wejściowe zawierającej posumowane elementy obu macierzy\\

    * ''**iloczyn_macierzy**'' - wykonuje operację mnożenia dwóch macierzy. \\ **Argumenty:** rozmiary macierzy macierzy pierwszej ''w1'' i ''k1'' oraz adres macierzy pierwszej ''m1'', rozmiary i adres macierzy drugiej ''w2'', ''k2'', ''m2''\\ **Wartość zwracana:** adres macierzy o wymiarach ''w1'' na ''k2'' stanowiącej iloczyn macierzy pierwszej i drugiej lub wartość ''NULL'', gdy nie udało się pomnożyć macierzy (np. niezgodne wymiary lub błąd alokacji pamięci) \\ 

Napisz program, który wczyta 2 macierze o zadanych rozmiarach do pamięci komputera a następnie umożliwi wykonanie operacji dodawania macierzy lub iloczynu macierzy. Po wykonaniu działania wynik prezentowany jest na standardowym wyjściu.

 
===== Ćwiczenie - Odwracanie zawartości pliku =====

Napisz program, który odwróci kolejność wszystkich znaków w pliku tekstowym o nazwie ''input.txt'' (plik powinien znajdować się w katalogu roboczym programu). 
Plik może zawierać dowolnie długi tekst. Ponieważ nie wiadomo ile znaków umieszczonych jest w pliku, program najpierw wyznacza ilość wszystkich znaków w pliku a następnie **tworzy dynamicznie** tablicę, o takim rozmiarze aby pomieścić całą zawartość pliku (w tym celu wykorzystaj funkcję ''malloc''). 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 ''input.txt'' 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>


===== Zadanie: Sortowanie liczb z pliku ======

Napisz program, który posortuje dowolnie długą sekwencję liczb rzeczywistych umieszczoną w pliku tekstowym ''liczby.txt''. 
Zakładamy, że plik zawiera wyłącznie liczby (po jednej liczbie w każdej linii). Program powinien pozwalać posortować dowolnie długą sekwencję liczb, dlatego powinien wykorzystywać mechanizm dynamicznego przydziału pamięci, tak aby wszystkie dane pomieścić w odpowiedniej strukturze danych. 
Zadanie można zrealizować za pomocą jednego z dwóch podejść:
  * listy jednokierunkowej. Każda kolejna wartość liczbowa wczytana z pliku dodawana jest do listy na takiej pozycji aby kolejne elementy listy zachowały porządek. 
  * tablicy o długości ''N''. Ponieważ nie wiadomo jak wiele będzie wartości wejściowych, program najpierw wyznacza wartość ''N'' (ilość liczb w pliku) a następnie, tworzy dynamicznie tablicę o takim rozmiarze aby pomieścić wszystkie liczby zawarte w pliku, po czym dane są wczytywane do tablicy.  Następnie wypełniamy tablicę wartościami z pliku i sortujemy zawartość tablicy. \\ Wskazówka: aby "przewinąć" pozycję w pliku ''f'' i ustawić wskaźnik na jego początku można użyć funkcji ''fseak(file, 0, 0)''. 
 

**Dane wejściowe programu:** plik tekstowy ''liczby.txt'' zawierający dowolnie długą 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\\

Przykładowy plik danych wejściowych: {{zajecia:pp1_2020_1:dane:liczby.txt}}

Rozwiązanie umieść w Moodle pod adresem https://moodle.umk.pl/WFAIIS/mod/assign/view.php?id=6436