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 kódu 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 – 23.10.2010 odevzdáno do 03/06.11.2010

Napište program, který bude realizovat obousměrně vázaný seznam. Program bude obsahovat dva moduly (tři soubory) – main a modul s kódem realizujícím vázaný seznam (implementaci seznamu). Dále bude v projektu hlavičkový soubor definic a prototypů funkcí doplňující soubor seznamu.
Navrhněte strukturu SElement vhodnou pro prvek seznamu. Struktura (prvek seznamu) obsahuje index, hodnotu, ukazatele 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ěňovat 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. Ukazatele budou ukazovat na následující a předchozí prvek.

Algoritmy funkcí by měly fungovat i pro prázdný seznam (ve funkcích testujte na začátku, zda mají smysl).
Napište funkci (Vloz), 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 (Zrus), 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 08.11.2010 odevzdáno do 17./20.11.2010

(Ú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 (ZjistiPocet), která zjistí počet prvků v seznamu a hodnotu maximálního indexu.
Napište funkci (VlozList) 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 (TiskList), 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 (SetridList), 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í (demonstrující různé varianty volání).

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

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

Vytvořte třídu CList, 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 implementováván pomocí struktury SElement, 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 int) vytvoří seznam s tímto počtem prvků (a vyplní proměnnou index hodnotami od jedné s inkrementací o jedna pro další prvky, a datový člen (ve struktuře ho zastupuje ukazatel na double) naplní tak, že jeho hodnoty budou nulované, nebude-li druhý parametr uveden. Bude-li uveden, naplní se předanou hodnotou),
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 [pocetdvojic, indexA, hodnotaA, indexC, hodnotaC, ... ]).
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 CList, jejichž součástí bude i struktura SElement, další soubor bude zdrojový soubor s funkcí main, která bude volat demonstrační funkci Test, ve které bude ukázána činnost třídy.
Odevzdávané soubory budou mít jména - dumainprj.cpp, duseznam.cpp, duseznam.h. Dodržujte uvedená jména funkcí a proměnných.
Zbývající soubory jsou soubory knihovny pro kontrolu správnosti alokací - check (viz literatura). Návod je přiložen a je též součástí souborů. Hlavičkový soubor je třeba načíst do každého zdrojového souboru projektu. Soubory knihovny nemusíte odevzdávat.

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

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. Splňte požadované názvy a počet souborů - jinak nedojde ke kontrole projektu a bude ohodnocen jako nepřeložitelný. V main ukázat volání všech metod, které byly vytvořeny, privátní metody volat v rámci jiných metod.

Napište do třídy metodu Pridej, 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 aktual).
Napište metody NaZacatek, NaKonec, 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 (CList), který bude mít prvky seřazené v opačném pořadí oproti prvkům původního seznamu. Původní seznam/prvek zůstane nezměněn.
Napište metodu Inv, která změní proměnnou tak, že přeskládá prvky seznamu v opačném pořadí (a vrátí tento nový seznam=přeskládaný starý).
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.2010, odevzdáno 3.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 - s parametrem int pro odstranění posledních prvků (počet dán intem). 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 2010-11-11