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