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;
}