Projekt třídy jednosměrně vázaný seznam

Jednosměrně vázaný seznam – množina prvků (typu struktura) které kromě informací o hodnotách nesou i znalost o následujícím prvku – realizovanou ukazatelem na typ stejny jako je prvek. Poslední prvek je takový, která nemá následující prvek – jeho ukazatel na další prvek je „NULL“.

Projekt budeme realizovat jako pět postupných úkolů.

Úkol 1 – úvod (zadáno na 3-tím tutoriálu – 26.10. odevzdáno do 10.11.)

Napište program, který bude realizovat jednosměrně vázaný seznam. Navrhněte strukturu vhodnou pro prvek seznamu. Prvek seznamu bude kromě jiného obsahovat index (pořadí vkládaného prvku od počátku běhu seznamu (první vkládaný bude mít index jedna, každý další vkládaný prvek index o jedno větší než minulý vkládaný, nezávisle na tom, zda-li byl některý prvek smazán), nezaměnovat s indexem, který je parametrem funkcí a který značí prostou pozici v seznamu (udávající, na kolikáté pozici je prvek od počátku seznamu, nezávisle na tom zda byly již nějaké prvky odstraněny nebo přidány)), a hodnotu (náhodnou typu float). Napište funkci, která vloží nový prvek do seznamu na danou pozici – není-li možné vložit na tuto pozici (pozice mimo rozsah) vložte prvek na konec seznamu – ukažte několik volání pro obě možnosti. Napište funkci, která zruší celý seznam. Ukažte volání na prázdný i naplněný seznam. Napište funkci, která odebere prvek na dané pozici. Napište funkci, která odebere prvek s daným indexem. Ukažte volání obou možností odebrání prvků a také volání pro neexistující prvek.

Dva moduly (tři soubory) – main a modul s kódem realizující vázaný seznam (implementace seznamu). Hlavičkový soubor definic a prototypů funkcí doplňující soubor seznamu.

Úkol 2 – pokračování(zadáno na 4-tém tutoriálu 10.11. odevzdáno do 24.11)

(Úkol 2 je pokračováním/rozšířením úkolu 1). Napište funkci, která zjistí počet prvků v seznamu a hodnotu maximálního indexu. Doplňte funkci vkládání prvku do seznamu (z minulého úkolu), tak aby umožnila i vložení seznamu (tj. Předávaný prvek nebude jediným prvkem ale prvním prvkem vkládaného (=druhého) seznamu) na danou pozici. Napište funkci, která vytiskne seznam ve formátu index, hodnota (jedna hodnota položka seznamu na řádek). Napište funkci, která seřadí prvky podle indexu nebo hodnoty (řazení provede na základě nastavení globální proměnné, která se bude měnit příslušnou funkcí).

Ukažte volání všech navržených funkcí (demonstující různé varianty volání).

Úkol 3 – základy třída(zadáno na 5-tém tutoriálu 24.11. odevzdáno do 8.12.)

Na základě minulých dvou úkolů realizujte třídu, která bude obstarávat práci se seznamem. Třídu rozdělte na hlavičkový a zdrojový soubor.

Vytvořte třídu, která bude obsahovat jednosměrně vázaný seznam (a případné další proměnné vhodné pro fungování třídy). Napište konstruktor implicitní (vytvoří prázdný seznam), kopykonstruktor (vytvoří prvek se shodným seznamem s vlastními prvky), konstruktor, který na základě celočíselné hodnoty vytvoří seznam s tímto počtem prvků (a vyplní proměnné indexy s hodnotami od nuly s inkrementací o jedna pro další prvky, hodnoty prvků budou náhodné), konstruktor, který vytvoří seznam na základě pole intů (první hodnota značí počet dvojic, další hodnoty jsou index a hodnota prvku s tímto indexem). Napište destruktor, který zruší daný seznam.

Ukažte použití navržených metod.

Úkol 4 – pokračování třída(zadáno na 6-tém tutoriálu – 8.12. odevzdáno do 22.12)

Napište metodu, která přidá prvek. Napište metody, které odeberou prvky (jako v úkolu 1). Přidejte do třídy proměnnou, která bude držet informaci o aktuálním prvku seznamu, se kterým se pracuje (např. ukazatel). Napište metody První, Poslední, Další, Předchozí, které budou pracovat (příslušně ho přemístí) s tímto aktuálním prvkem. Napište funkci (ne metodu) Inv, která vrátí (nový) seznam, který bude mít prvky inverzní k prvkům původního seznamu. Napište metodu Inv, která provede inverzi všech prvků seznamu (a tento bude návratovou hodnotou). Napište operátor „!“, který vrátí true, pokud jsme aktivním prvkem na posledním prvku seznamu.

Ukažte použití navržených metod. U dvojice Inv to bude např. S1 = Inv(S2); S3 = S2.Inv();

operátor ! by měl patřit ke třídě a je bez parametrů (unární).

Úkol 5 – dokončení třída(zadáno na 7-mém tutoriálu - 22.12.)

Napište pro strukturu prvku seznamu operátor „<“, který porovná prvky podle hodnoty nebo indexu, na základě statické proměnné této strukury. Napište metody (ve třídě i struktuře), které příslušně nastaví tuto statickou proměnnou pro porovnávání. Ve třídě napište metodu pro seřazení prvků.

Napište operátor = pro přiřazení seznamů. Napište operátor + pro spojení dvou seznamů. Napište metodu pro tisk prvků seznamu.

Ukažte použití navržených metod.

Poslední změna 2007-11-27