10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
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Ä…
wskaz
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ć"<·ð Gdy tablica nie jest już potrzebna zwalniamy jÄ… za pomocÄ… zmiennej wskaz
nikowej:
delete[] wti;
1
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
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Ä… wskaz
nik typu void *,
wskazujący na jego początek. Typ void * oznacza, że wskaz
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Ä… wskaz
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 wskaz
nik typu void można przypisać wskaz
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));
2
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
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
#include
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;iscanf("%d",&tablica[i]);
/* ... dalsze przetwarzanie danych */
.....
/* tutaj powinno się zwolnić pamięć */
free (tablica);
}
/* ... dalsze przetwarzanie */
return 0;
}
3
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
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
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
#include
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);
}
}
4
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
·ð PrzykÅ‚ad 3 - wÅ‚asna obsÅ‚uga zgÅ‚oszonego wyjÄ…tku
#include
#include
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
#include
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();
}
}
5
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
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
#include
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=\""<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 wskaz
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;
}
6
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
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 .
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
#include
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=\""<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Ä… wskaz
ników.
7
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
Przykłady list
·ð Lista jednokierunkowa (ang. singly-linked list)
pierwszy (głowa, ang.head) ostatni (ogon, ang.tail)
dowiÄ…zanie dowiÄ…zanie dowiÄ…zanie
NULL
dane dane dane
·ð Lista dwukierunkowa (ang. doubly-linked list)
pierwszy ostatni
dowiÄ…zanie dowiÄ…zanie dowiÄ…zanie
NULL
dowiÄ…zanie dowiÄ…zanie dowiÄ…zanie
NULL
dane dane dane
·ð Lista cykliczna (ang. circular list)
pierwszy (głowa, ang.head) ostatni (ogon, ang.tail)
dowiÄ…zanie dowiÄ…zanie dowiÄ…zanie
dane dane dane
Typy komórek w liście z dowiązaniami
·ð DostÄ™p do listy: za pomocÄ… wskaz
nika do pierwszego elementu.
·ð Dwa typy komórek: komórka wskazujÄ…ca poczÄ…tek listy i komórka, bÄ™dÄ…ca elementem listy
2
n
1 3
NULL



Wskaz
nik na
Węzeł
poczÄ…tek
listy
listy(głowa)
8
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
10.6.1 Tworzenie listy z dowiÄ…zaniami
Definicja struktury dla węzła listy
struct Wezel
{ int liczba; // wartość w węz
le
struct Wezel * nast; // wskaz
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ęz
le
Wezel * nast; // wskaz
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 wskaz
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ęz
le listy
nowy->liczba = i;
9
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
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
// znajdz
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; idrukuj(a[i]);
Lista
Wezel *biezacy;
for (biezacy=glowa; biezacy; biezacy=biezacy->nast)
drukuj(biezacy->dane);
10
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
Usuwanie węzła listy
// znajdz
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);
11
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
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;
}
}
12
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
·ð 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;
// Znajdz
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;
}
13
10. Dynamiczne przydzielanie pamięci
materiały: dr inż. Bożena A
opuch
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;
}
14