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 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 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 Seznamu 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 Seznamu 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

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;
	}
 
}

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.

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.

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é.

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 java.util.LinkedList a java.util.ArrayList (obě implementují rozhraní 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č).

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ší?)