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

Jedná se o složitější projekt návrhu třídy, který je rozložen do pěti kroků. První dva kroky slouží k pochopení činnosti vázaného seznamu a k zápisu kodu základních funkcí a proto se realizuje v jazyce C. V dalších cvičeních se tyto základy využijí při postupném tvoření třídy.

Jednosměrně vázaným seznamem rozumíme množinu prvků (typu struktura), které kromě informací o hodnotách vážících se k jednotlivým strukturám, nesou i informaci o následujícím prvku – realizovanou ukazatelem na typ stejný jako je prvek (tedy na strukturu stejného typu). Poslední prvek seznamu je takový, který nemá následující prvek – jeho ukazatel na další prvek je „NULL“.

Úkol 1 – úvod (pro KPPC zadáno na 3-tím tutoriálu – 25.10.2008 odevzdáno do 6/8.11.2008)

Napište program, který bude realizovat jednosměrně vázaný seznam. Program bude obsahovat 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.
Navrhněte strukturu vhodnou pro prvek seznamu. Struktura (prvek seznamu) obsahuje index, hodnotu, ukazatel pro propojování seznamu. Prvek seznamu bude tedy obsahovat index, který značí pořadí vkládaného prvku od počátku běhu programu (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 v dané chvíli, nezávisle na tom zda byly již nějaké prvky odstraněny nebo přidány). Dále struktura obsahuje hodnotu, ve které jsou uložena „užitečná“ data, které budou realizovány náhodně naplněnou proměnnou typu double
.
Algoritmy funkcí by měly fungovat i pro prázdný seznam.
Napište funkci (VlozPrvek), 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 (ZrusSeznam), která zruší celý seznam. Ukažte volání na prázdný i naplněný seznam.
Napište funkci (OdeberPozice), která odebere prvek na dané pozici – existuje-li tato pozice.
Napište funkci (OdeberHodnotu), která odebere prvky s danou hodnotou, pokud takové existují.
Ukažte volání obou možností odebrání prvků a také volání pro neexistující prvek.

Úkol 2 – pokračování (pro KPPC zadáno na 4-tém tutoriálu 8.11.2008 odevzdáno do 19/22.11.2008)

(Úkol 2 je pokračováním/rozšířením úkolu 1 – předpokládá se tedy, že budou odstraněny nedostatky z minulé úlohy).
Napište funkci (Zjisti), která zjistí počet prvků v seznamu a hodnotu maximálního indexu.
Doplňte funkci (VlozPrvek->VlozPrvky) 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 (Tisk), která vytiskne seznam ve formátu index, hodnota, ukazatel na aktuální prvek, ukazatel na následující prvek (jeden prvek seznamu se tiskne na řádek).
Napište funkci (Setrid), 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í (NastavTrideni)).

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

Úkol 3 – základy třídy (pro KPPC zadáno na 5-tém tutoriálu 22.11.2008 odevzdáno do 3/6.12.2008)

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ří objekt s vlastními prvky shodnými se seznamem, který je předán jako parametr),
konstruktor, který na základě celočíselné hodnoty vytvoří seznam s tímto počtem prvků (a vyplní proměnnou index 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.
Funkce z minulých úkolů, které nejsou potřebné, se v tomto bodě ještě do třídy nezahrnují – nezařazujte je zatím do tohoto projektu. Potřebné funkce budou – vytvoření seznamu, možná tisk. Třída bude realizovat „manažera“ obsluhujícího vlastní seznam – druhá struktura pro vlastní seznam.

Úkol 4 – pokračování třída(zadáno na 6-tém tutoriálu – 6.12.2008 odevzdáno do 17/20.12.2008)

pokračujte rozšířením příkladu z minulého úkolu – opravte chyby. Nezapomínejte, že jedna třída („manažer“) řídí práci se seznamem, který je realizován pomocí druhé třídy/struktury.

Napište do třídy metodu, která přidá prvek seznamu.
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 provádět operace (příslušně ho přemístí, nastaví tak aby ukazoval na) s tímto aktuálním prvkem.
Napište funkci (ne metodu) Inv, která vrátí (nový) seznam, který bude mít prvky inverzní (záporné) 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 nelze-li pracovat se seznamem přes aktuální prvek (to je pokud jsme aktivním prvkem na posledním prvku seznamu). (vracené true je vlastně negace false, které značí, že aktuální prvek seznamu není použitelný)

Ukažte použití navržených metod. U dvojice Inv to bude např.
S1 = Inv(S2); S2 se nezmění
S3 = S2.Inv(); S2 se změní, S1, S2 i S3 budou tedy mít stejné hodnoty

operátor ! by měl patřit ke třídě a je bez parametrů (unární, má pouze implicitní parametr prvku, který ho vyvolal).
if (!Seznam) printf(“jsme na konci – nepracujem“); else printf(“aktuální prvek je použitelný“);

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

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 2008-03-12