6. Algoritmy a štruktúry údajov

• Porovnajte štruktúry údajov rad, zoznam a zásobník.

• Porovnajte rad a zásobník z pohľadu operácií. Na konkrétnom príklade vysvetlite operácie pridania a odstránenia prvku zo zásobníka.

• Uveďte príklady z reálneho života, v ktorých sa dané štruktúry vyskytujú.

Údajová štruktúra je charakterizovaná operáciami, ktoré sa pomocou nej dajú realizovať.

Štruktúra údajov zoznam je ľubovoľná postupnosť prvkov, pričom vieme pridávať a odoberať prvky za alebo pred určeným prvkom, vieme zistiť či je prvok v zozname a zistiť či je zoznam prázdny.

Zoznam sa v praxi vyskytuje napr.

  • CD-čka alebo DVD-čka na poličke tvoria zoznam. Keď chceme pridať nové, môžeme ho dať na začiatok, na koniec, alebo ho vsunúť medzi niektoré dve (za alebo pred niektoré).
  • Okná na ploche sú organizované ako zoznam. Keď na ploche už máme nejaké okná a vytvoríme nové okno, zvyčajne sa pridá pred posledné aktívne okno. Môžeme postupne prechádzať po jednotlivých oknách a vybrať, ktoré bude aktívne.
  • Súbory na disku sú uložené ako zoznamy. Súbory nie sú uložené v jednom súvislom úseku, ale zvyčajne vo viacerých menších úsekoch pevnej veľkosti. Je to vymyslené tak, že vieme, kde sa nachádza prvý úsek. Každý úsek vie, kde sa na disku nachádza ďalší úsek. Táto stratégia umožňuje rozumne využiť priestor na disku. Čítanie z disku je oproti čítaniu z pamäte asi 106 pomalšie, preto je výhodné čítať z disku väčšie úseky naraz. Keďže nevieme odhadnúť dopredu veľkosti súborov, je dobre ich rozdeliť na menšie úseky rovnakej veľkosti, ktoré sa čítajú celé naraz. Teda „defragmentácia disku“ vlastne prehadzuje úseky, v ktorom je súbor uložený tak, aby sa dal súbor rýchlo čítať.

Teda operácie v zozname:

  • pridanie/odobranie prvku na začiatok/koniec
  • pridanie/odobranie prvku pred/za daný prvok
  • zistenie či je prvok v zozname
  • zistenie či je zoznam prázdny

Pre porovnanie operácie v poli:

  • čítanie prvku na danej pozícii
  • zápis prvku na danú pozíciu

Štruktúra údajov zásobník je tiež ľubovoľná postupnosť prvkov pričom vieme pridávať prvok a odoberať posledný prvok, vieme zistiť či je zásobník prázdny a zistiť hodnotu na vrchu zásobníka.

Zásobník je v praxi trocha ukrytejší: niekedy spracovávame prichádzajúce požiadavky tak, že najskôr sa usilujeme vybaviť poslednú ktorá prišla. V digitálnom fotoaparáte si často môžete pozrieť poslednú vytvorenú fotografiu ako prvú, predposlednú ako druhú, atď. Vagóny na slepej koľaji tvoria zásobník: vagón ktorý prišiel na slepú koľaj ako posledný, odíde ako prvý a pod. Aj CD média sa predávajú v zásobníkovom balení, v ktorom sú CD bez obalov uložené na kolíku. Vybrať sa dá iba vrchne CD a pridať sa dá len na vrch.

Teda operácie v zásobníku:

  • pridanie prvku
  • odobranie naposledy pridaného prvku
  • zistenie, či je zásobník prázdny
  • zistenie hodnoty prvku na vrchu zásobníka

Poznámka: Zásobník je užitočný keby sme chceli napísať napríklad program kalkulačka a mnoho iných programov, používa sa napríklad vtedy keď v programe zavoláme nejakú funkciu alebo procedúru, bez toho, že by sme o tom vedeli.

Zásobník sa dá realizovať jednoduchým spôsobom v jednorozmernom poli.

const

//budeme predpokladať, že zásobník bude mať najviac 100 prvkov

MaxVelkostZasobnika = 100;

type

TVelkostZasobnika = 1..MaxVelkostZasobnika;

THodnota = Integer;

var

Vrch: Integer;

Zasobnik : array[TVelkostZasobnika] of THodnota;

Premenná Vrch bude určovať pozíciu naposledy pridaného prvku do zásobníka. Prvky zásobníka sa budú ukladať v poli Zásobník od nižších pozícií smerom k vyšším. Keď bude zásobník prázdny, bude mať Vrch hodnotu 0. Takže operáciu, či je zásobník prázdny realizujeme jednoduchým testom:

function JePrazdnyZasobnik : Boolean;

begin

Result := Vrch = 0;

end;

Podobne jednoduchým testom zrealizujeme operáciu či je zásobník plný:

function JePlnyZasobnik : Boolean;

begin

Result := Vrch = MaxVelkostZasobnika;

end;

Operáciu pridania do zásobníka môžeme realizovať ako funkciu, ktorá vráti True, keď sa operácia pridania podarí. Môže sa aj nepodariť? Nepodarí sa napríklad vtedy, keď je už zásobník plný. Preto pred volaním PridajDoZasobnika funkciou JePlnyZasobnik zistíme, či nie je plný.

function PridajDoZasobnika(Prvok : THodnota) : Boolean;

begin

Result := Vrch < MaxVelkostZasobnika;

if Result then begin

Inc(Vrch);

Zasobnik[Vrch] := Prvok

end;

end;

Odobratie prvku zo zásobníka je rovnako jednoduché. Budeme predpokladať, že z prázdneho zásobníka sa nebudeme nikdy snažiť vyberať prvok. Pred volaním VyberZoZasobnika vždy zistíme funkciou JePrazdnyZasobnik, či nie je prázdny.

function VyberZoZasobnika : THodnota;

begin

Result := Zasobnik[Vrch];

Dec(Vrch);

end;

Štruktúra údajov rad je postupnosť prvkov, pričom prvky môžeme pridávať a odoberať, na rozdiel od zásobníka, z oboch jeho koncov (začiatku aj konca). Samozrejme vieme zistiť, či je rad prázdny a hodnoty prvkov na oboch jeho koncoch.

Rad je štruktúra údajov, s ktorou sa často stretávame v praxi. Rad poznáme napríklad z ambulancie lekára: posledný kto príde sa zaradí na koniec radu čakajúcich pacientov a k lekárovi ide ten, kto prišiel najskôr.

Teda operácie v rade:

  • pridanie prvku na začiatok
  • pridanie prvku na koniec
  • odobranie prvku zo začiatku
  • odobranie prvku z konca
  • zistenie, či je rad prázdny
  • zistenie hodnoty prvku na začiatku
  • zistenie hodnoty prvku na konci

Rad umožňuje napríklad ľahko vyriešiť úlohu ako nájsť cestu z bludiska.

Reklamy

Pridaj komentár

Zadajte svoje údaje, alebo kliknite na ikonu pre prihlásenie:

WordPress.com Logo

Na komentovanie používate váš WordPress.com účet. Odhlásiť sa / Zmeniť )

Twitter picture

Na komentovanie používate váš Twitter účet. Odhlásiť sa / Zmeniť )

Facebook photo

Na komentovanie používate váš Facebook účet. Odhlásiť sa / Zmeniť )

Google+ photo

Na komentovanie používate váš Google+ účet. Odhlásiť sa / Zmeniť )

Connecting to %s