3. sada domácich zadaní

Najneskorší termín odovzdania: 13.3.2022 (nedeľa) o 18: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.

Zduplikuj (3 body)

Do triedy SpajanyZoznam pridajte metódu zduplikuj(double dh, double hh), ktorá za každý výskyt čísla v intervale <dh, hh> hodnota vloží jeho duplikát. Vzájomné poradie ostatných uzlov (hodnôt) v zozname musí ostať zachované.

Príklad:

  • zo zoznamu s hodnotami [5, 7, 1, 9, 3, 30, 6, 4] po volaní zduplikuj(6, 20) vznikne zoznam s hodnotami [5, 7, 7, 1, 9, 9, 3, 30, 6, 6, 4].
public void zduplikuj(double dh, double hh)
[$[Get Code]]

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 zduplikuj(double dh, double hh) {
                // 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 main(String[] args) {
                // Demo


                SpajanyZoznam zoznam = new SpajanyZoznam();
                vlozNahodneHodnoty(zoznam, 20);
                System.out.println("Pred: " + zoznam);
                System.out.println("zduplikuj(...)");
                zoznam.zduplikuj(10, 20);
                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]]