Podatkovne strukture

Podatkovne strukture

Avtor: Matija Lokar

Več o projektu...

Podatkovne strukture

  • Podatkovna struktura je sistematični način kako organizirati skupino podatkov.
  • Za vsako podatkovno strukturo potrebujemo postopke za vstavljanje, brisanje, iskanje in podobno.

Abstraktni podatkovni tipi

  • Ko pišemo programe, nam je vseeno, kako je npr. zares predstavljen niz (npr. list v p.j. Python) v pomnilniku računalnika – le v spremenljivko shranimo npr. [] ... in uporabljamo dovoljene operacije.
  • Prav tako npr. ne vemo, kako je prestavljen objekt Button v p.j. Delphi. Poznamo le dovoljene operacije nad njim.
  • Abstraktni podatkovni tip je podatkovni tip, katerega predstavitev je skrita in ne vpliva na kodo programa
  • Z "odstranitvijo" vedenja o dejanski predstavitvi laže pišemo predvsem večje programe.
  • neodvisnost od dejanske predstavitve KAJ je struktura in ne KAKO jo predstaviti

Opis strukture

structure ime strukture

begin

declare

opis funkcij (metod)

where

opis aksiomov (pravil obnašanja funkcij)

end

Sklad

(Slika1.png)

Sklad

  • skladovnica zabojev
  • Držalo PEZ bonbonov
  • nabojnik, držalo za krožnike, hodnik brez izhoda, …
  • Prvi noter, zadnji ven
  • zadnji noter, prvi ven – LIFO (Last In First Out)‏

Kaj APS je in zakaj jo potrebujemo

  • Za reševanje nekega problema potrebujemo prostor za hranjenje podatkov, ki se bo obnašal tako kot sklad (skladovnica, upošteval princip LIFO)‏
  • Če bomo programirali v Pythonu – potrebujemo objekt iz razreda Sklad
  • V razredu Sklad morajo biti metode, ki delujejo tako, kot pričakujemo od sklada.
  • Dejanski način predstavite podatkov znotraj objekta nas čisto nič ne zanima – potrebujemo le ustrezne metode!
  • Če bomo delali v kakšnem drugem programskem jeziku bo predstavitev sklada sicer drugačna kot v Pythonu, a ustrezne metode (podprogrami, funkcije, ..) se bodo morali “obnašati” v skladu s principom LIFO.

Podatkovne strukture

  • podatki
  • operacije nad podatki
  • lastnosti operacij
  • neodvisnost od dejanske predstavitve KAJ je struktura in ne KAKO jo predstaviti
  • ABSTRAKTNE PODATKOVNE STRUKTURE
  • Abstract Data Type (ADT)‏

Sklad

  • Podatke vstavljamo in jemljemo iz sklada na enem koncu

  • Operacije:

    • pripravi sklad
    • vstavi element v sklad (push)‏
    • poglej element na vrhu sklada (peek, top)‏
    • odstrani element na vrhu sklada (pop)‏
    • je sklad prazen (empty)‏

Sklad

Uporaba sklada

  • Obiskane strani v brskalniku
  • Zaporedje UNDO ukazov
  • računalniški sklad (rekurzija, dodeljevanje pomnilnika ob klicu funkcij, …),
  • Sklad klicev metod
  • Pomožni pomnilnik pri različnih algoritmih
  • Nastopa kot del drugih podatkovnih struktur

ADT Sklad

structure SKLAD
begin
   declare // naštejemo operacije z vhodnimi in izhodnimi podatki
  pripravi: 0 -->  sklad;
  vstavi: (sklad, podatek) --> sklad;
  vrh: sklad --> podatek;
  odstrani: sklad --> sklad;
  prazen: sklad --> {true, false};
   where // opis delovanja operacij
  // kako se obnaša operacija prazen
  // dve možnosti – dobi prazen sklad ali pa dobi neprazen sklad
  prazen(pripravi) ::= true; // kako deluje metoda na poljubnem praznem skladu
  prazen(vstavi(s,p)) ::= false; // kako deluje metoda na poljubnem nepraznem skladu
  // kako se obnaša operacija odstrani
  // spet dve možnosti – dobi prazen sklad ali pa dobi neprazen sklad
  odstrani(pripravi) ::= NAPAKA; // kako deluje metoda na poljubnem praznem skladu
  odstrani(vstavi(s,p)) ::= s;  // vstavi(s,p) je LE EDEN OD NAČINOV, kako dobimo neprazen sklad
  // kako se obnaša operacija vrh
  vrh(pripravi) ::= NAPAKA; // lahko bi tudi bilo vrh(odstrani(vstavi(pripravi,p))) ::= NAPAKA
  vrh(vstavi(s,p)) ::= p;
end;
// obnašanja operacij pripravi in vstavi ni bilo potrebno opisati – sta že določeni z obnašanjem ostalih!

Delo s skladom

  • S pomočjo osnovnih operacij nad skladom preštej število podatkov v skladu – sklada po tem ne potrebjemo več.
  • S pomočjo osnovnih operacij nad skladom preštej število podatkov v skladu – sklada naj ostane nespremenjen.
  • Obrni vrstni red elementov v skladu.
  • Za vsak element v skladu pokliči metodo obdelaj, ki kot argument sprejme element sklada. Sklada po koncu ne potrebujemo več.
  • Za vsak element v skladu pokliči metodo obdelaj, ki kot argument sprejme element sklada. Sklada mora ostati nespremenjen.

Delo s skladom

  • S pomočjo osnovnih operacij nad skladom sestavi operacijo n-ti, ki vrne podatek o n-tem element v skladu, če obstaja. Sklada potem ne potrebujemo več!
  • Odstrani n-ti element iz sklada – sklad ima po operacij vse podatke tako kot prvotno, le n-tega ni.
  • V dveh skladih so podatki urejeni. Sestavi metodo, ki jih preloži v nov sklad v katerem so podatki tudi urejeni (v enakem vrstnem redu).
  • Preloži elemente iz tabele v sklad.

N-ti

n_ti: (sklad, int) podatek

n-ti v skladu

def n_ti(sklad, n) :
  # vrne n-ti podatek tipa Podatek v nizu
  if sklad.prazen() :
     NAPAKA
  else  :
     pod = sklad.vrh()
     sklad.odstrani()
     if (n == 1) :
         return pod # če iščemo prvega, je to vrhnji
     else :
        return n_ti(sklad, n-1) # v preostanku sklada poiščemo n-1 tega

N-ti

def n_ti(sklad, n) :
  # vrne n-ti podatek tipa Podatek v nizu
  if sklad.prazen() :
      raise ValueError('Prazen sklad!')
  else :
     pod = sklad.vrh()
     sklad.odstrani()
     if (n == 1) :
         return pod # če iščemo prvega, je to vrhnji
     else :
        return n_ti(sklad,n-1)
            # v preostanku sklada poiščemo n-1 tega

N-ti

  • Operacija “uniči” sklad
  • Seveda možna nerekurzivna različica!

  • “Nedestruktivna” oblika:

    • Zgornjih n – 1 elementov je napoti
    • Preložimo jih v pomožni sklad
    • Odstranimo element (n-ti)‏
    • Preložimo elemente iz pomožnega sklada nazaj

N-ti

  • Kaj pa, če je n prevelik?
  • Metoda naj v tem primeru sproži izjemo.
  • A sklad mora ostati nespremenjen.
0%
0%