DYNAMICZNE STRUKTURY DANYCH
Do tworzenia dynamicznych struktur danych w ANSI C używa się 3 funkcji dynamicznej
alokacji pamięci;
calloc(); malloc(); free();
malloc()
prototyp funkcji: void *malloc(size_t size);
Funkcja ta rezerwuje blok pamięci o rozmiarze size bajtów oraz zwraca wskaz
nik do
pierwszego bajtutego bloku.
malloc zwraca wskaz
nik do typu pustego (void, stad rzutowanie naodpowiedni typ (typ *).
typ w;
w = (typ *) malloc(rozmiar);
rozmiar - wielkość rezerwowanego obszaru pamięci w bajtachsizeof(typ);
w - wskaz
nik do pierwszego bajtuw tym obszarze;
np.
int *t;
t = (int *)malloc(10*sizeof(int)); //Rezerwuje tablicę 10 liczb typu int.
DYNAMICZNE STRUKTURY DANYCH
calloc()
prototyp funkcji:
void *calloc(size_t num, size_t size);
Funkcja ta rezerwuje blok pamięci o rozmiarze num*size bajtów oraz zwraca wskaz
nik
do pierwszego bajta tego bloku. To samo można uzyskać pisząc:
malloc(num*size);
free()
prototyp funkcji:
void *free(void *ptr);
Funkcja ta zwalnia uprzednio zarezerwowaną pamięć, na którą wskazuje wskaz
nik ptr.
Wszystkie te funkcje znajdują się w bibliotece stdlib.h.
DYNAMICZNE STRUKTURY DANYCH
Tworzenie własnych typów
typedef int * Moj_Wskaznik;
typedef struct Punkt{
Przykład:
float x;
float y;
typedef struct Punkt{
} pkt1;
float x;
float y;
np. main() {
} pkt1;
Moj_Wskaznik i;
pkt1 a[20];
main() {
pkt1*t;
t = (pkt1*)malloc(10*sizeof(pkt1));
(*t).x = 1.0;
t[1].x = 1.0;
(*(t+2)).x = 1.0;
t->x = 1.0;
(t+3)->x = 1.0; }
DYNAMICZNE STRUKTURY DANYCH
struct pnt { int x; } *t;
*t.x /* wartość, na którą wskazuje x - y
LE */
(*t).x /* składowa x struktury, na którą wskazuje t - DOBRZE */
t->x /* składowa x struktury, na którą wskazuje t - DOBRZE */
struct pnt { int *x; } t;
*t.x /* wartość, na którą wskazuje x - DOBRZE */
(*t).x /* składowa x struktury, na którą wskazuje t - y
LE */
struct pnt { int x; } t[10];
++t->x /* składowa t[0].x zwiększona o 1 */
(++t)->x /* składowa t[1].x */
DYNAMICZNE STRUKTURY DANYCH
Dynamiczne tworzenie tablic polega jedynie na zarezerwowaniu odpowiedniej ilości
pamięci, której rozmiar będzie podzielny przez rozmiar typu, który tablica ta ma
przechowywać.
Możemy tego dokonać za pomocą funkcji malloc() lub calloc().
np..
int *tab; tab = (int *)calloc(n, sizeof(int));
lub
tab = (int *)malloc(n*sizeof(int));
Odnosimy się do tej tablicy tak jak do zwykłej, czyli: tab[0], tab[1], ..., tab[n]
Można to zrobić przy pomocy wskaz
nika:
*(tab), *(tab+1), ..., *(tab+n)
DYNAMICZNE STRUKTURY DANYCH
Tablice wskaz
ników do tablic.
int **tab_wsk; -> wskaz
niki na wskaz
nik
tab_wsk = (int **)malloc(n*sizeof(int *));
Następnie każdy wskaz
nik z tablicy tab_wsk przypisujemy do nowej tablicy:
tab_wsk[k] = (int *)malloc(ak*sizeof(int)); // dla k={0,1,...,n} oraz ak={1,2,...}
gdyby a0=a1=...= anto byłaby zwykła tablica
statyczna 2-wymiarowa
Aby odczytać np. komórkę 4 w 3 wierszu:
tab_wsk[2][3]
lub *(*(tab_wsk+2)+3)
DYNAMICZNE STRUKTURY DANYCH
Tablice wskaz
ników do tablic.
DYNAMICZNE STRUKTURY DANYCH
Tablice wskaz
ników do struktur.
Załóżmy, że mamy strukturę o nazwie structure i chcemy stworzyć tablicę wskaz
ników
do obiektów tej struktury. Postępujemy tak:
struct structure**tab_struct;
tab_struct = (struct structure**)malloc(n*sizeof(struct structure *));
Teraz tworzymy nasze obiekty i przypisujemy je do wskaz
ników z tablicy:
tab_struct[k] = (struct structure *)malloc(sizeof(struct structure));
Dzięki temu możemy się odnosić do naszych obiektów w następujący sposób:
(Zakładamy, że w naszej strukturze jest zmienna o nazwie x)
tab_struct[k]->x lub *(tab_struct+k)->x
Inny sposób:
*(tab_struct[k]).x lub *(*(tab_struct+k)).x
DYNAMICZNE STRUKTURY DANYCH
1. Napisz program pozwalający na prowadzenie elektronicznej ewidencji
ilości książek podanej przez użytkownika. Wykorzystaj strukturę
zawierającą pola:
imię i nazwisko autora, tytuł książki, rok wydania. (Skorzystaj z tablicy
struktur, oraz dynamicznego przydziału pamięci).
2. Zmodyfikuj program z pkt. 1 poprzez napisanie funkcji pozwalających na:
- dopisanie kolejnych książek;
- przeszukiwanie tablicy pod kątem nazwiska autora lub roku wydania
(wypisywanie książek na ekran);