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 21

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

Oznamy

Plán prednášok a cvičení na zvyšok semestra:

  • Dnes informácia o skúškach, detaily skúšky z programovania, pokračujeme v učive o stromoch
  • Tento piatok 10.12. cez cvičenia semestrálny test.
  • V pondelok 13.12. bude bežná prednáška, pokračujú stromy.
  • V stredu 15.12. dokončíme stromy, potom nepovinná prednáška o nepreberaných črtách jazykov C a C++ (táto nepovinná časť učiva nebude vyžadovaná na skúške, ale môžete ju použiť).
  • V utorok 14.12. v rámci cvičení tréning na skúšku.
    • Už dnes po prednáške sa na testovači objavia tréningové príklady na skúšku. Za niektoré budete môcť získať bonusový bod, ak ich vyriešite do 12.1. (ako tréning sa dajú riešiť aj neskôr). V utorok na cvičeniach pribudne ešte jeden tréningový príklad za 4 body. Ak prídete na cvičenia a odovzdáte na konci aspoň rozumne rozrobenú verziu programu, získate jeden bonusový bod, aj keď ho nestihnete dokončiť.
  • V piatok 17.12. od 12:00 predtermín skúšky, doplnkové cvičenia nebudú

Sylaby predmetu

Základy

Konštrukcie jazyka C

  • premenné typov int, double, char, bool, konverzie medzi nimi
  • podmienky (if, else, switch), cykly (for, while)
  • funkcie (a parametre funkcií - odovzdávanie hodnotou, referenciou, smerníkom)
void f1(int x){}                                 //hodnotou
void f2(int &x){}                                //referenciou
void f3(int* x){}                                //smerníkom
void f(int a[], int n){}                         //polia bez & (ostanú zmeny)
void kresli(Turtle &t){}                         //korytnačky, SVGdraw a pod. s &

Polia, reťazce (char[])

int A[4]={3, 6, 8, 10}; 
int B[4];               
B[0]=3; B[1]=6; B[2]=8; B[3]=10;

char C[100] = "pes";
char D[100] = {'p', 'e', 's', 0};
  • funkcie strlen, strcpy, strcmp, strcat

Súbory, spracovanie vstupu

  • cin, cout alebo printf, scanf
  • fopen, fclose, feof
  • fprintf, fscanf
  • getc, putc, ungetc, fgets, fputs
  • spracovanie súboru po znakoch, po riadkoch, po číslach alebo slovách

Smerníky, dynamicky alokovaná pamäť, dvojrozmerné polia

int i;    // „klasická“ celočíselná premenná
int *p;   // ukazovateľ na celočíselnú premennú

p = &i;         // spravne
p = &(i + 3);   // zle i+3 nie je premenna
p = &15;        // zle konstanta nema adresu
i = *p;         // spravne ak p bol inicializovany

int * cislo = new int;  // alokovanie jednej premennej
*cislo = 50;
..
delete cislo;

int a[4];
int *b = a;  // a,b su teraz takmer rovnocenne premenne 

int *A = new int[n]; // alokovanie 1D pola danej dlzky
..
delete[] A;

int **a;       // alokovanie 2D matice
a = new int *[n];
for (int i = 0; i < n; i++) a[i] = new int[m];
..
for (int i = 0; i < n; i++) delete[] a[i];
delete[] a;

Abstraktné dátové typy

Abstraktný dátový typ dynamické pole (rastúce pole)

  • operácie init, add, get, set, length

Abstraktný dátový typ dynamická množina (set)

  • operácie init, find, insert, remove
  • implementácie pomocou
    • neutriedeného poľa
    • utriedeného poľa
    • spájaných zoznamov
    • binárnych vyhľadávacích stromov
    • hašovacej tabuľky
    • lexikografického stromu (ak kľúč je reťazec)

Abstraktné dátové typy rad a zásobník

  • operácie pre rad (frontu, queue): init, isEmpty, enqueue, dequeue, peek
  • operácie pre zásobník (stack): init, isEmpty, push, pop
  • implementácie: v poli alebo v spájanom zozname
  • využitie: ukladanie dát na spracovanie, odstránenie rekurzie
  • kontrola zátvoriek a vyhodnocovanie výrazov pomocou zásobníka


Dátové štruktúry

PROG-list.png

Spájané zoznamy

struct node {
    int data;
    item* next;
};
struct linkedList {
    item* first;
};
void insertFirst(linkedList &z, int d){
    /* do zoznamu z vlozi na zaciatok novy prvok s datami d */
    item* p = new item;   // vytvoríme nový prvok
    p->data = d;          // naplníme dáta
    p->next = z.first;    // prvok bude prvým prvkom zoznamu (ukazuje na doterajší začiatok)
    z.first = p;          // tento prvok je novým začiatkom
}
Strom pre výraz (65 – 3*5)/(2 + 3)

Binárne stromy

struct node {
    /* vrchol stromu  */
    dataType data;
    node * left;  /* lavy syn */
    node * right; /* pravy syn */
};

node * createNode(dataType data, node *left, node *right) {
    node *v = new node;
    v->data = data;
    v->left = left;
    v->right = right;
    return v;
}
  • prehľadávanie inorder, preorder, postorder
  • použitie na uloženie aritmetických výrazov
P22-BST.png

Binárne vyhľadávacie stromy

  • vrcholy vľavo od koreňa menší kľúč, vpravo od koreňa väčší
  • insert, find, remove v čase závisiacom od hĺbky stromu
Trie.jpg

Lexikografické stromy

  • ukladajú množinu reťazcov
  • nie sú binárne: vrchol môže mať veľa synov
  • insert, find, remove v čase závisiacom od dĺžky kľúča, ale nie od počtu kľúčov, ktoré už sú v strome
struct node {
    /* vrchol lexikografickeho stromu  */
    char data; // pismeno ulozene v tomto vrchole
    bool isWord; // je tento vrchol koncom slova?
    node* next[Abeceda]; // pole smernikov na deti    
};


Hašovanie

  • hašovacia tabuľka veľkosti m
  • kľúč k premietneme nejakou funkciou na index v poli (0,...,m-1}
  • každé políčko hašovacej tabuľky spájaný zoznam prvkov, ktoré sa tam zahašovali
  • v ideálnom prípade sa prvky rozhodia pomerne rovnomerne, zoznamy krátke, rýchle hľadanie, vkladenie, mazanie
  • v najhoršom prípade všetky prvky v jednom zozname, pomalé hľadanie a mazanie
int hash(int k, int m){ // veľmi jednoduchá hašovacia funkcia, v praxi väčšinou zložitejšie
    return abs(k) % m;
}
struct node {
    int item;
    node* next;
};

struct set {
    node** data;
    int m;
};

Algoritmy

Rekurzia

  • Rekurzívne funkcie
  • Vykresľovanie fraktálov
  • Prehľadávanie s návratom (backtracking)
  • Vyfarbovanie
  • Prehľadávanie stromov

Triedenia

  • nerekurzívne: Bubblesort, Selectionsort, Insertsort
  • rekurzívne: Mergesort, Quicksort
  • súvisiace algoritmy: binárne vyhľadávanie

Matematické úlohy

  • Euklidov algoritmus, Eratostenovo sito
  • Práca s aritmetickými výrazmi: vyhodnocovanie postfixovej formy, prevod z infixovej do postfixovej, reprezentácia vo forme stromu

Binárne vyhľadávacie stromy

Príklad binárneho vyhľadávacieho stromu.

Stromy sa v informatike často používajú. Ďalším príkladom sú binárne vyhľadávacie stromy, ktoré slúžia na ukladanie množiny prvkov. Prvky množiny teda nemáme v poli, ani v spájanom zozname, ale vo vrcholoch binárneho stromu.

  • V binárnom vyhľadávacom strome má každý vrchol 0,1 alebo 2 deti
  • V každom vrchole máme položku s dátami (pre jednoduchosť typu int)
  • Pre každý vrchol v stromu platí:
    • Každý vrchol v ľavom podstrome v má hodnotu data menšiu ako vrchol v
    • Každý vrchol v pravom podstrome v má hodnotu data väčšiu ako vrchol v
  • Z toho vyplýva, že ak vypíšeme strom v inorder poradí, dostaneme prvky usporiadané
  • Pre danú množinu kľúčov existuje veľa vyhľadávacích stromov


Cvičenie: nájdite všetky binárne vyhľadávacie stromy pozostávajúce z troch uzlov s kľúčmi 1, 2, 3.

Definícia dátových štruktúr

Vrchol typu node

  • Položka data typu int
  • Smerník na ľavé a pravé dieťa
  • Na niektoré úlohy (napr. mazanie vrcholu) sa hodí aj smerník na rodiča (ten má hodnotu NULL v koreni)

Celý strom je štruktúra obsahujúca iba smerník na koreň

  • Pre prázdny strom je to NULL.
struct node {
    /* vrchol binárneho vyhľadávacieho stromu  */
    int data;       /* hodnota */
    node * parent;  /* rodič vrchola, NULL v koreni */
    node * left;    /* ľavé dieťa, NULL ak neexistuje */
    node * right;   /* pravé dieťa, NULL ak neexistuje */
};

/* Samotná štruktúra binárneho vyhľadávacieho stromu (obal pre používateľa). */
struct binarySearchTree {
    node *root;  /* koreň stromu, NULL pre prázdny strom */
};

Inicializácia prázdneho binárneho vyhľadávacieho stromu

/** Funkcia inicializuje prázdny binárny vyhľadávací strom */
void bstInit(binarySearchTree &t) {    
    t.root = NULL;
}

Likvidácia binárneho vyhľadávacieho stromu

Likvidáciu podstromu zakoreneného v danom uzle root realizujeme funkciou destroy, obdobne ako pri všeobecných binárnych stromoch. Používateľovi navyše dáme k dispozícii aj funkciu bstDestroy, ktorá zlikviduje binárny vyhľadávací strom t tak, že zavolá funkciu destroy na jeho koreň.

/* Uvolni pamat pre podstrom s korenom *root. */
void destroy(node *root) {
    if (root != NULL) {
        destroy(root->left);
        destroy(root->right);
        delete root;
    }
}

/* Zlikviduje strom t (uvolni pamat). */
void bstDestroy(binarySearchTree &t) {
    destroy(t.root);
}

Hľadanie v binárnom vyhľadávacom strome

Funkcia findNode v podstrome s koreňom root hľadá uzol, ktorého položka dáta obsahuje hľadaný kľúč key. Vráti takýto uzol alebo NULL ak neexistuje

  • Najskôr porovná hľadaný kľúč s dátami v koreni
    • Ak sa rovnajú, končíme (našli sme, čo hľadáme)
    • Ak je hľadaná hodnota menšia ako dáta v koreni, musí byť v ľavom podstrome, ak je väčšia v pravom
  • V príslušnom podstrome sa rozhodujeme podľa tých istých pravidiel
  • Keď narazíme na prázdny podstrom, dáta sa v strome nenachádzajú
  • Dá sa zapísať rekurzívne alebo cyklom, lebo vždy ideme iba do jedného podstromu

Funkcia bstFind zavolá funkciu findNode pre koreň daného binárneho vyhľadávacieho stromu t a pomocou nej zistí, či tento strom obsahuje uzol s kľúčom key.

/* Ak v strome s korenom root existuje uzol s klucom key, 
 * vrati ho na vystupe. Inak vrati NULL. */
node * findNode(node *root, int key) {
    node * v = root;
    while (v != NULL && v->data != key) {
        if (key < v->data) {
            v = v->left;
        } else {
            v = v->right;
        }
    }
    return v;
}

/** Rekurzívna verzia */
node *findNodeR(node *root, int key) {
    if (root == NULL || key == root->data) {
        return root;
    } else if (key < root->data) {
        return findNodeR(root->left, key);
    } else {  // key > root->data
        return findNodeR(root->right, key);
    }
}

/* Zisti, ci strom t obsahuje uzol s klucom key. */
bool bstFind(binarySearchTree &t, int key) {
    return findNode(t.root, key) != NULL;
}

Čas výpočtu je v najhoršom prípade úmerný výške stromu.