2. Uzly v dynamických údajových štruktúrach

Dynamické premenné, ktoré sú navzájom prepojené ukazovateľmi a tvoria tak dynamickú štruktúru sa nazývajú tiež uzly. Jednotlivé uzly nesú vždy istú hodnotu (obsah) a sprístupňujú iné uzly hodnotou príslušných ukazovateľov.

Každý uzol obsahuje preto dve časti:

  • hodnotovú časť, ktorá vyjadruje vlastnú hodnotu (obsah) uzla
  • spojovaciu časť (väzobnú) tvorenú hodnotou ukazovateľa na iný uzol (resp. hodnotami ukazovateľov na iné uzly).
Preto je vhodným údajovým typom používaným pre definíciu uzla dynamickej štruktúry záznam - v jazyku C nazvaný štruktúra - struct.

  Štruktúra (struct) v jazyku C je obdobou pascalovského záznamu (record). Ide o heterogénny údajový typ, čo znamená, že je vnútorne zložený z prvkov rôznych typov. (Pre porovnanie - pole je homogénny údajový typ - je zložené z prvkov rovnakého typu.) Aby sme predišli prípadnému nedorozumeniu, budeme používať v ďalšom zaužívaný termín záznam. Ako uzly v dynamických údajových štruktúrach sa teda používajú rôzne druhy záznamov.

Uvažujme dynamickú údajovú štruktúru podľa obrázka:

Ide o zoznam kamarátov, ktorý má štyri prvky t.j. dynamickú štruktúru so štyrmi uzlami. Každý uzol je záznam, ktorý má 4 zložky: meno, priezvisko, vek a ukazovateľ na ďalší uzol v zozname. Definujme nový údajový typ:

 

typedef struct uzol {
  char meno[15]; 
  char priezvisko[20];
  int vek;
  struct uzol *dalsi;
} TUzol;
          

Prvé dve zložky sú reťazce znakov, tretia je celé číslo a posledná je ukazovateľ na záznam rovnakého typu - takáto rekurzívna definícia je možná len ak záznam, ktorý ideme definovať, hneď na začiatku pomenujeme (to pri "bežnom" zázname robiť nemusíme). Zvykne sa zvoliť meno podobné menu nového typu, v našom prípade sme záznam pomenovali uzol. Nový typ sme pomenovali TUzol. Každý prvok v uvažovanom zozname je typu TUzol.

  Spojovaciu časť každho uzla tvorí ukazovateľ na ďalší uzol v zozname. Toto zreťazenie je na obrázku znázornené symbolicky pomocou . Symbol budeme používať, ak hodnota príslušného ukazovateľa je NULL t.j. neukazuje na ďalší uzol. Pri prehľadávaní štruktúry spravidla postupujeme tak, že prechádzame dynamickou štruktúrou uzol po uzle pomocou ukazovateľa dovtedy, kým tento nemá hodnotu NULL, t.j. kým sme nenarazili na posledný uzol (s touto problematikou sa bližšie zoznámime v nasledujúcich kapitolách).

Aby sme mohli s dynamickou štruktúrou (jej prvkami) pracovať, postačí, ak máme k dispozícii ukazovateľ na jej začiatok. Nech teda pointer

TUzol *p;

ukazuje na prvý prvok zoznamu.

Chceme zmeniť hodnotu položky vek v druhom uzle na 11. Urobíme to príkazom

p->dalsi->vek = 11;

Čítajme tento príkaz priradenia zľava doprava (porovnajte s obrázkom):

  • p je ukazovateľ na prvý uzol
  • p->meno, p->priezvisko, p->vek, p->dalsi  sú jednotlivé položky v prvom uzle
  • p->dalsi  je ukazovateľ na nasledujúci uzol zoznamu
  • p->dalsi->vek  je práve tá položka v druhom uzle, ktorej hodnotu chceme príkazom priradenia zmeniť