====== PRO1 - 5.3.2014 - Spojový seznam ======
===== Nastudujte si z prezentace v Olivě =====
Nastudujte si z prezentace v Olivě (PRO1 - Materiály předmětu - Spojový seznam) ukazující, jak funguje datová struktura „spojový seznam“.
===== Importujte si ukázkový projekt a prostudujte =====
Importujte si ukázkový projekt SpojovySeznam (ke stažení z Olivy v ZIPu) do Eclipse a prostudujte.
Klíčové poznatky (pokud Vám některé nejsou jasné, ptejte se ;-) ):
* Rozhraní Seznam určuje metody pro práci s libovolným seznamem.
* Třída Prvek funguje jako jakási „přepravka“ obsahující odkaz na objekt v seznamu a odkaz na další Prvek.
* Proměnná ''hodnota'' ve třídě ''Prvek'' je typu ''[[http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html|Object]]'' (prapředek všech tříd v Javě), lze tedy do ní díky typové kompatibilitě (potomek může zastoupit předka) uložit odkaz na instanci libovolné třídy (např. ''Kontakt'' v tomto ukázkovém projektu).
* Třída ''SpojovySeznam'' implementuje rozhraní ''Seznam'' tak, že interně používá spojový seznam tvořený instancemi třídy ''Prvek''.
* Třída ''PoleSeznam'' implementuje rozhraní ''Seznam'' tak, že interně používá pole (array) pevné délky, kde jeden prvek pole je typu ''Object'' (opět lze do něj tedy uložit odkaz na jakoukoliv instanci).
* Při vkládání prvků do ''Seznam''u pomocí metody ''pridej'' dojde k implicitnímu přetypování vkládaného objektu na typ ''Object'' (Seznam nezajímá, jakého typu je vkládaný prvek, používá tedy nejobecnější možný typ).
* Při získávání prvků ze ''Seznam''u pomocí metody ''get'' je musíme přetypovat zpět na původní typ (tedy například ''Kontakt''), pokud s nimi chceme plnohodnotně pracovat (volat jejich specifické metody atd.) , viz řádek z třídy ''SpojovySeznamApp'':
k = (Kontakt)s.get(i); //Prirazeni s pretypovanim
===== Vytvořte vlastní řešení =====
V našem projektu se zlomky si zkuste vytvořit vlastní řešení (rámcově odpovídající příkladu z Olivy).
Vytvořte rozhraní ''Seznam'' dle tohoto předpisu (zvolte vhodný balíček):
public interface Seznam {
/**
* Pridana noveho objektu do seznamu
* @param o
*/
public void pridej(Object o);
/**
* Vraci objekt na i-tou pozici v seznamu. Prvni prvek ma index 0.
* @param pozice
* @return objekt
*/
public Object ziskej(int pozice);
/**
* Vypusti prvek na i-te pozici
* @param i
*/
public void smaz(int pozice);
/**
* Vyprazdni cely seznam
*/
public void smazVse();
/**
* Vraci aktualni pocet prvku v seznamu
* @return
*/
public int getPocetPrvku();
}
Vytvořte třídu SpojovySeznam, která toto rozhraní implementuje. Nechte Eclipse, aby Vám vygeneroval kostry metod, které musí tato třída mít. Tip:
public class SpojovySeznam implements Seznam {
/* tady budou implementace metod... */
}
Jednotlivé metody správně implementujte.
Jako "přepravku" můžete použít buďto veřejnou třídu podobně jako v příkladu z Olivy nebo privátní třídu následujícím způsobem (k atributům privátní třídy ''Prvek'' máte ve třídě ''SpojovySeznam'' přímý přístup.
public class SpojovySeznam implements Seznam {
/* tady budou implementace metod... */
private class Prvek {
private Object hodnota;
private Prvek dalsi;
}
}
===== Otestujte Vaše řešení =====
Vytvořte nový JUnit Test (File - New - Other - JUnit Test Case), vložte do něj následující kód, který testuje jednotlivé metody:
public class SpojovySeznamTest {
Seznam seznam;
@Before
public void setUp() throws Exception {
seznam = new SpojovySeznam();
seznam.pridej(new Zlomek(1,2));
seznam.pridej(new Zlomek(2,3));
seznam.pridej(new Zlomek(3,4));
seznam.pridej(new Zlomek(4,5));
}
@Test
public void testPridat() {
Zlomek z = new Zlomek(10,3);
seznam.pridej(z);
assertEquals(z, seznam.ziskej(seznam.getPocetPrvku()-1));
}
@Test
public void testZiskej() {
Zlomek z = (Zlomek) seznam.ziskej(3);
assertNotNull(z);
assertEquals(5, z.getJmenovatel());
}
@Test
public void testSmazat() {
seznam.smaz(2);
Zlomek z = (Zlomek) seznam.ziskej(2);
assertNotNull(z);
assertEquals(5, z.getJmenovatel());
}
@Test
public void testVelikost() {
int pocet = seznam.getPocetPrvku();
seznam.pridej(new Zlomek(10,3));
assertEquals(pocet+1, seznam.getPocetPrvku());
}
}
A test spusťte. Pokud proběhne v pořádku, je Vaše řešení otestováno.
===== Použijte Vaše řešení =====
Zkuste si v ''main'' metodě spouštěcí třídy vytvořit instanci třídy ''SpojovySeznam'', vložit do seznamu několik Zlomků (podobně jako v metodě ''setUp'' testu) a následně je ve for-cyklu vypsat. Dále všechny zlomky v seznamu postupně sečtěte (naší metodou ''plus'', mezivýsledek vždy zkraťte metodou ''zkrat'') a výsledek vypište.
===== Poučte se z chyb jiných =====
Další (spíše špatný) příklad na adrese http://javaalgoritmy.wz.cz/spojsez.htm ukazuje variantu, kdy propojování objektů do seznamu umožňuje přímo daná třída – v tomto případě ''Zamestnanec'', neboť má v sobě odkaz na dalšího zaměstnance. Řešení nepoužívá žádnou „přepravku“ jako ukázkový projekt. Uvažujte, v čem je takové řešení špatné.
===== Autoři Javy poskytují hotová řešení =====
Na tomto příkladu jsme se naučili základní princip a využití datové struktury „spojového seznamu“, případně seznamu uloženého ve formě pole. Autoři Javy samozřejmě tyto struktury pro nás již implementovali a jsou dostupné ve třídách ''[[http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html|java.util.LinkedList]]'' a ''[[http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html|java.util.ArrayList]]'' (obě implementují rozhraní ''[[http://docs.oracle.com/javase/7/docs/api/java/util/List.html|java.util.List]]''). Obě implementace se liší například výkonností jednotlivých operací (např. pro ''ArrayList'' je náročné vkládat prvek někam „doprostřed“ seznamu – uvažujte proč).
===== Bonus pro pokročilejší programátory =====
Prostudujte si, co jsou to tzv. generika v Javě http://www.algoritmy.net/article/30003/Generika-iterator-17 a upravte si Seznam a SpojovySeznam, aby byly generické. (Proč je generická varianta lepší?)