Rešitev: Implementacija dvojne vrste v Mathematici

Iz MaFiRaWiki

Naloga: Implementacija dvojne vrste v Mathematici

  • Opis strukture Dvojna vrsta:

Dvojna vrsta je podatkovna struktura, pri kateri lahko, za razliko od podatkovne strukture vrsta, elemente vstavljamo in brišemo tako iz začetka kot iz konca vrste. Vrsta ima torej dva repa. Dvojna vrsta je primer urejenega seznama.

  • Operacije:

Pripravi : {} --> DVrsta

VstaviNaCelo: DVrsta x Element --> DVrsta

OdstraniCelo: DVrsta --> DVrsta

VstaviNaRep: DVrsta x Element --> DVrsta

OdstraniRep: DVrsta --> DVrsta

JePrazna: DVrsta --> Boolean

Rep: DVrsta --> Element

Celo: DVrsta --> Element


  • Prosta implementacija dvojne vrste:
Clear[Pripravi,VstaviNaCelo,OdstraniCelo,OdstraniRep,VstaviNaRep,JePrazna,Celo,Rep];

JePrazna[Pripravi[]]:=True;
JePrazna[VstaviNaCelo[v_,e_]]:=False;
JePrazna[VstaviNaRep[v_,e_]]:=False;

OdstraniRep[Pripravi[]]:=Pripravi[];
OdstraniRep[VstaviNaRep[v_,e_]]:=v;
OdstraniRep[VstaviNaCelo[v_,e_]]:=If[JePrazna[v],Pripravi[],VstaviNaCelo[OdstraniRep[v],e]];

OdstraniCelo[Pripravi[]]:=Pripravi[];
OdstraniCelo[VstaviNaCelo[v_,e_]]:=v;
OdstraniCelo[VstaviNaRep[v_,e_]]:=If[JePrazna[v],Pripravi[],VstaviNaRep[OdstraniCelo[v],e]];

Celo[Pripravi[]]:=Null;
Celo[VstaviNaCelo[v_,e_]]:= e;
Celo[VstaviNaRep[v_,e_]]:=If[JePrazna[v],e,Celo[v]];

Rep[Pripravi[]]:=Null;
Rep[VstaviNaRep[v_,e_]]:= e;
Rep[VstaviNaCelo[v_,e_]]:=If[JePrazna[v],e,Rep[v]];

JePrazna::usage ="Funkcija JePrazna[v] pove, ali je vrsta v prazna ali ne."
OdstraniRep::usage = "Funkcija OdstraniRep[v] vrne vrsto v brez repa."
OdstraniCelo::usage = "Funkcija OdstraniCelo[v] vrne vrsto v brez čela."
Rep::usage = "Funkcija Rep[v] vrne rep vrste v."
Celo::usage = "Funkcija Celo[v] vrne čelo vrste v."
  • Opomba:

Operaciji

OdstraniRep[Pripravi[]]:=Pripravi[];

OdstraniCelo[Pripravi[]]:=Pripravi[];

bi lahko sporočila napako. Odločili smo se, da prazne vrste ne moremo še bolj izprazniti in napake ne sporočamo.

  • Primer uporabe pri prosti implementaciji:
In[17]:=Clear[v,vv,vvv];

In[18]:=v=VstaviNaCelo[VstaviNaRep[VstaviNaCelo[VstaviNaRep[Pripravi[],a],b],c],d]

Out[18]=VstaviNaCelo[VstaviNaRep[VstaviNaCelo[VstaviNaRep[Pripravi[],a],b],c],d]

In[19]:=Celo[v]

Out[19]=d

In[20]:=Rep[v]

Out[20]=c

In[21]:=vv=OdstraniRep[v]

Out[21]=VstaviNaCelo[VstaviNaCelo[VstaviNaRep[Pripravi[],a],b],d]

In[22]:=Rep[vv]

Out[22]=a

In[23]:=vvv =OdstraniRep[OdstraniCelo[vv]]
JePrazna[vvv]

Out[23]=VstaviNaCelo[Pripravi[],b]

Out[24]=False
  • Implementacija vrste s seznamom:
Clear[Pripravi,VstaviNaCelo,OdstraniCelo,OdstraniRep, VstaviNaRep,JePrazna,Celo,Rep];

Pripravi[]:={}
VstaviNaRep[v_, e_]:=Prepend[v,e]
VstaviNaCelo[v_, e_]:=Append[v,e]
JePrazna[{}]:=True
JePrazna[{___}]:=False
Celo[v_]:=Last[v]
Rep[v_]:=First[v]
OdstraniRep[v_]:=Drop[v,1]
OdstraniCelo[v_]:=Drop[v,-1]

  • Primer uporabe pri implementaciji s seznamom:
In[35]:=Clear[v];

In[36]:=v=VstaviNaCelo[VstaviNaRep[VstaviNaCelo[VstaviNaRep[Pripravi[],a],b],c],d]

Out[36]={c,a,b,d}

In[37]:=Celo[v]

Out[37]=d

In[38]:=Rep[v]

Out[38]=c

In[39]:=vv=OdstraniRep[v]

Out[39]={a,b,d}

In[40]:=Rep[vv]

Out[40]=a

In[41]:=vvv =OdstraniRep[OdstraniCelo[vv]]
JePrazna[vvv]

Out[41]={b}

Out[42]=False

Glej tudi

Osebna orodja