3. sada domácich zadaní

Najneskorší termín odovzdania: 9.3.2014 (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 maximum (4 body)

Do triedy SpajanyZoznam pridajte metódu vlozPredMaximum(hodnota), ktorá do spájaného zoznamu pridá zadanú hodnotu pred posledný prvok s maximálnou hodnotou v zozname, resp. na začiatok zoznamu, ak je zoznam prázdny.

Príklady:

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

Intervalový filter (3 body)

Do triedy SpajanyZoznam pridajte metódu filtruj(double dh, double hh), ktorá zo spájaného zoznamu odstráni všetky uzly, ktorých hodnota neleží v intervale <dh, hh>. 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í filtruj(6, 20) vznikne zoznam s hodnotami [7, 9, 6],
public void filtruj(double dh, double hh)
[$[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 vlozPredMaximum(double hodnota) {

        }

        public void filtruj(double dh, double hh) {

        }

        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]]