Pavel Kříž - UHK FIM

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== 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'':

<code java>
k = (Kontakt)s.get(i);	//Prirazeni s pretypovanim
</code>






===== 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):

<code java>
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();
}
</code>

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:

<code java>
public class SpojovySeznam implements Seznam {

        /* tady budou implementace metod... */

}
</code>

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.

<code java>
public class SpojovySeznam implements Seznam {

        /* tady budou implementace metod... */

        private class Prvek {
		private Object hodnota;
		private Prvek dalsi;
	}

}
</code>


===== 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:

<code java>
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()); 
	}
}

</code>

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ší?)
Pavel Kříž - UHK FIM

Uživatelské nástroje

Nástroje pro tento web

Nástroje pro stránku
