Programozó Páternoszter

2011. április 6-án megtartottuk a nyolcadik előadást, írtunk katalógust, mert kevesebben voltunk, mint szoktunk lenni, 100 fő alá csökkent a létszám, csupán 97-en voltunk...

A végleges előadások itt elérhetőek: nehogy.fw.hu/

Korábbi posztunkban foglalkoztunk már a szavak számlálásával: előre hivatkozva, a Google MapReduce kapcsán. Most a K&R könyv C struktúrás szószámoló progiját írjuk meg C++-ban a korábbi osztályunk kódjának egyszerűsítésével. Mélyen nyomjuk majd a backspace-t, mert valódi karcsúsítás lesz, hiszen a jelen feladatban nem az LZW algoritmus logikájával, hanem csak a'la nature kell a bináris fát felépíteni.

Megtehetnénk, hogy a túlterhelt << operátor implementációjából hívunk egy ugyanolyan rekurzív függvényt, mint a K&R hasonló funkciójú

struct tnode* tree (struct tnode*, char *)függvénye, de legyünk már egy kicsit kreatívabbak! (Esetünkben persze Csomopont* lenne a struct tnode* helyett.)

 void operator<<(std::string s)
    {
        int e;

        if (csomopont == NULL) {

            csomopont = new Csomopont (s);
            gyoker = csomopont;

        } else if ((e = csomopont->tartalma().compare(s)) == 0) {

            csomopont->novel();

        } else if (e > 0) {

            if (csomopont->balra() == NULL) {
                csomopont->balra(new Csomopont (s));
            } else {
                csomopont = csomopont->balra();
                *this << s;
            }

        } else if (e < 0) {

            if (csomopont->jobbra() == NULL) {
                csomopont->jobbra(new Csomopont (s));
            } else {
                csomopont = csomopont->jobbra();
                *this << s;
            }

        }

        csomopont = gyoker;

    }

 A "csomopont" mindig a gyökértől indul és oda mutat, ahová éppen megpróbáljuk beszúrni a kapott új szót. Kezdetben nincs fa (szemben az LZW-s példánkban a gyökér nem a szabad tárban, hanem a vermen ott volt alapban) ezért az első szóval az if ág felveszi a szót. Aztán a második szó, ha az elsővel egyezik tartalomra, akkor az első else if ág szerint csak növeljük az aktuális csomópont számlálóját, ha kisebb volt a szó, akkor a jobboldali, ha nagyobb akkor a bal oldali részfába (vagy pont fordítva :) kérjük újra a beszúrását.

Kattints a tovább linkre a teljes forrásért, illetve néhány alternatív "szó-számoló" megoldásért.