10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

1

10 Dynamiczne przydzielanie pamięci

10.1 Przydzielanie pamięci w języku C++



Do przydzielania pamięci służy operator new.

DowolnyTyp *ZmiennaWskaznikowa=new TypZmiennej;



Domyślnie obszar przydzielonej pamięci nie jest zainicjowany.



Pamięć jest przydzielona do momentu zwolnienia jej. Do zwalniania przydzielonej pamięci służy operator
delete

. Postać instrukcji zależy od tego, czy mamy do czynienia ze zmienną prostą czy tablicą.



Obiekt utworzony za pomocą operatora new nie ma nazwy. Można na nim operować tylko za pomocą

wskaźników.



Jeśli nie można przydzielić pamięci, to:

o zwracany jest adres 0 (sposób "dawny") ,
o

wyrzucany jest wyjątek bad_alloc, który jeśli nie będzie obsłużony spowoduje zakończenie programu,

o

można zdefiniować własną funkcję, która będzie obsługiwała taką sytuację.



Przykład 1: proste zmienne

int *wi = new int;
*wi = 5;
delete wi;



Przykład 2: tablice

// tablice jednowymiarowe

int *wti = new int [100];
int *wti3 = new int[ile];
int *wti4 = new int[pobierzWymiar()];



Jeżeli chcemy zainicjować elementy tablicy w pamięci przydzielanej dynamicznie, musimy przypisać wartości
poszczególnym elementom.

int *wtab = new int[100];
if (wtab != 0)

for (int i=0; i<100; ++i)

wtab[i]=100;

else

cout << "Tablicy nie udało się utworzyć"<<endl;



Gdy tablica nie jest już potrzebna zwalniamy ją za pomocą zmiennej wskaźnikowej:

delete[] wti;

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

2

10.2 Przydzielanie pamięci w stylu języka C



Funkcje związane z dynamicznym przydzielaniem pamięci wymagają dołączenia pliku nagłówkowego:
stdlib.h



Funkcje przydzielania (ang. allocate) pamięci:

/* przydzielenie pamięci o wielkości równej liczba_bajtów */
void* malloc(size_t liczba_bajtów)

/* przydzielenie pamięci o wielkości równej
liczba_elementów*liczba_bajtów_jednego_elementu */
void* calloc(size_t liczba_elementów, size_t liczba_bajtów)

/* zmiana wielkości przydzielonej wcześniej pamięci
wskazywanej przez wsk – zwraca adres przydzielonego obszaru – może być

inny */

void* realloc(void *wsk, size_t liczba_bajtów)



Funkcja zwalniania (ang. free) pamięci przydzielonej za pomocą malloc(), calloc(), realloc():

void free(void *wsk)



Funkcje przydzielania pamięci przydzielają programowi blok pamięci i zwracają wskaźnik typu void *,
wskazujący na jego początek. Typ void * oznacza, że wskaźnik ten może być przypisany do dowolnego
typu.



Jeżeli nie ma odpowiedniej ilości wolnego miejsca w pamięci, to funkcje te zwracają wskaźnik zerowy
(NULL)

Przykład 1.



W funkcji malloc() trzeba podać liczbę bajtów przydzielanego obszaru pamięci.

/* przydzielenie pamięci dla tablicy typu char o 1000 elementach */
char *p;
p=(char *)malloc(1000); /* znak zajmuje jeden bajt */
/* przydzielenie pamięci dla tablicy typu int o 100 elementach */
int *p1;
p1=(int *)malloc(100*sizeof(int)); /* int zajmuje sizeof(int) bajtów */



Uwaga: W ANSI C wskaźnik typu void można przypisać wskaźnikowi dowolnego typu. Oznacza to, że
można pominąć rzutowanie. W starszych wersjach C rzutowanie było konieczne. Obydwa zapisy są
akceptowane w ANSI C. W C++ wymagane jest jawne rzutowanie.

char *p1, *p2;
p1=malloc(1000); // konwersja automatyczna do char *
p=(char *)malloc(1000); // rzutowanie

Przykład 2.



W funkcji calloc() trzeba podać liczbę elementów i rozmiar pojedynczego elementu. Dodatkowo funkcja

ta wstawia 0 do przydzielonego obszaru.

/* przydzielenie pamięci dla tablicy typu char o 1000 elementach */
char *p;
p=(char *)calloc(1000,sizeof(char)); /* znak zajmuje jeden bajt */
/* przydzielenie pamięci dla tablicy typu int o 100 elementach */
int *p1;
p1=(int *)calloc(100,sizeof(int));

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

3

Przykład 3.



Funkcja realloc() zmienia wielkość przydzielonego wcześniej obszaru pamięci. Nowo przydzielany

obszar pamięci może być większy lub mniejszy od dotychczasowego obszaru.

char *p;
p=(char *)malloc(10);
p=(char *)realloc(p,12);

Przykład 4.

#include <stdio.h>
#include <stdlib.h>

int main() {

int i, ile, *tablica;
printf("Podaj ilosc danych: " );
scanf("%d",&ile);
if (ile>0) {

tablica=(int *) malloc(ile*sizeof(int));
if (!tablica)

{ printf("Zbyt mala ilosc pamieci\n"); return 1; }

for (i=0;i<ile;++i)

scanf("%d",&tablica[i]);

/* ... dalsze przetwarzanie danych */
.....
/* tutaj powinno się zwolnić pamięć */
free (tablica);

}
/* ... dalsze przetwarzanie */
return 0;

}

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

4

10.3 Niepowodzenia przydziału pamięci



Niepowodzenia przydziału pamięci można obsługiwać za pomocą kilku metod:

o

Standard języka C++ przewiduje zgłoszenie wyjątku bad_alloc, gdy nie powiedzie się new.

o

Wiele kompilatorów nie jest jeszcze zgodnych z tym standardem, new w przypadku niepowodzenia
zwraca 0.

o

Standard języka C++ pozwala używać wersję new, która zwraca 0 w przypadku niepowodzenia, ale
trzeba to odpowiednio zgłosić kompilatorowi.

o

Można również wykorzystać do obsługi niepowodzeń new funkcję set_new_handler.



Przykład 1: w starym stylu ( w stylu języka C)

#include <iostream>
using namespace std;

void brak_pamieci(int licznik)
{

cerr << "Brak pamieci po " << licznik

<< " przydzialach"<< endl;

cin.get();
exit(1);

}

int main()
{

int *wsk;
int licznik;
while(1) {

licznik++;
wsk=new int[1000];
if (!wsk) brak_pamieci(licznik);

}

}



Przykład 2: w stylu C++, wyłączenie zgłaszania wyjątku

#include <iostream>
#include <new>
using namespace std;

void brak_pamieci(int licznik)
{

cerr << "Brak pamieci po " << licznik

<< " przydzialach"<< endl;

cin.get();
exit(1);

}

int main()
{

int *wsk;
int licznik;
while(1) {

licznik++;
wsk=new (nothrow) int[30000];
if (!wsk) brak_pamieci(licznik);

}

}

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

5



Przykład 3 - własna obsługa zgłoszonego wyjątku

#include <iostream>
#include <new>
using namespace std;

int licznik;

void brak_pamieci()
{

cerr << "Brak pamieci po " << licznik

<< " przydzialach"<< endl;

cin.get();
exit(1);

}

int main()
{

int *wsk;
set_new_handler(brak_pamieci);
while(1) {

licznik++;
wsk=new int[30000];

}

}



Przykład 4: w stylu języka C, wykorzystane funkcje przydziału pamięci przejęte z C

#include <iostream>
#include <cstdlib>
using namespace std;

int licznik=0;
void brak_pamieci()
{

cerr << "Brak pamieci po " << licznik
<< " przydzialach"<< endl;
exit(1);

}

int main()
{

int *wsk;
while(1) {

licznik++;
wsk = (int*)malloc(30000*sizeof(int));
if (!wsk) brak_pamieci();

}

}

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

6

10.4 Dynamiczne przydzielanie pamięci na napisy



Jeśli nie znamy najdłuższego napisu, to nie możemy z góry zarezerwować odpowiednio dużej tablicy.

#include <iostream>
#include <cstring>

int main(){

char bufor[256];
cout << "Wpisz teskt\n";
cin.getline(bufor,256);
int rozmiar=strlen(bufor);
char *tekst1=new char[rozmiar+1];
strcpy(tekst1,bufor);
cout << "tekst1=\""<<tekst1<<"\""<<endl;
cin.getline(bufor,256);
// dalszy ciąg programu
...
return 0;

}



Zamiast strcpy() można użyć funkcji memcpy(), patrz: Działania na obszarach pamięci



W wielu implementacjach kompilatorów zdefiniowana jest specjalna funkcja biblioteczna strdup, która
tworzy kopię napisu w dynamicznie przydzielonej pamięci. Funkcja ta ma następujący prototyp:

char *strdup(const char *s);

Tworzy kopię napisu s w pamięci dynamicznie przydzielonej; zwraca wskaźnik do kopii napisu



Przykładowa własna realizacja funkcji strdup() z przydzielaniem pamięci za pomocą operatora new:

char *strdup(const char *str)
{

int rozmiar=strlen(str)+1;
char *wynik=new char[rozmiar];
memcpy(wynik,str,rozmiar);
return wynik;

}

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

7

10.5 Działania na obszarach pamięci



Z definicji napis w stylu języka C zakończony jest znakiem '\0', tak więc tekst nie może zawierać tego
znaku.



Jeśli chcielibyśmy przetwarzać dane zawierające znaki '\0', na przykład kopiować, nie możemy stosować do
nich funkcji działających na napisach.



Istnieje zbiór funkcji o działaniu podobnym do działania funkcji napisowych, ale funkcje te operują na ciągu
bajtów.



Funkcje te wymagają dołączenia pliku nagłówkowego <cstring>.

void *memcpy(void *dest, const void *src, size_t n);

void *memmove(void *dest, const void *src, size_t n);

int *memcmp(const void *a, const void *b, size_t n);

void *memchr(const void *a, int c, size_t n);

void *memset(void *a, int c, size_t n);



Przykład:

#include <iostream>
#include <cstring>
using namespace std;

int main(){

char bufor[256];
cin.getline(bufor,256);
int rozmiar=strlen(bufor);
char *tekst1=new char[rozmiar+1];
memcpy(tekst1,bufor,rozmiar+1);
cout << "tekst1=\""<<tekst1<<"\""<<endl;
cin.getline(bufor,256);
...
return 0;

}

10.6 Lista dowiązaniowa



Zbiór elementów, z których każdy zawiera dane oraz łącze do następnego elementu nazywamy listą z
dowiązaniami (ang. linked list).



Element składowy listy przechowywany jest w niezależnym fragmencie pamięci nazywanym komórką (ang.
cell) lub węzłem (ang. node).



Związek pomiędzy elementami listy wyznaczany jest za pomocą wskaźników.

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

8

Przykłady list



Lista jednokierunkowa (ang. singly-linked list)



Lista dwukierunkowa (ang. doubly-linked list)



Lista cykliczna (ang. circular list)

Typy komórek w liście z dowiązaniami



Dostęp do listy: za pomocą wskaźnika do pierwszego elementu.



Dwa typy komórek: komórka wskazująca początek listy i komórka, będąca elementem listy

dowiązanie

dane

dowiązanie

dane

dowiązanie

dane

pierwszy (głowa, ang.head)

NULL

ostatni (ogon, ang.tail)

dowiązanie

dowiązanie

dowiązanie

dowiązanie

dowiązanie

dowiązanie

pierwszy

NULL

ostatni

dane

dane

dane

NULL

dowiązanie

dane

dowiązanie

dane

dowiązanie

dane

pierwszy (głowa, ang.head)

ostatni (ogon, ang.tail)

●

NULL

n

●

1

●

2

●

3

Wskaźnik na
początek
listy(głowa)

Węzeł
listy

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

9

10.6.1 Tworzenie listy z dowiązaniami

Definicja struktury dla węzła listy

struct Wezel
{ int liczba;

// wartość w węźle

struct Wezel * nast; // wskaźnik do następnego węzła
};



Nie definiujemy na razie zmiennych, bo pamięć będzie przydzielana dynamicznie dla każdego elementu listy.

Uwaga: w C++ po wprowadzeniu nowego typu strukturalnego można się odnosić do niego z pominięciem słowa
struct

. Zatem w języku C++ poprawny będzie również zapis uproszczony:

struct Wezel
{ int liczba;

// wartość w węźle

Wezel * nast; // wskaźnik do następnego węzła

};

Definicja zmiennej przechowującej adres początku listy



Musimy zdefiniować zmienną, w której będzie przechowywany adres początku listy.

Wezel *glowa; // zmienna typu wskaźnik do struktury opisującej węzeł

Utworzenie pustej listy



Pusta lista to lista, której adres jest równy 0 (NULL):

glowa=NULL;

Wstawianie nowego węzła



Etapy:

o

przydzielenie pamięci na nowy węzeł listy

o

wstawienie do węzła przechowywanej w nim wartości

o dodanie do listy:



pustej



na początek istniejącej listy



na koniec istniejącej listy



w wybranym miejscu

Przydzielanie pamięci na nowy węzeł listy

Wezel *nowy;

nowy = new Wezel; // jezyk C++

nowy = (struct Wezel) malloc(sizeof (struct Wezel)); // język C

Wstawienie wartości przechowywanej w nowym węźle listy

nowy->liczba = i;

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

10

Dodanie nowego węzła do listy



Przypadek 1: Wstawienie węzła do pustej listy

nowy->nast = 0; /* pierwszy i ostatni element listy */
glowa = nowy; /* głowa wskazuje na nowy



Przypadek 2: Wstawienie węzła na początek listy

nowy->nast = glowa; // nowy wskazuje na poprzedni początek listy
glowa = nowy; // głowa wskazuje na nowy



Przypadek 3: Wstawienie węzła na końcu listy

Wezel * biezacy
biezacy = glowa; // adres początku listy

// znajdź ostatni wezeł listy
while (biezacy->nast)

biezacy = biezacy->nast;

// dodaj do listy nowy węzeł
biezacy->nast = nowy;

Przetwarzanie węzłów listy



Wyświetlanie wartości przechowywanych w węzłach listy

Tablica

int i;
for (i=0; i<n; i++)

drukuj(a[i]);

Lista

Wezel *biezacy;

for (biezacy=glowa; biezacy; biezacy=biezacy->nast)

drukuj(biezacy->dane);

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

11

Usuwanie węzła listy

// znajdź usuwany i jego adres umieść w zmiennej poprzedni
...
// usuń węzeł
usuwany=poprzedni->nast;
poprzedni->nast=usuwany->nast;
delete usuwany;

// język C++
// w języku C: free(usuwany);

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

12

10.7 Przykłady



Przykład 1. Funkcja wstawia element na początku listy

bool Wstaw( Wezel* &glowa, int dana )
{

Wezel *nowy;

// 1. Przydziel pamięć na nowy węzeł
nowy = new Wezel;
if( !nowy )

return false; // brak pamięci

// 2. Skopiuj dane do nowego węzła

nowy->liczba = dana;

// 3. Dołącz nowy węzeł na początku listy

nowy->nast = glowa;
glowa=nowy;

return true;

}



Przykład 2. Dana jest lista posortowana rosnąco. Zadaniem funkcji jest wstawienie elementu we właściwej
pozycji. Funkcja zwraca true, jeśli czynność ta się udała, false w przeciwnym wypadku. W funkcji
znajdują się błędy - zidentyfikuj je i popraw. Wskazówka: czy prawidłowo wstawiany jest element na końcu i
na początku listy?

bool Wstaw( Wezel *biezacy, int dana ) {

Wezel *poprzedni;
Wezel *nowy;

while( biezacy->liczba < dana ){

poprzedni = biezacy;
biezacy = biezacy->nast;

}

nowy = new Wezel;
if( nowy == NULL )

return false;

nowy->liczba = dana;
nowy->nast = biezacy;

poprzedni->nast = nowy;

return true;

}



Przykład 3. Funkcja przetwarza elementy listy, sposób przetwarzania jest określony za pomocą funkcji
przekazywanej w postaci argumentu

void Przetwarzaj(Wezel biezacy, void (* fun)(int liczba) ) {

while (biezacy) {

(*fun)(biezacy->liczba);
biezacy=biezacy->nast;
}

}

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

13



Przykład 4. Funkcja usuwa węzeł, w którym umieszczona jest określona wartość

bool Usun (Wezel* &glowa, int wartosc) {

Wezel *biezacy;
Wezel *poprzedni = 0;
biezacy = glowa;

// Znajdź węzeł do usunięcia, przechowuj adres poprzedniego węzeła
while (biezacy && (biezacy->liczba != wartosc)) {

poprzedni = biezacy;
biezacy = biezacy->nast;

}

// Nie znaleziono węzła do usunięcia
if (!biezacy)

return false;

// Odłącz węzeł z listy
if (poprzedni)

poprzedni->nast = biezacy->nast;

else

glowa = biezacy->nast;

// Usuń przydzieloną pamięć
delete biezacy;

return true;

}

10. Dynamiczne przydzielanie pamięci

materiały: dr inż. Bożena Łopuch

14

Przykład 5. Zapisywanie listy do pliku i czytanie listy z pliku - plik tekstowy

bool ZapiszListeT(char *Plik, Wezel *glowa) {

ofstream f;
f.open(Plik);
if (!f.good()) return false;

Wezel *biezacy;
for (biezacy=glowa; biezacy; biezacy=biezacy->nast)

f<< biezacy->dane << endl;

f.close();
return true;

}

Wezel *CzytajListeT(char *Plik) {

ifstream f;
f.open(Plik);
if (!f.good()) return 0;

Wezel *glowa=0;
int dane;
if (f>>dane) { // plik może być pusty

DodElement(dane,&glowa);
while (f>>dane)

DodElement(dane,&glowa);

}
f.close();
return glowa;

}



Przykład 6. Zapisywanie listy do pliku i czytanie listy z pliku - plik binarny

bool ZapiszListeB(char *Plik, Wezel *glowa) {

ofstream f;
f.open(Plik,ios::out|ios::binary);
if (!f.good()) return false;

Wezel *biezacy;
for (biezacy=glowa; biezacy; biezacy=biezacy->nast)

f.write((char *)&(biezacy->dane), sizeof(biezacy->dane));

f.close();
return true;

}

Wezel *CzytajListeB(char *Plik) {

ifstream f;
f.open(Plik,ios::in|ios::binary|ios::nocreate);
if (!f.good()) return 0;

Wezel *glowa=0;
int dane;
if (f.read((char *)&dane, sizeof(dane)))
{

DodElement(dane,&glowa);
while (f.read((char *)&dane,sizeof(dane)))

DodElement(dane,&glowa);

}
f.close();

return glowa;

}