18. cvičení

Dynamická alokace

Datová struktura je organizované úložiště pro reprezentaci dat v paměti počítače. Nejjednodušší datovou strukturou, se kterou jsme zatím pracovali, je pole, kde lze ukládat fixní počet prvků stejného typu. Pole je tedy statická datová struktura, neboť jeho velikost je pevně daná a nelze ji po vytvoření měnit (nelze tedy přidávat nebo odebírat prvky). V dalších cvičeních se budeme zabývat vytvářením dynamických datových struktur, kde není třeba předem znát počet prvků a prvky lze přidávat a odebírat i po vytvoření datové struktury.

Pro vytváření dynamických datových struktur slouží dynamická alokace, která umožňuje vyhradit paměť pro libovolný počet prvků libovolného typu. Na rozdíl od „klasických“ proměnných není životnost dynamicky alokovaných proměnných vázána na žádnou funkci, dynamicky alokovaná data jsou k dispozici dokud je programátor ručně nedealokuje.

Dynamická alokace se provede pomocí funkce malloc, která má jeden parametr udávající požadovaný počet bytů a vrací ukazatel na nově alokovaná data. Např. alokaci jedné proměnné typu int a 10 proměnných typu float (tj. pole délky 10) lze provést takto:

int* ukazatel = malloc(sizeof(int));
float* pole = malloc(10*sizeof(float));

Po skončení práce s dynamicky alokovanými proměnnými je třeba ručně provést dealokaci pomocí funkce free, aby se zabránilo úniku paměti (tzv. memory leak):

free(ukazatel);
free(pole);

Poznámka: Pro použití funkcí malloc a free je třeba includovat hlavičkový soubor stdlib.h:

#include <stdlib.h>

Zásady práce s ukazateli a dynamickou alokací

  1. Nulový ukazatel (hodnota NULL) představuje neplatný ukazatel – nelze dereferencovat (operátor *), ani přistoupit k prvkům pole (operátor []) nebo struktury (operátor ->), ani dealokovat (funkce free).
  2. Každou dynamickou alokaci musí následovat dealokace.
  3. Adresy, které chceme dealokovat pomocí funkce free, musí pocházet z funkce malloc. Nelze dealokovat paměť vyhrazenou pro tzv. automatické proměnné nebo statická pole.
  4. Každou adresu lze dealokovat nejvýše jednou, tj. funkci free nelze volat několikrát po sobě se stejnou adresou. Aby se tomu zabránilo, je dobré nastavit hodnotu ukazatele po dealokaci na NULL:

    free(ukazatel);
    ukazatel = NULL;
    

Porušení těchto pravidel způsobuje tzv. nedefinované chování, (undefined behaviour) které může mít libovolné (nedefinované) následky. Program se v takovém případě může zachovat jakkoliv: může provést očekávaný výpočet, může vrátit chybný výsledek, může skončit s chybou (tzv. crashnout), ale může třeba i naformátovat disk…

Další příklady nedefinovaného chování: používání neinicializovaných proměnných, chybějící příkaz return na konci funkce, atd.

Probrané příklady

  1. Použití funkcí malloc a free.
  2. Dynamické pole.

Nejjednodušší dynamickou datovou strukturou je tzv. dynamické pole, u kterého lze měnit velikost. Pro jeho reprezentaci použijeme strukturu, která obsahuje ukazatel na data a aktuální velikost pole:

typedef struct
{
    float* data;
    int pocet;
}
dynamicke_pole;

Pro vytvoření pole můžeme vytvořit samostatnou funkci, která má jeden parametr udávající počet prvků a vrací hodnotu typu dynamicke_pole:

dynamicke_pole vytvor_pole(int pocet)
{
    dynamicke_pole pole;

    // dynamicka alokace
    if (pocet > 0)
        pole.data = malloc(pocet * sizeof(float));
    else
        pole.data = NULL;

    // osetreni chyby alokace
    if (pole.data != NULL)
        pole.velikost = pocet;
    else
        pole.velikost = 0;

    return pole;
}

Podobně definujeme funkci pro zrušení pole:

void zrus_pole(dynamicke_pole pole)
{
    free(pole.data);
    pole.data = NULL;
    pole.velikost = 0;
}

Při změně velikosti je potřeba alokovat nové pole s požadovanou velikostí, překopírovat prvky ze starého pole do nového a dealokovat původní pole. Funkce může vypadat např. takto (první verze ze cvičení):

dynamicke_pole zvetsi_pole(dynamicke_pole pole, int pocet_novych)
{
    // alokace noveho pole
    dynamicke_pole nove = vytvor_pole(pole.velikost + pocet_novych);
    // prekopirovat prvky
    for (int i = 0; i < nove.velikost && i < pole.velikost; i++)
        nove.data[i] = pole.data[i];
    // dealokace stareho pole
    zrus_pole(pole);
    return nove;
}

Tato verze je ale poměrně nešikovná, protože při použití této funkce musíme uvést dvakrát název proměnné pole, které chceme zvětšit:

// alokace
dynamicke_pole pole = vytvor_pole(10);
// zvetseni
pole = zvetsi_pole(pole, 2);

Šikovnější verze využívá předání prvního parametru pomocí ukazatele, aby se změny ve struktuře reprezentující dynamické pole projevily i mimo funkci zvetsi_pole:

void zvetsi_pole(dynamicke_pole* pole, int pocet_novych)
{
    // alokace noveho pole
    dynamicke_pole nove = vytvor_pole(pole->velikost + pocet_novych);
    // prekopirovat prvky
    for (int i = 0; i < nove.velikost && i < pole->velikost; i++)
        nove.data[i] = pole->data[i];
    // dealokace stareho pole
    zrus_pole(*pole);
    // vraceni vysledku
    pole->data = nove.data;
    pole->velikost = nove.velikost;
}

Použití této funkce:

// alokace
dynamicke_pole pole = vytvor_pole(10);
// zvetseni
zvetsi_pole(&pole, 2);

Funkce main ze cvičení:

int main()
{
    // alokace
    dynamicke_pole pole = vytvor_pole(10);

    for (int i = 0; i < pole.velikost; i++)
        pole.data[i] = i;

    // zvetseni
    zvetsi_pole(&pole, 2);

    printf("velikost = %d\n", pole.velikost);
    for (int i = 0; i < pole.velikost; i++)
        printf("%g ", pole.data[i]);
    printf("\n");

    // dealokace
    zrus_pole(pole);

    return 0;
}