Dynamick‚ çtrukt£ry £dajov

V predch dzaj£cich kapitol ch 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. 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 po§ijeme pre 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.

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‚ a typy smern¡k

Dynamickou premennou budeme rozumieœ tak£ premenn£, ktor  nie je zaveden  v deklar cii premennìch, ale vznikne vykonan¡m çpeci lneho pr¡kazu.

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.

Tento popis m  tvar

^dom‚novì typ

Dom‚novìm typom m“§e byœ –ubovo–nì typ a v popise typu smern¡k sa oznaŸuje identifik torom typu. Napr¡klad,

ak je v programe definovanì typ MENO, potom pomocou deklar cie

type SMER=^MENO;

je definovanì typ SMER, ktor‚ho hodnotami s£ smern¡ky identifikuj£ce dynamick‚ premenn‚ typu MENO.

V popise typu smern¡k m“§e byœ pou§itì tie§ identifik tor typu, ktorì na danom nieste programu nie je eçte definovanì. T to vìnimka je nutn  k tomu, aby bolo mo§n‚ definovaœ typy dynamickìch premennìch, z ktorìch sa vytv raj£ smern¡kov‚ reprezent cie dynamickìch £dajovìch çtrukt£r.

Zvl çtnu hodnotu, 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

P:= nil,

tak premenn  P neukazuje na §iadnu dynamick£ premenn£.

Ovl danie vo–nej pam„ti

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œ.

Smern¡kovej premennej m“§eme priradiœ hodnotu troma sp“sobmi:

· New(...),

· 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.

· funkciou Ptr - function Ptr(segment, offset:word): pointer;

Proced£ry a funkcie pre dynamick£ alok ciu:

· Dispose(var p: pointer)

uvo–åuje dynamick£ premenn£, na ktor£ ukazuje premenn  p; hodnota smern¡ka po jej vykonan¡ zost va nedefinovan .

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

uvo–åuje pam„œ stanovenej ve–kosti; smern¡k mus¡ ukazovaœ na dynamick£ premenn£, ktor  bola vytvoren  proced£rou GetMem; size urŸuje poŸet uvo–åovanìch bytov.

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

zaklad  nov£ dynamick£ premenn£ uvedenej ve–kosti size (<= 65521) a ulo§¡ jej adresu do premennej p typu smern¡k.

· Mark(var p: pointer)

zaznamen  do premennej p aktu lnu adresu hromady (heap); t to adresa m“§e byœ nesk“r vyu§it  proced£rou Release;

p m“§e byœ smern¡k –ubovo–n‚ho typu.

· MaxAvail: logint

vìsledkom je ve–kosœ maxim lnnej s£vislej pam„ti v hromade s£hlas¡ s maxim lnou ve–kosœou dynamickej premennej, ktor£ je mo§n‚ alokovaœ.

· MemAvail: logint

vìsledkom je ve–kosœ s£Ÿtu vçetkìch vo–nìch blokov pam„ti v hromade.

· New(var p: pointer)

vytv ra nov£ dynamick£ premenn£ a nastavuje smern¡k na åu.

· 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.

Topologick‚ triedenie - TOPSORT

O topologickom trieden¡ hovor¡me v s£vislosti s ŸiastoŸne usporiadanìmi mno§inami, na ktorìch je definovan  rel cia ŸiastoŸn‚ho usporiadania, t.j. takìch mno§¡n, v ktorìch je definovan‚ usporiadanie len pre niektor‚ dvojice prvkov, (nemus¡ byœ pre vçetky dvojice).

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 patriace do mno§iny S t to rel cia sp’åa nasleduj£ce vlastnosti (axi¢my):

· 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.

Pr¡klady ŸiastoŸne usporiadanìch mno§¡n:

· Matematickì pr¡klad

· Slov  v slovn¡ku

· éloha rozdelen  na pod£lohy

· Individu lny pl n vìuŸby

· V programoch

Z praktickìch d“vodov sa budeme zaoberaœ koneŸnìmi ŸiastoŸne usporiadanìmi mno§inami.

¬iastoŸne usporiadan‚ mno§iny m“§eme zobraziœ n zorne pomocou grafov. Prvky mno§iny bud£ ulo§en‚ vo vrcholoch a pomocou orientovanìch hr n vyjadr¡me smer usporiadania.

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.

Ka§dì prvok m“§eme charakterizovaœ pomocou troch atrib£tov: 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. Teda odpovedaj£ce typy £dajov bud£ maœ nasleduj£ci tvar:

Type psmer = ^vrchol;

lsmer = ^prives;

vrchol = record

kluc:hodnota;

pocit:integer;

dalsi:psmer;

priv:lsmer;

end;

prives = record

vrch:psmer;

dalsi:lsmer;

end;

Celì program m“§e maœ nasleduj£ci tvar:

program TOPSORT;

type hodnota = integer;

psmer = ^vrchol;

lsmer = ^prives;

vrchol = record

kluc:hodnota;

pocit:integer;

dalsi:psmer;

priv:lsmer;

end;

prives = record

vrch:psmer;

dalsi:lsmer;

end;

var

hlava, chvost, p, q:psmer;

t:lsmer;

z:integer;

ff:text;

x, y:hodnota;

function l(w:hodnota):psmer;

{Hodnotou funkcie je smernik k vrcholu, v ktorom je ulozene w}

var

h:psmer;

begin

h:=hlava; chvost^.kluc:=w; {Ulozenie zarazky}

while h^.kluc<>w do h:=h^.dalsi;

if h=chvost then

begin

{Ziadny prvok s hodnotou w nebol ulozeny}

new(chvost); z:=z+1;

chvost^.pocit:=0; chvost^.dalsi:=nil;

chvost^.priv:=nil;

h^.dalsi:=chvost;

end;

l:=h

end; {Koniec funkcie l}

begin

{ Vytvorenie prazdnej struktury}

z:=0;

new(hlava); chvost:=hlava;

with hlava^ do

begin dalsi:=nil; priv:=nil; pocit:=0; end;

{Vstupna faza}

assign(ff,'tpsort.dta'); rewrite(ff);

read(x);

while x<>0 do

begin

readln(y); writeln(ff,'x= ',x:3,'=> y= ',y:3);

p:=l(x); q:=l(y);

new(t);

t^.dalsi:=p^.priv; t^.vrch:=q;

p^.priv:=t; inc(q^.pocit);

read(x)

end;

{Hladanie clenov s nulovym poctom predchodcov}

p:=hlava; hlava:=nil;

while p<>chvost do

begin

q:=p; p:=p^.dalsi;

if q^.pocit=0 then

begin

q^.dalsi:=hlava; hlava:=q;

end;

end;

writeln('Pocet vrcholov je ',z:3);

{Vystupna faza}

q:=hlava;

while q<>nil do

begin

writeln(q^.kluc); writeln(ff,q^.kluc);

z:=z-1;

t:=q^.priv; q:=q^.dalsi;

while t<>nil do

begin

p:=t^.vrch; dec(p^.pocit);

if p^.pocit = 0 then

begin

{Ulozenie do zoznamu prvkov s nulovym poctom predchodcov}

p^.dalsi:=q; q:=p;

end;

t:=t^.dalsi;

end;

end;

if z<>0 then

begin writeln(' Tato mnozina nie je ciastocne usporiadana');

writeln(ff,'Tato mnozina nie je ciastocne usporiadana')

end;

close(ff);

readln;

end.