Edytuj stronę Odnośniki Fold/unfold all ODT export Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić. ====== 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