3. sada domácich zadaní

Najneskorší termín odovzdania: 15.3.2015 (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 celých čí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(int[] 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).

Deliteľnosť (3 body)

Do triedy SpajanyZoznam pridajte metódu ibaDelitelne(int delitel), ktorá zo spájaného zoznamu odstráni všetky uzly, ktorých hodnoty nie sú deliteľné zadaným číslom delitel (delitel > 0). Odstráni znamená, že nie je dovolené kopírovať hodnoty medzi uzlami (uzol v reálnej aplikácii môže eventuálne obsahovať aj ďalšie údaje vo svojich inštančných premenných - atribútoch). Vzájomné poradie ostatných uzlov (hodnôt) v zozname musí ostať zachované.

Príklad:

  • zo zoznamu s hodnotami [2, 6, 0, 12, 10, 1, 15] po volaní ibaDelitelne(3) vznikne zoznam s hodnotami [6, 0, 12, 15],
public void ibaDelitelne(int delitel)
[$[Get Code]]
/**
 * Trieda zapuzdrujuca spajany zoznam a manipulaciu s nim
 */
public class SpajanyZoznam {

        /**
         * Sukromna trieda reprezentujuca jeden uzol spajaneho zoznamu
         */
        private static class Uzol {
                int 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(int 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(int[] vektor) {

        }

        public void ibaDelitelne(int delitel) {

        }

        public static void main(String[] args) {
                // Demo
                SpajanyZoznam zoznam = new SpajanyZoznam();
                for (int i = 0; i < 20; i++)
                        zoznam.pridajNaZaciatok((int)(Math.random() * 1000));
                System.out.println(zoznam);
        }
}
[$[Get Code]]