Rešitev: Implementacija skladja

Iz MaFiRaWiki

Naloga: Implementacija skladja



KAJ JE SKLADJE?

Skladje je podatkovna struktura pri kateri obravnavamo več skladov istočasno.

KAKO DELUJE?

Za skladje veljajo podobni aksiomi in podobne operacije kot pri skladu (jasno v nadaljevanju).
Razlika je le v tem, da pri skladju ne vemo kako dolg bo seznam, saj ne vemo koliko elementov bomo 
vstavili v posamezen sklad v skladju. Ravno zato pa si dopuščamo možnost,da lahko v vsakem trenutku 
obseg skladja povečamo. Pri skladju torej poznamo operacije: Pripravi, Vstavi, Odstrani, JePrazen, Vrh in StElementov.
Z njihovo pomočjo lahko gradimo skladje (Vstavi) in sicer tako, da v posamezen sklad v skladju dodajamo elemente 
(enako kot pri skladu) nato pa ga lahko poljubno spreminjamo (Odstrani), ugotavljamo koliko elementov je v 
posameznem skladu (StElementov), če ti sploh obstajajo (JePrazen). Same operacije in  njihove funkcije 
(ki pravzaprav delujejo na posameznem skladu) bom v nadaljevanju bolje spoznali.


IMPLEMENTACIJA SKLADJA (IN SKLADA)

Clear[Pripravi, Vstavi, Odstrani, JePrazen, Vrh, StElementov]

Pripravi[] := {}
Pripravi::usage = "Pripravi[] nam vrne prazeno skladje oz. sklad.";
 
Vstavi[s_, e_] := Join[s, {e}]
Vstavi::usage =
     "Vstavi[s,e] je operacija, ki na vrh sklada s doda element e in nam vrne \
novi sklad.";

Vstavi[s_, i_, e_] /; StElementov[s] < 
    i := Vstavi[Vstavi[s, Pripravi[]], i, e]
Vstavi[s_, i_, e_] := MapAt[Vstavi[#, e] &, s, i]
Vstavi::usage = "Vstavi[s,i,e] i-temu skladu v skladju s doda element e in \
nam vrne novo skladje. Ce nimamo dovolj skladov v skladju, potem 
nam pogoj, StElementov[s]<i, omogoči da skladju dodamo nove 
    prazne sklade (dodajajo se dokler je pogoj izpolnjen).";

JePrazen[s_] := (Length[s] == 0)
JePrazen::usage = "JePrazen[s] nam vrne True, če 
    je sklad s prazen, sicer nam vrne False.";

JePrazen[s_, i_] /; StElementov[s] < i := Null
JePrazen[s_, i_] := JePrazen[s[[i]]]
JePrazen::usage = "
    JePrazen[s,i] nam vrne True, če je i-ti sklad skladja s prazen, sicer nam 
    vrne False.";

Vrh[s_] /; Length[s] == 0 := Null
Vrh[s_] := Last[s]
Vrh::usage = "Vrh[s] nam vrne vrh sklada s (zadnji dodani element).";

Vrh[s_, i_] /; StElementov[s] < i := Null
Vrh[s_, i_] := Vrh[s[[i]]] 
Vrh::usage = "Vrh[s,i] nam vrne vrh i-tega sklada skladja s.";

Odstrani[s_] /; s == {} := s
Odstrani[s_] := Most[s]
Odstrani::usage =
     "Odstrani[s] je operacija, ki odstrani element iz sklada s (tistega, ki 
    smo zadnjega dodali) in vrne nov sklad.";

Odstrani[s_, i_] /; StElementov[s] < i := s
Odstrani[s_, i_] :=
 MapAt[Odstrani[#] &, s, i]

    Odstrani::usage = "Odstrani[s,i] je operacija, ki odstrani element iz i-
    tega sklada v skladju s in vrne novo skladje.";

StElementov[s_] := Length[s]
StElementov::usage = "StElementov[s] nam vrne število elementov v skladu s.";

StElementov[s_, i_] /; StElementov[s] < i := Null
StElementov[s_, i_] := StElementov[s[[i]]]
StElementov::usage = "
StElementov[s,i] nam vrne stevilo elementov v i-tem skladu skladja s." ;

Sedaj smo prikazali implementacijo skladja (in tudi sklada). Za lažjo predstavo kako implementacija 
skladja deluje t.j. kako delujejo posamezne operacije na skladju, pa si oglejmo naslednji primer.

PRIMER:

Clear[skladje]

skladje=Pripravi[]

{}

skladje=Vstavi[skladje,4,a]

{{},{},{},{a}}

skladje=Vstavi[skladje,2,b]

{{},{b},{},{a}}

skladje=Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[skladje,4,d],1,2],4,e],5,z],1,h],5,c],8,i],6,9]

{{2,h},{b},{},{a,d,e},{z,c},{9},{},{i}}

StElementov[skladje,4]

3

StElementov[skladje,7]

0

Vrh[skladje,5]

c

Vrh[skladje,4]

e

Odstrani[skladje,4]

{{2,h},{b},{},{a,d},{z,c},{9},{},{i}}

skladje

{{2,h},{b},{},{a,d,e},{z,c},{9},{},{i}}

skladje=Odstrani[skladje,4]

{{2,h},{b},{},{a,d},{z,c},{9},{},{i}}

skladje

{{2,h},{b},{},{a,d},{z,c},{9},{},{i}}

Vrh[skladje,4]

d

JePrazen[skladje,7]

True

JePrazen[skladje,4]

False


Zgled s tabelo:








Glej tudi

Osebna orodja