3. sada domácich zadaní

Najneskorší termín odovzdania: 12.3.2017 (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

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

Metódy pridajNaZaciatok a toString nemodifikujte, keďže sú využívané evaluátorom.

Vlož usporiadane (3 body)

Predpokladajme, že všetky hodnoty v spájanom zozname sú usporiadané od najmenšej po najväčšiu. Do triedy SpajanyZoznam pridajte metódu vlozUsporiadane, ktorá vloží do zoznamu parametrom zadanú hodnotu na takú pozíciu, že zoznam ostane po vložení tejto hodnoty naďalej usporiadaný.

public void vlozUsporiadane(double hodnota)
[$[Get Code]]

Príklad: Predpokladajme, že spájaný zoznam obsahuje hodnoty [3, 8, 10]. Volanie metódy:

  • vlozUsporiadane(9) spôsobí, že spájaný zoznam bude obsahovať hodnoty [3, 8, 9, 10],
  • vlozUsporiadane(2) spôsobí, že spájaný zoznam bude obsahovať hodnoty [2, 3, 8, 10],
  • vlozUsporiadane(8) spôsobí, že spájaný zoznam bude obsahovať hodnoty [3, 8, 8, 10],
  • vlozUsporiadane(12) spôsobí, že spájaný zoznam bude obsahovať hodnoty [3, 8, 10, 12],

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]
  • zo zoznamu s hodnotami [-3, -6, -9, -3] po volaní odstranZaporne() vznikne zoznam s hodnotami []
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 vlozUsporiadane(double hodnota) {
                // TODO implementovat
        }

        public void rastucaPodpostupnost() {
                // TODO implementovat
        }

        public static void vlozNahodneHodnoty(SpajanyZoznam zoznam, int pocet) {
                for (int i = 0; i < pocet; i++) {
                        zoznam.pridajNaZaciatok((int) (500 - Math.random() * 1000) / 10.0);
                }
        }

        public static void vlozNahodneUsporiadaneHodnoty(SpajanyZoznam zoznam, int pocet) {
                int hodnota = (int) (500 + Math.random() * 1000);
                for (int i = 0; i < pocet; i++) {
                        zoznam.pridajNaZaciatok(hodnota / 10.0);
                        hodnota -= (int) (Math.random() * 100);
                }
        }

        public static void main(String[] args) {
                // Demo
                zoznam = new SpajanyZoznam();
                vlozNahodneUsporiadaneHodnoty(zoznam, 20);
                System.out.println("Pred: " + zoznam);
                System.out.println("vlozUsporiadane(...)");
                zoznam.vlozUsporiadane(10);
                System.out.println("Po: " + zoznam);

                System.out.println();

                zoznam = new SpajanyZoznam();
                vlozNahodneHodnoty(zoznam, 20);        
                System.out.println("Pred: " + zoznam);
                System.out.println("rastucaPodpostupnost()");
                zoznam.rastucaPodpostupnost();
                System.out.println("Po: " + zoznam);
        }
}
[$[Get Code]]