Vázané seznamy

Jednosměrně vázaný seznam

Vytvořte knihovnu pro práci s jesnosměrně vázaným seznamem.
Knihovna bude obsahovat:
- funkci Push pro vložení prvku na první pozici seznamu
- funkci Pop pro odebrání prvku, který je na první pozici seznamu
- funci Print pro vytištění hodnot prvků v seznamu
- funkci Destroy pro zrušení seznamu.

Pro uzel vázaného seznamu nadefinujte strukturu
struct TNode {
TYP iValue; // hodnota pro kterou je lineární seznam vytvořen
TNode* iNext; }; // ukazatel na následující uzel seznamu

Pro práci se seznamem vytvořte strukturu
struct TLinSeznam
{
TNode *iHead; // ukazatel na první prvek seznamu
size_t iCount; // počet prvků v seznamu
TNode *iTail; // ukazatel na poslední prvek seznamu
};

Krok 0: založte si nový projekt – zdrojový soubor projektu mainseznam.c, zdrojový a hlavičkový soubor seznamu seznam.h a seznam.c. Do projektu přidejte check.c a check.h.
TYP definujte pomocí #define na typ double.
Při psaní funkcí se soustřeďte na funkčnost. Testy vstupních parametrů doplňte až v závěru práce (z programátorského hlediska není dobře, ale funkčnost je nyní důležitější).
Krok 1: Definujte strukturu uzlu seznamu TNode. Dále definujte strukturu seznamu TLinSeznam a vytvořte její proměnnou ve funkci main a inicializujte ji. Definice struktur budou v *.h souboru.
Krok 2: Napište funkci Push, která vloží prvek na začátek seznamu.
void Push(TLinSeznam *Seznam, TNode *aVal);
Ve funkci main vytvořte postupně dvě dynamické proměnné typu TNode. Jejich hodnoty iValue nastavte na 1 a 2. Proměnné vložte pomocí funkce Push do seznamu. Prvky se stávají součástí seznamu, který provede jejich odalokaci.

Krok 3: Napište funkci Pop, která odebere prvek ze začátku seznamu. Prvek odalokuje a příslušně upraví seznam.
void Pop(TLinSeznam *Seznam);
Ve funkci main vytvořte postupně dvě dynamické proměnné typu TNode. Jejich hodnoty iValue nastavte na 3 a 4. Proměnné vložte pomocí funkce Push do seznamu. Proveďte jednu operaci Pop.

Krok 4: napište funkci Print pro tisk seznamu na konzolu (vytiskněte seznam).
void Print(TLinSeznam *aSeznam)
Ve funkci main vytiskněte seznam vytvořený v předchozích bodech.

Krok 5: Napište funkci Destroy pro zrušení seznamu. Proveďte odalokování všech prvků seznamu a vynulování všech proměnných struktury TLinSeznam.
void Destroy(TLinSeznam *aSeznam)
Ve funkci main zavolejte funkci Destroy dvakrát po sobě, poté opět proveďte přidání prvků jako v kroku 2. (Tím se zjistí, zda je ošetřeno vícenásobné odalokování, a zda po odalokování je možné seznam znovu použít)

Lineární seznam - pokračování

Krok 6: Napište funkci Top, která vrátí ukazatel na prvek TNode seznamu na první pozici. Bude-li seznam prázdný, vrátí NULL. Při úspěchu funkce vrátí ukazatel na prvek na udané pozici. Prvek ponechá v seznamu.
TNode* Top(TLinSeznam *aSeznam);
Ve funkci main s využitím funkce Top nastavte hodnotu v prvním prvku seznamu na hodnotu 100. Seznam vytiskněte.

Krok 7: Napište funkci Remove pro odebrání prvku z dané pozice seznamu TLinSeznam (odeberte prvek na dané pozici počítáno od počátku seznamu) – prvek je odebrán ze seznamu a vrácen volající funkci. Ta ho musí odalokovat.
Funkce prvek vyjme z dané pozice s upravením návazností. Dále provede příslušné změny v TLinSeznam. Pokud bude seznam kratší než udává index, vrátí NULL. Při úspěchu funkce vrátí prvek na udané pozici.
TNode* Remove(TLinSeznam *aSeznam, size_t aIndex);
Ve funkci main postupně vložte do seznamu deset prvkůl TNode s hodnotami iValue 10 až 19. Následně pomocí funkce Remove vyberte prvky od pozice 10 až 5 a ihned je uložte na počtáek seznamu funkcí Push. Seznam vytiskněte.
Krok 8: napište funkci Sort pro seřazení prvků seznamu od nejmenšího po největší. Řazení provádějte výměnou celých TNode.
void Sort(TLinSeznam *aSeznami);
Krok 9: Doplňte program tak aby pracoval korektně při volání s nevhodnými parametry.

Lineární seznam – pokračovávní:
Krok 7: Napište funkci Insert pro přidání prvku na danou pozici seznamu TLinSeznam (vložte prvek na dané pozici počítáno od počátku seznamu).
Pokud bude seznam kratší než udává index, vrátí hodnotu 1 a prvek nezařadí. Při úspěchu funkce vrátí hodnotu nula.
int Insert(TLinSeznam *aSeznam, TNode* aVal, size_t aIndex);
Ve funkci main postupně vložte do seznamu deset prvků TNode s hodnotami iValue 100 s krokem 10 na sudé pozice počínaje pozicí 4. Seznam vytiskněte.

Krok 9: Vytvořte nový projekt. Zkopírujte do něj soubory vytvořené v předchozích bodech projektu.
Upravte struktury a funkce pro práci s obousměrně vázaným seznamem.
Do struktury TNode přidejte ukazatel na předchozí prvek
TNode* iPred; // ukazatel na předchozí uzel seznamu

poslední úpravy 2019-02-12