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.
// z6.cpp // // LZW fa építő 6. C++ átirata a C valtozatbol (ez már sima bináris fára) // Programozó Páternoszter // // Copyright (C) 2011, Bátfai Norbert, nbatfai@inf.unideb.hu, nbatfai@gmail.com // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/>. // // Ez a program szabad szoftver; terjeszthetõ illetve módosítható a // Free Software Foundation által kiadott GNU General Public License // dokumentumában leírtak; akár a licenc 3-as, akár (tetszõleges) késõbbi // változata szerint. // // Ez a program abban a reményben kerül közreadásra, hogy hasznos lesz, // de minden egyéb GARANCIA NÉLKÜL, az ELADHATÓSÁGRA vagy VALAMELY CÉLRA // VALÓ ALKALMAZHATÓSÁGRA való származtatott garanciát is beleértve. // További részleteket a GNU General Public License tartalmaz. // // A felhasználónak a programmal együtt meg kell kapnia a GNU General // Public License egy példányát; ha mégsem kapta meg, akkor // tekintse meg a <http://www.gnu.org/licenses/> oldalon. // // // Version history: // // 0.0.1, http://progpater.blog.hu/2011/02/19/gyonyor_a_tomor // 0.0.2, csomópontok mutatóinak NULLázása (nem fejtette meg senki :) // 0.0.3, http://progpater.blog.hu/2011/03/05/labormeres_otthon_avagy_hogyan_dolgozok_fel_egy_pedat // 0.0.4, z.cpp: a C verzióból svn: bevezetes/C/ziv/z.c átírjuk C++-ra // http://progpater.blog.hu/2011/03/31/imadni_fogjatok_a_c_t_egy_emberkent_tiszta_szivbol // 0.0.5, z2.cpp: az fgv(*mut)-ok helyett fgv(&ref) // 0.0.6, z3.cpp: Csomopont beágyazva // http://progpater.blog.hu/2011/04/01/imadni_fogjak_a_c_t_egy_emberkent_tiszta_szivbol_2 // 0.0.7, z4.cpp: az fgv(*mut)-ok helyett fgv(&ref) // 0.0.8, z5.cpp: template változat // 0.0.9, z6.cpp: átírva sima bináris fára // http://progpater.blog.hu/2011/04/03/elmondtam_milliomezerszer_2 #include <iostream> #include <string> class BinFa { public: BinFa ():csomopont(0), gyoker(0) {} 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; } void kiir (void) { melyseg = 0; kiir (gyoker); } void szabadit (void) { szabadit (gyoker); } private: class Csomopont { public: Csomopont (std::string s):szo(s), hanyszor(1), bal (0), jobb (0) {}; ~Csomopont () {}; Csomopont *balra () { return bal; } Csomopont *jobbra () { return jobb; } void balra (Csomopont * bal) { this->bal = bal; } void jobbra (Csomopont * jobb) { this->jobb = jobb; } std::string& tartalma() { return szo; } void novel() { ++hanyszor; } int volt() { return hanyszor; } private: friend class BinFa; std::string szo; int hanyszor; Csomopont *bal; Csomopont *jobb; Csomopont (const Csomopont &); Csomopont & operator=(const Csomopont &); }; Csomopont *gyoker; Csomopont *csomopont; int melyseg; BinFa (const BinFa &); BinFa & operator=(const BinFa &); void kiir (Csomopont* elem) { if (elem != NULL) { ++melyseg; kiir (elem->jobb); // ez a postorder bejáráshoz képest // 1-el nagyobb mélység, ezért -1 for (int i = 0; i < melyseg; ++i) std::cout << "---"; std::cout << elem->tartalma() << "(" << elem->volt() << ", " << melyseg - 1 << ")" << std::endl; kiir (elem->bal); --melyseg; } } void szabadit (Csomopont * elem) { if (elem != NULL) { szabadit (elem->jobb); szabadit (elem->bal); delete elem; } } }; int main () { BinFa binFa; std::string s; while (std::cin >> s) { binFa << s; } /* binFa << "barack"; binFa << "alma"; binFa << "korte"; binFa << "alma"; binFa << "ribizli"; binFa << "dio"; binFa << "cseresznye"; binFa << "ribizli"; binFa << "ribizli"; binFa << "ribizli"; binFa << "banan"; binFa << "piszke"; binFa << "alma"; binFa << "ribizli"; binFa << "ribizli"; binFa << "ribizli"; binFa << "alma"; binFa << "banan"; */ binFa.kiir (); binFa.szabadit (); return 0; }
Egy asszociatív tárolós alternatíva
#include <iostream> #include <string> #include <map> int main () { std::string s; std::map<std::string, int> szoszmap; while (std::cin >> s) ++szoszmap[s]; for (std::map<std::string, int>::iterator iter = szoszmap.begin(); iter != szoszmap.end(); ++iter) std::cout << iter->first << ", " << iter->second << std::endl; return 0; }
