DatovΘ struktury a algoritmy (5.)

Dnes se budeme prozatφm naposledy, jak bylo slφbeno v poslednφm dφlu, zab²vat t°φdicφmi algoritmy - povφme si n∞co o stabilit∞ algoritm∙ a ukß₧eme si, jak tΘto vlastnosti vyu₧φt. Nßsledovat bude algoritmus pro vyhledßvßnφ v ut°φd∞nΘm poli. A koneΦn∞ se dostaneme k prvnφ odvozenΘ datovΘ struktu°e - konkrΘtn∞ to bude zßsobnφk.

5.1. Vlastnosti t°φdicφch algoritm∙ - pokraΦovßnφ

Stabilita algoritmu urΦuje, jak algoritmus zachßzφ s t°φd∞n²mi prvky, kterΘ majφ stejnou velikost (hodnotu klφΦe podle kterΘho t°φdφme). Algoritmus nazveme stabilnφm pokud se v set°φd∞nΘm poli nachßzejφ prvky ve stejnΘm po°adφ jako v p∙vodnφm poli. Toho se dß vyu₧φt nap°. nßsledujφcφm zp∙sobem. P°edstavme si seznam lidφ, u nich₧ si uchovßvßme jmΘno a rok narozenφ. Pro vyhledßvßnφ lidφ se nßm bude hodit mφt seznam set°φd∞n² podle jmen. Pozd∞ji se vÜak m∙₧eme rozhodnout, ₧e pot°ebujeme pracovat s rokem narozenφ a bude t°eba vypsat seznam lidφ podle roku narozenφ. Samoz°ejm∞ budeme chtφt zachovat abecednφ po°adφ osob narozen²ch ve stejnΘm roce. Nenφ nic snazÜφho, ne₧-li pou₧φt stabilnφho t°φdicφho algoritmu a set°φdit jφm pole podle v∞ku. Ukß₧eme si tedy p°φklad na set°φd∞nφ pole, kterΘ bude sestßvat z instancφ objekt∙ CClovek. Pro set°φd∞nφ podle jmen pou₧ijeme algoritmus rychlΘho t°φd∞nφ (Quicksort) a pro set°φd∞nφ podle roku narozenφ pak algoritmu p°φmΘho vklßdßnφ (Insertsort). K≤d (n∞kterΘ Φßsti jsou vynechßny):

#include <iostream>

using namespace std;

class CClovek
{
    bool operator<(CClovek _pravy)
    {
        bool bNavrat = false;

        if(strcmp(m_Jmeno, _pravy.VratJmeno()) < 0)
        {
            bNavrat = true;
        }

        return bNavrat;
    }

    bool operator>(CClovek _pravy)
    {
        bool bNavrat = false;

        if(strcmp(m_Jmeno, _pravy.VratJmeno()) > 0)
        {
            bNavrat = true;
        }

        return bNavrat;
    }

    bool operator==(CClovek _pravy)
    {
        bool bNavrat = false;

        if(strcmp(m_Jmeno, _pravy.VratJmeno()) == 0)
        {
            bNavrat = true;
        }

        return bNavrat;
    }

    void Vypis()
    {
        cout << m_Jmeno << ", " << m_Rocnik << endl;
    }
};

void qsort1(CClovek *pPole, int dwLevy, int dwPravy)
{
    // ...
}

void QuickSortJmeno(CClovek *pPole, unsigned int dwVel)
{
    qsort1(pPole, 0, dwVel - 1);
}

void qsort2(CClovek *pPole, int dwLevy, int dwPravy)
{
    // ...
}

void QuickSortVek(CClovek *pPole, unsigned int dwVel)
{
    qsort2(pPole, 0, dwVel - 1);
}

void PrimeVkladani(CClovek *pPole, unsigned int dwVel)
{
    // ...
}

void VypisPole(CClovek *pPole, unsigned int dwVel)
{
    for(int i = 0; i < dwVel; i++)
    {
        pPole[i].Vypis();
    }
}

static char* Jmena[] = {"Ofelie", "Honza", "Zlatek", "Lenka", "Zuzana", "Ondra", "Petr", "Petra", "Jana", "Ema", "Michal",         "Jiri", "Karel", "Zdenek", "Martin", "Lucie", "Tereza", "Martina", "Ivana", "Lukas" };

static unsigned short Roky[] = { 1980, 1980, 1950, 1982, 1981, 1982, 1977, 1983, 1999, 1955, 1980, 1980, 1981, 1955, 1974, 1984,     1980, 1982, 1911, 1980 };

int main(int argc, char* argv[])
{
    CClovek pole[20];

    for(int i = 0; i < 20; i++)
    {
        pole[i].NastavJmeno(Jmena[i]);
        pole[i].NastavRok(Roky[i]);
    }

    cout << "Podle roku narozeni pred setridenim podle jmen: " << endl;

    PrimeVkladani(pole, 20);

    VypisPole(pole, 20);

    cout << endl << "Setrideni podle jmena: " << endl;

    QuickSortJmeno(pole, 20);

    VypisPole(pole, 20);

    // Nyni mame seznam setriden podle jmen. Pokud ho nyni setridime stabilnim algoritmem podle roku narozeni, pak
    // budeme mit setridene lidi pod jednotlivymi daty opet podle jmena

    cout << endl << "Podle roku narozeni (stabilni algoritmus) po setrideni podle jmen: " << endl;

    PrimeVkladani(pole, 20);

    VypisPole(pole, 20);

    // nyni utridime pole opet podle jmena
    QuickSortJmeno(pole, 20);

    // a zkusime nestabilni algoritmus podle veku (QuickSortVek())
    cout << endl << "Podle roku narozeni (NEstabilni algoritmus) po setrideni podle jmen: " << endl;

    QuickSortVek(pole, 20);

    VypisPole(pole, 20);

    char c;
    cin >> c;

    return 0;
}

Pro t°φdu CClovek mßme p°etφ₧eny operßtory porovnßnφ, tak₧e porovnßnφ dvou instancφ tΘto t°φdy znamenß lexikografickΘ porovnßnφ jmen. LexikografickΘ porovnßnφ je provedeno pomocφ knihovnφ funkce strcmp(), ovÜem pro ΦeÜtinu bychom si museli napsat vlastnφ (nap°. kv∙li ch). Dßle mßme dv∞ verze t°φd∞nφ pomocφ algoritmu rychlΘho t°φd∞nφ, jedna ut°φdφ pole podle jmΘna a druhß podle v∞ku. Procedura PrimeVkladani() implementuje p°φsluÜnou t°φdicφ metodu. Poslednφ je pak pomocnß procedura pro kontrolnφ v²pis pole.

My si vÜimneme p°edevÜφm dvou poslednφch v²pis∙. Prvnφ v²pis ukazuje stav po ut°φd∞nφ stabilnφm algoritmem - z∙stalo nßm zachovßno abecednφ po°adφ osob se stejn²m rokem narozenφ (ale pole muselo b²t p°edtφm set°φd∞no podle abecedy). Poslednφ v²pis pak ukazuje, co se stane pokud pou₧ijeme nestabilnφho algoritmu (Quicksort) - dojde k zp°ehßzenφ jmen.

Z algoritm∙ se kter²mi jsme se seznßmili pat°φ mezi stabilnφ:

Bublinka() - bublinkovΘ t°φd∞nφ
Bublinka2() - bublinkovΘ t°φd∞nφ s kontrolou prohozenφ
Pretres() - t°φd∞nφ p°et°ßsßnφm
PrimeVkladani() - t°φd∞nφ p°φm²m vklßdßnφm
MergeSort() - t°φd∞nφ sluΦovßnφm. Pokud je ovÜem implementovßno jako nerekurzivnφ verze, pak je nestabilnφ
CountingSort() - t°φd∞nφ v²poΦtem po°adφ

Mezi nestabilnφ pak pat°φ:

PrimyVyber() - t°φd∞nφ p°φm²m v²b∞rem. Lze implementovat jako stabilnφ - z prvk∙ se stejn²mi velikostmi se musφ vybrat poslednφ
QuickSort() - rychlΘ t°φd∞nφ
ShellSort() - Shellovo t°φd∞nφ

5.2. Vyhledßvßnφ v set°φd∞nΘm poli

V druhΘm dφlu serißlu v∞novanΘmu datov²m strukturßm a algoritm∙m jsme se seznßmili s algoritmem pro vyhledßnφ hodnoty v poli. Pole jsme museli ovÜem celΘ, prvek po prvku, projφt, proto₧e se jednalo o neset°φd∞nΘ pole. Nynφ u₧ vφme jak pole ut°φdit a dokonce si m∙₧eme vybrat z n∞kolika algoritm∙. Nßsledujφcφ algoritmus pro vyhledßvßnφ prvku v ut°φd∞nΘm poli je vßm vÜem urΦit∞ dob°e znßm, tedy pokud jste se alespo≥ jednou v ₧ivot∞ setkali t°eba s telefonnφm seznamem. Je jasnΘ, ₧e v telefonnφm seznamu se nedß hledat od zaΦßtku a postupovat jmΘno po jmΘnu. LepÜφ je vzφt seznam, otev°φt ho zhruba v polovin∞, podφvat se na jmΘno, to porovnat s hledan²m jmΘnem a podle v²sledku porovnßnφ se vrhnout na levou nebo pravou Φßst. Takov² algoritmus si prßv∞ naprogramujeme:

int Hledani(int *pPole, unsigned int dwVelikost, int iHodnota)
{
    int iIndex;    // navratova hodnota - index hledaneho prvku nebo -1 pokud je prvek nenalezen

    unsigned int dwLevy = 0, dwPravy = dwVelikost - 1;

    do {
        iIndex = (dwLevy + dwPravy) / 2;

        if(iHodnota > pPole[iIndex])
        {
            dwLevy = iIndex + 1; // neni v leve polovine pole
        }
        else
        {
            dwPravy = iIndex - 1; // neni v prave polovine pole
        }
    } while((iHodnota != pPole[iIndex]) && (dwLevy <= dwPravy)); // dokud neni prvek nalezen, nebo nedojde k prekrizeni indexu

    if(iHodnota != pPole[iIndex])
    {
        iIndex = -1; // hodnota se v poli nenachazi, smycka skoncila prekrizenim indexu
    }

    // jinak iIndex urcuje, kde se nachazi prvek

    return iIndex;
}

Algoritmy pro hledßnφ v neset°φd∞nΘm poli m∞ly slo₧itost O(n), tento algoritmus mß slo₧itost O(log n), co₧ je pro rozsßhlß pole velik² rozdφl. Nesmφme vÜak zapomenout, ₧e pole musφ b²t ut°φd∞nΘ, jinak algoritmus nebude fungovat.

5.3. DatovΘ struktury - zßsobnφk

Dnes se seznßmφme s prvnφ ze dvou datov²ch struktur, kterΘ budeme implementovat pomocφ polφ. V n∞kterΘm z pozd∞jÜφch dφl∙ si ukß₧eme i implementaci zalo₧enou na lineßrnφch spojov²ch seznamech. Proto₧e jsme dob°e seznßmeni s objektov²m programovßnφm v jazyce C++, budeme datovΘ struktury implementovat v podob∞ t°φd a vyu₧ijeme i Üablon.

5.3.1. Zßsobnφk (stack)

Zßsobnφk nßm umo₧≥uje p°idßvßnφ a ubφrßnφ prvk∙ pouze z jednoho konce pole (tomuto prvku °φkßme vrchol zßsobnφku). Druh² konec se naz²vß dnem zßsobnφku a nenφ mo₧nΘ z tohoto konce odebφrat nebo p°idßvat prvky (stejn∞ jako to nenφ mo₧nΘ z prost°edku pole). Vybrßnφ prvku ze zßsobnφku znamenß tedy ubrßnφ posledn∞ p°idanΘho prvku, proto se takΘ zßsobnφk oznaΦuje jako struktura typu LIFO (z angl. Last in, first out (poslednφ dovnit°, prvnφ ven)). Nßsleduje rozhranφ t°φdy a implementace metod:

// Hlavickovy soubor Zasobnik.h - deklarace tridy pro strukturu zasobnik

#ifndef ZASOBNIK_H
    #define ZASOBNIK_H

    #include <iostream.h>

    template<class T> class CZasobnik {
    private :
        T *m_Pole;
        int m_Velikost; // Velikost zasobniku
        int m_Vrchol; // kde se prave nachazi vrchol zasobniku

    public :
        CZasobnik(int _Velikost);
        ~CZasobnik();

        bool Vloz(const T& _Vklad);
        bool Vyjmi(T& _Vyber);

        bool JePrazdny() { return ((-1 == m_Vrchol) ? true : false); }
        bool JePlny() { return ((m_Velikost - 1) == m_Vrchol); }

        void Vypis();
    };

    template<class T> CZasobnik<T>::CZasobnik(int _Velikost)
    {
        m_Velikost = -1;
        m_Vrchol = -1;

        m_Pole = new T[_Velikost];

        if(m_Pole)
        {
            // pokud se podarilo nastavime velikost
            m_Velikost = _Velikost;
        }
    }

    template<class T> CZasobnik<T>::~CZasobnik()
    {
        if(m_Pole)
        {
            delete[] m_Pole;
            m_Pole = NULL;
            m_Velikost = 0;
        }
    }

    template<class T> bool CZasobnik<T>::Vloz(const T& _Vklad)
    {
        bool bNavrat = false;

        if(m_Pole)
        {
            if(!JePlny()) // pokud neni zasobnik plny
            {
                m_Vrchol++;

                m_Pole[m_Vrchol] = _Vklad;

                bNavrat = true;
            }
        }

        return bNavrat;
    }

    template<class T> bool CZasobnik<T>::Vyjmi(T& _Vyber)
    {
        bool bNavrat = false;

        if(m_Pole)
        {
            if(!JePrazdny())
            {
                _Vyber = m_Pole[m_Vrchol];

                m_Vrchol--;

                bNavrat = true;
            }
        }

        return bNavrat;
    }

    template <class T> void CZasobnik<T>::Vypis()
    {
        if(m_Pole)
        {
            if(!JePrazdny())
            {
                cout << "Obsahuje " << m_Vrchol + 1 << " objektu (volnych " << m_Velikost - (m_Vrchol + 1) << ")" << endl;
                for(int i = 0; i <= m_Vrchol; i++)
                {
                    cout << m_Pole[i] << endl;
                }
            }
            else
            {
                cout << "Seznam je prazdny" << endl;
            }
        }
    }

#endif

Jak jsme se dozv∞d∞li v kurzu Φφslo 16 v∞novanΘmu jazyku C++, tak Üablony vy₧adujφ specißlnφ postup p°i kompilaci a proto je Üablona implementovßna p°φmo v hlaviΦkovΘm souboru.

V∞tÜinou se pro zßsobnφk implementuje jeÜt∞ metoda pro nakouknutφ na prvek le₧φcφ na vrcholu zßsobnφku. Metoda je ·pln∞ stejnß jako metoda Vyjmi(), ale uvnit° t∞la nem∞nφme Φlenskou prom∞nnou m_Vrchol. Metodu zde neuvßdφm, ale je implementovßna v p°ilo₧enΘm projektu jako metoda Nakoukni().

Proto₧e datovß struktura zßsobnφk je velice d∙le₧itou a Φasto pou₧φvanou, uvedu si i anglickΘ ekvivalenty jednotliv²ch metod:

Vloz() - PUSH
Vyjmi() - POP
Nakoukni() - PEEK

Pokud jste se n∞kdy setkali s k≤dem napsan²m v assembleru, pak prvnφ dv∞ z nich jsou instrukcemi procesoru °ady x86 urΦenΘ prßv∞ pro uklßdßnφ (resp. vybφrßnφ) ·daj∙ do/z datovΘ struktury p°φstupnΘ programu, co₧ je prßv∞ nßÜ zßsobnφk. Pou₧φvajφ se nap°φklad p°i volßnφ funkcφ pro ulo₧enφ parametr∙, vytvß°enφ lokßlnφch prom∞nn²ch a takΘ pro ulo₧enφ adresy pro nßvrat z podprogramu. Pokud bude zßjem, pak se v n∞kterΘm z dalÜφch Φlßnk∙ na zßklady assembleru podφvßme.

5.4. Co bude p°φÜt∞

Seznßmφme se s druhou strukturou zalo₧enou na polφch - frontou. Probereme takΘ jejφ modifikace - oboustrannou frontu a kruhovou frontu. PokraΦovat budeme lineßrnφm spojov²m seznamem a budeme pomocφ n∞ho implementovat zßsobnφk a frontu.

PřφÜtě nashledanou.

Ond°ej BuriÜin