Prednáška 17

Oznamy

• Na začiatku piatkových cvičení bude krátka písomka zameraná na rekurziu a smerníky, body za ktorú budú riadnou súčasťou hodnotenia cvičení č. 9.
• Za písomku bude možné získať najviac 6 bodov – plný počet bodov za tohtotýždňové cvičenia teda bude 12 (ďalšie 2 body možno získať za bonusovú úlohu).
• Zverejnenie zadaní, ako aj odovzdávanie riešení bude realizované prostredníctvom testovača. Na začiatku písomky nájdete svoje zadanie, vo forme editovateľného PDF, ako prvý odovzdaný súbor v rámci príslušnej úlohy. Riešenia budete vypĺňať priamo do vyhradených políčok v zadaní (alebo v prípade technických problémov do priloženej „kostry” v textovom formáte).
• Dnes po prednáške bude na testovači zverejnená ukážková písomka (za 0 bodov), na ktorej si možno proces odovzdávania riešení vyskúšať (reálna piatková písomka bude podstatne náročnejšia). V prípade problémov nás, prosím, kontaktujte.

Binárne súbory

Textové súbory sú v praxi často nepostačujúcim formátom na ukladanie dát. Ich nevýhody sú napríklad nasledujúce:

• Aj číselné dáta sú v textovom súbore uložené ako postupnosti znakov, čoho dôsledkom je plytvanie pamäťou a pomalé čítanie a zápis (v dôsledku nutnosti konvertovať reťazce na čísla a opačne).
• Pri zápise reálnych čísel môže dochádzať k strate presnosti.
• Pri zápise štruktúr alebo polí je nutné vymyslieť formát ich textovej reprezentácie a naprogramovať funkcie realizujúce ich načítanie a zápis.
• ...

Alternatívnym riešením je použitie binárnych súborov, do ktorých sa namiesto textovej reprezentácie dát ukladá priamo postupnosť bytov zodpovedajúca reprezentácii týchto dát v pamäti počítača. Napríklad 4-bytová premenná typu int s hodnotou 2000000000 sa tak v binárnom súbore reprezentuje 4 bytmi, kým v textovom súbore by bol nutný jeden byte pre každý znak (čiže dohromady 10 bytov) a pravdepodobne aj nejaký oddeľovač od ďalších dát, čomu zodpovedá minimálne jeden ďalší byte.

Binárne súbory teda poskytujú vo všeobecnosti pamäťovo aj časovo efektívnejší spôsob ukladania dát. Nevýhodou tohto prístupu však je, že typicky nie je prenositeľný medzi rôznymi architektúrami, operačnými systémami, či kompilátormi. Napísať program, ktorý na ľubovoľnom systéme vytvorí rovnaký binárny súbor, je pomerne zložité – typicky sa na tento účel používajú špecializované knižnice.

Na tomto predmete budeme pracovať len s textovými súbormi. V nasledujúcom sa však pre úplnosť v krátkosti zameriame aj na základy práce s binárnymi súbormi.

Funkcia fwrite

Funkcia

size_t fwrite(const void *p, size_t size, size_t count, FILE *f);

zapíše do súboru, na ktorý ukazuje smerník f, presne count pamäťových úsekov veľkosti size bytov, nachádzajúcich sa v pamäti od adresy p. Výstupom je potom počet reálne zapísaných úsekov. V hlavičke funkcie fwrite sa vyskytujú dva nové prvky:

• Typ size_t je celočíselný typ, ktorý sa používa na meranie veľkosti pamäte (každý index poľa je napríklad určite tohto typu). Je definovaný vo viacerých knižniciach, napríklad aj v cstdio a je prakticky ekvivalentný nezáporným celým číslam.
• Smerník na void je špeciálny smerníkový typ, ktorý slúži ako vyjadrenie toho, že argumentom môže byť smerník ľubovoľného typu.

Aby bolo možné použiť túto funkciu, musí byť súbor f otvorený na zápis v móde wb (b tu znamená binárny súbor).

Príklad: nasledujúci program vytvorí pole pozostávajúce z druhých odmocnín čísel 0 až 99 a toto pole uloží do binárneho súboru binarny.dat. Využíva pritom operátor sizeof, ktorý vracia veľkosť reprezentácie daného typu v bytoch.

#include <cstdio>
#include <cmath>
using namespace std;

int main(void) {
    double a[100];
    FILE *f;
    
    for (int i = 0; i <= 99; i++) {
        a[i] = sqrt(i);
    }
    
    f = fopen("binarny.dat", "wb");
    fwrite(a, sizeof(double), 100, f);
    fclose(f);
    
    return 0;
}

Funkcia fread

Funkcia

size_t fread(void *p, size_t size, size_t count, FILE *f);

zo súboru, na ktorý ukazuje smerník f, prečíta count položiek veľkosti size a uloží ich do pamäte od adresy p.

Ak by sme napríklad chceli overiť, že piatym reálnym číslom uloženým v súbore vytvorenom pomocou programu z predchádzajúceho príkladu je skutočne číslo 2, môžeme napríklad do poľa a uložiť prvých 5 položiek zo súboru binarny.dat a skontrolovať prvok a[4]:

#include <cstdio>
using namespace std;

int main(void) {
    FILE *f;
    double a[5];

    f = fopen("binarny.dat", "rb");
    fread(a, sizeof(double), 5, f);
    fclose(f);
    printf("%f\n", a[4]);
    
    return 0;
}

Nasledujúce alternatívne riešenie je o niečo pamäťovo efektívnejšie:

#include <cstdio>
using namespace std;

int main(void) {
    FILE *f;
    double *x = new double;

    f = fopen("binarny.dat", "rb");
    for (int i = 0; i <= 4; i++) {
        fread(x, sizeof(double), 1, f);
    }
    fclose(f);
    printf("%f\n", *x);
    delete x;
                     
    return 0;
}

Práca so súbormi prostredníctvom knižnice fstream

So súbormi sme pracovali prostredníctvom knižnice cstdio, ktorá je štandardnou knižnicou jazyka C. Druhou možnosťou, ktorú tu iba telegraficky spomenieme, je využitie knižnice fstream. Tá je štandardnou knižnicou jazyka C++ a umožňuje so súbormi pracovať podobne ako s konzolou prostredníctvom knižnice iostream.

Základy tohto prístupu demonštrujeme na príklade programu, ktorý zo súboru vstup.txt prečíta prirodzené číslo N a následne N ďalších čísel. Tieto čísla potom v obrátenom poradí a oddelené medzerami vypíše do súboru vystup.txt.

#include <fstream>
using namespace std;

const int maxN = 100;

int main(void) {
    ifstream input;
    ofstream output;
    
    int N;
    int a[maxN];
    
    input.open("vstup.txt");
    input >> N;
    for (int i = 0; i <= N-1; i++) {
        input >> a[i];
    }
    input.close();
    
    output.open("vystup.txt");
    for (int i = N-1; i >= 0; i--) {
        output << a[i] << " ";
    }
    output.close();
 
    return 0; 
}

Abstraktný dátový typ

Abstraktné dátové typy (ADT) sú abstrakciami dátových štruktúr nezávislými od samotnej implementácie. Zvyčajne bývajú dané prostredníctvom množiny operácií (hlavičiek funkcií), ktoré daný abstraktný dátový typ poskytuje na prácu s dátami používateľovi. Témou 14. prednášky bol napríklad abstraktný dátový typ dynamická množina, ktorý poskytuje tri základné operácie:

• Zistenie príslušnosti prvku do množiny (contains).
• Pridanie prvku do množiny (add).
• Odobranie prvky z množiny (remove).

Jeden abstraktný dátový typ môže byť implementovaný pomocou viacerých dátových štruktúr. Na 14. prednáške bol napríklad abstraktný dátový typ dynamická množina (presnejšie jeho operácie contains a add) implementovaný pomocou neutriedeného poľa, utriedeného poľa, spájaného zoznamu, priameho adresovania a hešovania.

Výhodou abstraktných dátových typov je predovšetkým oddelenie implementácie dátovej štruktúry od programu, ktorý ju používa. Napríklad program pracujúci s dynamickou množinou prostredníctvom funkcií contains, add a remove možno rovnako dobre použiť pri implementácii množiny pomocou neutriedených polí, ako pri jeho implementácii pomocou hešovania.

Témou dnešnej prednášky budú dva nové abstraktné dátové typy: zásobník (angl. stack) a rad alebo front (angl. queue).

Rad a zásobník

Rad (často aj front; angl. queue) a zásobník (angl. stack) sú jednoduché abstraktné dátové typy umožňujúce udržiavať postupnosť nejakých prvkov (typicky môže ísť o úlohy alebo dáta čakajúce na spracovanie). Rad aj zásobník poskytujú funkciu umožňujúcu vložiť do nich používateľom zadaný prvok. Druhou základnou funkciou poskytovanou oboma týmito abstraktnými dátovými typmi je výber jedného prvku z radu resp. zo zásobníka. Rad sa od zásobníka líši najmä správaním tejto druhej operácie.

Rad

Z radu sa zakaždým vyberie ten jeho prvok, ktorý doň bol vložený ako prvý spomedzi jeho aktuálnych prvkov – možno ho tak pripodobniť k radu pri pokladni v obchode. Takáto metóda manipulácie s dátami sa v angličtine označuje skratkou FIFO, podľa first in, first out.

Prvky radu môžu byť ľubovoľného typu. Namiesto konkrétneho typu (ako napríklad int alebo char) tak budeme pracovať so všeobecným typom, ktorý nazveme dataType. Za ten možno dosadiť ľubovoľný konkrétny typ – napríklad int dosadíme za dataType takto:

typedef int dataType;

Pri využití tohto prístupu tak napríklad bude možné získať z radu prvkov typu int rad prvkov typu char zmenou v jedinom riadku programu.

Abstraktný dátový typ pre rad môže poskytovať napríklad tieto operácie (kde queue je názov štruktúry reprezentujúcej rad):

/* Inicializuje prazdny rad */
void init(queue &q);

/* Zisti, ci je rad prazdny */
bool isEmpty(queue &q);

/* Prida prvok item na koniec radu */
void enqueue(queue &q, dataType item);

/* Odoberie prvok zo zaciatku radu a vrati jeho hodnotu */
dataType dequeue(queue &q);

/* Vrati prvok zo zaciatku radu, ale necha ho v rade */
dataType peek(queue &q);

/* Uvolni pamat */
void destroy(queue &q);

Zásobník

Zo zásobníka sa naopak zakaždým vyberie ten prvok, ktorý doň bol vložený ako posledný. Táto metóda manipulácie s dátami sa v angličtine označuje skratkou LIFO, podľa last in, first out.

Abstraktný dátový typ pre zásobník tak môže poskytovať napríklad nasledujúce operácie (stack je názov štruktúry reprezentujúcej zásobník a opäť pracujeme s prvkami všeobecného typu dataType):

/* Inicializuje prazdny zasobnik */
void init(stack &s);

/* Zisti, ci je zasobnik prazdny */
bool isEmpty(stack &s);

/* Prida prvok item na vrch zasobnika */
void push(stack &s, dataType item);

/* Odoberie prvok z vrchu zasobnika a vrati jeho hodnotu */
dataType pop(stack &s);

/* Vrati prvok na vrchu zasobnika, ale necha ho v zasobniku */
dataType peek(stack &s);

/* Uvolni pamat */
void destroy(stack &s);

Programy využívajúce rad a zásobník

Bez ohľadu na samotnú implementáciu vyššie uvedených funkcií vieme písať programy, ktoré ich využívajú. Napríklad nasledujúci program pracuje s radom:

#include <iostream>
using namespace std;

typedef int dataType;


/* Sem pride definicia struktury queue a vsetkych potrebnych funkcii. */


int main(void) {
    queue q;
    init(q);
    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    cout << dequeue(q) << endl;  // Vypise 1
    cout << dequeue(q) << endl;  // Vypise 2
    cout << dequeue(q) << endl;  // Vypise 3
    destroy(q);
    return 0;
}

Podobne nasledujúci program pracuje so zásobníkom:

#include <iostream>
using namespace std;

typedef int dataType;


/* Sem pride definicia struktury stack a vsetkych potrebnych funkcii. */


int main(void) {
    stack s;
    init(s);
    push(s, 1);
    push(s, 2);
    push(s, 3);
    cout << pop(s) << endl;  // Vypise 3
    cout << pop(s) << endl;  // Vypise 2
    cout << pop(s) << endl;  // Vypise 1
    destroy(s);
    return 0;
}

Implementácia zásobníka a radu

Zásobník pomocou poľa

Na úvod implementujeme zásobník pomocou poľa items, ktoré budeme alokovať na fixnú dĺžku maxN (rovnako dobre by sme však mohli použiť aj dynamické pole). Spodok zásobníka pritom bude v tomto poli uložený na pozícii 0 a jeho vrch na pozícii top. V prípade, že je zásobník prázdny, bude hodnota premennej top rovná -1.

#include <cassert>

// ...

const int maxN = 1000;

struct stack {
    dataType *items; // Alokujeme na pole reprezentujuce jednotlive prvky zasobnika.
    int top;         // Index vrchu zasobnika v poli items. Ak je zasobnik prazdny, ma hodnotu -1.
};

/* Inicializuje prazdny zasobnik */
void init(stack &s) {
    s.items = new dataType[maxN];
    s.top = -1; 
}

/* Zisti, ci je zasobnik prazdny */
bool isEmpty(stack &s) {
    return s.top == -1;
}

/* Prida prvok item na vrch zasobnika */
void push(stack &s, dataType item) {
    assert(s.top <= maxN - 2);
    s.top++;
    s.items[s.top] = item;
} 

/* Odoberie prvok z vrchu zasobnika a vrati jeho hodnotu */
dataType pop(stack &s) {
    assert(!isEmpty(s));
    s.top--;
    return s.items[s.top + 1];
}

/* Vrati prvok na vrchu zasobnika, ale necha ho v zasobniku */          
dataType peek(stack &s) {
    assert(!isEmpty(s));
    return s.items[s.top];
}

/* Uvolni pamat */
void destroy(stack &s) {
    delete[] s.items;
}

Rad pomocou poľa

Rad sa od zásobníka líši tým, že prvky sa z neho vyberajú z opačnej strany, než sa doň vkladajú. Keby sa teda prvý prvok radu udržiaval na pozícii 0, museli by sa po každom výbere prvku tie zvyšné posunúť o jednu pozíciu „doľava”, čo je časovo neefektívne. Rad teda implementujeme tak, aby jeho začiatok mohol byť na ľubovoľnej pozícii first poľa items. Pole items pritom budeme chápať ako cyklické – prvky s indexom menším ako first pritom budeme interpretovať ako nasledujúce za posledným prvkom poľa.

#include <cassert>

// ...

const int maxN = 1000;

struct queue {
    dataType *items; // Alokujeme na pole reprezentujuce jednotlive prvky radu.
    int first;       // Index prveho prvku radu v poli items.
    int count;       // Pocet prvkov v rade. 
};

/* Inicializuje prazdny rad */
void init(queue &q) {
    q.items = new dataType[maxN];
    q.first = 0;
    q.count = 0;
}

/* Zisti, ci je rad prazdny */
bool isEmpty(queue &q) {
    return q.count == 0;
}

/* Prida prvok item na koniec radu */
void enqueue(queue &q, dataType item) {
    assert(q.count < maxN);
    int index = (q.first + q.count) % maxN;
    q.items[index] = item;
    q.count++;
} 

/* Odoberie prvok zo zaciatku radu a vrati jeho hodnotu */
dataType dequeue(queue &q) {
    assert(!isEmpty(q));
    dataType result = q.items[q.first];
    q.first = (q.first + 1) % maxN;
    q.count--;
    return result;
}

/* Vrati prvok zo zaciatku radu, ale necha ho v rade */
dataType peek(queue &q) {
    assert(!isEmpty(q));
    return q.items[q.first];
}         

/* Uvolni pamat */
void destroy(queue &q) {
    delete[] q.items;
}

Zásobník pomocou spájaného zoznamu

Zásobník teraz interpretujeme pomocou spájaného zoznamu. Narozdiel od implementácie pomocou poľa bude výhodnejšie uchovávať vrch zásobníka ako prvý prvok zoznamu (pri jednosmerne spájaných zoznamoch je totiž jednoduchšie vkladať a odoberať prvky na jeho začiatku).

Výhoda tohto prístupu oproti implementácii pomocou poľa bude spočívať predovšetkým v tom, že maximálny počet prvkov v zásobníku už nebude obmedzený konštantou maxN. Podobný efekt síce možno docieliť použitím dynamického poľa, jeho realokácia je však časovo neefektívna.

#include <cassert>

// ...

struct node {
    dataType data;
    node *next;
};

struct stack {
    node *top; // Smernik na vrch zasobnika (zaciatok spajaneho zoznamu). Ak je zasobnik prazdny, ma hodnotu NULL.
};

/* Inicializuje prazdny zasobnik */
void init(stack &s) {
    s.top = NULL;
}

/* Zisti, ci je zasobnik prazdny */
bool isEmpty(stack &s) {
    return s.top == NULL;
}

/* Prida prvok item na vrch zasobnika */
void push(stack &s, dataType item) {
    node *tmp = new node;
    tmp->data = item;
    tmp->next = s.top;
    s.top = tmp;  
} 

/* Odoberie prvok z vrchu zasobnika a vrati jeho hodnotu */
dataType pop(stack &s) {
    assert(!isEmpty(s));
    dataType result = s.top->data;
    node *tmp = s.top->next;
    delete s.top;
    s.top = tmp;
    return result;
}

/* Vrati prvok na vrchu zasobnika, ale necha ho v zasobniku */          
dataType peek(stack &s) {
    assert(!isEmpty(s));
    return s.top->data;
}

/* Uvolni pamat */
void destroy(stack &s) {
    while (!isEmpty(s)) {
        pop(s);
    }
}

Rad pomocou spájaného zoznamu

Pri implementácii radu pomocou spájaného zoznamu rozšírime spájané zoznamy zo 14. prednášky o smerník last na posledný prvok zoznamu. Bude tak možné jednoducho vkladať prvky na koniec zoznamu, ako aj odoberať prvky zo začiatku zoznamu.

Výhodou oproti implementácii radu pomocou poľa bude, podobne ako pri zásobníkoch, eliminácia obmedzenia na maximálny počet prvkov v rade.

#include <cassert>

// ...

struct node {
    dataType data;
    node *next;
};

struct queue {
    node *first; // Smernik na prvy prvok radu (spajaneho zoznamu). Ak je rad prazdny, ma hodnotu NULL.
    node *last;  // Smernik na posledny prvok radu (spajaneho zoznamu). Ak je rad prazdny, ma hodnotu NULL.
};

/* Inicializuje prazdny rad */
void init(queue &q) {
    q.first = NULL;
    q.last = NULL;
}

/* Zisti, ci je rad prazdny */
bool isEmpty(queue &q) {
    return q.first == NULL;
}

/* Prida prvok item na koniec radu */
void enqueue(queue &q, dataType item) {
    node *tmp = new node;
    tmp->data = item;
    tmp->next = NULL;
    if (isEmpty(q)) {
        q.first = tmp;
        q.last = tmp;
    } else {
        q.last->next = tmp;
        q.last = tmp;
    }
} 

/* Odoberie prvok zo zaciatku radu a vrati jeho hodnotu */
dataType dequeue(queue &q) {
    assert(!isEmpty(q));
    dataType result = q.first->data;
    node *tmp = q.first->next;
    delete q.first;
    if (tmp == NULL) {
        q.first = NULL; 
        q.last = NULL;
    } else {
        q.first = tmp;
    } 
    return result;
}

/* Vrati prvok zo zaciatku radu, ale necha ho v rade */
dataType peek(queue &q) {
    assert(!isEmpty(q));
    return q.first->data;
}         

/* Uvolni pamat */
void destroy(queue &q) {
    while (!isEmpty(q)) {
        dequeue(q);
    }
}

Použitie zásobníka a radu

Zásobník aj rad často uchovávajú dáta určené na spracovanie, zoznamy úloh, atď. Rad sa zvyčajne používa v prípadoch, keď je žiadúce zachovať ich poradie. Typicky môže ísť o situácie, keď jeden proces generuje úlohy spracúvané iným procesom, napríklad:

• Textový procesor pripravuje strany na tlač a vkladá ich do radu, z ktorého ich tlačiareň (resp. jej ovládač) postupne vyberá.
• Sekvenčne vykonávané výpočtové úlohy čakajú v rade na spustenie.
• Zákazníci čakajú na zákazníckej linke na voľného operátora.
• Pasažieri na standby čakajú na voľné miesto v lietadle.

Zásobník sa, ako o niečo implementačne jednoduchší koncept, zvyčajne používa v situáciách, keď na poradí spracúvania nezáleží, alebo keď je žiadúce vstupné poradie obrátiť. Najvýznamnejší príklad situácie druhého typu je nasledujúci:

• Operačný systém ukladá lokálne premenné volaných funkcií na tzv. zásobníku volaní (angl. call stack), čo umožňuje používanie rekurzie.
• Rekurzívne programy sa dajú prepísať na nerekurzívne pomocou „ručne vytvoreného” zásobníka (na budúcej prednáške si ako príklad ukážeme nerekurzívnu verziu triedenia Quick Sort).

Príklad: kontrola uzátvorkovania

Ako jednoduchý príklad na použitie zásobníka uvažujme nasledujúcu situáciu: na vstupe je daný reťazec pozostávajúci (okrem prípadných ďalších znakov, ktoré možno ignorovať) zo zátvoriek (,),[,],{,}. Úlohou je zistiť, či je tento reťazec dobre uzátvorkovaný. To znamená, že:

• Pre každú uzatváraciu zátvorku musí byť posledná dosiaľ neuzavretá otváracia zátvorka rovnakého typu, pričom musí existovať aspoň jedna dosiaľ neuzavretá zátvorka.
• Každá otváracia zátvorka musí byť niekedy neskôr uzavretá.

Príklady očakávaného vstupu a výstupu:

()
Retazec je dobre uzatvorkovany

nejaky text bez zatvoriek
Retazec je dobre uzatvorkovany

[((({}[])[]))]()
Retazec je dobre uzatvorkovany

[[#))
Retazec nie je dobre uzatvorkovany

())(
Retazec nie je dobre uzatvorkovany

((
Retazec nie je dobre uzatvorkovany

((cokolvek
Retazec nie je dobre uzatvorkovany

Túto úlohu rieši nasledujúci program, ktorý postupne prechádza cez vstupný reťazec, pričom pre každú otváraciu zátvorku si na zásobník pridá uzatváraciu zátvorku rovnakého typu. Ak narazí na uzatváraciu zátvorku, výraz môže byť dobre uzátvorkovaný len v prípade, že je na zásobníku aspoň jedna zátvorka, pričom zátvorka na vrchu zásobníka sa zhoduje so zátvorkou na vstupe. V prípade úspešného prechodu cez celý vstup je reťazec dobre uzátvorkovaný práve vtedy, keď na zásobníku nezostala žiadna zátvorka.

#include <iostream>
#include <cassert>
using namespace std;

typedef char dataType;

/* Sem pride definicia struktury stack a vsetkych potrebnych funkcii. */

int main(void) {
    char vyraz[100];
    cin.getline(vyraz, 100);
    
    stack s;
    init(s);
    
    bool dobre = true;
    
    for (int i = 0; vyraz[i] != 0; i++) {
        switch (vyraz[i]) {
            case '(':
                push(s, ')');
                break;
            case '[':
                push(s, ']');
                break;
            case '{':
                push(s, '}');
                break;
            case ')':
            case ']':
            case '}':
                if (isEmpty(s)) {
                    dobre = false;
                } else {
                    char c = pop(s);
                    if (c != vyraz[i]) {
                        dobre = false;
                    }
                }
                break;
        }
    }
    
    dobre = dobre && isEmpty(s);
        
    destroy(s);
    
    if (dobre) {
        cout << "Retazec je dobre uzatvorkovany." << endl;
    } else {
        cout << "Retazec nie je dobre uzatvorkovany." << endl;
    }
    
    return 0;
}

Cvičenie: Prepíšte program na kontrolu zátvoriek do rekurzívnej podoby. Použite pritom iba premenné typu char; špeciálne nepoužívajte žiadne polia. Reťazec načítavajte pomocou funkcií getc a ungetc. Môžete predpokladať, že je ukončený koncom riadku.