9. DYNAMICKÉ DATOVÉ STRUKTURY

9.1. Dynamická alokace paměti.
9.2. Seznam.
9.3. Pole ukazatelů.

Dynamické datové struktury představují jakýsi protiklad ke statickým datovým strukturám. Povězme si tedy nejprve něco o nich. Porovnáním jejich vlastností lépe vyniknou přednosti těch či oněch pro jisté třídy úloh.

Statická data (SD) mají svou velikost přesně a neměnně určenou v okamžiku překladu zdrojového textu. Proto se s nimi pracuje jednoduše. Odpadá možnost práce s nepřidělenou pamětí. Potud klady. Nyní zápory. Ať náš program potřebuje dat méně či více, nedá se s tím nic dělat. Proto často raději volíme SD poněkud naddimenzovaná, aby náš program zvládl "většinu" úloh, jejichž třídu je schopen řešit. Pro příklady nemusíme chodit daleko. Napíšeme-li program pro práci s maticemi postavený na SD, musíme určit jejich dimenzi. Dimenze 3 x 3 asi nepostačí, tak raději sáhneme k dimenzi 10 x 10, nebo raději k 20 x 20. A budeme mít dobrý pocit, že naše úloha vyřeší vše. Pocit je pochopitelně mylný. Úloha si neporadí už s maticí 21 x 21. Navíc klademe na OS vždy stejné, a to většinou přemrštěné, požadavky na operační paměť. V jednoúlohovém systému to obvykle nevadí. Ve víceúlohovém, natož ještě víceuživatelském prostředí je takové plýtvání téměř neodpustitelné. SD jsou pochopitelně statická ve smyslu velikosti paměti, kterou mají přidělenu. Jejich hodnoty se během programu mohou měnit.

Dynamická data (DD) nemají velikost při překladu určenou. Při překladu jsou vytvořeny pouze proměnné vhodného typu ukazatel na, které nám za chodu slouží jako pevné body pro práci s DD. O požadovaný paměťový prostor ovšem musíme požádat OS. Ten naši žádost uspokojí, nebo nikoliv. Rozhodně však žádáme vždy jen tolik paměti, kolik se za chodu ukázalo být potřeba. Popravdě řečeno, požadujeme jí trošku víc. Ta trocha navíc je dána jednak nutnou režií, jednak našimi schopnostmi. Záleží jen na nás, jak vhodné dynamické datové struktury vybereme (nebo si oblíbíme). Pochopitelně vznikají mnohá nebezpečí, zejména při opomenutí požádání o paměť a zápisu do nepřidělených prostor.

DD mají ještě jednu přednost proti SD. Pokud požadavky na DD vystupují v na sobě nezávislých částech programu, může paměťová oblast být menší, než prostý součet těchto požadavků. Jakmile totiž končí část programu, vrátí přidělenou část DD zpět. Naopak nový úsek programu podle potřeby o paměť požádá.

DD tedy snižují paměťové nároky ze dvou důvodů. Jednak proto, že požadují tolik paměti, kolik je třeba. Jednak díky možnému vícenásobnému používání přidělěné dynamické paměti.

SD jsou umístěna v datovém segmentu. Klasický program je totiž rozdělen na datový segment a kódový segment.

Kódový segment obsahuje kód, který překladač vytvoří na základě našeho zdrojového textu. Tento kód by se za chodu programu tedy neměl měnit. Neměnnost kódového segmentu operační systémy obvykle kontrolují a zaručují. MS-DOS ovšem nikoli. Právě z toho plynou prakticky jisté havárie dokonce celého OS při chybné práci s ukazateli.

Datový segment je opět vytvořen překladačem. Jsou v něm umístěna všechna statická data programu. Tato část programu se během chodu programu mění.

Kromě kódového a datového segmentu přiděluje při spuštění (zavádění) programu OS ještě jisté prostředí. To má buď nějakou standardní velikost, nebo je tato velikost určena na základě požadavků zaváděného programu. Zde je umístěn zásobník. O něm víme, že je nezbytný při předávání argumentů funkcím, návratové hodnoty od funkcí a také pro nalezení návratové adresy po ukončení funkce. Tato návratová adresa je na zásobník zapsána při volání funkce.

Zásobník však zpravidla neobsadí celou zbývající paměť, kterou má program (proces) k dispozici. Část přidělené paměti zůstává volná. Té se zpravidla říká hromada či halda (heap). Její velikost můžeme při tvorbě programu určit. A právě halda představuje oblast paměti, do které se umisťují DD.

9.1. Dynamická alokace paměti.

Aby části programu mohly jak žádat o přidělení dynamické paměti, tak již nepotřebnou paměť vracet, musí existovat alespoň základní programová podpora. Tu si ovšem nebudeme vytvářet sami. Je definována ANSI normou jazyka a tudíž ji dostáváme spolu s překladačem.

Souhrně se programová podpora pro dynamickou alokaci paměťi nazývá podle oblasti, jíž se přidělování týká, správce haldy (heap manager). Součástí správce haldy jsou nejen potřebné funkce, ale i datové struktury. Jako uživatele nás pochopitelně zajímají především funkce správce haldy. Popišme si tedy některé z nich. Náš výběr určen zejména jejich přenositelností. Deklarace funkcí správce haldy jsou umístěny v alloc.h, případně ve stdlib.h.

void *malloc(size_t size);

představuje požadavek o přidělení souvislého bloku paměti o velikosti size. Je-li úspěšný, dostáváme ukazatel na jeho začátek, jinak NULL.

void *calloc(size_t nitems, size_t size);

jako předchozí s tím, že náš požadavek je rozložen na nitems položek, každá o size bytech. Navíc je přidělená paměť vyplněna nulami.

void free(void *block);

je naopak vrácení dříve alokované paměti, na kterou ukazuje block1.


void *realloc(void *block, size_t size);

umožňuje změnit velikost alokované paměti, na kterou ukazuje block na novou velikost určenou hodnotou size. V případě potřeby (požadavek je větší, než původní blok) je obsah původního bloku překopírován. Vrací ukazatel na nový blok.

UNIX a MS-DOS definují pro dynamickou změnu velikosti haldy dvojici funkcí. První z nich,

int brk(void *addr);

nastaví hranici haldy programu na hodnotu danou addr. Druhá v dvojice,

void *sbrk(int incr);

umožní zvýšit tuto hodnotu o incr bajtů.

MS-DOS přidává ještě funkci, která vrací počet volných bajtů na hromadě (v závislosti na paměťovém modelu vrací unsigned int nebo unsigned long):

unsigned coreleft(void);

Krátkou ukázku přidělení a navrácení paměti pro řetězec představují dvě následující funkce. Rozsáhlejší a úplné programy jsou součástí každé z následujících podkapitol.

char *newstr(char *p)
{
 register char *t;
 t = malloc(strlen(p) + 1);
 strcpy(t, p);
 return t;
}

void freestr(char *p)
{
 free(p);
}

První funkce vytvoří na hromadě dostatečný prostor a nakopíruje do něj předávaný řetězec. Ukazatel na tuto kopii vrací jako svou funkční hodnotu. Druhá funkce provádí činnost opačnou. Oblast určenou ukazatelem vrátí správci haldy.

Detailní vlastnosti správce haldy mohou být různé. Čemu se však obvykle nevyhneme je situace zvaná segmentace haldy. Nejsou-li úseky z haldy vráceny v opačném pořadí, než byly přidělovány (LIFO), vzniknou na hromadě střídavě úseky volné a obsazené paměti. Celková velikost volné paměti, daná součtem všech volných úseků, je pak větší než velikost největšího souvislého volného bloku. Může pak nastat situace, kdy volné paměti je sice dost, ale náš požadavek na její přidělení není uspokojen, protože není k dispozici dostatečně velká souvislá oblast.

9.2. Seznam.

Je dynamická datová struktura, která mezi svými členy obsahuje kromě datové části i vazebný člen, který ukazuje na následující prvek seznamu, nebo NULL, je-li posledním prvkem. Datové minimum², které pro správu seznamu potřebujeme, je ukazatel na jeho první prvek. Popsaný seznam se rovněž nazývá jednosměrný. Postupně totiž můžeme projít od začátku seznamu až k jeho konci, nikoliv však naopak. Existuje ještě jedna varianta seznamu, mající vazebné členy dva. Jeden ukazuje opět na následníka, druhý na předchůdce.

Ukázku použití seznamu přináší následující úloha (a program). Mějme za úkol spočítat četnost výskytu všech slov ve vstupním textu. Pro jednoduchost budeme rozlišovat malá a velká písmena. Na závěr vytiskneme tabulku, v níž bude uvedena četnost výskytu a řetězec, představující slovo. Za slova považuje program řetězce písmen a číslic. Tuto skutečnost můžeme ovšem měnit úpravou vlastností funkce odstran_neslova. Jména funkcí i proměnných v programu jsou volena s ohledem na jejich maximální popisnost. Vstupem může být soubor, je-li zadán jako 1. argument příkazového řádku. Jinak je vstupem standardní vstup.

Obrázek odpovídá datové struktuře vytvořené v programu. Hodnoty jsou pouze ilustrativní. Jediný nedynamický objekt seznamu je ukazatel prvni na začátek seznamu. Ostatní objekty jsou dynamické. V obrázku je tato skutečnost odlišena tvarem rohů obdélníčků.

Obrázek může být i návodem, jak dynamické objekty rušit. Tato činnost totiž v programu obsažena není. Rozhodně je zřejmé, že musíme uvolnit jak paměť vyčleněnou pro hodnoty typu struct_info, tak i paměť, kterou obsazují řetězce, na něž je ze struktury ukazováno.

/****************************************************************/
/* soubor SLOVA.C                                               */
/* provede nacteni vstupniho textu, jeho rozlozeni na slova     */
/* a z techto slov vytvori seznam s jejich cetnosti vyskytu.    */
/* Na zaver vytiskne slova a jejich cetnosti.                   */
/****************************************************************/

#include <stdio.h>
#include <string.h>
#include <alloc.h>
#include <ctype.h>
#include <conio.h>

#define DELKA_RADKU 500
#define PAGE        24

/* typedef struct info; */
typedef struct struct_info {
   int pocet;
   char *slovo;
   struct struct_info *dalsi;
  } info;

void odstran_neslova(char *ptr)
/* odstrani mezery, tabelatory a znaky CR, LF ze zacatku retezce */
{char *pom;
 pom = ptr;
 if (strlen(ptr) == 0)
   return;
 while ((*pom != '\0') && ((*pom == 0x20) || (*pom == '\t') ||
         (*pom == '\n') || (*pom == '\r') || (!isalnum(*pom))))
    {pom++;}
 strcpy(ptr, pom);
} /* void odstran_neslova(char *ptr) */

void vrat_slovo(char *r, char *s)
{
 int i = 0;
 while ((r[i] != 0x0) && (isalnum(r[i]) || (r[i] == '_')))
   {i++;} /* while */
 if (i == 0)
   {*s = 0x0;}
 else
   {strncpy(s, r, i);
    s[i] = 0x0;
    strcpy(r, r + i);
   }
} /* void vrat_slovo(char *r, char *s) */

void pridej_slovo(info **prvni, char *s)
{
 info *prvek;
 prvek = *prvni;
 while (prvek != NULL)
   {
    if (strcmp(s, prvek->slovo) == 0)
      {(prvek->pocet)++;
       return;
      }
    prvek = prvek->dalsi;
   }
 prvek = malloc(sizeof(info));
 prvek->slovo = malloc(strlen(s) + 1);
 strcpy(prvek->slovo, s);
 prvek->pocet = 1;
 prvek->dalsi = *prvni;
 *prvni = prvek;
} /* void pridej_slovo(info **prvni, char *s) */

void tiskni(info *prvni)
{
 int vytisknuto = 0;
 while (prvni != NULL)
   {
    printf("%4d..%s\n", prvni->pocet, prvni->slovo);
    prvni = prvni->dalsi;
    vytisknuto++;
    if ((vytisknuto % PAGE) == 0)
      {
       printf("pro pokracovani stiskni klavesu");
       getch();
       printf("\n");
      }
   }
} /* void tiskni(info *prvni) */

int main(int argc, char **argv)
{
 info *prvni = NULL;
 char radek[DELKA_RADKU + 1], slovo[DELKA_RADKU + 1];
 FILE *f;
 if (argc != 1)
   f = fopen(argv[1], "rt");
 else
   f = stdin;
 if (f == NULL)
   return(1);
 while (fgets(radek, DELKA_RADKU, f) != NULL)
   {
    odstran_neslova(radek);
    while (strlen(radek) != 0)
      {vrat_slovo(radek, slovo);
       odstran_neslova(radek);
       pridej_slovo(&prvni, slovo);
      }
   }
 tiskni(prvni);
 return 0;
} /* int main(int argc, char **argv) */

9.3. Pole ukazatelů.

Velmi pohodlnou dynamickou datovou strukturou je dynamické pole ukazatelů. Princip je jednoduchý. Požádáme o paměť pro dostatečně veliké pole ukazatelů. Dále již pracujeme stejně, jako by pole bylo statické (až na ten ukazatel na pole navíc). K jednotlivým prvkům můžeme přistupovat pomocí indexu. Nesmíme zapomenout, že prvky jsou ukazatele, a že tedy musíme paměť, na kterou ukazují, také alokovat. Díky funkci realloc() máme možnost snadno měnit³ počet prvků našeho pole ukazatelů. Navíc s tím, že naše dynamická data svou adresu nemění a funkce realloc() přenese správné (stále platné) adresy do nového (většího) bloku ukazatelů. My k nim přistupujeme pomocí stejné proměnné⁴, indexy všech prvků zůstavají stejné, jen jich přibylo. Skvělé.

Ukázková úloha, kterou řešíme, načítá vstupní řádky textu, ukládá je na hromadu s přístupem pomocí pole ukazatelů a nakonec řádky vytiskne ve stejném pořadí, v jakém byly načteny.

Hodnoty START a PRIRUSTEK jsou úmyslně voleny malé, aby se ukázala možnost realokace pole i při zadávání vstupu z klávesnice. Pro rozsáhlejší pokusy doporučujeme přesměrovat vstup.

/************************************************/
/* soubor STR_ARRY.C                            */
/* ze standardniho vstupu cte radky, alokuje    */
/* pro ne pamet a ukazatele na tuto kopii       */
/* nacteneho radku uklada do pole ukazatelu     */
/* pole ukazatelu ma pocatecni velikost, ktera  */
/* se ovsem v pripade potreby zmeni - realloc() */
/* po ukonceni vstupu nactene radky vytiskne    */
/************************************************/

/********************************/
/* obvykle navratove hodnoty:   */
/*       O.K.      0            */
/*      error      !0 (casto -1)*/
/********************************/

#include <stdio.h>
#include <alloc.h>
#include <string.h>

#define LADENI

#define      START            2
#define      PRIRUSTEK        1
#define      DELKA_RADKU      100

typedef char *          retezec;
typedef retezec *       pole_retezcu;


#if defined(LADENI)
 void volno(void)
 {
  printf("\nje volnych %10lu bajtu\n", coreleft()); /* LARGE */
 } /* void volno(void) */

 void uvolni(pole_retezcu *p_r, int pocet)
 {
  int i;
  for (i = 0; i < pocet; i++)
    {
     free((*p_r)[i]);
    }
  free(*p_r);
 } /* void uvolni(pole_retezcu *p_r, int pocet) */
#endif /* defined(LADENI) */

int alokace(pole_retezcu *p_r, int pocet)
{
 *p_r = malloc(pocet * sizeof(retezec));
 return (*p_r == NULL) ? -1 : 0;
} /* int alokace(pole_retezcu *p_r, int pocet) */

int re_alokace(pole_retezcu *p_r, int novy_pocet)
{
 pole_retezcu pom;
 if (*p_r == NULL)
   if (alokace(p_r, novy_pocet))
     return -1;      /* chyba */
 pom = realloc(*p_r, sizeof(retezec) * novy_pocet);
 if (pom == NULL)
    return -1;
 else
   {
    *p_r = pom;
    return 0;
   }
} /* int re_alokace(pole_retezcu *p_r, int novy_pocet) */

int pridej_radek(pole_retezcu *p_r, retezec s, int index)
{
 int delka = strlen(s) + 1;
 if (((*p_r)[index] = malloc(delka)) == NULL)
   return -1;
 strcpy((*p_r)[index], s);
 return 0;
} /* int pridej_radek(pole_retezcu *p_r, retezec s, int index) */

int cti_a_pridavej(pole_retezcu *p_r, int *pocet, int *alokovano, int prir)
{
 char radek[DELKA_RADKU], *pom;
 puts("Zadavej retezce, posledni CTRL-Z na novem radku");
 do
   {
    if ((pom = gets(radek)) != NULL)
      {
       if (*pocet + 1 > *alokovano)
       {
        if (re_alokace(p_r, *alokovano + prir))
          {
           puts("nedostatek pameti");
           return -1;
          }
        *alokovano += prir;
       }
       if (pridej_radek(p_r, radek, *pocet))
       {
        puts("nedostatek pameti");
        return 1;
       }
       (*pocet)++;
      }
   } while (pom != NULL);
 return 0;
} /*int cti_a_pridavej(pole_retezcu *p_r, int *pocet, int *alokovano, int prir)*/

void zobrazuj(pole_retezcu p_r, int pocet) {
 while (pocet--)
   {
    puts(*p_r++);
   }
} /* void zobrazuj(pole_retezcu p_r, int pocet) */

int main(void)
{
 int      pocet        = 0,
      alokovano = START,
      prirustek = PRIRUSTEK;
 pole_retezcu p_ret = NULL;

#if defined(LADENI)
 volno();
#endif /* defined(LADENI) */
 if (alokace(&p_ret, alokovano)) {
    puts("nedostatek pameti");
    return 1;
   }
 if (cti_a_pridavej(&p_ret, &pocet, &alokovano, prirustek))
   return 1;
 zobrazuj(p_ret, pocet);

#if defined(LADENI)
 uvolni(&p_ret, pocet);
 volno();
#endif /* defined(LADENI) */

 return 0;
} /* int main(void) */

V programu je funkce volno() definována v závislosti na skutečnosti, je-li definováno makro LADENI. Jde tedy o podmíněný překlad. Proč jsme jej zaváděli je nasnadě. Ve fázi ladění potřebujeme mít jistotu, že paměť, kterou jsme alokovali, později správně vracíme. Jakmile je program odladěn, není tato pomocná funkce potřeba. Nemusíme ale vnášet chyby tím, že ji i její volání bezhlavě smažeme. Výhodnější je, promyslet si takovou situaci již při návrhu programu. Pak ji, stejně jako v příkladu, budeme překládat podmíněně.

Poznamenejme, že obě popsané dynamické datové struktury lze modifikovat přidáním dalších funkcí na zásobník, frontu, ... .

Pro podrobnější popis dynamických datových struktur doporučujeme skvělé dílo profesora Niclause Wirtha Algoritmy a struktury údajů.

Výsvětlivky:

¹ Ze skutečnosti, že k uvolnění alokované oblasti paměti stačí ukazatel na tuto oblast, můžeme odhadovat i některé skryté vlastnosti správce haldy. Potřebné informace o velikosti alokovaného bloku musí mít správce interně k dispozici. I to je součástí celkové režie použití DD.
² Dále potřebujeme podpůrné funkce.
³ V popisu jsme předpokládali, že naše paměťové nároky stoupají. Pokud je tomu naopak, je naše činnost obdobná. Jen se počet použitelných indexů snižuje.
⁴ Pokud si ještě vzpomeneme na funkci qsort(), tak její použití pro uspořádání pole ukazatelů se přímo nabízí. Předchozí dynamická datová struktura (seznam) by pro uspořádání vyžadovala zcela jiné techniky.