3. sada domácich zadaní

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

Rastúca podpostupnosť (3 body)

Do triedy SpajanyZoznam pridajte metódu rastucaPodpostupnost(), ktorá v spájanom zozname ponechá prvú hodnotu (ak existuje) a pre každú inú ponechanú hodnotu platí, že: - je väčšia ako predošlá ponechaná hodnota - medzi ňou a predošlou ponechanou hodnotou nie je v pôvodnom zozname žiadna iná väčšia hodnota ako predošlá ponechaná hodnota.

Príklad:

  • zo zoznamu s hodnotami [5, 1, 2, 7, 1, 9, 3, 30, 6, 4] po volaní rastucaPodpostupnost() vznikne zoznam s hodnotami [5, 7, 9, 30],
  • zo zoznamu s hodnotami [1, 2, 3, 4] po volaní rastucaPodpostupnost() vznikne zoznam s hodnotami [1, 2, 3, 4],
  • zo zoznamu s hodnotami [10, 10, 10, 9, 11, -5, -2, 12, 7, 12] po volaní rastucaPodpostupnost() vznikne zoznam s hodnotami [10, 11, 12],
public void rastucaPodpostupnost()
[$[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
        }

        public void rastucaPodpostupnost() {
                // TODO        
        }

        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


                SpajanyZoznam 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();

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