Lekce 1 - Úvod do kolekcí a datových struktur v jazyce C

Pokud se podíváme do výkladového slovníku, co znamená slovo kolekce, tak je to soubor předmětů uspořádaných podle určitého systému. Může to být kolekce šatů na určité výstavě nebo kolekce bonbónů v bonboniéře.

Z hlediska programátorského jsou kolekce datové struktury uspořádané podle určitého systému. Do kolekce můžeme podle určitých pravidel data přidávat, odebírat a přistupovat k nim. Aby to bylo možné, prvky kolekce musí být mezi sebou propojeny.

Pojmem datová struktura můžeme označovat jak celkovou kolekci, tak i jednotlivé prvky v kolekci, viz dále.

Statické vs. dynamické datové struktury

Kolekce jsou buď statické nebo dynamické:

• Statické datové struktury se používají hlavně v mikroprocesorových systémech (embedded systems), kde je omezené množství RAM paměti. Při statických kolekcích se v programu určí předem daný prostor pro datové struktury (prvky kolekce), většinou jako pole. Propojení prvků kolekce je pak implicitně definováno indexem pole.
• V dynamických kolekcích se pro datové struktury prvků prostor vytváří až při vzniku prvku. Na jejich propojení se používá ukazatel (pointer), který ukazuje z prvku na jiný prvek, jako by byly v řetězu. Hlavní výhodou je, že nám v kolekci nedojde místo, jako se to může stát u statického pole s pevně daným počtem prvků. Na klasických počítačích zanedbatelnou nevýhodou je nějaká režie navíc na ukazatele a práci s kolekcí.

Dynamické kolekce

Nyní se budeme věnovat dynamickým strukturám, statické si ukážeme v pozdějších lekcích. V dynamických datových strukturách se každý prvek skládá ze dvou částí:

• Ukazatele (v obrázku níže next) na jiný prvek a z
• Těla (v obrázku body), což je hodnota uložená v prvku. Tělo může být jednoduché číslo, jiná struktura nebo ukazatel na něco, co potřebujeme (v obrázku Object):

V úvodních lekcích budeme do našich kolekcí ukládat jen celá čísla, tělo struktury prvku tedy bude typu int. Pro pochopení principu je to dostačující. V následujících lekcích kurzu si pak ukážeme i složitější struktury.

Struktura

Náš prvek v kolekci bude tedy reprezentován jednoduchou strukturou:

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

Položka struktury ITEM* next je ukazatel na další prvek ITEM v kolekci a number je číslo v daném prvku uložené. Je tedy tělem datové struktury.

Kolekce těchto struktur spojených za sebe potom bude vypadat např. takto:

Podobné řetězení struktur přes ukazatele jsme si již zkoušeli v lekci Spojové seznamy v jazyce C.

Zásobník

Jednou z nejjednodušších kolekcí na implementaci je zásobník (anglicky stack) a proto jím i začneme. Jinak se nazývá i LIFO, podle anglického Last In First Out, což znamená poslední přišel, první odešel.

Kolekce funguje doslova jako např. zásobník samopalu. Posledně nabitý náboj v zásobníku je ten, který první vystřelí:

Jednoduchost spočívá v tom, že vždy nakládáme pouze s vrcholem zásobníku:

Reálný příklad užití je např. funkce Undo (zpět), kde se jednotlivé kroky (např. změny v nějakém editoru) ukládají do zásobníku a funkce Undo nás vždy vrátí do toho posledního uloženého stavu. Dále se používá k parsování matematických výrazů a spoustě dalších algoritmů.

Call stack

I když si to možná neuvědomujeme, zásobník je vnitřně používán v každém našem programu. Při každém volání nějaké funkce je totiž aktuální návratová adresa programu uložena do zásobníku (tzv. call stack). Díky němu se pak program může vrátit na původní pozici, odkud byla daná funkce zavolána, a pokračovat dál. Funkce v sobě pak může volat další funkci a podobně. Přes zásobník se pak vždy program vrátí na původní "řádku". Navíc všechny parametry funkce se přenášejí přes zásobník. Toto ale není problematika této lekce. Na principu zásobníku jsou založeny programovací jazyky jako PostScript nebo Forth, ale ani to není problematika této lekce

Funkce zásobníku

Datová struktura typu zásobník má tyto funkce, které si my v tom našem také definujeme:

• push() (přidej) - přidá na vrchol zásobníku nový ITEM obsahující dané číslo typu int
• pop() (odeber) - odebere z vrcholu zásobníku poslední ITEM a vrátí jej
• peek() (viz) - vrátí vrchol zásobníku, ale prvek ze zásobníku neodstraňuje
• print_collection() (vytiskni zásobník) - vypíše obsah zásobníku od vrcholu po dno

Vrchol zásobníku

Definujme proměnnou, která ukazuje na vrchol zásobníku. Nyní na chvíli porušíme hlavní zásady dobrého programování a uděláme proměnnou globální pro snadnější vysvětlení. Později kód ještě upravíme. Deklarace vrcholu (hlavy) zásobníku vypadá následovně:

ITEM *header = NULL;

Proměnná header zatím ukazuje na nic (NULL), zásobník je tedy prázdný.

push()

První funkce zásobníku je push(). Ta má na starosti vložení položky, tedy v našem případě celého čísla, do zásobníku:

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;
}

Funkce přebírá parametr new_number typu int. Jejím úkolem je vytvořit nový prvek ITEM, do něj vložit požadované číslo a prvek umístit na vrchol zásobníku. Funkce malloc() nám vyhradí novou paměť pro novou proměnnou ITEM. Pokud je nedostatek paměti nebo jakákoli jiná okolnost, co neumožní přiřadit paměť, vrací se hodnota NULL, tedy nepřidělené.

Umístění na vrchol zásobníku je jednoduché. V nové položce nastavujeme ukazatel next tam, kam dosud ukazoval header. A header pak nastavujeme na novou položku, která se stala novým vrcholem. Pro další použití v programu vrátíme ukazatel na novou položku. Ten není nutné v programu použít, ale může se hodit.

Možná funkci jednodušeji pochopíte z následujícího obrázku:

pop()

Druhá funkce zásobníku je pop(), vracející položku, která je teď na řadě:

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

Funkce nemá parametry a odstraňuje z vrcholu zásobníku položku ITEM, kterou nám vrátí jako návratovou hodnotu. Ukazatel header se posune na další položku. Pokud je zásobník prázdný, vrátí nám NULL.

Je třeba upozornit, že položka není odstraněna z paměti. Proto by měl slušný program, který zavolá funkci pop(), položku i odstranit pomocí funkce free(). Jinak bude během běhu celého programu alokovat paměť.

peek()

Třetí funkcí zásobníku je peek(). Tu použijeme, pokud chceme "vidět" položku z vrcholu zásobníku:

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

Jedná se pouze o primitivní vrácení ukazatele na vrchol zásobníku, v zásobníku se nic nemění. V pozdějších lekcích si vysvětlíme, k čemu se taková funkce používá.

print_collection()

Čtvrtá funkce zásobníku 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čátku funkce vypíše "PRINT COLLECTION START:", abychom výstup v konzoli dobře viděli. Potom prochází prvky od vrcholu zásobníku až na jeho dno a vypíše pořadové číslo položky ITEM a hodnotu int v ní uloženou. Nakonec vypíše "PRINT COLLECTION END".

Hlavní program

Teď si vytvoříme hlavní program, na kterém zásobník vyzkoušíme:

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 programu do zásobníku postupně vložíme čísla 11, 7, 8 a vypíšeme jeho obsah. Vidíme, že jsou v kolekci typu zásobník prvky opravdu uloženy v "opačném pořadí". Následně se podíváme pomocí peek() na vrchol a vypíšeme tento prvek (což je posledně přidané číslo 8). Dále pomocí pop() získáme poslední prvek, což je stále 8. Tím tento prvek ze zásobníku zmizí.

V další části programu přidáme další 2 prvky, -88 a 100, a kolekci opět vypíšeme. Nakonec zásobník postupně vyprázdníme.

Na obrazovce uvidíme následující výstup:

Konzolová aplikace
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 princip dynamických kolekcí je v podstatě jednoduchý. Jen je třeba dávat pozor na ukazatele. Pokud bychom např. změnili pořadí řádků ve funkci push() z:

new_item->next = header;
header = new_item;

na:

header = new_item;
new_item->next = header;

Tak to je hrubá chyba, protože header bude ukazovat na novou položku, ale ukazatel nové položky next bude ukazovat na header a ztratíme celý zásobník.

V příští lekci, Implementace zásobníku v jazyce C, si ukážeme, jak udělat zásobník bez použití globální proměnné.

 

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.