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