Spis treści

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\n",dtab[n];
 
   /* zwolnienie pamieci */
 
   free(dtab);
}

Lista jednokierunkowa

Struktura dynamiczna, w której :

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:

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: 

Lorem ipsum dolor
sit amet, consectetur
adipiscing elit.

na ekranie pojawi się taka treść 

.tile gnicsipida
rutetcesnoc ,tema tis
rolod muspi meroL

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ść:

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: liczby.txt

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