Dynamiczny przydział pamięci

Dynamiczny przydział pamięci pozwala uzyskać dostęp do obszaru pamięci na stercie o zadanej wielkości po to aby w tym obszarze przechowywać dane. Dostęp do tej pamięci możliwy jest przez wskaźnik (adres), 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 stały i musi być z góry zadeklarowany 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\n",dtab[n];
 
   /* zwolnienie pamieci */
 
   free(dtab);
}

Ć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

Wskazówka: aby „przewinąć” pozycję w pliku file i ustawić wskaźnik na jego początku można użyć funkcji fseak(file, 0, 0).

Przykładowo, dla pliku wejściowego input.txt 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

Lista jednokierunkowa

Zobacz: Struktury danych: lista jednokierunkowa

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:

struct osoba
{
   char nazwisko[MAX];
   char imie[MAX];
   int wiek;
   struct osoba *nastepny;
};

Ć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:

1. wyswietl - wyświetlenie całej bazy danych
2. dodaj - dodanie nowego rekordu do bazy danych. Program przydziela pamięć dla pojedynczego rekordu, pozwala wypełnić zawartość rekordu i dodaje go do listy.
3. usun - usunięcie z bazy danych rekordu wskazanego przez użytkownika
4. zamien - modyfikacja zawartości rekordu wskazanego przez użytkownika
5. 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ęć 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.

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.

/* 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;
}

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

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