3. sada domácich zadaní

Najneskorší termín odovzdania: 13.3.2016 (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 zoznam, bodový zisk bude znížený o 30%.

Pripočítaj vektor (3 body)

Do triedy SpajanyZoznam pridajte metódu pripocitajVektor, ktorá ako parameter dostane referenciu na pole čísel. Označme dĺžku tohto poľa d a počet prvkov zoznamu n. Výsledkom metódy pripocitajVektor je:

  • Ak d≤n, tak ku prvým d prvkom spájaného zoznamu prirátame prislúchajúcu hodnotu z poľa. Konkrétne k i-temu prvku spájaného zoznamu pripočítame i-ty prvok poľa.
  • Ak d>n, tak ku každému prvku spájaného zoznamu pripočítame prislúchajúcu hodnotu z poľa (k i-temu prvku zoznamu pripočítame i-ty prvok poľa) a na koniec zoznamu pridáme zostávajúce (nepripočítane) prvky poľa (celkovo d-n prvkov).
public void pripocitajVektor(double[] vektor)
[$[Get Code]]

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

  • pripocitajVektor([2, 8]) spôsobí, že spájaný zoznam bude obsahovať hodnoty [10, 13, 2] (pretože [10=8+2, 13=5+8, 2]).
  • pripocitajVektor([2, 8, 10, 15, 20]) spôsobí, že spájaný zoznam bude obsahovať hodnoty [10, 13, 12, 15, 20] (=[8+2, 5+8, 2+10, 15, 20]).

Metóda nech pracuje v lineárnom čase vzhľadom k dĺžke zoznamu a vektora, t.j. O(n+k).

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 pripocitajVektor(double[] vektor) {

        }

        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((Math.random() * 1000) / 10);
                System.out.println(zoznam);
        }
}
[$[Get Code]]