Programozó Páternoszter

Folytatjuk állatorvosi sorozatunkat, ha ezt olvasod, akkor feltételezhetően már túl vagy az alábbi, erősorrendben hivatkozott posztokon:

• a Tömör a gyönyörben kifejlesztettünk egy C struktúrás LZW (bináris) fa építőt
• mélyebben megismerkedhettél a kóddal a Labormérés otthon, avagy hogyan dolgozok fel egy példát posztban
• amit jó (K&R) szokás szerint továbbfejlesztések sorát át elkezdtünk átteni C++-ba

Ez a poszt is ebbe a sorozatba illeszkedik.

Olyan objektum lenne jó, ami teljesen elrejtené a korábbi C-s progi logikáját (ami tk. az algoritmus, az LZW fa építésének logikája) mondjuk csak "<<" operátorral kéne belenyomni az inputról bejövő betűket az LZW fa objektumba, nem?

Lássuk, mit is szeretnénk: 

int
main ()
{
    char b;
    LZWBinFa binFa;

    while (std::cin >> b)
    {
        binFa << b;
    }

    binFa.kiir ();
    binFa.szabadit ();

    return 0;
}

Ezt azért tehetjük meg, mert a LZWBinFa osztályban definiáltuk a << operátort: 

    void operator<<(char b)
    {
        if (b == '0')
        {
            // van '0'-s gyermeke az aktuális csomópontnak?
            if (!fa->nullasGyermek ()) // ha nincs, csinálunk
            {
                Csomopont *uj = new Csomopont ('0');
                fa->ujNullasGyermek (uj);
                fa = &gyoker;
            }
            else // ha van, arra lépünk
            {
                fa = fa->nullasGyermek ();
            }
        }
        else
        {
            if (!fa->egyesGyermek ())
            {
                Csomopont *uj = new Csomopont ('1');
                fa->ujEgyesGyermek (uj);
                fa = &gyoker;
            }
            else
            {
                fa = fa->egyesGyermek ();
            }
        }
    }

 Aminek kódja teljesen ugyanaz, mint az előző változat, csupán az osztálynév változott a csomópontot mostmár a "Csomopont" osztály absztrahálja. Ennek érdekessége, hogy definícióját beágyaztuk az LZWBinFa osztályba:

private:

    class Csomopont
    {
    public:
        Csomopont (char b = '/'):betu (b), balNulla (0), jobbEgy (0) {};
        ~Csomopont () {};
        Csomopont *nullasGyermek () {
            return balNulla;
        }
        Csomopont *egyesGyermek ()
        {
            return jobbEgy;
        }
        void ujNullasGyermek (Csomopont * gy)
        {
            balNulla = gy;
        }
        void ujEgyesGyermek (Csomopont * gy)
        {
            jobbEgy = gy;
        }
    private:
        friend class LZWBinFa;
        char betu;
        Csomopont *balNulla;
        Csomopont *jobbEgy;
        Csomopont (const Csomopont &);
        Csomopont & operator=(const Csomopont &);
    }; 

Növeltük az absztrakció mértékét a csomópont definiálásával, de a meglévő kódot csak kicsi lépésekben akarjuk módosítani, s most az LZWBinFa módszerei ezért dolgoznak a csomópont védett tagjaival, hogy ez mehessen, ezért a csomópont barátjának deklaráltuk a fát elvonatkoztató tartalmazó osztályt.

Tekerj a tovább linkre a folytatásért.

Miután az 5 előadás verem{1-17}.cpp példáit reprodukáltuk, megrágtuk, elfogyasztottuk, majd kimásztunk az asztal alól, ahová unalmunkban közben be-beestünk, kicsit komolyabb fába vágtuk a fejszét: a Tömör a gyönyörben kifejlesztett C struktúrás LZW (bináris) fa építőnket több lépésben átírjuk C++-ba. Jó (K&R) szokás szerint továbbfejlesztések sorát készítjük majd el, e mostanival kezdjük a C++ sorozatot. Mikor vagy kész? Ha az 5. alőadás alapján készített progid lefordul és ugyanazt nyomja ki, mint a Labormérés otthon, avagy hogyan dolgozok fel egy pédát posztbeli teszteléskor a C változat.

Kezdjük! Az első változatot tehát úgy készítjük, hogy nézzük a C kódot és melegében írjuk át C++-ra (ennek megfelelően egyelőre nem használunk például referenciákat) egyszerűen csak egy osztállyal helyettesítjük a fa csomópontjait leíró struktúrát.

Az osztálynév nem a legszerencsésebb, lehetne LZWBinFaCsomopont is, de most a gyökér csomópont kitüntetett abban az értelemben, hogy számunkra ő lesz majd maga a fa, innen a név.

class LZWBinFa
{

    char betu;
    LZWBinFa *balNulla;
    LZWBinFa *jobbEgy;

public:
    LZWBinFa (char b = '/'):betu (b), balNulla (NULL), jobbEgy (NULL) {};
    ~LZWBinFa () {};

 A struktúrával teljesen analóg módon itt is megvan a két önhivatkozó tag, itt hogy '0'-val vagy '1'-el címkézve vettük fel az új (a gyermek) csomópontot, azt egy char-ban (betu) tároljuk (ennek kapcsán megnézheted a 3. hullám kapcsolódó 1 trófeását). Konstruktorunkat tipikusan majd ezzel a '0' vagy '1' címkével fogjuk hívni, de ha ezt nem adjuk meg, akkor a gyökér "jele" a '/' betű lesz feltételezve. Továbbá az újonan készített csomópontok gyerekekre mutató mutatóját úgy állítjuk be, hogy kezdetben nincsenek gyerekei a csomópontnak /balNulla (NULL), jobbEgy (NULL)/ Az alábbi kódcsiperben tehát a "gyoker" az az LZWBinFa csomópont objektum, amiben a "betu" értéke a '/' jel, azt is észrevehetjük, hogy lokális változóként vettük fel, nem kell majd szabadítani. Kezdetben erre a gyökérre állítjuk a "fa" mutatót, s majd ez mutatja mindig, hogy az algoritmus üzeme során hol vagyunk éppen a fában.

int
main ()
{
    char b;
    LZWBinFa gyoker, *fa = &gyoker;

    while (std::cin >> b)
    {
        if (b == '0')
        {
            // van '0'-s gyermeke az aktuális csomópontnak?
            if (!fa->nullasGyermek ()) // ha nincs, csinálunk
            {
                LZWBinFa *uj = new LZWBinFa ('0');
                fa->ujNullasGyermek (uj);
                fa = &gyoker;
            }
            else // ha van, arra lépünk
            {
                fa = fa->nullasGyermek ();
            }
        }

 A működés teljesen ugyanaz, csak kicsit egyszerűsödött a kód, s jobban is olvasható, mint a C változat. Egyszerűen meghagytuk a C program logikáját és a struktúra használata helyett beütöttük az újdonsült osztályunk használatát. A konstruktor és a new operátor használata is levett pár sort a meglévő kódból a vállunkról. Fordítsuk, futtassuk:

[norbi@sgu ~]$ g++  z.cpp -o z
[norbi@sgu ~]$ ./z <tesztminta.txt
------------1(3)
---------1(2)
------1(1)
---------0(2)
------------0(3)
---------------0(4)
---/(0)
---------1(2)
------0(1)
---------0(2)OK, ugyanaz.
Tekerj a továbbra a teljes forrásért és persze a folytatásért.

*: "Imádni fogják a légiót, egy emberként, tiszta szívből", www.imdb.com/title/tt0126388/