3. sada domácich zadaní
Najneskorší termín odovzdania: 11.3.2012 (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ý
Periodické add (3 body)
Do triedy SpajanyZoznam pridajte metódu vlozOpakovane(perioda, hodnota), ktorá do spájaného zoznamu po každých perioda prvkoch pridá jeden prvok (uzol) s hodnotou hodnota. Metóda musí pracovať v čase O(n), kde n je počet hodnôt (uzlov) v spájanom zozname.
Príklady:
- zo zoznamu s hodnotami
[3, 2, 4, 1, 8, 3, 2]po volanívlozOpakovane(2, 9)vznikne zoznam s hodnotami[3, 2, 9, 4, 1, 9, 8, 3, 9, 2] - zo zoznamu s hodnotami
[3, 1]po volanívlozOpakovane(1, 9)vznikne zoznam s hodnotami[3, 9, 1, 9] - zo zoznamu s hodnotami
[3, 1]po volanívlozOpakovane(2, 9)vznikne zoznam s hodnotami[3, 1, 9] - zo zoznamu s hodnotami
[3, 1]po volanívlozOpakovane(3, 9)sa zoznam nezmení (iba po každých 3 prvkoch vkládame hodnotu 9)
public void vlozOpakovane(int perioda, double hodnota)
Filter pre malé hodnoty (4 body)
Do triedy SpajanyZoznam pridajte metódu odstranVsetkyMensie(hranica) , ktorá zo spájaného zoznamu odstráni všetky uzly s hodnotou menšou (<) ako hranica. Vzájomné poradie ostatných uzlov (hodnôt) v zozname musí ostať zachované. Metóda musí pracovať v čase O(n), kde n je počet hodnôt (uzlov) v spájanom zozname.
Príklady:
- zo zoznamu s hodnotami
[3, 2, 4, 1, 8, 3, 2]po volaníodstranVsetkyMensie(3)vznikne zoznam s hodnotami[3, 4, 8, 3] - zo zoznamu s hodnotami
[3, 2, 4, 1, 8, 3, 2]po volaníodstranVsetkyMensie(4)vznikne zoznam s hodnotami[4, 8]
public void odstranVsetkyMensie(double hranica)
/**
* 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 vlozOpakovane(int perioda, double hodnota) {
}
public void odstranVsetkyMensie(double hranica) {
}
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);
}
}
* 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 vlozOpakovane(int perioda, double hodnota) {
}
public void odstranVsetkyMensie(double hranica) {
}
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);
}
}