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 – 24.10.2009 odevzdáno do 4/07.11.2009

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 ukazatel na 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 07.11.2009 odevzdáno do 18./21.11.2009

(Ú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.
Napište funkci (VlozSeznam) pro vkládání jednoho seznamu do druhého seznamu (tj. Předávaný prvek bude prvním prvkem vkládaného (=druhého) seznamu) a vloží se na danou pozici seznamu druhého. Navrhněte tak, aby se vložený seznam stal „majetkem“ prvního seznamu (tj. aby došlo pouze ke vložení, a ne k vytváření kopie druhého seznamu).
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). Seznam bude vytištěn tak, že prvním vytištěným prvkem bude poslední prvek seznamu.
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)). Řadit bude sestupně.

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 21.11.2009 odevzdáno do 2.12/5.12.2009

Na základě minulých dvou úkolů realizujte třídu, která bude obstarávat práci se seznamem.

Vytvořte třídu CSeznam, která bude obsahovat jednosměrně vázaný seznam a bude zprostředkovávat práci s ním. Tato třída bude obsahovat i případné další proměnné vhodné pro fungování třídy. Vlastní vázaný seznam bude implemtován pomocí struktury SPrvek, která bude obsahovat datové prvky („hodnoty“ daného uzlu a ukazatel na další prvek).
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 (unsigned long int) vytvoří seznam s tímto počtem prvků (a vyplní proměnnou index hodnotami od nuly s inkrementací o jedna pro další prvky, a datový člen (ve struktuře ho zastupuje ukazatel na double) naplní tak, že jeho hodnoty 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é pomocné funkce budou – vytvoření seznamu, možná tisk. Třída bude realizovat „manažera“ obsluhujícího vlastní seznam – druhá struktura pro vlastní seznam.

Výsledný projekt bude obsahovat pět souborů - hlavičkový a zdrojový soubor pro třídu CSeznam a (totéž) pro strukturu SPrvek, poslední soubor bude zdrojový soubor s funkcí main, která bude volat demonstrační funkci Test, ve které bude ukázána činnost třídy.

Úkol 4 – pokračování třída(zadáno na 6-tém tutoriálu – 5.12.2009 odevzdáno do 16.12./19.12.2009

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 PridejPrvek, která přidá prvek seznamu.
Napište metody OdeberPozice a OdeberHodnotu, 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 aktualni).
Napište metody NaPrvní, NaPoslední, NaDalší, NaPředchozí, které budou provádět operace s tímto aktuálním prvkem (příslušně ho přemístí, nastaví tak aby ukazoval na).
Napište funkci (ne metodu) Inv, která vrátí (nový) seznam, který bude mít prvky seřazené v opačném pořadí oproti prvkům původního seznamu. Původní prvek zůstane nezměněn.
Napište metodu Inv, která změní prvek tak, že přeskládá prvky seznamu v opačném pořadí (a vrátí tento nový prvek).
Napište operátor „!“, který vrátí true lze-li pracovat se seznamem tj. obsahuje alespoň jeden prvek (vracené true je vlastně negace false, které značí, že aktuální seznam 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(“seznam prázdný - nepracujem“); else printf(“aktuální seznam je použitelný“);

Úkol 5 – dokončení třída(zadáno na 7-mém tutoriálu – 19.12.2009, odevzdáno 4.1.2010

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 unární operátor + (který se chová k proměnným jako (tentýž) operátor u standardních typů)
Napište binární operátor + pro spojení dvou seznamů. Tento operátor by měl mít obdobné vlastnosti jako pro standardní typy (nemění ani jeden operand ...)
Napište metodu pro tisk prvků seznamu.

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

U metod (zvláště u operátorů +) preferujte předávání pomocí referencí (pokud je to možné).
Při trasování příkazu d = c = a + b ; si prověřte znalosti z volání metod, konstruktorů a destruktorů.

Poslední změna 2009-11-27