C/C++ & Visual C++

DatovΘ struktury a algoritmy (10.)

┌vodem  |  DatovΘ struktury |  Kurz DirectX  |  Downloads  |  Otßzky a odpov∞di

10.1 Lineßrnφ spojov² seznam (obousm∞rn²)

    Nejprve si ukß₧eme grafickou reprezentaci obousm∞rnΘ fronty:

    Vidφme, ₧e budeme v t°φd∞ prvku spojovΘho seznamu pot°ebovat jeden ukazatel navφc. Tento ukazatel bude ukazovat bu∩ na p°edch∙dce prvku nebo na NULL, pokud prvek bude prvnφm prvkem seznamu. Pop°φpad∞ bychom pro zjednoduÜenφ vyhledßvßnφ mohli implementovat obousm∞rn² seznam se zarß₧kou. Jinak se zatφm nic nezm∞nφ. Upravenß t°φda prvku bude tedy vypadat nßsledovn∞:

#ifndef OBOUSEZNAM_H
    #define OBOUSEZNAM_H

    template<class T> class CObouPrvek {
    private:
        T m_Data;
        CPrvek<T> *m_lpDalsi;
        CPrvek<T> *m_lpPredchozi;
    public:
        CPrvek() : m_lpDalsi(NULL), m_lpPredchozi(NULL) { }
        CPrvek(const T& _Data) : m_Data(_Data), m_lpDalsi(NULL), m_lpPredchozi(NULL) { }

        T VratData() const { return m_Data; }
        CPrvek<T>* VratDalsi() const { return m_lpDalsi; }
        CPrvek<T>* VratPredchozi() const { return m_lpPredchozi; }
        void NastavDalsi(CPrvek<T> *_lpDalsi) { m_lpDalsi = _lpDalsi; }
        void NastavPredchozi(CPrvek<T> *_lpPredchozi) { m_lpPredchozi = _lpPredchozi; }
        void NastavData(const T& _Data) { m_Data = _Data; }
    };

    Nynφ t°φda CObouSeznam, kterß bude obsluhovat naÜφ obousm∞rnou frontu. Nejprve si ukß₧eme deklaraci t°φdy a pak budeme implementovat jednotlivΘ metody. Tato t°φda bude mφt obdobnΘ metody jako m∞la t°φda pro obsluhu jednosm∞rnΘho seznamu. Vytvo°φme t°φdu kterß bude mφt na ka₧dΘ stran∞ prvek navφc - zarß₧ku - pomocφ kterΘho budeme provßd∞t vyhledßvßnφ hodnot:

    template<class T> class CObouSeznam {
    private:
        CObouPrvek<T> *m_lpPrvni, *m_lpPosledni;
    public:
        CObouSeznam() : m_lpPrvni(NULL), m_lpPosledni(NULL) { }
        ~CObouSeznam() { if(!JePrazdny()) { SmazSeznam(); } }

        bool VytvorPrazdny();

        bool SmazSeznam();

        bool JePrazdny();

        bool VlozNaKonec(const T& _Data); // vklada na konec seznamu
        bool VlozNaZacatek(const T& _Data); // vklada na zacatek seznamu

        CObouPrvek<T>* Najdi(const T& _Data); // vrati ukazatel na nalezeny prvek nebo NULL
        CObouPrvek<T>* NajdiBezZarazky(const T& _Data);
        CObouPrvek<T>* Najdi(const T& _Data, unsigned int _k);

        bool VlozZa(CObouPrvek<T>* _lpPrvek, const T& _Data);
        bool VlozPred(CObouPrvek<T>* _lpPrvek, const T& _Data);

        bool SmazZa(CObouPrvek<T>* _lpPrvek);
        bool SmazPrvek(CObouPrvek<T>* _lpPrvek);

        CObouPrvek<T>* NajdiNejmensi(CObouPrvek<T>* _lpPrvek);
        void SetridVyberem();

        void VypisOdZacatku();
        void VypisOdKonce();
    };

    Metoda JePrazdny() vracφ, zda je ukazatel na p°edchozφ prvek poslednφho prvku (pokud tento ovÜem existuje) roven prvku prvnφmu. Tedy vracφ, jestli naÜe zarß₧ky na sebe ukazujφ:

    template<class T> bool CObouSeznam<T>::JePrazdny()
    {
        bool bNavrat = true;

        if(m_lpPosledni) { bNavrat = (m_lpPosledni->VratPredchozi() == m_lpPrvni); }

        return bNavrat;
    }

    Nßsleduje metoda, kterou musφme zavolat p°ed pou₧itφm seznamu nebo pro novou inicializaci seznamu (nap°φklad po smazßnφ):

    template<class T> bool CObouSeznam<T>::VytvorPrazdny()
    {
        bool bNavrat = false;

        if(!JePrazdny())    // lze zavolat i pro existujici seznam, proto radeji overime i toto
        {
            SmazSeznam(); // smazeme puvodni seznam
        }

        // nova inicializace promennych
        m_lpPrvni = new CObouPrvek;

        if(m_lpPrvni)
        {
            m_lpPosledni = new CObouPrvek;

            if(m_lpPosledni)
            {
                // NULL do predchoziho prvku da konstruktor
                m_lpPrvni->NastavDalsi(m_lpPosledni);
                // NULL do nasledujiciho prvku da konstruktor
                m_lpPosledni->NastavPredchozi(m_lpPrvni);

                bNavrat = true;
            }
            else
            {
                delete m_lpPrvni; // pokud se nevytvoril posledni, smazeme prvni
                m_lpPrvni = NULL;
            }
        }

        return bNavrat;
    }

    Nynφ je na Φase vlo₧it do seznamu n∞jakΘ prvky. ZaΦneme vklßdßnφm na zaΦßtek a na konec, kterΘ je nejlehΦφ. Jeden z mo₧n²ch zp∙sob∙ implementace:

    template<class T> bool CObouSeznam<T>::VlozNaZacatek(const T& _Data)
    {
        bool bNavrat = false;

        if(m_lpPrvni) // pokud je seznam inicializovan
        {
            CObouPrvek<T> *lpNovy = new CObouPrvek<T>(_Data);

            if(lpNovy)
            {
                lpNovy->NastavPredchozi(m_lpPrvni); // predchudcem noveho prvku je zarazka
                lpNovy->NastavDalsi(m_lpPrvni->VratDalsi()); // a ukazuje na nasledujici
                m_lpPrvni->VratDalsi()->NastavPredchozi(lpNovy);
                m_lpPrvni->NastavDalsi(lpNovy);

                bNavrat = true;
            }

            // novy prvek nemazeme
        }

        return bNavrat;
    }

    template<class T> bool CObouSeznam<T>::VlozNaKonec(const T& _Data)
    {
        bool bNavrat = false;

        if(m_lpPosledni) // pokud je seznam inicializovan
        {
            CObouPrvek<T> *lpNovy = new CObouPrvek<T>(_Data);

            if(lpNovy)
            {
                lpNovy->NastavPredchozi(m_lpPosledni->VratPredchozi());
                lpNovy->NastavDalsi(m_lpPosledni);
                m_lpPosledni->VratPredchozi()->NastavDalsi(lpNovy);
                m_lpPosledni->NastavPredchozi(lpNovy);

                bNavrat = true;
            }
        }

        return bNavrat;
    }

    A¥ prvek vklßdßme na zaΦßtek nebo na konec, ob∞ zarß₧ky v₧dy z∙stßvajφ na sv²ch mφstech, jsou krajnφmi prvky seznamu. Jin²m zp∙sobem implementace by mohlo b²t vlo₧enφ dat do p∙vodnφ zarß₧ky, vytvo°enφ zarß₧ky novΘ a potom samoz°ejm∞ nastavenφ p°φsluÜn²ch ukazatel∙. Te∩ si ukß₧eme jak vlo₧it prvek za n∞jak² prvek v seznamu (to, ₧e prvek opravdu pat°φ do tohoto seznamu nekontrolujeme, stejn∞ jako jsme to ned∞lali doposud):

    template<class T> bool CObouSeznam<T>::VlozZa(CObouPrvek<T>* _lpPrvek, const T& _Data)
    {
        bool bNavrat = false;

        if(!JePrazdny() && _lpPrvek)
        {
            CObouPrvek<T> *lpNovy = new CObouPrvek<T>(_Data); // vytvorime novy prvek

            if(lpNovy)
            {
                // naslednik prvku z parametru je naslednikem noveho
                lpNovy->NastavDalsi(_lpPrvek->VratDalsi());
                // prvek z parametru je predchudcem noveho prvku
                lpNovy->NastavPredchozi(_lpPrvek);
                // novy prvek je predchudce naslednika prvku
                _lpPrvek->VratDalsi()->NastavPredchozi(lpNovy);
                // novy prvek je za prvkem v parametru
                _lpPrvek->NastavDalsi(lpNovy);

                bNavrat = true;
            }

            // klasicky nesmime prvek smazat
        }

        return bNavrat;
    }

    Podobn∞ se implementuje vklßdßnφ p°ed prvek, je tu tedy vynechßno (najdete ho v k≤du). JedinΘ na co je nutnΘ dßt si v obou p°φpadech pozor je po°adφ p°i°azenφ, abychom si nesmazali d∙le₧itΘ ukazatele. DalÜφ v∞c, kterou je d∙le₧itΘ si uv∞domit je, ₧e pokud vklßdßme prvek, tak musφme v₧dy zm∞nit Φty°i ukazatele, kterΘ si °ekneme u vklßdßnφ za. Slovem prvek nynφ budeme rozum∞t prvek z argumentu funkce, tedy prvek za kter² se bude vklßdat. Nejprve zapojφme nov² prvek, ten musφ mφt jako p°edch∙dce prvek, jako nßslednφka pak nßslednφka prvku. PotΘ upravφme ukazatel na p°edchozφ prvek nßslednφka prvku, ten musφ ukazovat na nov² prvek a koneΦn∞ nastavφme ukazatel na nßslednφka v prvku, ten bude ukazovat na nov∞ vlo₧en² prvek.

    Ji₧ umφme vklßdat prvky do seznamu, je tedy na Φase nauΦit se prvky mazat, nejprve se ale podφvßme na smazßnφ celΘho seznamu. To je naprosto shodnΘ jako u jednosm∞rnΘho seznamu, ale navφc si m∙₧eme vybrat sm∞r odkud budeme prvky mazat:

    template<class T> bool CObouSeznam<T>::SmazSeznam()
    {
        bool bNavrat = false;

        if(m_lpPrvni && m_lpPosledni) // pokud je seznam platny, tak ho cely smazeme ...
        {
            CObouPrvek<T> *lpMazany;

            while(m_lpPrvni)
            {
                lpMazany = m_lpPrvni;
                m_lpPrvni = m_lpPrvni->VratDalsi(); // posun na dalsi prvek
                delete lpMazany;
            }

            m_lpPrvni = NULL;
            m_lpPosledni = NULL;

            bNavrat = true;
        }

        return bNavrat;
    }

    Tato metoda sma₧e kompletn∞ cel² seznam, vΦetn∞ zarß₧ek a zaΦφnß od prvnφ zarß₧ky. Pro znovupou₧itφ instance CObouSeznam je v tΘto implementaci op∞t nutnΘ zavolat metodu VytvorPrazdny(). Nynφ mazßnφ konkrΘtnφho prvku:

    template<class T> bool CObouSeznam<T>::SmazPrvek(CObouPrvek<T>* _lpPrvek)
    {
        bool bNavrat = false;

        if(!JePrazdny() && _lpPrvek)
        {
            _lpPrvek->VratPredchozi()->NastavDalsi(_lpPrvek->VratDalsi());
            _lpPrvek->VratDalsi()->NastavPredchozi(_lpPrvek->VratPredchozi());

            // Vse v poradku, muzeme prvek smazat
            delete(_lpPrvek);
            _lpPrvek = NULL;

            bNavrat = true;
        }

        return bNavrat;
    }

    Jde tedy jen o to, vynechat prvek ze seznamu a pote ho smazat. Pro jistotu ho jeÜt∞ nastavφme na NULL, aby nenastaly n∞jakΘ potφ₧e. Zde nßm staΦφ navßzat na sebe prvek p°ed a za vynechßvan²m prvkem, tedy dva ukazatele. Metody pro mazßnφ prvku za dan²m prvkem, pop°φpad∞ p°ed nφm pak implementujeme velice jednoduÜe, prßv∞ s vyu₧itφm tΘto metody:

    template<class T> bool CObouSeznam<T>::SmazZa(CObouPrvek<T>* _lpPrvek)
    {
        bool bNavrat = false;

        if(!JePrazdny() && _lpPrvek) // nemuzeme mazat zarazku
        {
            CObouPrvek<T> *lpMazany = _lpPrvek->VratDalsi();

            // zkontrolujeme jestli prvek existuje a jestli to neni zarazka
            if(lpMazany && (lpMazany != m_lpPosledni))
            {
                bNavrat = SmazPrvek(lpMazany);
            }
        }

        return bNavrat;
    }

#endif

    Metoda mazßnφ prvku p°edchßzejφcφho je pak zcela analogickß.

    Ostatnφ metody z∙stßvajφ shodnΘ s jednosm∞rn²m lineßrnφm spojov²m seznamem. Jen si u naÜφ implementace musφme uv∞domit, ₧e data jsou ulo₧ena a₧ v prvku nßsledujφcφm za zarß₧kou, resp. p°ed nφ. Tedy na mφstech v pam∞ti m_lpPrvni->VratDalsi(), resp. m_lpPosledni->VratPredchozi(). TakΘ je dobrΘ si uv∞domit, ₧e v∞tÜinu metod lze implementovat z obou stran, Φeho₧ se dß n∞kdy s v²hodou vyu₧φt. Jedinou metodu, kterou jsem napsal zvlßÜ¥ pro ob∞ strany je metoda pro v²pis. Tato oboustrannß metoda je vhodnß p°i tvorb∞ nov²ch metod, kde pot°ebujeme zjistit, jestli jsme v seznamu p°i p°i°azovßnφ ukazatel∙ neud∞lali chybu. Seznam toti₧ z jednΘ strany m∙₧e b²t v po°ßdku a z druhΘ mohou b²t n∞kterΘ prvky vynechßny nebo seznam jinak poruÜen. Ukß₧eme si tedy jen metodu najdi prvek s danou hodnotou a implementujeme ji pro hledßnφ odzadu seznamu:

    template<class T> CObouPrvek<T>* CObouSeznam<T>::Najdi(const T& _Data)
    {
        CObouPrvek<T> *lpNavrat = NULL; // implicitne nenalezeno

        if(!JePrazdny())
        {
            CObouPrvek<T> *lpZkoumany = m_lpPosledni->VratPredchozi(); // zarazka nas nezajima

            m_lpPrvni->NastavData(_Data); // ulozime data do zarazky
            while(lpZkoumany->VratData() != _Data)
            {
                lpZkoumany = lpZkoumany->VratPredchozi();
            }

            if(lpZkoumany != m_lpPrvni)
            {
                lpNavrat = lpZkoumany; // nalezli jsme prvek
            }
        }

        return lpNavrat;
    }

Jen jako prvnφ zkouman² prvek vezmeme p°edch∙dce poslednφho prvku a pokud neobsahuje hledanou hodnotu, bereme p°edch∙dce zkoumanΘho prvku. To d∞lßme nejdΘle tak dlouho, dokud nedosßhneme zarß₧ky, prvku m_lpPrvni, kterß z definice obsahuje hledanou hodnotu. Porovnßme, zda nalezen² ukazatel neukazuje na zarß₧ku. Pokud ne, pak jsme nalezli hledan² prvek.

    K≤d naleznete v sekci Downloads (projekt ObouSeznam).

    Obousm∞rn² (i jednosm∞rn²) seznam se dß z°et∞zit tak, ₧e ukazatel poslednφho prvku bude ukazovat na prvnφ prvek a p°edch∙dcem prvnφho prvku bude prvek poslednφ. Tak dostßvßme kruhov² seznam, staΦila by nßm tedy jen jedna zarß₧ka a jeden ukazatel ve t°φd∞ kruhovΘho seznamu. Takov² seznam se nßm m∙₧e hodit p°i lad∞nφ (staΦil by i jednosm∞rn²), kdybychom uklßdali nap°. 500 zprßv. PotΘ by se zase od zaΦßtku zaΦaly p°episovat nejstarÜφ ulo₧enΘ zprßvy.

    Jedinou nev²hodou obousm∞rnΘho seznamu je v∞tÜφ pam∞¥ovß nßroΦnost, musφme ulo₧it v ka₧dΘm uzlu jeden ukazatel navφc. Na druhou stranu, n∞kterΘ metody, nap°. pro vypouÜt∞nφ prvku se stanou jednoduÜÜφmi. Slo₧itost vlo₧enφ novΘho prvku je u naÜφ implementace konstantnφ, nezßvislß na poΦtu prvk∙ v seznamu. Pokud bychom si udr₧ovali jen ukazatel na hlavu seznamu, pak bychom p°i vlo₧enφ novΘho prvku museli p°ejφt na konec seznamu - slo₧itost by tedy byla O(n) ve vÜech p°φpadech. Konstantnφ slo₧itost je nynφ i u smazßnφ prvku . Nemusφme toti₧ v p°φpad∞ mazßnφ konkrΘtnφho prvku hledat jeho p°edch∙dce, jak tomu bylo v p°φpad∞ jednosm∞rnΘho seznamu. Slo₧itost hledßnφ v obousm∞rn∞ z°et∞zenΘm seznamu se samoz°ejm∞ nem∞nφ a zßvisφ na poΦtu prvku obsa₧en²ch v seznamu - je to tedy O(n) v nejhorÜφm p°φpad∞, kdy hledan² prvek najdeme a₧ na konci seznamu.

10.2 Co bude p°φÜt∞

    P°φÜtφ m∞sφc se zaΦneme zab²vat stromy - nejprve obecn²mi a pak se podrobn∞ji podφvßme na binßrnφ stromy. Povφme si, co jsou to vyvß₧enΘ stromy a ukß₧eme si jak lze prochßzet stromy, jako₧to rekurzivnφmi strukturami a mnoho dalÜφho.

    Nashledanou u dalÜφho dφlu