LABORATORUL 09

Alocare dinamică de memorie

Durată: 2 ore Bibliotecă: stdlib.h Precedent: Laboratorul 8 PDF îndrumar EN English version

Până acum, dimensiunea datelor era fixată la scrierea programului. Alocarea dinamică permite stabilirea ei în timpul execuției, cerând memorie exact atunci când este nevoie și eliberând-o când nu mai este utilă.

1Obiectivele lucrării

  • Distingerea alocării statice, automate și dinamice
  • Utilizarea funcțiilor malloc, calloc, realloc și free
  • Verificarea obligatorie a reușitei alocării
  • Identificarea și prevenirea pierderilor de memorie
  • Folosirea operatorilor new și delete din C++

2De ce este necesară alocarea dinamică

La declararea unui tablou, dimensiunea trebuie să fie o constantă cunoscută la compilare. Aceasta duce la două probleme opuse:

SituațieConsecință
Se declară un tablou mult mai mare decât e nevoiememorie ocupată inutil
Numărul real de elemente depășește dimensiunea declaratătrebuie modificat codul și recompilat
SoluțiaSe stabilește dimensiunea în momentul execuției, când numărul de elemente este cunoscut, se alocă exact atât cât trebuie, iar la final memoria se eliberează pentru a putea fi refolosită în alt scop.

3Segmentele de memorie

Memoria unui program este împărțită în zone specializate, adresate prin regiștri de segment (CS, DS, ES, SS):

ZonăCe conțineCând se alocăCând se eliberează
Segment de cod (CS)instrucțiunile executabilela încărcarea programuluila terminare
Segment de date (DS)variabile globale și staticela încărcarela terminare
Stivă (SS)variabile locale, parametri, adrese de revenirela intrarea în blocautomat, la ieșire
Heapdate alocate dinamicla apelul malloc / newmanual, prin free / delete
Segment de cod - instrucțiuni Date statice - globale, static HEAP - alocare dinamică crește în sus ↑ (malloc / new) crește în jos ↓ (apeluri de funcții) STIVĂ - variabile locale adrese mici adrese mari alocare manuală alocare automată
Fig. 1 - Organizarea memoriei unui program în execuție

4Funcțiile de alocare din C

FuncțiePrototipEfect
mallocvoid* malloc(size_t n)alocă n octeți, neinițializați
callocvoid* calloc(size_t nr, size_t dim)alocă nr×dim octeți, puși pe zero
reallocvoid* realloc(void* p, size_t n)redimensionează o zonă deja alocată
freevoid free(void* p)eliberează zona indicată
tiparul corect de utilizare
int *v = (int *)malloc(n * sizeof(int));   // 1. alocare

if (v == NULL) {                            // 2. VERIFICARE obligatorie
    printf("Memorie insuficienta!\n");
    return 1;
}

/* ... utilizare ... */                     // 3. folosire

free(v);                                    // 4. eliberare
v = NULL;                                   // 5. evita folosirea accidentala
Verificarea nu este opționalăDacă sistemul nu poate satisface cererea, malloc returnează NULL. Folosirea rezultatului fără verificare duce la dereferențierea unui pointer nul și oprirea brutală a programului.
realloc - atenție la pointerul returnatFuncția poate muta blocul la altă adresă. Nu scrieți niciodată v = realloc(v, ...) direct: dacă alocarea eșuează, se returnează NULL, iar adresa veche se pierde definitiv. Folosiți o variabilă temporară.

5Simulator: pointer către zona alocată

Selectați ținta pentru a vedea diferența dintre un pointer valid, unul care indică spre altă zonă și unul pus pe NULL după eliberare.

Pointer, heap și starea NULL
De ce se pune pointerul pe NULL după freeDupă eliberare, pointerul păstrează adresa veche, dar zona nu mai este a noastră. Un free repetat pe aceeași adresă produce coruperea structurilor interne ale alocatorului. Atribuirea v = NULL transformă o eroare subtilă într-una imediat vizibilă.

6Operatorii new și delete din C++

OperațieCC++
Alocare pentru o valoarep = (int*)malloc(sizeof(int));p = new int;
Alocare cu inițializarealocare + atribuire separatăp = new int(42);
Alocare pentru un tablouv = (int*)malloc(n*sizeof(int));v = new int[n];
Eliberare valoarefree(p);delete p;
Eliberare tabloufree(v);delete[] v;
Nu amestecați cele două mecanismeMemoria obținută cu malloc se eliberează cu free; cea obținută cu new, cu delete. Pentru tablouri se folosește obligatoriu delete[] - altfel destructorii elementelor nu se apelează.
Avantajele lui newNu necesită conversie explicită de tip, calculează singur dimensiunea, apelează constructorii pentru obiecte și, la eșec, generează o excepție în loc să returneze NULL în tăcere.

7Erori clasice

EroareCauzăEfect
Memory leaklipsa freeconsum crescător de memorie; programele lungi ajung să epuizeze sistemul
Double freeeliberare de două oricorupere internă a alocatorului, oprire imprevizibilă
Use after freeacces după eliberaredate aleatoare sau blocare; vulnerabilitate de securitate
Buffer overflowscriere peste dimensiunea alocatăsuprascrierea structurilor vecine din heap
Alocare neverificatălipsa testului == NULLdereferențierea unui pointer nul
Regula de aurFiecare malloc trebuie să aibă exact un free corespunzător, iar fiecare new exact un delete. Scrieți-le pereche, chiar în momentul alocării, ca să nu le uitați.

8Cod sursă

vector_dinamic.c - dimensiune stabilită la execuție
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n;

    printf("Cate elemente? ");
    if (scanf("%d", &n) != 1 || n <= 0) {
        printf("Valoare invalida\n");
        return 1;
    }

    int *v = (int *)malloc(n * sizeof(int));   // alocare exacta
    if (v == NULL) {                            // verificare obligatorie
        printf("Alocare esuata!\n");
        return 1;
    }

    for (int i = 0; i < n; i++) {
        printf("v[%d] = ", i);
        scanf("%d", &v[i]);
    }

    long suma = 0;
    for (int i = 0; i < n; i++) suma += v[i];

    printf("\nSuma = %ld, media = %.3f\n", suma, (double)suma / n);

    free(v);        // eliberare
    v = NULL;       // protectie impotriva folosirii accidentale

    return 0;
}
redimensionare.c - realloc folosit corect
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int capacitate = 4, nr = 0;
    int *v = (int *)malloc(capacitate * sizeof(int));
    if (!v) return 1;

    printf("Introduceti numere (0 = stop):\n");

    int x;
    while (scanf("%d", &x) == 1 && x != 0) {

        if (nr == capacitate) {                 // s-a umplut: dublam capacitatea
            capacitate *= 2;

            int *temp = (int *)realloc(v, capacitate * sizeof(int));
            if (temp == NULL) {                 // NU atribuim direct lui v!
                printf("Redimensionare esuata\n");
                free(v);
                return 1;
            }
            v = temp;
            printf("  [capacitate marita la %d]\n", capacitate);
        }
        v[nr++] = x;
    }

    printf("\nAti introdus %d valori: ", nr);
    for (int i = 0; i < nr; i++) printf("%d ", v[i]);
    printf("\n");

    free(v);
    return 0;
}
matrice_dinamica.c - tablou bidimensional alocat dinamic
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int linii, coloane;

    printf("Linii si coloane: ");
    scanf("%d %d", &linii, &coloane);

    // 1. tablou de pointeri catre linii
    int **m = (int **)malloc(linii * sizeof(int *));
    if (!m) return 1;

    // 2. cate o linie pentru fiecare pointer
    for (int i = 0; i < linii; i++) {
        m[i] = (int *)malloc(coloane * sizeof(int));
        if (!m[i]) {                          // eliberam ce am alocat deja
            for (int k = 0; k < i; k++) free(m[k]);
            free(m);
            return 1;
        }
    }

    for (int i = 0; i < linii; i++)
        for (int j = 0; j < coloane; j++)
            m[i][j] = (i + 1) * (j + 1);      // tabla inmultirii

    for (int i = 0; i < linii; i++) {
        for (int j = 0; j < coloane; j++) printf("%5d", m[i][j]);
        printf("\n");
    }

    // eliberare in ordine INVERSA alocarii
    for (int i = 0; i < linii; i++) free(m[i]);
    free(m);

    return 0;
}
new_delete.cpp - varianta C++
#include <iostream>
using namespace std;

int main()
{
    int n;
    cout << "Cate elemente? ";
    cin >> n;

    int *v = new int[n];              // fara conversie, fara sizeof

    for (int i = 0; i < n; i++) v[i] = (i + 1) * (i + 1);

    for (int i = 0; i < n; i++) cout << v[i] << " ";
    cout << endl;

    delete[] v;                       // OBLIGATORIU cu paranteze patrate

    // alocare cu initializare
    int *p = new int(42);
    cout << "*p = " << *p << endl;
    delete p;                         // fara paranteze, pentru o singura valoare

    return 0;
}

9Atelier de cod

În modul Pas cu pas, panoul din dreapta are o secțiune heap: acolo apar blocurile alocate cu malloc și se vede exact când devin „eliberate”.

Un vector a cărui dimensiune se află la execuție
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n, i, *v;

    printf("Cate elemente? ");
    scanf("%d", &n);

    v = (int*) malloc(n * sizeof(int));
    if (v == NULL) {
        printf("Alocare esuata\n");
        return 1;
    }

    for (i = 0; i < n; i++) v[i] = (i + 1) * (i + 1);

    printf("Patratele primelor %d numere: ", n);
    for (i = 0; i < n; i++) printf("%d ", v[i]);
    printf("\n");

    free(v);
    return 0;
}
De încercatȘtergeți linia free(v); și rulați din nou: programul funcționează la fel. Tocmai de aceea scurgerile de memorie sunt periculoase - nu se văd. Acum mutați free(v); înainte de bucla de afișare și veți primi o eroare clară.
Exercițiu - realloc și eliberare corectă
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *v, i;

    v = (int*) malloc(3 * sizeof(int));
    for (i = 0; i < 3; i++) v[i] = i + 1;

    /* Mariti zona la 6 elemente folosind realloc,
       apoi completati elementele 3, 4, 5 cu valorile 4, 5, 6.
       Nu uitati sa verificati rezultatul lui realloc. */

    for (i = 0; i < 6; i++) printf("%d ", v[i]);
    printf("\n");

    free(v);
    return 0;
}

10Exerciții cu verificare automată

Aici scrieți voi codul. Butonul ✓ Verifică rulează programul pe mai multe seturi de date și vă arată imediat unde diferă rezultatul. La final trimiteți traseul ales, iar profesorul îl notează automat.

Fiecare exercițiu are programul deja început, iar comentariile vă spun ce mai trebuie adăugat. Scrieți codul, apăsați ✓ Verifică și citiți ce spune fiecare test picat. Dacă v-ați blocat, deschideți câte un indiciu. Puteți afișa și mesaje pentru utilizator (de tipul Introduceti n:), testul se uită la ce afișați la final.

P1

Vector alocat dinamic

Citiți n (1 ≤ n ≤ 10 000), alocați cu malloc un vector de n întregi, citiți valorile în el și afișați suma lor. La final eliberați memoria.

intrare3 1 2 3
ieșire6
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n, i;
    long long s = 0;
    int *v;
    scanf("%d", &n);

    /* 1. v = (int *)malloc(n * sizeof(int));
       2. verificați că v nu este NULL;
       3. citiți cele n valori în v[i] și adunați-le la s;
       4. free(v); */

    printf("%lld\n", s);
    return 0;
}
P2

calloc pornește de la zero

Citiți n și alocați cu calloc un vector de n întregi (toate devin 0). Apoi citiți k perechi poziție valoare și scrieți valorile la pozițiile date. Afișați vectorul.

intrare5 2 1 7 3 9
ieșire0 7 0 9 0
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n, k, i, poz, val;
    int *v;
    scanf("%d", &n);

    /* v = (int *)calloc(n, sizeof(int));  - spre deosebire de malloc,
       calloc umple zona cu zerouri.
       Citiți k, apoi de k ori: poz val, și puneți v[poz] = val.
       Afișați cele n elemente și eliberați memoria. */

    return 0;
}
P3

Copia exactă a unui șir

Citiți un cuvânt. Alocați dinamic exact câți octeți îi trebuie unei copii (inclusiv '\0'), copiați cuvântul cu strcpy și afișați copia și numărul de octeți alocați.

intraremere
ieșiremere 5
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    char s[101];
    char *copie;
    int dim;
    scanf("%100s", s);

    /* dim = strlen(s) + 1;   - +1 pentru terminatorul '\0'
       copie = (char *)malloc(dim);
       strcpy(copie, s);
       printf("%s %d\n", copie, dim);   apoi free(copie); */

    return 0;
}
P4

new și delete[] în C++

În C++, citiți n, alocați cu new un vector de n valori reale, citiți-le și afișați media cu două zecimale. Eliberați memoria cu delete[].

intrare3 1.5 2.5 3.5
ieșire2.50
#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    int n;
    double s = 0;
    cin >> n;

    /* double *v = new double[n];
       citiți v[i] cu cin și adunați-le la s;
       cout << fixed << setprecision(2) << s / n << endl;
       delete[] v;   - cu paranteze drepte, pentru că e un vector */

    return 0;
}
P5

Un vector care crește cu realloc

Citiți numere întregi până la valoarea 0 (care nu face parte din date). Păstrați-le într-un vector alocat dinamic care își dublează capacitatea cu realloc când se umple. Afișați câte numere sunt, apoi numerele în ordine inversă.

intrare5 8 2 0
ieșire3 2 8 5
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int cap = 2, n = 0, x, i;
    int *v = (int *)malloc(cap * sizeof(int));

    /* Cât timp citiți un x diferit de 0:
         - dacă n == cap, dublați cap și v = realloc(v, cap * sizeof(int));
         - v[n++] = x;
       La final: printf("%d\n", n); apoi elementele de la v[n-1] la v[0]. */

    free(v);
    return 0;
}

Problemele pornesc de la un main gol. Formatul ieșirii trebuie respectat exact (spațiile și rândurile noi nu contează, dacă enunțul nu spune altfel), deci nu afișați mesaje pentru utilizator. Testele vizibile acoperă doar cazurile simple; la notare se rulează și teste ascunse, alese să prindă cazurile limită.

A1

Matrice alocată dinamic

Citiți n m (1 ≤ n, m ≤ 100) și o matrice n × m de întregi, alocată dinamic ca vector de pointeri către rânduri. Afișați suma fiecărei coloane, pe un rând. Eliberați corect memoria.

intrare2 3 1 2 3 4 5 6
ieșire5 7 9
#include <stdio.h>

int main(void)
{
    /* scrieți aici rezolvarea */

    return 0;
}
A2

Lipirea cuvintelor

Citiți n (1 ≤ n ≤ 100) și apoi n cuvinte (fiecare cel mult 50 de litere). Construiți un șir alocat dinamic, de lungime exactă, care conține cuvintele unite prin -. Afișați șirul și lungimea lui.

intrare3 unu doi trei
ieșireunu-doi-trei 12
#include <stdio.h>

int main(void)
{
    /* scrieți aici rezolvarea */

    return 0;
}
A3

Interclasare

Citiți un vector sortat crescător de n întregi, apoi altul de m întregi (pe fiecare rând întâi lungimea). Alocați dinamic un vector de n + m elemente, interclasați-i în el și afișați rezultatul.

intrare3 1 4 9 2 2 5
ieșire1 2 4 5 9
#include <stdio.h>

int main(void)
{
    /* scrieți aici rezolvarea */

    return 0;
}
A4

Triunghiul lui Pascal

Citiți n (1 ≤ n ≤ 30). Alocați dinamic un „triunghi”: rândul i are exact i + 1 elemente. Completați triunghiul lui Pascal și afișați primele n rânduri.

intrare4
ieșire1 1 1 1 2 1 1 3 3 1
#include <stdio.h>

int main(void)
{
    /* scrieți aici rezolvarea */

    return 0;
}

11Sarcini de lucru

  • Alocați dinamic un vector de dimensiune citită de la tastatură și calculați suma și media.
  • Verificați ce returnează malloc pentru o cerere absurd de mare (de exemplu 10¹⁰ octeți).
  • Comparați conținutul zonelor obținute cu malloc și cu calloc, imediat după alocare.
  • Implementați un vector care își dublează capacitatea prin realloc când se umple.
  • Alocați dinamic o matrice și eliberați-o corect, în ordinea inversă alocării.
  • Omiteți intenționat free într-o buclă și observați creșterea memoriei în Task Manager.
  • Rescrieți unul dintre programe în C++, folosind new și delete[].

12Aplicație de aprofundare

ExtindereImplementați o listă simplu înlănțuită de numere întregi, cu alocare dinamică pentru fiecare nod: adăugare la început și la sfârșit, ștergerea unui element după valoare, afișarea listei și eliberarea completă a memoriei. Verificați cu un contor global că numărul de apeluri malloc este egal cu numărul de apeluri free la terminarea programului.

13Întrebări de verificare

14Resurse