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.

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

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:

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ęć 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.

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

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

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