8.8. Alocarea dinamica a memoriei

2019/03/17 in Programare in C

Limbajul C permite utilizatorului sa aloce date atat pe stiva (date automatice), cat si in zonele de memorie care nu apartin stivei (date globale sau statice).

Alocarea datelor pe stiva se face la executie si ea nu este permanenta. Astfel, daca declaratia tip nume; se utilizeaza in corpul unei functii, atunci variabila nume se aloca pe stiva la fiecare apel al functiei respective. La revenirea din functie, stiva se "curata" (se reduce la starea avuta inaintea apelului) si prin aceasta, variabila nume nu mai este alocata (devine nedefinita). O alocare de acest fel a memoriei se spune ca este dinamica.

Pentru datele globale sau statice, memoria este alocata in fazele precedente executiei si alocarea ramane valabila pana la terminarea executiei programului. De aceea, pentru datele de acest fel se spune ca alocarea este statica (nu este dinamica).

Limbajele C si C++ ofera utilizatorului posibilitatea de a aloca dinamic memorie si in alt mod decat cel indicat mai sus pentru datele automatice. Aceasta se realizeaza intr-o zona de memorie speciala, distincta de stiva. Aceasta zona de memorie se numeste memorie heap (memorie gramada, morman, de acumulare etc.) Ea poate fi gestionata prin functii standard in ambele limbaje.

Mai jos indicam cateva functii care pot fi utilizate la alocarea dinamica a datelor in memoria heap. Aceste functii sunt comune ambelor limbaje. In C++ exista chiar operatori pentru alocari dinamice in memoria heap.

Functiile standard pentru gestionarea memoriei heap au prototipurile in fisierul alloc.h

NOTA: Compilatorul gnu gcc a eliminat fisierul <alloc.h> si l-a inclus in <stdlib.h>

Alocarea unei zone de memorie in memoria heap se poate realiza cu ajutorul mai multor functii. O functie utilizata frecvent este functia malloc. Aceasta are prototipul:

void *malloc(unsigned n);

Functia aloca in memoria heap o zona contigua de n octeti. Ea returneaza adresa de inceput a zonei alocate. Aceasta adresa reprezinta un pointer de tip void (void *). Prin intermediul acestuia se pot pastra date in zona de memorie alocata in acest fel. Pentru a pastra o data de un tip dat intr-o zona de memorie alocata prin malloc este necesar sa convertim adresa returnata de functie spre tipul datei respective.

Exemplu:

Se cere sa se aloce in memoria heap o zona de memorie pentru a pastra n valori de tip int. In acest scop, declaram un pointer spre tipul int:

int *p;

Apoi, apelam functia malloc cu ajutorul expresiei de atribuire:

p = (int *)malloc(n*sizeof(int));

Se observa ca valoarea returnata de functia malloc a fost convertita spre tipul int *, adica pointer spre int.

In continuare putem pastra si utiliza date de tip int, folosind pointerul p. De exemplu, expresia:

*p = 123;

pastreaza intregul 123 in primii doi octeti ai zonei alocate prin expresia de mai sus.

Expresia:

y = *p;

atribuie lui y valoarea pastrata mai sus in memoria heap.

In general, expresia:

*(p + i) = k

atribuie valoare lui k in zona de memorie de adresa definita prin expresia pointer p + i. Aceeasi expresie se poate utiliza pentru a face acces la data respectiva.

Observatii:

  1. Functia malloc are ca parametru un intreg fara semn, adica acesta trebuie sa apartina intervalului [0, 65535];
  2. In cazul in care in memoria heap nu se poate aloca o zona de memorie de atatia octeti cat este valoarea parametrului de la apel, se va returna pointerul nul, adica valoarea zero.

De aceea, dupa apelul functiei malloc vom testa valoarea returnata pentru a ne asigura ca aceasta nu este zero.

Zonele alocate prin functia malloc pot fi eliberate, pentru a putea fi eventual realocate, folosind functia standarad free. Aceasta are prototipul:

void free(void *p);

Prin apelul ei se elibereaza zona de memorie din memoria heap, spre care pointeaza p. Mentionam ca valoarea lui p trebuie sa fie obtinuta printr-un apel al unei functii standard de alocare, cum este de exemplu functia malloc.

Se recomanda ca aceasta functie sa fie apelata de indata ce datele dintr-o zona de memorie heap nu mai sunt necesare.

In felul acesta zona respectiva poate fi ulterior realocata. De asemenea, eliberarea sistematica a zonelor din memoria heap poate preveni faramitarea excesiva a memoriei heap.

O alta functie standard utila pentru a aloca zone de memorie in memoria heap este functia calloc. Ea are prototipul:

void *calloc(unsigned nrelem, unsigned dimelem);

Functia aloca o zona de memorie de nrelem*dimelem octeti.

Ca si functia malloc, functia calloc returneaza valoarea de inceput a zonei de memorie alocata, adresa care reprezinta un pointer spre void.

In cazul in care nu se pot aloca nrelem*dimelem octeti, functia returneaza valoarea zero.

Elementele unei zone de memorie alocata prin calloc sunt initializate cu valoarea zero.

Zona de memorie alocata cu ajutorul functiei calloc se elibereaza folosind functia free indicata mai sus.

Pentru programe relativ mici, pointerii se pastreaza pe 16 biti. Aceasta inseamna ca ei pot pastra adrese de pana la 64k. Despre un astfel de pointer se spune ca este de tip near.

Programele mai complexe, care necesita adrese mai mari de 64k, utilizeaza pointeri alocati pe 32 biti. Despre un astfel de pointer se spune ca este de tip far.

Biblioteca standard contine functii pentru a aloca in memoria heap zone de memorie a caror adrese se reprezinta in memoria heap pe mai mult de 16 biti. De asemenea, dimensiunea unei astfel de zone de memorii poate depasi 64k. Astfel, pentru a aloca in memoria heap zone de memorie de adrese mai mari ca 64k, putem folosi functiile farmalloc si farcalloc, functii analoge cu functiile malloc, respectiv calloc, indicate mai sus.

Functia farmalloc are prototipul:

void far *farmalloc(unsigned long n);

Ea se utilizeaza la fel ca si functia malloc. In acest caz, functia returneaza un pointer de tip far (se aloca pe 32 biti). De asemenea, la apelul functiei farmalloc, parametrul n poate depasi 64k = 65536.

Zona alocata cu ajutorul functiei farmalloc se elibereaza apeland functia free. Ea are prototipul:

void farfree(void far *p);

Exercitii:

8.15. Sa se scrie o functie care pastreaza un sir de caractere intr-o zona de memorie alocata in memoria heap.

Functia returneaza adresa de inceput a zonei in care se pastreaza sirul de caractere sau zero (pointerul nul), in cazul in care nu se poate rezerva zona respectiva in memoria heap.

char *memsir(char *s)
/* pastreaza in memoria heap 
sirul de caractere spre care 
se pointeaza */
{
  char *p;

  if((p = (char *)malloc(strlen(s) + 1)) != 0) {
/* p are ca valoare adresa 
de inceput a zonei de 
memorie rezervata in 
memoria heap si care are 
strlen(s) + 1 octeti */

    strcpy(p, s);
/* copiaza sirul spre care 
pointeaza s, in zona spre care 
pointeaza p */

    return p;
  }
  else
    return 0;
/* pointerul nul; 
nu s-a putut aloca zona necesara 
pentru a putea pastra sirul s */
}

Observatii:

  1. Functia de fata returneaza un pointer spre caractere, deci tip din antetul ei este char *
  2. Conditia din paranteza lui if se poate scrie si fara partea != 0, adica
    if(p = (char *)malloc(strlen(s)+1))
    Apelul strlen(s) determina numarul de octeti necesari pentru a pastra caracterele proprii ale sirului spre care pointeaza s.
    Numarul returnat de functia strlen se mareste cu 1 pentru a aloca un octet pentru caracterul NUL care trebuie sa termine orice sir de caractere.
  3. Apelul strcpy(p, s); copiaza caracterele sirului, inclusiv caracterul NUL, in zona de memorie a carei adresa de inceput este valoarea lui p.

8.16. Sa se scrie un program care citeste o succesiune de cuvinte si il afiseaza pe cel mai lung dintre ele.

Un astfel de program este descris la exercitiul 8.13. In programul respectiv, cuvantul maxim se pastreaza in tabloul cuvmax alocat pe stiva. In programul de fata se va pastra cuvantul maxim in memoria heap.

NOTA: Programul de mai jos utilizeaza fisierul header <stdlib.h> in locul lui <alloc.h> pentru ca compilatorul gnu gcc a eliminat fisierul <alloc.h>.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "FUNCTIA101.C";

#define MAX 100

main()
/* citeste o succesiune de cuvinte 
si il afiseaza pe cel mai mare */
{
    char cuvcrt[MAX+1];
    char *cuvmax = 0;
/* pointeaza spre cuvantul maxim; 
initial are ca valoare pointerul nul */

    while(scanf("%100s", cuvcrt) != EOF)
      if(cuvmax == 0) /* prima citire */
        cuvmax = memsir(cuvcrt);
      else
        if(strcmp(cuvcrt, cuvmax) > 0) {
/* cuvantul citit este mai mare decat 
cel din memoria heap si spre care 
pointeaza cuvmax */

/* se elibereaza zona din memoria heap 
in care se pastreaza cuvantul maxim 
intalnit in citirile anterioare */
          free(cuvmax);

/* se aloca zona in memoria heap 
si se pastreaza in ea 
cuvantul curent citit */
          cuvmax = memsir(cuvcrt);
        }
      printf("cel mai mare cuvant este\n");
      printf("%s\n", cuvmax);
      free(cuvmax);
}

Observatie: In acest program nu s-a testat imposibilitatea pastrarii sirului maxim in memoria heap deoarece acesta are cel mult 101 caractere. Ori memoria heap are alocat un spatiu mult mai mare.

8.17. Sa se scrie o functie care sorteaza in ordine crescatoare n siruri de caractere.

Functia are 2 parametri:

tpointer - tablou unidimensional de tip pointer spre char;
- fiecare element al tabloului este un pointer spre unul dintre cele n siruri de caractere;
- tpointer[i] este pointer spre al i+1-lea sir de caractere;
n - intreg de tip int care are ca valoare numarul sirurilor de caractere care se sorteaza.

Functia utilizeaza metoda bulelor. Pentru a ordona sirurile in ordine crescatoare se permuta pointerii in locul sirurilor, ca in exercitiul 8.14.

La compararea sirurilor de caractere se ignora diferenta dintre literele mari si mici.

void ordsircresc(char *tpointer[], int n)
/* sorteaza in ordine crescatoare cele n siruri 
de caractere spre care pointeaza elementele 
tpointer[0], tpointer[1],.., tpointer[n-1] */
{
  int ind, i;
  char *t;

  ind = 1;
  while(ind) {
    ind = 0;
    for(i=0; i < n-1; i++)
      if(strcmp(tpointer[i], tpointer[i+1]) > 0) {
        t = tpointer[i];
        tpointer[i] = tpointer[i+1];
        tpointer[i+1] = t;
        ind = 1;
      }
  }
}

8.18. Sa se scrie un program care citeste o succesiune de cuvinte si le afiseaza in ordine crescatoare. Se ignora diferenta dintre literele mari si cele mici.

Prin cuvant se intelege o succesiune de caractere care nu sunt albe. Cuvintele sunt separate prin caractere albe. Succesiunea de cuvinte se termina prin sfarsitul de fisier (Ctrl-Z).

Cuvintele citite se pastreaza in memoria heap. Programul utilizeaza un tablou de pointeri ale carui elemente pointeaza fiecare catre un cuvant.

Se presupune ca sunt cel mult 500 de cuvinte.

#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#include "FUNCTIA101.C";
#include "FUNCTIA102.C";

#define MAXCUV 500

main()
/* citeste o succesiune de cuvinte 
si le afiseaza in ordine crescatoare */
{
  char *tp[MAXCUV];
  int i, j;
  char t[255];
	
/* se citesc cuvintele si se pastreaza 
in memoria heap */
  for(i=0; scanf("%s", t) == 1; i++)
    if((tp[i] = memsir(t)) == 0) {
      printf("memorie insuficienta\n");
      exit(1);
    }

/* se sorteaza cuvintele 
in ordine crescatoare */
  if(i)
    ordsircresc(tp, i);

/* listarea cuvintelor dupa sortare */
  for(j=0; j < i; j++) {
    printf("%s\n", tp[j]);
    if((j+1)%23 == 0) {
      printf("actionati o tasta pentru a continua\n");
      getch();
    }
  }
}

Observatie:

Acest program are un avantaj fata de cel din exercitiul 8.14., deoarece in cazul de fata se aloca pentru fiecare cuvant o zona de memorie de lungime egala cu numarul de caractere ale cuvantului respectiv, plus 1 (pentru caracterul NUL). In programul de la exercitiul 8.14. se aloca o zona fixa de memorie de (30+1)*500 octeti, care este de obicei prea mare, deoarece cuvintele au in medie mai putin de 30 de caractere.

In general, alocarea dinamica in memoria heap permite alocari optime, fata de cele facute in mod obisnuit, folosind tablouri automatice, statice sau globale.

8.9. Utilizarea tablourilor de pointeri la prelucrari de date de tip sir de caractere