Programovanie (1) v C/C++
1-INF-127, ZS 2024/25

Úvod · Pravidlá · Prednášky · Softvér · Testovač
· Kontaktujte nás pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Prosíme študentov, aby si pravidelne čítali e-maily na @uniba.sk adrese alebo aby si tieto emaily preposielali na adresu, ktorú pravidelne čítajú.


Prednáška 17

Z Programovanie
Skočit na navigaci Skočit na vyhledávání

Oznamy

  • Budúci týždeň budú cvičenia v utorok a v piatok iba online, nebude rozcvička, iba príklady, ktoré môžete riešiť do ďalšieho utorka
  • Na testovači pribudlo zadanie tretej (a poslednej) domácej úlohy s odovzdaním do 6. decembra, 22:00.
  • Tento piatok sa ešte dá prísť na cvičenia osobne, v prípade záujmu si dajte pozor, aby ste boli zapísaní v tabuľke
  • Blíži sa semestrálny test
    • Treba z neho získať aspoň 50% bodov, inak známka Fx
    • Opravný termín bude v januári (iba jeden)
    • Pôvodne bola písomka ohlásená na stredu 8.12. večer, ale presúvame ju na piatok 10.12. počas doplnkových cvičení o 11:30
    • Ak máte s týmto presunom problém, dajte nám vedieť dnes alebo zajtra
    • Večerné termíny bývajú pre študentov náročné
    • Ak bude umožnená prezenčná výučba, písomka bude na fakukulte, inak online

Abstraktný dátový typ

Abstraktný dátový typ (ADT) je abstrakcia dátovej štruktúry nezávislá od samotnej implementácie.

  • Býva zadaný pomocou množiny operácií (hlavičiek funkcií), ktoré poskytuje
  • Jeden abstraktný dátový typ môže byť implementovaný pomocou viacerých dátových štruktúr.

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).

Videli sme implementácie (pre jednoduchosť bez operácie remove) pomocou neutriedeného poľa, utriedeného poľa, spájaného zoznamu, priameho adresovania a hašovania.

Podobne by sa za ADT dalo považovať dynamické pole s operáciami add, length, get a set.

Výhodou abstraktných dátových typov je 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 sú dva nové abstraktné dátové typy.

Rad a zásobník

  • Zásobník (angl. stack) a rad alebo front (angl. queue) sú jednoduché abstraktné dátové typy, ktoré udržiavajú postupnosť nejakých prvkov.
  • Typicky ide o úlohy alebo dáta čakajúce na spracovanie.
  • Rad aj zásobník poskytujú funkciu, ktorá vkladá nový prvok.
  • Druhou základnou funkciou je výber jedného prvku, pričom rad sa od zásobníka líši tým, ktorý prvok sa vyberá.

Prvky radu a zásobníka 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.
  • Taká istá úprava by sa dala spraviť aj pri ADT množina a dynamické pole.


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.

Abstraktný dátový typ pre rad poskytuje 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ý.
  • Môžeme si ho predstaviť ako stĺpec tanierov, kde umyté taniere dávame na vrch stĺpca a tiež z vrchu aj berieme taniere na použitie.
  • 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 poskytuje tieto operácie (stack je názov štruktúry reprezentujúcej zásobník):

/* 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>

typedef int dataType;
const int maxN = 1000;

struct stack {
    // Alokovane pole prvkov zasobnika.
    dataType *items; 
    // Index vrchu zasobnika v poli items, -1 ak prazdny
    int top;         
};

/* 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 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 budeme interpretovať ako nasledujúce za posledným prvkom poľa.
#include <cassert>

typedef int dataType;

const int maxN = 1000;

struct queue {
    dataType *items; // Alokovane pole obsahujuce 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.
  • Na rozdiel 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 je v tom, že maximálny počet prvkov v zásobníku nebude obmedzený konštantou maxN. Podobný efekt je možné docieliť aj dynamického poľa, tam však dochádza k realokácii.
#include <cassert>

typedef int dataType;

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é efektívne vkladať prvky na koniec zoznamu, ako aj odoberať prvky zo začiatku zoznamu.
  • Výhodou oproti implementácii radu pomocou poľa je, podobne ako pri zásobníkoch, eliminácia obmedzenia na maximálny počet prvkov v rade.
#include <cassert>

typedef int dataType;

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

struct queue {
    // Smernik na prvy uzol. Ak je rad prazdny, ma hodnotu NULL.
    node *first; 
    // Smernik na posledny uzol. Ak je rad prazdny, ma hodnotu NULL.
    node *last;  
};

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