3. sada domácich zadaní

Najneskorší termín odovzdania: 10.3.2013 (nedeľa) o 21:00
Odovzdávaný súbor: SpajanyZoznam.java

Doplňujúce požiadavky:

  • riešenia, ktoré nebude možné skompilovať (t.j. riešenia so syntaktickými chybami) nebudú hodnotené,
  • zdrojový kód správne naformátujte (CTRL+SHIFT+F),
  • komentovaný zdrojový kód je vítaný

Obe metódy musia pracovať v čase O(n), kde n je počet hodnôt (uzlov) v spájanom zozname. Ak metódy budú potrebovať viac ako jeden prechod spájaným zoznam, bodový zisk bude znížený o 30%.

Vlož pred "chvost" (4 body)

Chvostom spájaného zoznamu nazveme takú najdlhšiu možnú sufixovú podpostupnosť (=súvislá podpostupnosť prvkov v zozname končiaca v poslednom prvku zoznamu), ktorá je tvorená len rovnakými hodnotami. Príklady:

  • v zozname [3, 2, 3, 1, 1, 1, 1] sú chvostom posledné 4 prvky s hodnotou 1,
  • v zozname [8, 8, 4, 1, 3, 3] sú chvostom posledné 2 prvky s hodnotou 3,
  • v zozname [5, 5, 5] sú chvostom všetky prvky zoznamu (tie majú hodnotou 5),
  • v zozname [4, 2, 5] má chvost dĺžku 1 a je tvorený len posledným prvkom s hodnotou 5.

Do triedy SpajanyZoznam pridajte metódu vlozPredChvost(hodnota), ktorá do spájaného zoznamu pridá zadanú hodnotu pred prvý prvok chvostu, resp. na začiatok zoznamu, ak je zoznam prázdny.

Príklady:

  • zo zoznamu s hodnotami [3, 2, 3, 1, 1, 1, 1] po volaní vlozPredChvost(9) vznikne zoznam s hodnotami [3, 2, 3, 9, 1, 1, 1, 1],
  • zo zoznamu s hodnotami [] po volaní vlozPredChvost(9) vznikne zoznam s hodnotami [9],
  • zo zoznamu s hodnotami [3, 1] po volaní vlozPredChvost(9) vznikne zoznam s hodnotami [3, 9, 1].
public void vlozPredChvost(double hodnota)
[$[Get Code]]

Odstráň záporné (3 body)

Do triedy SpajanyZoznam pridajte metódu odstranZaporne(), ktorá zo spájaného zoznamu odstráni všetky uzly so zápornou hodnotou. Vzájomné poradie ostatných uzlov (hodnôt) v zozname musí ostať zachované.

Príklady:

  • zo zoznamu s hodnotami [-4, -6, 5, -5, -6, 8, 5, -9, -8] po volaní odstranZaporne() vznikne zoznam s hodnotami [5, 8, 5],
  • zo zoznamu s hodnotami [5, 6, 9, -3, -6, -9, -3, 9] po volaní odstranZaporne() vznikne zoznam s hodnotami [5, 6, 9, 9]
public void odstranZaporne()
[$[Get Code]]
/**
 * Trieda zapuzdrujuca spajany zoznam a manipulaciu s nim
 */
public class SpajanyZoznam {

        /**
         * Sukromna trieda reprezentujuca jeden uzol spajaneho zoznamu
         */
        private static class Uzol {
                double hodnota;
                Uzol dalsi;
        }

        /**
         * Referencia na prvy uzol spajaneho zoznamu
         */
        private Uzol prvy = null;

        /**
         * Prida novu hodnotu na zaciatok spajaneho zoznamu
         *
         * @param hodnota
         *            pridavana hodnota
         */
        public void pridajNaZaciatok(double hodnota) {
                Uzol pridavany = new Uzol();
                pridavany.hodnota = hodnota;
                pridavany.dalsi = prvy;
                prvy = pridavany;
        }

        @Override
        public String toString() {
                String vysledok = "[";
                Uzol aktualny = prvy;
                while (aktualny != null) {
                        if (aktualny != prvy)
                                vysledok += ", ";

                        vysledok += aktualny.hodnota;
                        aktualny = aktualny.dalsi;
                }

                return vysledok + "]";
        }

        public void vlozPredChvost(double hodnota) {

        }

        public void odstranZaporne() {

        }

        public static void main(String[] args) {
                // Demo
                SpajanyZoznam zoznam = new SpajanyZoznam();
                for (int i = 0; i < 20; i++)
                        zoznam.pridajNaZaciatok((int)(Math.random() * 1000) / 10.0);
                System.out.println(zoznam);
        }
}
[$[Get Code]]