Izpitno vprašanje DIRI2005 7500

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)


Vsebina

Vprašanje

Formalno opiši podatkovno strukturo vrsta.


Odgovor

Lastnosti

Vrsta je abstraktna podatkovna struktura, pri kateri elemente vstavljamo na enem koncu, jemljemo jih na drugem. Zato elementi zapuščajo vrsto v enakem vrstnem redu, kot so vanjo prišli: prvi noter, prvi ven (FIFO - First In First Out).

Uporabljamo jo, kadar želimo iz strukture dobiti element, ki najdlje čaka:

  • povsod, kjer se moramo držati vrstnega reda prihoda
  • simulacije, tiskanje

Različice:

Operacije

  1. pripravi vrsto
  2. vstavi element v vrsto
  3. element na začetku vrste
  4. odstrani
  5. prazna

Formalna predstavitev

structure VRSTA

declare
pripravi: 0 → vrsta;
vstavi: (vrsta, podatek) → vrsta;
zacetek: vrsta → podatek;
odstrani: vrsta → vrsta;
prazna: vrsta → {true, false};
where
prazna(pripravi) ::= true;
prazna(vstavi(v,p)) ::= false;
odstrani(pripravi) ::= NAPAKA;
odstrani(vstavi(v,p)) ::=
if (prazna(v)) then pripravi
else vstavi(odstrani(v),p);
zacetek(pripravi) ::= NAPAKA;
zacetek(vstavi(v,p)) ::=
if (prazna(v)) then p
else zacetek(v);

end;

Predstavitve vrste

Vrsto lahko predstavimo z naslednjimi podatkovnimi strukturami:

  1. Tabela: nastopi problem drsenja vrste
  2. Krožna tabela: odpravimo problem drsenja vrste, operacije začetek in konec izvajamo po modulu dolžine tabele
  3. Linearni seznam: uporabimo referenco na prvi in zadnji element
  4. Dvojno povezan seznam: vstavljanje in brisanje elementov je enostavnejše
Osebna orodja