Zoznamy alebo "Ide vláčik ši, ši, ši."

Táto lekcia bude istým spôsobom výnimočná. Napriek tomu, že sa nachádza v cykle o knižnici Allegro, nebudeme túto knižnicu tentokrát používať. Vystačíme si s obyčajným C-čkom. Totiž -- v mnohých programoch je potrebné ukladať si informácie o rôznych objektoch do pamäte. Ak je počet objektov stále rovnaký, je možné vytvoriť si pole a do neho informácie ukladať. Ale je veľmi pravdepodobné, že počet ufónov, ktorí budú útočiť na vašu základňu sa bude meniť. A tu nastupujú dátové štruktúry ako napríklad zoznamy.

Predstavte si, že si potrebujete uložiť údaje o viacerých potvorách, ktoré vo vašej hre budú útočiť na chudáka hráča. Pre jednoduchosť si budeme pamätať iba ich súradnice (v reálnej hre môže byť tých údajov oveľa viac). Najprv si vyrobíme novú štruktúru určenú pre jednu potvoru. Môže vyzerať napríklad takto:

   typedef struct potvora 
   {
       int x;
       int y;
       struct potvora *dalsia;
   } POTVORA;

Štruktúra POTVORA má tri zložky. Prvé dve -- x a y budú obsahovať súradnice, na ktorých sa bude potvora nachádzať. Tretia zložka je smerník na ďalšiu štruktúru typu POTVORA. To nám umožní zoradiť všetky potvory ktoré sú práve na hracej ploche do vláčiku, ktorý bude vyzerať napríklad takto:

Dá sa to spraviť napríklad nasledujúcim spôsobom. Najprv si deklarujeme premennú i typu int a tri smerníky na štrukúru POTVORA, ktoré nazveme zaciatok, aktualna a nova. S pomocou funkcie malloc si v pamäti alokujeme prvú potvoru. Smerník aktualna nastavíme tak, aby na ňu ukazoval tiež. Hodnoty x a y nastavíme na náhodné hodnoty a smerník dalsia predbežne nastavíme na NULL.

    int i;
    POTVORA *zaciatok, *aktualna, *nova;
    
    zaciatok = (POTVORA *) malloc(sizeof(POTVORA));
    aktualna = zaciatok;
    aktualna -> x = random() % 640;
    aktualna -> y = random() % 480;
    aktualna -> dalsia = NULL;

Keď tento kód prebehne, situácia bude približne takáto:

A teraz môžeme pridávať ďalšie vagóniky napríklad týmto spôsobom:

    for( i = 0; i < 10; i++ )
    {
        nova = (POTVORA *) malloc(sizeof(POTVORA));
        aktualna -> dalsia = nova;
        aktualna = nova;
        aktualna -> x = random() % 640;
        aktualna -> y = random() % 480;
        aktualna -> dalsia = NULL;
    }

Smerník aktualna ukazuje na poslednú potvoru v zozname. V prvom príkaze v tele cyklu alokujeme v pamäti miesto pre novú potvoru. V druhom príkaze ju pripojíme na koniec vláčiku. Potom smerník aktualna nastavíme na novopridaný prvok a naplníme jednotlivé položky. V každom behu cyklu pridáme jeden vagónik. Keď ho teda necháme zbehnúť dvakrát, bude situácia vyzerať presne ako na prvom obrázku, ak prebehne desaťkrát, vagónikov bude 11.

Dôležité upozornenie: Ak neopatrne zmeníte hodnotu smerníka zaciatok, zabudnete, kde vláčik začína a ten sa nenávratne stratí v hlbinách pamäte počítača. Preto si dávajte pozor pri manipulácii s týmto smerníkom.

Ak chcete prejsť všetky prvky zoznamu, spraví sa to jednoducho. Nasledujúci cyklus vypíše súradnice všetkých zúčastnených potvor:

    aktualna = zaciatok;
    while (aktualna != NULL)
    {
        printf("[%d, %d]\n", aktualna -> x, aktualna -> y);
        aktualna = aktualna -> dalsia;
    }

Na začiatku smerník aktualna nastavíme na začiatok. Vypíšeme údaje potvory, na ktorú ukazuje a smerník aktuálna nastavíme na ďalšiu. Toto opakujeme dovtedy, kým smerník aktuálna ukazuje na niečo zmysluplné.

Keď prácu so zoznamom skončíme, patrí sa uvoľniť pamäť. Spravíme to napríklad takto:

    while (zaciatok != NULL)
    {
        aktualna = zaciatok -> dalsia;
        free((void *) zaciatok);
        zaciatok = aktualna;
    }

Funguje to tak, že si v premennej aktualna uložíme druhý prvok v zozname, potom zmažeme začiatok zoznamu a smerník zaciatok nastavíme na nový začiatok vláčiku. Toto opakujeme, kým je čo mazať.

Uf. Je toho hodne na pochopenie. Takže si to pre istotu prečítajte ešte raz a potom sa pustite do úloh.

Úloha č.1 Pochopte, poskladajte z toho zmysluplný program a vyskúšajte.

Úloha č.2 Napíšte funkciu, ktorá v hotovom zozname vynuluje súradnice všetkých potvor.

Úloha č.3 Napíšte funkciu, ktorá zo zoznamu vymaže piaty prvok, ak taký existuje. Vypíšte obsah zoznamu pred a po zavolaní funkcie.

Úloha č.4 Vytvorte zoznam, v ktorom sa dá pohybovať oboma smermi. (Každý vagónik obsahuje okrem šipky na ďalšiu potvoru aj šipku na predošlú.) Vyrobte zoznam s desiatimi prvkami a vypíšte ho odpredu aj odzadu.