====== Příklady ====== Příklady naleznete v GIT repository http://gitlab.fjfi.cvut.cz/culikzde/zalg Nejjednodušší přístup k zdrojovým souborům na zmíněné webové stránce je tlačítko "Download", schované vedle tlačítka "Clone". (A nemusíte se zabývat následujícím odkazem popisujícím přistup k GIT.) Stručný návod pro přístup k GIT [[zalg::git|git]] Přehled některých vývojových prostředí [[zalg::ide|ide]] Videa o algoritmech [[zalg::video|video]] ====== Binární strom ====== [[zalg::strom_add|Vkládání prvku do stromu]] [[zalg::strom_del|Vymazání prvku ze stromu]] ====== Osm dam ===== [[zalg::dama|Osm dam]] ====== Hledání nejkratší cesty jezdcem ====== [[zalg::jezdec| Hledání nejkratší cesty jezdcem]] ====== Heap sort ====== [[zalg::heapsort|Heap sort]] http://www.youtube.com/watch?v=HqPJF2L5h9U ====== Quick sort ====== [[zalg::quicksort|quick sort]] QuickSort http://www.youtube.com/watch?v=7h1s2SojIRw QuickSort Analysis http://www.youtube.com/watch?v=-qOVVRIZzao Jenny's lectures, QuickSort https://www.youtube.com/watch?v=QN9hnmAgmOc ====== Vyvážené stromy ====== [[zalg:avl|AVL tree]] AVL tree http://www.youtube.com/watch?v=jDM6_TnYIqE \\ Jenny's lectures, AVL tree http://www.youtube.com/watch?v=YWqla0UX-38 ====== B-stromy ====== [[zalg:btree|B-tree]] ====== Hanojské věže ====== [[zalg:veze|Hanojské věže]] ====== Lexikografické třídění ====== [[zalg:lexi|Lexikografické třídění]] Příhrádkové třídění - skripta 5.4.1 Lexikografické třídění - skripta 5.4.2 * Budeme třídit řetězce dlouhé **D** znaků * Každý znak může nabývat **K** hodnot, vytvoříme **K** příhrádek * V našem programu budeme třídit jen řetězce složené z číslic, stačilo by 10 příhrádek * Pro třídění řetězců obsahující libolovné znaky použijeme 256 příhrádek * Budeme třídit **N** řetězců, v našem programu N použijeme jen při generování náhodných vstupních řetězců ===== Jednotlivé řetězce ===== Jednotlivé řetězce budeme ukládat do datové struktury **Item**. \\ V poli **key** budou uloženo **D** osmibitových znaků a na konec přidáme nulový znak (jen kvůli tisku řetězců). Řetězce propojíme ukazatelem **next** do jednosměrného seznamu.


const int D = 20; // pocet pismen ve slove

struct Item
{
    char key [D+1]; // znak 0 na konci
    Item * next;
};

===== Jedna příhrádka ===== Jednu příhrádku budeme reprezentovat strukturou **List**. Příhrádka bude skladovat posloupnost řetězců. Bude obsahovat ukazatele **first** a **last** na první a poslední řetězec. Díky **last** bude přidávání na konec seznamu jednoduchou operací ... O(1).


struct List
{
    Item * first;
    Item * last;
};

===== Pole příhrádek ===== **K** příhrádek budeme mít uloženo v poli **tab**. Přístup i-té příhrádkce bude opět jednoduchá operace.


List tab [K];

=== Vstupní posloupnost řetězců === Pro vstupní posloupnost řetězců použijeme stený typ **List** jako pro jednotlivé příhrádky. Proměnná **inp** bude obsahovat řetězce které máme třídit. * Řetězce rozházíme podle r-tého znaku do příhrádek. * A z příhrádek sesypeme zpět do proměnné **inp**. * To budeme opakovat pro r = D-1, D-2, ...., 2, 1, 0. (znaky v poli **key** indexujeme od nuly) Nakonec v proměnné **inp** bude výsledná setříděná posloupnost řetězců


List inp;

===== Vyprázdnění příhrádky ===== Funkce **init** má parametr předávaný odkazem (**&**), skutešný parametr se bude měnit. \\ Nastavíme ukazatele **first** a **last** na nulov0 ukazatele, to odpovídá prázdné příhrádce.


void init (List & a)
{
    a.first = nullptr;
    a.last = nullptr;
}

===== Přidání prvku do příhrádky ===== Funkce **add** přidá nový řetězec zadaný ukazatelem **p** na konec seznamu **a**. //Stabilita třídění:// pokud na vstupu budou dva řetězce, které padnou do stejné příhrádky, \\ zachovají si svoje pořadí i v příhrádce a nakonec i ve výstupní posloupnosti.


void add (List & a, Item * p)
{
    p->next = nullptr;
    if (a.first == nullptr)
        a.first = p;
    else
        a.last->next = p;
    a.last = p;
}

===== Příhrádkové třídění podle r-tého znaku ===== Nejprve všechny příhrádky vyprázdníme (vynulujeme **first** a **last**, tím zapomeneme ukazatele na staré hodnoty). Potom procházíme vstupní posloupnost. \\ Do proměnné **p** dáme ukazatel na první řetězec. \\ Vyzvedneme hodnotu r-tého znaku v našem řetězci a uložíme do proměnné **inx**. \\ Tím jsem získali číslo příhrádky, do které řetězec patří. \\ // Zde používáme pro číslo příhrádky ascii hodnotu znaku//, \\ // pokud bychom měli jen deset příhrádek pro číslice, museli bychom do inx uložit číslo od nuly do devíti.// Přidáme prvek **p** do příhrádky číslo **inx**. \\ To ale nastaví p->next na nulový ukazatel (Prvek **p** bude na konci seznamu/příhrádky). \\ Ukazatel na následníka si uložíme do proměnná **t**, dříve než o něj přideme. Cyklus **while** opakujeme pro všechny řetězce.


void sort (int r) // tridime podle r-teho pismene
{
    for (int inx = 0; inx < K; inx++)
        init (tab[inx]);

    Item * p = inp.first;
    while (p != nullptr)
    {
        Item * t = p->next; // zapamatovat naslednika pred odpojenim
        int inx = p->key[r]; // cislo prihradky
        add (tab[inx], p);
        p = t;
    }

Seznam vstupních hodnot již nepotřebujeme. \\ V proměnné **inp** nastavíme first i last na nulové uzazatele \\ a **inp** budete skladovat výstupní posloupnost. Ve **for** cyklu projdeme všechny příhrádky a jejich obsah připojíme na konec **inp**. Jako komentář je zde naznačen postupné procházení příhrádky a přidávání na konec **inp**. \\ Proměnné **p** a **t** by v tomto případě existolaly jen vrámci **{ }**, kde byly deklarovány. Funkce **link** připojí obsah příhrádky k **inp** rychleji. \\ //Ale složitost to stejně neovlivní.//


    init (inp);
    for (int inx = 0; inx < K; inx++)
    {
        link (inp, tab[inx]);
        /*
        Item * p = tab[inx].first;
        while (p != nullptr)
        {
            Item * t = p->next;
            add (inp, p);
            p = t;
        }
        */
    }

===== Celá funkce sort =====


void sort (int r) // tridime podle r-teho pismene
{
    for (int inx = 0; inx < K; inx++)
        init (tab[inx]);

    Item * p = inp.first;
    while (p != nullptr)
    {
        Item * t = p->next; // zapamatovat naslednika pred odpojenim
        int inx = p->key[r]; // cislo prihradky
        add (tab[inx], p);
        p = t;
    }

    init (inp);
    for (int inx = 0; inx < K; inx++)
    {
        link (inp, tab[inx]);
        /*
        Item * p = tab[inx].first;
        while (p != nullptr)
        {
            Item * t = p->next;
            add (inp, p);
            p = t;
        }
        */
    }
}

===== Spojování seznamů ===== Funkce **link (a, b)** připojí na konec seznamu **a** seznam **b**. Pokud je **b** prázdný nemáme co dělat. Pokud je **a** prázdný stavá se **b.first** prvním prvkem seznamu **a**. \\ V opačném případě propojíme poslední prvek původního seznamu **a** se prvním prvek **b**. Poslední prvek **b** se stává poslední prvkem **a**.


void link (List & a, List & b) 
{
    if (b.first != nullptr)
    {
        if (a.first == nullptr)
            a.first = b.first;
        else
            a.last->next = b.first;
        a.last = b.last;
    }
}

===== Lexikografické třídění ===== Celé lexikografické třídění je pouze několik příhrádkových třídění. Funkce **sort** vstup získává ze seznamu **inp** a do stejné proměné uloží svůj výstup, // který je vstupem pro další **sort**, // nakonec v **inp** nalezneme setříděný výsledek. Třídíme postupně podle posledního písmene (s indexem **D-1**) \\ až nakonec podle podle prvního písmene (s indexem **0**). //Pokud třídíme řetězce tvořené číslicemi.// \\ Tříděním podle posledního písmene na začátek dostaneme řětězce končící **0**, na konci budou řětězce končící **9**. Závěrečné třídění podle prvního písmene (s indexem 0, v případě čísel: číslice s největší váhou) \\ umístí na zacčátek posloupnosti řětězce začínající **0**, na konci budou řětězce začínající **9**. \\ Stabilita třídění zajistí, že řetězce zůstanou setříděné podle nižžších řádů.


int main ()
{
    /* ... */

    for (int r = D-1; r >= 0; r--)
       sort (r);

    /* ... */
}

===== Složitost ===== Pokud třídíme **N** řetězců musíme **D**-krát rozházet prvky do **K** příhrádek, \\ Práce s jedním prvkem je **O(1)**, neboť nic nehledáme a provádíme stále stejný počet instrukcí. \\ **K** a **D** jsou konstanty, tak výsledná složitost je **O(N)**. Ale je to za cenu, že jsem si pevně stanovili počet příhrádek a délku řetězců. ===== Vyváření řetězců ===== Funkce **create (int c)** uloží celé číslo **c** do nově vytvořeného prvku typu **Item**. S index **i** postupujeme od konce řetězce (**D-1**). \\ Zbytek po dělení čísla **c** deseti přičteme k ascii kódu číslice nula ( nula v jednoducých uvozovkách pro znakové konstanty, **'0'** ) \\ A číslici uložíme jako i-té písmeno. \\ Číslo **c** vydělíme deseti (celočíselné dělění zbytek zahodí) a pokračujeme s vyššími řády. Na konec řetězce přidáme nulový znakem (znak s vniřním kódem nula, **0** bez uvozovek, tj. číslo nula ). Typ **int** bývá 32-bitový, tak získáme jen deset číslic a ve vyšších řádech budou jen nuly.


Item * create (int c)
{
    Item * p = new Item;
    for (int i = D - 1; i >= 0; i--)
    {
        p->key[i] = '0' + c % 10;
        c = c / 10;
    }
    p->key[D] = 0; // znak nula na konci
    return p;
}

===== Funkce main ==== * Vygenerujeme N řetězců * Spustíme třídění * Zkontrolujeme pořadí Při tisku a porovnávání pomocí **strcmp** musí být řetězce ukončeny nulovým znakem.


int main ()
{
    init (inp);
    srand (time(NULL));
    for (int i = 0; i < N; i++)
        add (inp, create (rand() % 10000));

    for (int r = D-1; r >= 0; r--)
       sort(r);

    bool ok = true;
    Item * p = inp.first;
    while (p != nullptr)
    {
        cout << p->key;
        Item * t = p->next;
        if (t != nullptr && strcmp (t->key , p->key) < 0) 
           { ok = false; cout << " CHYBA"; }
        cout << endl;
        p = t;
    }
    if (ok)
       cout << "O.K." << endl; 
}

===== Celý program =====


#include 
#include 
#include 
using namespace std;

const int N = 20;
const int D = 20; // pocet pismen ve slove
const int K = 256; // pocet prihradek

struct Item
{
    char key [D+1]; // znak 0 na konci
    Item * next;
};

struct List
{
    Item * first;
    Item * last;
};

List inp; // vstup a vystup

List tab [K]; // pole prihradek

void init (List & a)
{
    a.first = nullptr;
    a.last = nullptr;
}

void add (List & a, Item * p)
{
    p->next = nullptr;
    if (a.first == nullptr)
        a.first = p;
    else
        a.last->next = p;
    a.last = p;
}

void link (List & a, List & b) // pridat b na konec a
{
    if (b.first != nullptr)
    {
        if (a.first == nullptr)
            a.first = b.first;
        else
            a.last->next = b.first;
        a.last = b.last;
    }
}

Item * create (int c)
{
    Item * p = new Item;
    for (int i = D - 1; i >= 0; i--)
    {
        p->key[i] = '0' + c % 10;
        c = c / 10;
    }
    p->key[D] = 0; // znak nula na konci
    return p;
}

void sort (int r) // tridime podle r-teho pismene
{
    for (int inx = 0; inx < K; inx++)
        init (tab[inx]);

    Item * p = inp.first;
    while (p != nullptr)
    {
        Item * t = p->next; // zapamatovat naslednika pred odpojenim
        int inx = p->key[r]; // cislo prihradky
        add (tab[inx], p);
        p = t;
    }

    init (inp);
    for (int inx = 0; inx < K; inx++)
    {
        link (inp, tab[inx]);
        /*
        Item * p = tab[inx].first;
        while (p != nullptr)
        {
            Item * t = p->next;
            add(inp, p);
            p = t;
        }
        */
    }
}

int main ()
{
    init (inp);
    srand (time (nullptr));
    for (int i = 0; i < N; i++)
        add (inp, create (rand() % 10000));

    for (int r = D-1; r >= 0; r--)
       sort(r);

    bool ok = true;
    Item * p = inp.first;
    while (p != nullptr)
    {
        cout << p->key;
        Item * t = p->next;
        if (t != nullptr && strcmp (t->key , p->key) < 0) 
           { ok = false; cout << " CHYBA"; }
        cout << endl;
        p = t;
    }
    if (ok)
       cout << "O.K." << endl; 
}