Zadanie 3
Odovzdávaný súbor: SpajanyZoznam.java
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. Metódy by mali potrebovať iba jeden prechod spájaným zoznamom.
Metódy pridajNaZaciatok a toString nemodifikujte, keďže sú využívané evaluátorom.
Vlož usporiadane
Predpokladajme, že všetky hodnoty v spájanom zozname sú usporiadané od najmenšej po najväčšiu. Do triedy SpajanyZoznam pridajte metódu vlozUsporiadane, ktorá vloží do zoznamu parametrom zadanú hodnotu na takú pozíciu, že zoznam ostane po vložení tejto hodnoty naďalej usporiadaný.
Príklad: Predpokladajme, že spájaný zoznam obsahuje hodnoty [3, 8, 10].
Volanie metódy:
vlozUsporiadane(9)spôsobí, že spájaný zoznam bude obsahovať hodnoty[3, 8, 9, 10],vlozUsporiadane(2)spôsobí, že spájaný zoznam bude obsahovať hodnoty[2, 3, 8, 10],vlozUsporiadane(8)spôsobí, že spájaný zoznam bude obsahovať hodnoty[3, 8, 8, 10],vlozUsporiadane(12)spôsobí, že spájaný zoznam bude obsahovať hodnoty[3, 8, 10, 12],
Odstráň záporné
Do triedy SpajanyZoznam pridajte metódu odstranZaporne(), ktorá zo spájaného zoznamu odstráni všetky uzly so zápornou hodnotou. Vzájomné poradie ostatných uzlov (hodnôt) v zozname musí ostať zachované.
Príklady:
- zo zoznamu s hodnotami
[-4, -6, 5, -5, -6, 8, 5, -9, -8]po volaníodstranZaporne()vznikne zoznam s hodnotami[5, 8, 5], - zo zoznamu s hodnotami
[5, 6, 9, -3, -6, -9, -3, 9]po volaníodstranZaporne()vznikne zoznam s hodnotami[5, 6, 9, 9] - zo zoznamu s hodnotami
[-3, -6, -9, -3]po volaníodstranZaporne()vznikne zoznam s hodnotami[]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
* 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 vlozUsporiadane(double hodnota) {
// TODO implementovat
}
public void odstranZaporne() {
// TODO implementovat
}
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 vlozNahodneUsporiadaneHodnoty(SpajanyZoznam zoznam, int pocet) {
int hodnota = (int) (500 + Math.random() * 1000);
for (int i = 0; i < pocet; i++) {
zoznam.pridajNaZaciatok(hodnota / 10.0);
hodnota -= (int) (Math.random() * 100);
}
}
public static void main(String[] args) {
// Demo
SpajanyZoznam zoznam = new SpajanyZoznam();
vlozNahodneHodnoty(zoznam, 20);
System.out.println("Pred: " + zoznam);
System.out.println("odstranZaporne()");
zoznam.odstranZaporne();
System.out.println("Po: " + zoznam);
System.out.println();
zoznam = new SpajanyZoznam();
vlozNahodneUsporiadaneHodnoty(zoznam, 20);
System.out.println("Pred: " + zoznam);
System.out.println("vlozUsporiadane(...)");
zoznam.vlozUsporiadane(10);
System.out.println("Po: " + zoznam);
}
}