Rešitev: Podatkovna struktura VS10

Iz MaFiRaWiki

Naloga: Podatkovna struktura VS10

Pogledamo si impementacijo naravnih števil NAT.

 
 Clear[Nic, Ena, Naslednik, JeEnak, Vsota, JeVecji, JeManjsi, Vrednost];

 Ena;
 Nic;
 Ena := Naslednik[Nic];
 
 Vsota[Nic, n_] := n;
 Vsota[Naslednik[m_], n_] := Naslednik[Vsota[m, n]];
 
 JeEnak[Nic, Nic] := True;
 JeEnak[Nic, n_] := False;
 JeEnak[n_, Nic] := False;
 JeEnak[Naslednik[n_], Naslednik[m_]] := JeEnak[n, m];
 
 JeVecji[Nic, m_] := False;
 JeVecji[Naslednik[n_], Nic] := True;
 JeVecji[Naslednik[n_], Naslednik[m_]] := JeVecji[n, m];
 
 JeManjsi[n_, m_] := JeVecji[m, n];
 
 JeVecjiEnak[n_, m_] := Or[JeVecji[n, m], JeEnak[n, m]];
 
 JeManjsiEnak[n_, m_] := JeVecjiEnak[m, n];
 
 Vrednost[Nic] := 0;
 Vrednost[Naslednik[s_]] := 1 + Vrednost[s];

Pogledamo si prosto implementacijo Sklada.

 Clear[Pripravi, Vstavi, JePrazen, Vrh, OdstraniS, StElementov];
 
 JePrazen[PripraviS[]] := True;
 JePrazen[VstaviS[s_, e_]] := False;
 JePrazen::usage = "Funkcija JePrazen[s] vrne True, če je sklad s prazen in False sicer.";
 
 Vrh[Pripravi[]] := Null;
 Vrh[Vstavi[s_, e_]] := e;
 Vrh::usage = "Funkcija Vrh[s] vrne zgornji element sklada s. Če je sklad prazen, vrne Null.";
 
 OdstraniS[Pripravi[]] := Pripravi[]; 
 OdstraniS[Vstavi[s_, e_]] := s;
 OdstraniS::usage = "Funkcija OdstraniS[s] vrne sklad s brez zgornjega elementa. Če je sklad prazen, vrne prazni sklad.";
 
 StElementov[Pripravi[]] := Nic;
 StElementov[VstaviS[s_, e_]] := Vsota[StElementovS[s] , Ena];
 StElementov::usage = "Funkcija StElementov[s] vrne število elementov v skladu s.";

Pogledamo si še prosto implementacijo Vrste

 JePrazna[Pripravi[]] := True;
 JePrazna[Vstavi[v_, e_]] := False;
 JePrazna::usage = "Funkcija preveri, če je dana vrsta prazna";
 
 OdstraniV[Pripravi[]] := Pripravi[];
 OdstraniV[Vstavi[v_, e_]] := If[JePrazna[v], Pripravi[], Vstavi[OdstraniV[v], e]];
 OdstraniV::usage = "Funkcija odstrani element na čelu vrste.";
 
 Celo[Pripravi[]] := Null;
 Celo[Vstavi[v_, e_]] := If[JePrazna[v], e, Celo[v]];
 Celo:usage = "Funkcija izpiše element na čelu vrste";
 
 Rep[Pripravi[]] := Null;
 Rep[Vstavi[v_, e_]] := e;
 Rep:usage = "Funkcija izpiše element na repu vrste";

 Dolzina[Pripravi[]] := Nic;
 Dolzina[Vstavi[v_, e_]] := Vsota[Dolzina[v], Ena];
 Dolzina::usage = "Funkcija izpiše število elementov v vrsti.";

S pomočjo implementacij naravnih števil, vrste in sklada implementiramo podatkovno strukturo VS10.

 Clear[Pripravi, Vstavi, JePrazna, Vrh, Odstrani, Celo, Deset, JeKratka];
 
 JePrazna[vs_] := TrueQ[JeEnak[Dolzina[vs], Nic]];
 JePrazna::usage = "Funkcija preveri, če je naša vrsta/sklad prazna";
 
 Celo[Pripravi[]] := Null;
 Celo[Vstavi[vs_, e_]] := If[JePrazna[vs], e, Celo[vs]];
 Celo::usage = "Funkcija izpiše element na čelu.";
 
 Dolzina[Pripravi[]] := Nic;
 Dolzina [Vstavi[vs_, e_]] := Vsota[Dolzina[vs], Ena];
 Dolzina::usage = "FUnkcija izračuna dolžino vrste (število elementov v skladu)";

 Deset := Naslednik[Naslednik[Naslednik[Naslednik[Naslednik[Naslednik[Naslednik[Naslednik[Naslednik[Naslednik[Nic]]]]]]]]]];
 
 JeKratka[vs_] := JeVecji[Deset, Dolzina[vs]];
 JeKratka::usage = "Funkcija preveri, če je vrsta krajša od 10 elementov";
 
 Odstrani[vs_] := If[
      JeManjsi[Dolzina[vs], Deset],
      OdstraniV[vs],
      OdstraniS[vs]];

Delovanje preverimo na dveh primerih:

 In[1]:= Odstrani[Vstavi[Vstavi[Pripravi[], e], a]]
 Out[1]:= Vstavi[Pripravi[], a]
 
 In[2]:= Odstrani[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Pripravi[], a], s], d], e], r], t], g], h], t], z], d]]
 Out[2]:= Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Vstavi[Pripravi[], a], s], d], e],r], t], g], h], t], z]


Glej tudi

Osebna orodja