1. diel - Úvod do kolekcií a dátových štruktúr v jazyku C

Ak sa pozrieme do výkladového slovníka, čo znamená slovo kolekcia, tak je to súbor predmetov usporiadaných podľa určitého systému. Môže to byť kolekcie šiat na určité výstave alebo kolekcia cukríkov v bonboniére.

Z hľadiska programátorského sú kolekcie dátové štruktúry usporiadané podľa určitého systému. Do kolekcie môžeme podľa určitých pravidiel dátumu pridávať, odoberať a pristupovať k nim. Aby to bolo možné, prvky kolekcia musí byť medzi sebou prepojené.

Pojmom dátová štruktúra môžeme označovať ako celkovú kolekciu, tak aj jednotlivé prvky v kolekcii, viď ďalej.

Statické vs. dynamické dátové štruktúry

Kolekcie sú buď statické alebo dynamické:

• Statické dátové štruktúry sa používajú hlavne v mikroprocesorových systémoch (embedded systems), kde je obmedzené množstvo RAM pamäte. Pri statických kolekciách sa v programe vyhradí vopred daný priestor pre dátové štruktúry (prvky kolekcie), väčšinou ako pole. Prepojenie prvkov kolekcie je potom implicitne definované indexom poľa.
• V dynamických kolekciách sa pre dátové štruktúry prvkov priestor vytvára až pri vzniku prvku. Na ich prepojenie sa používa ukazovateľ (pointer), ktorý ukazuje z prvku na iný prvok, ako by boli v reťazi. Hlavnou výhodou je, že nám v kolekcii nedôjde miesto, ako sa to môže stať u statického poľa s pevne daným počtom prvkov. Na klasických počítačoch zanedbateľnou nevýhodou je nejaká réžia navyše na ukazovatele a prácu s kolekciou.

Dynamické kolekcie

Teraz sa budeme venovať dynamickým štruktúram, statické si ukážeme v neskorších lekciách. V dynamických dátových štruktúrach sa každý prvok skladá z dvoch častí:

• Ukazovatele (v obrázku nižšie next) na iný prvok az
• Telá (v obrázku body), čo je hodnota uložená v prvku. Telo môže byť jednoduché číslo, iná štruktúra alebo ukazovateľ na niečo, čo potrebujeme (v obrázku Object):

V úvodných lekciách budeme do našich kolekcií ukladať len celé čísla, telo štruktúry prvku teda bude typu int. Pre pochopenie princípu je to dostačujúce. V nasledujúcich lekciách kurze si potom ukážeme aj zložitejšie štruktúry.

Štruktúra

Náš prvok v kolekcii bude teda reprezentovaný jednoduchou štruktúrou:

struct ITEM
{
    struct ITEM* next;
    int number;
};

Položka štruktúry ITEM* next je ukazovateľ na ďalší prvok ITEM v kolekcii a number je číslo v danom prvku uložené. Je teda telom dátové štruktúry.

Kolekcia týchto štruktúr spojených za seba potom bude vyzerať napr. Nasledovne:

Podobné reťazenie štruktúr cez ukazovatele sme si už skúšali v lekcii Spojové zoznamy v jazyku C.

Zásobník

Jednou z najjednoduchších kolekcií na implementáciu je zásobník (anglicky stack) a preto ním aj začneme. Inak sa nazýva aj LIFO, podľa anglického Last In First Out, čo znamená posledný prišiel, prvý odišiel.

Kolekcia funguje doslova ako napr. Zásobník samopalu. Naposledy nabitý náboj v zásobníku je ten, ktorý prvý vystrelí:

Jednoduchosť spočíva v tom, že vždy nakladáme iba s vrcholom zásobníka:

Reálny príklad použitia je napr. Funkcia Undo (späť), kde sa jednotlivé kroky (napr. Zmeny v nejakom editore) ukladajú do zásobníka a funkcie Undo nás vždy vráti do toho posledného uloženého stavu. Ďalej sa používa na parsovanie matematických výrazov a množstvu ďalších algoritmov.

Call stack

Aj keď si to možno neuvedomujeme, zásobník je vnútorne používaný v každom našom programe. Pri každom volaní nejaké funkcia je totiž aktuálna návratová adresa programu uložená do zásobníka (tzv. Call stack). Vďaka nemu sa potom program môže vrátiť na pôvodnú pozíciu, odkiaľ bola daná funkcia zavolaná, a pokračovať ďalej. Funkcie v sebe potom môže volať ďalšiu funkciu a podobne. Cez zásobník sa potom vždy program vráti na pôvodnú "riadku". Navyše všetky parametre funkcie sa prenášajú cez zásobník. Toto ale nie je problematika tejto lekcie. Na princípe zásobníka sú založené programovacie jazyky ako PostScript alebo Forth, ale ani to nie je problematika tejto lekcie:)

Funkcie zásobníka

Dátová štruktúra typu zásobník má tieto funkcie, ktoré si my v tom našom tiež definujeme:

• push() (pridaj) - pridá na vrchol zásobníka nový ITEM obsahujúce dané číslo typu int
• pop() (odober) - odoberie z vrcholu zásobníka poslednej ITEM a vráti ho
• peek() (viď) - vráti vrchol zásobníka, ale prvok zo zásobníka neodstraňuje
• print_collection() (vytlač zásobník) - vypíše obsah zásobníka od vrcholu po dno

Vrchol zásobníka

Definujme premennú, ktorá ukazuje na vrchol zásobníka. Teraz na chvíľu porušíme hlavné zásady dobrého programovania a urobíme premennú globálne pre ľahšie vysvetlenie. Neskôr kód ešte upravíme. Deklarácia vrcholu (hlavy) zásobníka vyzerá nasledovne:

ITEM *header = NULL;

Premenná header zatiaľ ukazuje na nič (NULL), zásobník je teda prázdny.

push()

Prvá funkcia zásobníka je push(). Tá má na starosti vloženie položky, teda v našom prípade celého čísla, do zásobníka:

struct ITEM* push( int new_number)
{
    struct ITEM* new_item = (struct ITEM*)malloc(sizeof(struct ITEM));
    if (new_item == NULL)
        return NULL;
    new_item->number = new_number;
    new_item->next = header;
    header = new_item;
    return new_item;
}

Funkcia preberá parameter new_number typu int. Jej úlohou je vytvoriť nový prvok ITEM, doň vložiť požadované číslo a prvok umiestniť na vrchol zásobníka. Funkcia malloc() nám vyhradí novú pamäť pre novú premennú ITEM. Ak je nedostatok pamäte alebo akákoľvek iná okolnosť, čo neumožní priradiť pamäť, vracia sa hodnota NULL, teda nepridelené.

Umiestnenie na vrchol zásobníka je jednoduché. V novej položke nastavujeme ukazovateľ next tam, kam doteraz ukazoval header. A header potom nastavujeme na novú položku, ktorá sa stala novým vrcholom. Pre ďalšie použitie v programe vrátime ukazovateľ na novú položku. Ten nie je nutné v programe použiť, ale môže sa hodiť.

Možno funkciu jednoduchšie pochopíte z nasledujúceho obrázku:

pop()

Druhá funkcia zásobníka je pop(), vracajúci položku, ktorá je teraz na rade:

struct ITEM* pop( void )
{
    struct ITEM* old_item;
    if (header == NULL)
        return NULL;
    old_item = header;
    header = header->next;
    return old_item;
}

Funkcia nemá parametre a odstraňuje z vrcholu zásobníka položku ITEM, ktorú nám vráti ako návratovú hodnotu. Ukazovateľ header sa posunie na ďalšiu položku. Ak je zásobník prázdny, vráti nám NULL.

Je potrebné upozorniť, že položka nie je odstránená z pamäte. Preto by mal slušný program, ktorý zavolá funkciu pop(), položku aj odstrániť pomocou funkcie free(). Inak bude počas behu celého programu alokovať pamäť.

peek()

Treťou funkciou zásobníka je peek(). Tú použijeme, ak chceme "vidieť" položku z vrcholu zásobníka:

struct ITEM* peek( void )
{
    return header;
}

Jedná sa len o primitívne vrátenie ukazovatele na vrchol zásobníka, v zásobníku sa nič nemení. V neskorších lekciách si vysvetlíme, na čo sa taká funkcia používa.

print_collection()

Štvrtá funkcie zásobníka je print_collection():

void print_collection( void )
{
    int i = 1;
    struct ITEM* item;
    printf("PRINT COLLECTION START:\r\n");
    item = header;
    while (item != NULL)
    {
        printf("%2d: %4d\r\n", i, item->number);
        i++;
        item = item->next;
    }
    printf("PRINT COLLECTION END.\r\n");
}

Na začiatku funkcie vypíše "PRINT COLLECTION START:", aby sme výstup v konzole dobre videli. Potom prechádza prvky od vrcholu zásobníka až na jeho dno a vypíše poradové číslo položky ITEM a hodnotu int v nej uloženú. Nakoniec vypíše "PRINT COLLECTION END".

Hlavný program

Teraz si vytvoríme hlavný program, na ktorom zásobník vyskúšame:

int main()
{
    struct ITEM* polozka;
    push( 11 );     // vlozime polozku na vrchol zasobniku
    push( 7 );      // vlozime polozku na vrchol zasobniku
    push( 8 );      // vlozime polozku na vrchol zasobniku
    print_collection(); // vypiseme zasobnik

    polozka = peek();   // podivame se na vrchol zasobniku
    if (polozka != NULL)
    {
        printf("Item top of stack: %d\r\n", polozka->number);
    }
    polozka = pop();
    if( polozka != NULL)
    {
        // polozku muzeme dale pouzivat, ale uz neni v zasobniku
        printf("Item pop from top of stack: %d\r\n", polozka->number);
        // chceme byt slusni, tak po pouziti polozku odstranime i z pameti
        free(polozka);
        // uz ji dale nemuzeme pouzivat
    }
    push(-88);      // vlozime polozku na vrchol zasobniku
    push(100);      // vlozime polozku na vrchol zasobniku
    print_collection();

    free( pop() ); // i takto odstranime polozku ze zasobniku i z pameti
    pop();  // odstranime polozku z vrcholu zasobniku
            // ale neni odstranena z pameti
            // zabira pamet az do skonceni programu
    print_collection();
    free( pop() );
    pop();
    // toto neodstranilo nic, protoze zasobnik je prazdny
    print_collection();
    getchar(); // abychom videli vystup na obrazovce
    return 0;
}

V programe do zásobníka postupne vložíme čísla 11, 7, 8 a vypíšeme jeho obsah. Vidíme, že sú v kolekcii typu zásobník prvky naozaj uložené v "opačnom poradí". Následne sa pozrieme pomocou peek() na vrchol a vypíšeme tento prvok (čo je posledne pridané číslo 8). Ďalej pomocou pop() získame posledný prvok, čo je stále 8. Tým tento prvok zo zásobníka zmizne.

V ďalšej časti programu pridáme ďalšie 2 prvky, -88 a 100, a kolekcii opäť vypíšeme. Nakoniec zásobník postupne vyprázdnime.

Na obrazovke uvidíme nasledujúci výstup:

Konzolová aplikácia
PRINT COLLECTION START:
 1:    8
 2:    7
 3:   11
PRINT COLLECTION END.
Item top of stack: 8
Item pop from top of stack: 8
PRINT COLLECTION START:
 1:  100
 2:  -88
 3:    7
 4:   11
PRINT COLLECTION END.
PRINT COLLECTION START:
 1:    7
 2:   11
PRINT COLLECTION END.
PRINT COLLECTION START:
PRINT COLLECTION END.

Vidíme, že princíp dynamických kolekcií je v podstate jednoduchý. Len je treba dávať pozor na ukazovateľa. Ak by sme napr. Zmenili poradie riadkov vo funkcii push() z:

new_item->next = header;
header = new_item;

na:

header = new_item;
new_item->next = header;

Tak to je hrubá chyba, pretože header bude ukazovať na novú položku, ale ukazovateľ nové položky next bude ukazovať na header a stratíme celý zásobník.

V budúcej lekcii, Implementácia zásobníka v jazyku C , si ukážeme, ako urobiť zásobník bez použitia globálne premenné.

 

Mal si s čímkoľvek problém? Stiahni si vzorovú aplikáciu nižšie a porovnaj ju so svojím projektom, chybu tak ľahko nájdeš.