Cvičenie 3 – Údajové štruktúry

Ciele cvičení:

  • zoznámiť sa s údajovými štruktúrami spájaný zoznam, rad a zásobník
  • rozumieť a vedieť implementovať algoritmy, ktoré využívajú spomenuté údajové štruktúry

Spájané zoznamy

  • Navrhnite a implementujte do triedy SpajanyZoznam z 3. prednášky tieto metódy:


1
2
3
4
5
6
7
private Uzol vratITy(int index);



public int get(int index);

public void set(int index, int value);

public void add(int value);

public void add(int index, int value);

public void remove(int index);
  • Privátna metóda vratITy nech vráti poradím zadaný uzol v spájanom zozname, resp. null ak neexistuje.
  • Metódy get, add, set a remove implementujte s využitím metódy vratITy podľa toho, ako to predpisuje rozhranie List.
  • Upravte implementáciu triedy SpajanyZoznam tak, aby ste si v privátnych inštančných premenných ukladali aktuálny počet prvkov v zozname a referenciu na posledný uzol zoznamu.

Zásobníky

Správne ozátvorkovaný výraz

  • Odsimulujte algoritmus z prednášky na rozpoznávanie správne ozátvorkovaného výrazu na niekoľkých korektných aj nekorektných vstupoch.
  • Diskutujte a pokúste sa zdôvodniť prečo tento algoritmus funguje.
  • Navrhnite algoritmus na rozpoznanie správne ozátvorkovaného výrazu s jednou sadou zátvoriek bez použitia zásobníka. Porozmýšľajte, či je možné tento prístup zovšeobecniť aj na viac sád zátvoriek.

Ako implementovať zásobník?

  • Navrhnite a rozdiskutujte možnosti, ako je možné interne implementovať triedu, ktorá by realizovala údajovú štruktúru zásobník (pole, pole s kapacitou, spájaný zoznam, …). Porovnajte výhody a nevýhody jednotlivých prístupov s ohľadom na časovú zložitosť jednotlivých operácií.
  • Riešenie vám dá odpoveď na malú časť štátnicovej otázky „Ako by ste zásobník implementovali vo vhodnom programovacom jazyku?“

Zásobníky a matematika

Rady

Ako implementovať rad?

  • Navrhnite a rozdiskutujte možnosti, ako je možné interne implementovať triedu, ktorá by realizovala údajovú štruktúru rad (pole, pole s kapacitou, spájaný zoznam, …). Porovnajte výhody a nevýhody jednotlivých prístupov s ohľadom na časovú zložitosť jednotlivých operácií.
  • Navrhnite ako by ste vedeli pomocou poľa efektívne implementovať (všetky operácie v čase O(1)) rad v prípade, že viete, že v rade nikdy nebude čakať viac ako zadaný fixný počet hodnôt (pomôcka: spomeňte si moderné poradovníky v klientských centrách).

Prehľadávanie do šírky

  • Rozdiskutujte algoritmus na prehľadávanie do šírky v 2D poli. Vyskúšajte si ho odsimulovať na nejakom vstupe (všímajte si, v akom poradí sa pridávajú políčka do radu). Analyzujte časovú zložitosť tohto algoritmu.
  • Pri prehľadávaní do šírky si potrebujeme v rade uchovávať súradnice políčka, ktoré má byť spracované (majú sa „pozrieť“ jeho susedia). V zdrojovom kóde z prednášky sme tieto súradnice uchovávali v objektoch triedy Policko, t.j. použili sme rad Queue. Navrhnite, ako by išlo túto úlohu riešiť bez použitia pomocnej triedy Policko len s dvoma radmi typu Queue. Ako by sme riešili situáciu, ak by sme chceli použiť len jeden Queue?

Pre fajnšmekrov

  • Do triedy SpajanyZoznam pridajte metódu vycitanka:


1
public void vycitanka(int vypadava, int pocetZostavajucich);

Predpokladajte, že uzly v zozname sú usporiadané do kruhu (nasledovníkom posledného uzla je prvý uzol v zozname) – pozor, neznamená to, že máte implementovať cyklický spájaný zoznam. Metóda vycitanka implementuje jednoduchú vyčítanku, kedy každú k-tu osobu (parameter vypadava) vyhodíme z kruhu. Toto „vyhadzovanie“ uzlov nech sa opakuje dovtedy, kým v zozname neostane práve pocetZostavajucich uzlov (ak je pocetZostavajucich väčší ako počet uzlov v zozname, metóda nerobí nič).

  • Predstavte si situáciu, že v dôsledku chyby v programe sa stala taká vec, že pôvodne posledný uzol v zozname začal ako svojho nasledovníka referencovať nie null ale niektorý z predchádzajúcich uzlov zoznamu. V dôsledku tejto chyby vznikol v spájanom zozname cyklus. Ak by sme v takom zacyklenom zozname chceli zrealizovať iteráciu prvkami zoznamu, výsledkom bude nekonečný cyklus. Navrhnite metódu, ktorá pre zadaný spájaný zoznam overí, či je alebo nie je zacyklený. Hodnoty uzlov nesmiete nijako modifikovať. Keďže spájaný zoznam môže byť veľmi veľmi dlhý, nie je dovolené použiť väčšiu pomocnú pamäť ako O(1) – t.j. konštantne veľa pamäte.
    • Vedeli by ste naprogramovať metódu, ktorá „zacyklený“ spájaný zoznam opraví?