9. DYNAMICKE DATOVE STRUKTURY

9.1. Dynamicka alokace pameti.
9.2. Seznam.
9.3. Pole ukazatelu.

Dynamicke datove struktury predstavuji jakysi protiklad ke statickym datovym strukturam. Povezme si tedy nejprve neco o nich. Porovnanim jejich vlastnosti lepe vyniknou prednosti tech ci onech pro jiste tridy uloh.

Staticka data (SD) maji svou velikost presne a nemenne urcenou v okamziku prekladu zdrojoveho textu. Proto se s nimi pracuje jednoduse. Odpada moznost prace s nepridelenou pameti. Potud klady. Nyni zapory. At nas program potrebuje dat mene ci vice, neda se s tim nic delat. Proto casto radeji volime SD ponekud naddimenzovana, aby nas program zvladl "vetsinu" uloh, jejichz tridu je schopen resit. Pro priklady nemusime chodit daleko. Napiseme-li program pro praci s maticemi postaveny na SD, musime urcit jejich dimenzi. Dimenze 3 x 3 asi nepostaci, tak radeji sahneme k dimenzi 10 x 10, nebo radeji k 20 x 20. A budeme mit dobry pocit, ze nase uloha vyresi vse. Pocit je pochopitelne mylny. Uloha si neporadi uz s matici 21 x 21. Navic klademe na OS vzdy stejne, a to vetsinou premrstene, pozadavky na operacni pamet. V jednoulohovem systemu to obvykle nevadi. Ve viceulohovem, natoz jeste viceuzivatelskem prostredi je takove plytvani temer neodpustitelne. SD jsou pochopitelne staticka ve smyslu velikosti pameti, kterou maji pridelenu. Jejich hodnoty se behem programu mohou menit.

Dynamicka data (DD) nemaji velikost pri prekladu urcenou. Pri prekladu jsou vytvoreny pouze promenne vhodneho typu ukazatel na, ktere nam za chodu slouzi jako pevne body pro praci s DD. O pozadovany pametovy prostor ovsem musime pozadat OS. Ten nasi zadost uspokoji, nebo nikoliv. Rozhodne vsak zadame vzdy jen tolik pameti, kolik se za chodu ukazalo byt potreba. Popravde receno, pozadujeme ji trosku vic. Ta trocha navic je dana jednak nutnou rezii, jednak nasimi schopnostmi. Zalezi jen na nas, jak vhodne dynamicke datove struktury vybereme (nebo si oblibime). Pochopitelne vznikaji mnoha nebezpeci, zejmena pri opomenuti pozadani o pamet a zapisu do nepridelenych prostor.

DD maji jeste jednu prednost proti SD. Pokud pozadavky na DD vystupuji v na sobe nezavislych castech programu, muze pametova oblast byt mensi, nez prosty soucet techto pozadavku. Jakmile totiz konci cast programu, vrati pridelenou cast DD zpet. Naopak novy usek programu podle potreby o pamet pozada.

DD tedy snizuji pametove naroky ze dvou duvodu. Jednak proto, ze pozaduji tolik pameti, kolik je treba. Jednak diky moznemu vicenasobnemu pouzivani pridelene dynamicke pameti.

SD jsou umistena v datovem segmentu. Klasicky program je totiz rozdelen na datovy segment a kodovy segment.

Kodovy segment obsahuje kod, ktery prekladac vytvori na zaklade naseho zdrojoveho textu. Tento kod by se za chodu programu tedy nemel menit. Nemennost kodoveho segmentu operacni systemy obvykle kontroluji a zarucuji. MS-DOS ovsem nikoli. Prave z toho plynou prakticky jiste havarie dokonce celeho OS pri chybne praci s ukazateli.

Datovy segment je opet vytvoren prekladacem. Jsou v nem umistena vsechna staticka data programu. Tato cast programu se behem chodu programu meni.

Krome kodoveho a datoveho segmentu prideluje pri spusteni (zavadeni) programu OS jeste jiste prostredi. To ma bud nejakou standardni velikost, nebo je tato velikost urcena na zaklade pozadavku zavadeneho programu. Zde je umisten zasobnik. O nem vime, ze je nezbytny pri predavani argumentu funkcim, navratove hodnoty od funkci a take pro nalezeni navratove adresy po ukonceni funkce. Tato navratova adresa je na zasobnik zapsana pri volani funkce.

Zasobnik vsak zpravidla neobsadi celou zbyvajici pamet, kterou ma program (proces) k dispozici. Cast pridelene pameti zustava volna. Te se zpravidla rika hromada ci halda (heap). Jeji velikost muzeme pri tvorbe programu urcit. A prave halda predstavuje oblast pameti, do ktere se umistuji DD.

9.1. Dynamicka alokace pameti.

Aby casti programu mohly jak zadat o prideleni dynamicke pameti, tak jiz nepotrebnou pamet vracet, musi existovat alespon zakladni programova podpora. Tu si ovsem nebudeme vytvaret sami. Je definovana ANSI normou jazyka a tudiz ji dostavame spolu s prekladacem.

Souhrne se programova podpora pro dynamickou alokaci pameti nazyva podle oblasti, jiz se pridelovani tyka, spravce haldy (heap manager). Soucasti spravce haldy jsou nejen potrebne funkce, ale i datove struktury. Jako uzivatele nas pochopitelne zajimaji predevsim funkce spravce haldy. Popisme si tedy nektere z nich. Nas vyber urcen zejmena jejich prenositelnosti. Deklarace funkci spravce haldy jsou umisteny v alloc.h, pripadne ve stdlib.h.

void *malloc(size_t size);

predstavuje pozadavek o prideleni souvisleho bloku pameti o velikosti size. Je-li uspesny, dostavame ukazatel na jeho zacatek, jinak NULL.

void *calloc(size_t nitems, size_t size);

jako predchozi s tim, ze nas pozadavek je rozlozen na nitems polozek, kazda o size bytech. Navic je pridelena pamet vyplnena nulami.

void free(void *block);

je naopak vraceni drive alokovane pameti, na kterou ukazuje block1.


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

umoznuje zmenit velikost alokovane pameti, na kterou ukazuje block na novou velikost urcenou hodnotou size. V pripade potreby (pozadavek je vetsi, nez puvodni blok) je obsah puvodniho bloku prekopirovan. Vraci ukazatel na novy blok.

UNIX a MS-DOS definuji pro dynamickou zmenu velikosti haldy dvojici funkci. Prvni z nich,

int brk(void *addr);

nastavi hranici haldy programu na hodnotu danou addr. Druha v dvojice,

void *sbrk(int incr);

umozni zvysit tuto hodnotu o incr bajtu.

MS-DOS pridava jeste funkci, ktera vraci pocet volnych bajtu na hromade (v zavislosti na pametovem modelu vraci unsigned int nebo unsigned long):

unsigned coreleft(void);

Kratkou ukazku prideleni a navraceni pameti pro retezec predstavuji dve nasledujici funkce. Rozsahlejsi a uplne programy jsou soucasti kazde z nasledujicich podkapitol.

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

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

Prvni funkce vytvori na hromade dostatecny prostor a nakopiruje do nej predavany retezec. Ukazatel na tuto kopii vraci jako svou funkcni hodnotu. Druha funkce provadi cinnost opacnou. Oblast urcenou ukazatelem vrati spravci haldy.

Detailni vlastnosti spravce haldy mohou byt ruzne. Cemu se vsak obvykle nevyhneme je situace zvana segmentace haldy. Nejsou-li useky z haldy vraceny v opacnem poradi, nez byly pridelovany (LIFO), vzniknou na hromade stridave useky volne a obsazene pameti. Celkova velikost volne pameti, dana souctem vsech volnych useku, je pak vetsi nez velikost nejvetsiho souvisleho volneho bloku. Muze pak nastat situace, kdy volne pameti je sice dost, ale nas pozadavek na jeji prideleni neni uspokojen, protoze neni k dispozici dostatecne velka souvisla oblast.

9.2. Seznam.

Je dynamicka datova struktura, ktera mezi svymi cleny obsahuje krome datove casti i vazebny clen, ktery ukazuje na nasledujici prvek seznamu, nebo NULL, je-li poslednim prvkem. Datove minimum², ktere pro spravu seznamu potrebujeme, je ukazatel na jeho prvni prvek. Popsany seznam se rovnez nazyva jednosmerny. Postupne totiz muzeme projit od zacatku seznamu az k jeho konci, nikoliv vsak naopak. Existuje jeste jedna varianta seznamu, majici vazebne cleny dva. Jeden ukazuje opet na naslednika, druhy na predchudce.

Ukazku pouziti seznamu prinasi nasledujici uloha (a program). Mejme za ukol spocitat cetnost vyskytu vsech slov ve vstupnim textu. Pro jednoduchost budeme rozlisovat mala a velka pismena. Na zaver vytiskneme tabulku, v niz bude uvedena cetnost vyskytu a retezec, predstavujici slovo. Za slova povazuje program retezce pismen a cislic. Tuto skutecnost muzeme ovsem menit upravou vlastnosti funkce odstran_neslova. Jmena funkci i promennych v programu jsou volena s ohledem na jejich maximalni popisnost. Vstupem muze byt soubor, je-li zadan jako 1. argument prikazoveho radku. Jinak je vstupem standardni vstup.

Obrazek odpovida datove strukture vytvorene v programu. Hodnoty jsou pouze ilustrativni. Jediny nedynamicky objekt seznamu je ukazatel prvni na zacatek seznamu. Ostatni objekty jsou dynamicke. V obrazku je tato skutecnost odlisena tvarem rohu obdelnicku.

Obrazek muze byt i navodem, jak dynamicke objekty rusit. Tato cinnost totiz v programu obsazena neni. Rozhodne je zrejme, ze musime uvolnit jak pamet vyclenenou pro hodnoty typu struct_info, tak i pamet, kterou obsazuji retezce, na nez je ze struktury ukazovano.

/****************************************************************/
/* 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 ukazatelu.

Velmi pohodlnou dynamickou datovou strukturou je dynamicke pole ukazatelu. Princip je jednoduchy. Pozadame o pamet pro dostatecne velike pole ukazatelu. Dale jiz pracujeme stejne, jako by pole bylo staticke (az na ten ukazatel na pole navic). K jednotlivym prvkum muzeme pristupovat pomoci indexu. Nesmime zapomenout, ze prvky jsou ukazatele, a ze tedy musime pamet, na kterou ukazuji, take alokovat. Diky funkci realloc() mame moznost snadno menit³ pocet prvku naseho pole ukazatelu. Navic s tim, ze nase dynamicka data svou adresu nemeni a funkce realloc() prenese spravne (stale platne) adresy do noveho (vetsiho) bloku ukazatelu. My k nim pristupujeme pomoci stejne promenne⁴, indexy vsech prvku zustavaji stejne, jen jich pribylo. Skvele.

Ukazkova uloha, kterou resime, nacita vstupni radky textu, uklada je na hromadu s pristupem pomoci pole ukazatelu a nakonec radky vytiskne ve stejnem poradi, v jakem byly nacteny.

Hodnoty START a PRIRUSTEK jsou umyslne voleny male, aby se ukazala moznost realokace pole i pri zadavani vstupu z klavesnice. Pro rozsahlejsi pokusy doporucujeme presmerovat 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() definovana v zavislosti na skutecnosti, je-li definovano makro LADENI. Jde tedy o podmineny preklad. Proc jsme jej zavadeli je nasnade. Ve fazi ladeni potrebujeme mit jistotu, ze pamet, kterou jsme alokovali, pozdeji spravne vracime. Jakmile je program odladen, neni tato pomocna funkce potreba. Nemusime ale vnaset chyby tim, ze ji i jeji volani bezhlave smazeme. Vyhodnejsi je, promyslet si takovou situaci jiz pri navrhu programu. Pak ji, stejne jako v prikladu, budeme prekladat podminene.

Poznamenejme, ze obe popsane dynamicke datove struktury lze modifikovat pridanim dalsich funkci na zasobnik, frontu, ... .

Pro podrobnejsi popis dynamickych datovych struktur doporucujeme skvele dilo profesora Niclause Wirtha Algoritmy a struktury udaju.

Vysvetlivky:

¹ Ze skutecnosti, ze k uvolneni alokovane oblasti pameti staci ukazatel na tuto oblast, muzeme odhadovat i nektere skryte vlastnosti spravce haldy. Potrebne informace o velikosti alokovaneho bloku musi mit spravce interne k dispozici. I to je soucasti celkove rezie pouziti DD.
² Dale potrebujeme podpurne funkce.
³ V popisu jsme predpokladali, ze nase pametove naroky stoupaji. Pokud je tomu naopak, je nase cinnost obdobna. Jen se pocet pouzitelnych indexu snizuje.
⁴ Pokud si jeste vzpomeneme na funkci qsort(), tak jeji pouziti pro usporadani pole ukazatelu se primo nabizi. Predchozi dynamicka datova struktura (seznam) by pro usporadani vyzadovala zcela jine techniky.