V predchádzajúcich prednáškach sme sa stretli s viacerými štruktúrami údajov, ktorých veľkosť a umiestnenie v operačnej pamäti bola pevne deklarovaná pred ich použitím. Boli to napríklad polia a záznamy.

Údajovú štruktúru, ktorej rozsah sa počas jej existencie nemení, sa nazýva statická údajová štruktúra.

Pri riešení niektorých úloh však sú vytvárané štruktúry, ktoré menia svoj rozsah, tieto štruktúry budeme nazývať dynamické údajové štruktúry.

Typickým príkladom dynamickej údajovej štruktúry je zoznam prvkov určitého typu, na ktorom je používaná operácia pridávania prvkov a operácia odoberania prvkov.

Znamená to, že zoznam zväčšuje svoju veľkosť. Ak vieme ohraničiť počet prvkov zhora a vieme tiež, že pridávanie sa uskutočňuje na jednom konci zoznamu, tak je možné použiť na reprezentáciu zoznamu pole. Ak však pripustíme pridávanie prvkov aj doprostred zoznamu, potom reprezentácia pomocou poľa je nevýhodná, lebo operácia pridávania prvku bude vyžadovať posun mnohých iných prvkov v poli, aby bolo vytvorené miesto na uloženie nového prvku. Ak by bola povolená operácia vynechávania prvkov, tak by vznikli problémy s dierami v poli.

Operácie meniace rozsah dynamickej údajovej štruktúry sú efektívnejšie realizované, ak použijeme na ich reprezentáciu smerníky. Každý prvok zoznamu je uložený v samostatnom objekte, ktorého súčasťou je, okrem hodnoty prvku zoznamu, tiež položka obsahujúca smerník (spoj, referenciu, odkaz) na objekt, v ktorom je uložený ďalší prvok zoznamu. Operácia vloženia spočíva vo vytvorení objektu, ktorý obsahuje hodnotu nového prvku a smerník na objekt, pred ktorý sa nový prvok zaraďuje, a v zmene smerníka v tom objekte, za ktorý sa nový prvok zaraďuje.

Smerníkové reprezentácie dynamických údajových štruktúr sa v jazyku PASCAL vytvárajú pomocou dynamických premenných a hodnôt typu smerník.

Dynamická premenná nemá pridelený identifikátor, ale identifikuje sa pomocou hodnoty zvláštneho typu, ktorú nazývame smerník a ktorú môžeme považovať za abstrakciu adresy umiestnenia dynamickej premennej v pamäti. Podľa typu dynamických premenných rozlišujeme tiež typy smerníkov. Každý typ smerník je viazaný na jeden typ dynamických premenných, ktorý sa nazýva doménový typ smerníka a je určený v popise typu smerník.

je definovaný typ SMER, ktorého hodnotami sú smerníky identifikujúce dynamické premenné typu MENO.

Zvláštna hodnota, ktorá neidentifikuje žiadnu dynamickú premennú a ktorá môže byť priradená ľubovoľnej premennej typu smerník, je hodnota označená kľúčovým slovom nil.

Ak priradíme túto hodnotu premennej P príkazom

Premenná typu smerník obsahuje adresu v pamäti dynamickej premennej. Smerník je uložený na dvoch slovách a delí sa na offsetovú a segmentovú časť.

1. New(...),
2. operátorom @

@ je unárny operátor, ktorý vezme premennú alebo identifikátor procedúry alebo funkcie za operand a vráti smerník k operandu; môže byť priradený ľubovoľnej smerníkovej premennej.

3. funkciou Ptr

• Dispose(var p: pointer)

• FreeMem(var p: pointer; size: word)

• GetMem(var p: pointer; size: word)

zakladá novú dynamickú premennú uvedenej veľkosti size (menej ako 65522)a uloží jej adresu do premennej p typu smerník.

• Mark(var p: pointer)

• MaxAvail: longint

• MemAvail: longint

• New(var p: pointer)

• Release(var p: pointer)

vracia hromadu do stavu, pred ktorým bola smerníku p priradená hodnota procedúrou Mark; uvoľňuje všetky premenné vytvorené buď procedúrou New alebo GetMem, ktoré boli vytvorené po priradení hodnoty smerníku p procedúrou Mark.

Spájané zoznamy (linked list)

• každý prvok zoznamu je záznam (record) a okrem samotnej informácie obsahuje smerník na nasledovníka v zozname
• posledný prvok má hodnotu nasledovníka nil:

type
  prvok = integer;
  PVrchol = ^TVrchol;
  TVrchol = record
    info: prvok;
    next: PVrchol;
  end;

var
  z,p: PVrchol;
begin
  z:=nil;                             { z je prázdny zoznam}
    new(z); z^.info:=1; z^.next:=nil;   { z je jednoprvkový zoznam}
    new(p); p^.info:=2; p^.next:=nil;   { p je jednoprvkový zoznam}
   z^.next:=p;                         { z je dvojprvkový zoznam}
   new(p); p^.info:=3; p^.next:=nil;   { p je jednoprvkový zoznam}
   z^.next^.next:=p;                   { z je trojprvkový zoznam}
end;

 Writeln(z^.info, ' ', z^.next^.info,' 'z^.next^.next^.info);

  p:=z;
  while p<>nil do begin
    write(p^.info,' ');
    p:=p^.next;
  end;

  while z<>nil do begin
    dispose(z);
    z:=z^.next;
  end;

  while z<>nil do begin
    p:=z^.next;
    dispose(z);
    z:=p;
  end;

Poznámka:

• ak je info časť nejaká dynamická premenná, napr. string, dynamické pole, objekt alebo smerník na nejakú štruktúru, tak dispose vrcholu automaticky neuvoľňuje aj tieto premenné - tieto budú naďalej udržiavané v heap
• toto môže niekedy spôsobiť problémy s dynamickou pamäťou - zrejme pre malé školské úlohy nie, ale v budúcnosti pri nejakých zložitejších úlohách môžeme na toto natrafiť
• také isté dôsledky to má aj vtedy, keď info časť je záznam, ktorý v sebe obsahuje niečo dynamické
• preto niekedy pred samotným dispose sa uvoľňuje aj pamäť dynamického info, napr. pre string to môže byť z^.info:=''; alebo pre dynamické pole z^.info:=nil; a až potom sa robí dispose(z);

Postupné pridávanie prvkov do zoznamu

  z:=nil;
  for i:=1 to 20 do begin
    new(p); p^.info:=i; p^.next:=z;
    z:=p;
  end;

  Assign(t,'cisla.txt'); Reset(t);
  z:=nil;
  while not eof(t) do begin
    new(p); read(t,p^.info); p^.next:=nil;
    if z=nil then z:=p
    else begin
      k:=z;
      while k^.next<>nil do k:=k^.next;{ nájde posledný prvok v zozname}
      k^.next:=p;
    end;
  end;
  Close(t);

  Assign(t,'cisla.txt'); Reset(t);
  z:=nil; k:=nil;
  while not eof(t) do begin
    new(p); read(t,p^.info); p^.next:=nil;
    if z=nil then z:=p
    else k^.next:=p;
    k:=p;
  end;
  Close(t);

  p:=z;
  while p<>nil do
    with p^ do begin
      write(info,' ');
      p:=next;
    end;

Operácie na zozname

type
  prvok = integer;
  Svrchol = ^Tvrchol;
  TVrchol = record
    info:prvok;
    next:SVrchol;
end;

function Tvrchol_Create(i:prvok; n:TVrchol): SVrchol;
var t: SVrchol;
begin
  New(t};
With t^ do
begin info:=i; next:=n; end;
  Tvrchol_Create:= t;
end;


function Tvrchol_vypis(z: SVrchol): string;
begin
  Result:=' '+Str(z^.info);
end;

Var z, k : Svrchol;  {Smerniky na zaciatok a koniec}

{ Na zaciatku v oboch je ulozeny nil }

function Tzoznam_vypis:string;
var
  p:TVrchol;
begin
  Result:=''; p:=z;
  while p<>nil do begin
    Result:=Result+p_vypis(p);
    p:=p^.next;
  end;

procedure Tzoznam_pridajZ(i:prvok);

begin
  z:=Tvrchol_Create(i,z);
  if k=nil then k:=z;
end;

procedure Tzoznam_pridajKon(i:prvok);
var
  p:TVrchol;
begin
  p:=Tvrchol_Create(i,nil);
  if z=nil then z:=p
  else k^.next:=p;
  k:=p;
end;

procedure Tzoznam_vsun(pred: integer; i:prvok);
var
  p,q:TVrchol;
begin
  if pred<2 then pridajZ(i)
  else begin
    q:=z;
    while (q<>nil) and (pred>2) do begin
      dec(pred);
      q:=q^.next;
    end;
    p:=Tvrchol_Create(i,nil);
    if q=nil then k^.next:=p
    else begin
      p^.next:=q^.next;
      q^.next:=p;
    end;
    if p^.next=nil then k:=p;
  end;
end;

Matematická definícia presne popisuje pojem čiastočne usporiadaná množina. čiastočné usporiadanie množiny S je vo všeobecnosti dané reláciou medzi prvkami množiny S. Pre tri rôzne prvky x, y, z Î S táto relácia spĺňa nasledujúce vlastnosti x Đ y:

• tranzitívnosť: Ak platí xĐy a yĐz, tak platí xĐz.
• antisymetria: Ak platí xĐy, tak neplatí yĐx.
• ireflexívnosť: Neplatí xĐx.

• Prirodzené čísla
• Slová v slovníku
• Úloha rozdelená na podúlohy
• Plán štúdia jedného študenta (predmety s prerekvizitami)
• Podprogramy v programoch

Z praktických dôvodov sa budeme zaoberať konečnými čiastočne usporiadanými množinami.

Problém topologického triedenia spočíva vo vnorení čiastočného usporiadania do lineárneho usporiadania. Graficky to znamená, že vrcholy grafu (prvky množiny) nakreslíme do radu a všetky šípky hrán budú smerovať jedným smerom. Vlastnosti čiastočne usporiadanej množiny zaručujú, že graf neobsahuje žiadne cykly.

Postup pri hľadaní jedného z možných riešení je veľmi jednoduchý a môžeme ho vyjadriť takto: Začneme výberom prvkov, ktorým nepredchádza žiadny iný prvok (musí byť aspoň jeden, pretože inak by graf obsahoval cyklus). Tieto prvky odstránime z množiny S a zaradíme ich do vytváraného zoznamu, reprezentujúceho lineárne usporiadanie. Zostávajúca množina je stále čiastočne usporiadaná, a preto môžeme na ňu aplikovať ten istý algoritmus až dovtedy, kým nebude prázdna.

Aby sme tento algoritmus mohli presnejšie zapísať, musíme sa rozhodnúť o spôsobe reprezentácie množiny a čiastočného usporiadania.

• identifikačného kľúča (kluc),
• množiny nasledovníkov (smerník priv) a
• celkového počtu predchodcov (pocit).

Prvky spojíme do lineárneho zoznamu prepojeného smerníkom dalsi. Budeme predpokladať, že kľúče sú vyjadrené celočíselnými hodnotami (ale nie nutne po sebe idúcimi číslami 1 až n).

Zoznam nasledovníkov bude tiež lineárny zoznam pripojený k danému prvku pomocou smerníka priv. Prvok v tomto zozname bude teda ukazovať na nasledovníka pomocou smerníka vrch a na ďalší prvok tohto zoznamu pomocou smerníka dalsi.