Objektum-orientált C++ III.

Építsünk láncolt listákat.

Ahogy ígértem, itt a harmadik rész is. Mint már az előző ajánlóban említettem, egy adatok tárolására alkalmas szerkezetű objektumot fogunk elkészíteni. Hogy a jövőben elkerüljem az ilyen nyakatekert mondatokat, nevezzük csak a dolgot "láncolt listának". Így gondolom már több embernek ismerős lehet a dolog. Ismét hanyagolnám a további bevezető rizsázást, klattyanjunk a tovább gombra.

Az első képen gyönyörűen látszik a tömb (felül) és a láncolt lista (alul). Mi is a gondunk a szimpla tömbbel? Csak fix méretben foglalhatjuk le. Annyira fix méretben, hogy már a fordításkor tudnunk kell, hogy mekkorát szeretnénk. De ez csak egy gond. Egy másik gond, hogy ha nem egy szimpla int-et vagy hasonlóan egyszerű objektumot, hanem valami szép nagy dolgot pakolunk bele, és azt szeretnénk rendezni, az ugye nem kis erőforrásigényű, ahogy cserélgeti az objektumokat a memóriaterületen, hogy sorban legyenek. Perszer erre lehet azt mondani, hogy a kriz az hülye, mert miért nem objektumokra mutató mutatókból csinál tömböt, és akkor csak a mutatókat kell mozgatnia. No igen, ez egy fokkal jobb ötlet, és azt a problémánkat is megolja, hogy fordítási időben kell tudnunk a tömb méretét. Elég a tömb lefoglalásakor akár dinamikusan egy változóban tudni a méretet. A probléma még mindig probléma, hogy ha azt a fix méretet túllépjük, akkor az gáz.

Itt jön a képbe a láncolt lista. A szerkezet lényege, hogy egy listaelem egy adatrészből és egy mutatórészből áll. Pontosítok: egy listaelem egy adatrészből és legalább egy mutatórészből áll. Miért jó ez? Egyrészről azért, mert a listaelemeket dinamikusan, a futási idő alatt foglalgatjuk le, felső határ csak a memória mérete, nem pedig egy előre meghatározott szám. Másrészről pedig itt is megvan az az előny, hogy csak a pointereket kell új címre állítani ahhoz, hogy rendezni tudjuk a listánkat. Izgi, mi? :)

Hogy ne legyen ilyen egyszerű a helyzet, mi egy fejelemes, kétirányú, ciklikus láncolt listát fogunk csinálni. ez azt jelenti, hogy a listaelemben két mutató van, amiből az egyik az előző, a másik a következő elemre fog mutatni (ezért kétirányú), a lista első eleme nem tartalmaz adatot, az csak azért van hogy az első elem beszúrása és az utolsó elem törlése jóval könnyebb legyen (tehát fejelemes) és az utolsó elem "következő elem" mutatója nem nullpointer, hanem a fejelemre mutat (ugyanígy a fejelem "előző elem" mutatója az utolsó elemre mutat). Kezdjük talán a dolog egyszerűbb végénél, a listaelem szerkezetének a megvalósításánál:

struct listNode
{
    listNode* prev;
    listNode* next;
    int data;

    listNode()
    {
        next = prev = this;
    }
    listNode(const int& num)
    {
        next = prev = this;
        data = num;
    }
};

Csoddálatos. Értelem szerűen van egy prev mutató az előző elemre, egy next mutató a következő elemre és egy data, amiben az adatokat tároljuk. Itt az ideje, hogy magának a listának is nekiálljunk. A dolog végtelenül egyszerű, szükségünk lesz egy listNode* változóra, ami "tartani" fogja a lista fejelemét, egy befűző és egy kifűző függvényre, amivel új elemeket szúrhatunk be, illetve létezőket vehetünk ki.

class cList
{
    private:
        // A lista fejelemére mutató pointer
        listNode* list;

        // Üres lista létrehozása
        void Create(void);

        // Lista kiürítése
        void Destroy(void);

        // target című elem törlése
        void Remove(listNode* target);

        // target című elem kifűzése
        listNode* Get(listNode* target);
    public:
        // Konstruktor
        cList(void);

        // Copy Konstruktor
        cList(const cList& other);

        // Destruktor
        ~cList(void);

        // Kivétel osztályok
        class E_OUTOFMEMORY {};
        class E_INVALIDITEM {};

        void left_insert(listNode* target, listNode* data) {}
};

Ennyi egyenlőre elég is lesz, bár az objektum kezelőfelülete még a tervezés szintjén sincs kész (a left_join()-t leszámítva, ami csak azér került bele (üresen), hogy leforduljon a kód, majd a negyedik részben lesz rendesen kifejtve), de azzal ráérünk később is foglalkozni. Kezdjük akkor sorban a megvalósítást, először a Create() függvénnyel, ami létrehozza az üres listát (amiben csak a fejelem van).

void cList::Create(void)
{
    list = new listNode();
    if (!list) throw E_OUTOFMEMORY();

    list->next = list;
    list->prev = list;
    return;
}

A cList:: előtag annak köszönhető, hogy az osztály definícióján kívül van megvalósítva a függvény. Gondolom nem annyira ismeretlen eljárás ez. Az objektum szerkezete megy a fejelembe (.h vagy .hpp), a többi meg az ugyanolyan nevű .cpp fájlba. Áttérhetünk a Destroy() függvényre, ami a fejelemen kívül minden elemet töröl a listából.

void cList::Destroy(void)
{
    while (list->prev != list) {
        Remove(list->prev);
    }
    return;
}

Rettentő cselesen a Remove() függvényt használtam a dologhoz, így tulajdonképpen egyesével kifűzve az összes elemet a listából, mígnem a fejelem prev mutatója meg nem egyezik a lista fejelemének a címével. Ahogy illik, a Remove() megvalósításával folytatom a sort. Lassan, de biztosan közeledünk a vége felé... :)

void cList::Remove(listNode* target)
{
    listNode* tmp = Get(target);
    delete tmp;
    return;
}

Ismét továbbadjuk a dolog megvalósítását egy másik függvénynek, a Get()-nek, ami így is, úgy is kifűzi az elemet, akkor miért ismételnénk meg ugyanazt a kódot még egyszer a Remove()-ban is? Tehát, a Get()-tel kifűzetjük, majd a kapott elemet töröljük. Nna, nézzük azt a Get()-et, ha már egyszer ennyi minden épül rá:

listNode* cList::Get(listNode* target)
{
    target->prev->next = target->next;
    target->next->prev = target->prev;
    target->prev = target;
    target->next = target;
    return target;
}

Nos, ez egy nem egyszerű dolog. Igazából egyszerű, csak leírni lenne túl bonyolult, inkább veszem a bátorságot és rajzolok egy ábrát hozzá. Egy "jó" ábra felér egy bekezdésnyi szöveggel. Mindenesetre az ábrát is megmagyarázom inkább. Fő a biztonság. Szóval, a kép első sorában az alaphelyzetet látjuk. A második sor a függvény első sorának hatását hivatott szemléltetni, azaz a kifűzendő listaelem előtti elemnek a következő elemre mutató mutatóját átállítjuk a kifűzendő elem utáni elemre. A kép harmadik sorának lényege ugyanez, csak fordítva, mivel a kifűzendő elem utáni elem előző elemre mutató mutatóját állítjuk a kifűzendő elem előtti elemre. Így a lista maga már nem függ a kifűzendő elemtől, mindenesetre a biztonság kedvéért a két mutatóját saját magára állítjuk (a függvény utolsó két mutató állítása). Végül visszatérünk a kifűzött elem mutatójával. Ezzel le is tudtuk az objektum private részét, jöhet a public:

cList::cList(void)
{
    Create();
}

Egyszerűbb nem is lehetne, csak a Create()-et hívjuk, meg hogy legyen egy üres listánk. Nézzük a copy konstruktort:

cList::cList(const cList& other)
{
    Create();

    listNode* tmp = other.list->next;
    while (tmp != other.list) {
        listNode* node = new listNode(tmp->data);
        if (!node) throw E_OUTOFMEMORY();

        this->left_insert(this->list, node);
        tmp = tmp->next;
    }
}

Lényegében az értékül adott listán végigmegyünk és egyesével beszúrjuk az elemeit a saját listánkba. Mint említettem annak idején, a copy konstruktor fontos dolog. Gondoljunk csak bele, hogy mi történne akkor, ha nem írnánk sajátot. Az objektum változóinak értéke szépen átmásolódna. Tehát ha B objektumnak adjuk kezdőértékül A objektumot, akkor B objektum list változója ugyanoda fog mutatni, mint az A objektum list változója, tehát ha az A objektumot megszüntetjük, akkor a B objektum tulajdonképpen a "semmibe" fog mutatni. De ha B objektum listáján változtatunk (kifűzünk, befűzünk), akkor A objektum listája is változik.
A left_insert() az első paraméterként kapott pointer által mutatott listaelemhez képest balra fűz be egy elemet. Mivel esetünkben a lista fejelemét kapja meg a függvény, és mivel a lista fejelemének bal oldalra mutató mutatója (azaz a prev) a lista utolsó elemére mutat, ez azt jelenti, hogy a lista végére fűzzük be az elemet. Jöjjön végül, de nem utolsó sorban a destruktor:

cList::~cList(void)
{
    Destroy();
    delete list;
}

Nem meglepő módon a destruktor (ami ugyebár a konstruktor úgymond ellentéte, és akkor fut le, amikor az objektum megszűnik) a Destroy() függvénnyel kiüríti a listát, majd a list változó segítségével megszünteti a fejelemet is.
Asszem ennyi elég is lesz mára. Az objektum felhasználói felületét (a public függvények, mint például a left_insert()) és néhány operátort a következő részben fogunk megírni, és ha nem nyúlik túl hosszúra a dolog (mint ahogy most), akkor végre a sablonokat is kitárgyaljuk.

A sorozat további részei

Hozzáfűznél valamit?

Dobj egy emailt a blog kukac deadlime pont hu címre.

Feliratkoznál?

Az RSS feed-et ajánljuk, ha kedveled a régi jó dolgokat.