API tools faq
paste
Advertisement
Guest User

lzwbin_beauty

a guest
Mar 27th, 2013
131
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 27.73 KB | None | 0 0
raw download clone embed print report
  1. /*$T indentinput.cpp GC 1.140 03/26/13 23:33:53 */
  2.  
  3. /*
  4.  * z3a7.cpp ;
  5.  * * Együtt támadjuk meg:
  6.  * http://progpater.blog.hu/2011/04/14/egyutt_tamadjuk_meg ;
  7.  * LZW fa építő 3. C++ átirata a C valtozatbol (+mélység, atlag és
  8.  * szórás) ;
  9.  * Programozó Páternoszter ;
  10.  * * Copyright (C) 2011, 2012, Bátfai Norbert, [email protected],
  11.  * [email protected] ;
  12.  * * This program is free software: you can redistribute it and/or modify ;
  13.  * it under the terms of the GNU General Public License as published by ;
  14.  * the Free Software Foundation, either version 3 of the License, or ;
  15.  * (at your option) any later version. ;
  16.  * * This program is distributed in the hope that it will be useful, ;
  17.  * but WITHOUT ANY WARRANTY;
  18.  * without even the implied warranty of ;
  19.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;
  20.  * GNU General Public License for more details. ;
  21.  * * You should have received a copy of the GNU General Public License ;
  22.  * along with this program. If not, see <http://www.gnu.org/licenses/>. ;
  23.  * * Ez a program szabad szoftver;
  24.  * terjeszthetõ illetve módosítható a ;
  25.  * Free Software Foundation által kiadott GNU General Public License ;
  26.  * dokumentumában leírtak;
  27.  * akár a licenc 3-as, akár (tetszõleges) késõbbi ;
  28.  * változata szerint. ;
  29.  * * Ez a program abban a reményben kerül közreadásra, hogy hasznos lesz, ;
  30.  * de minden egyéb GARANCIA NÉLKÜL, az ELADHATÓSÁGRA vagy VALAMELY CÉLRA ;
  31.  * VALÓ ALKALMAZHATÓSÁGRA való származtatott garanciát is beleértve. ;
  32.  * További részleteket a GNU General Public License tartalmaz. ;
  33.  * * A felhasználónak a programmal együtt meg kell kapnia a GNU General ;
  34.  * Public License egy példányát;
  35.  * ha mégsem kapta meg, akkor ;
  36.  * tekintse meg a <http://www.gnu.org/licenses/> oldalon. ;
  37.  * * ;
  38.  * Version history: ;
  39.  * * 0.0.1, http://progpater.blog.hu/2011/02/19/gyonyor_a_tomor ;
  40.  * 0.0.2, csomópontok mutatóinak NULLázása (nem fejtette meg senki :) ;
  41.  * 0.0.3,
  42.  * http://progpater.blog.hu/2011/03/05/labormeres_otthon_avagy_hogyan_dolgozok_fel_egy_pedat
  43.  * ;
  44.  * 0.0.4, z.cpp: a C verzióból svn: bevezetes/C/ziv/z.c átírjuk C++-ra ;
  45.  * http://progpater.blog.hu/2011/03/31/imadni_fogjatok_a_c_t_egy_emberkent_tiszta_szivbol
  46.  * ;
  47.  * 0.0.5, z2.cpp: az fgv(*mut)-ok helyett fgv(&ref) ;
  48.  * 0.0.6, z3.cpp: Csomopont beágyazva ;
  49.  * http://progpater.blog.hu/2011/04/01/imadni_fogjak_a_c_t_egy_emberkent_tiszta_szivbol_2
  50.  * ;
  51.  * 0.0.6.1 z3a2.c: LZWBinFa már nem barátja a Csomopont-nak, mert annak tagjait
  52.  * nem használja direktben ;
  53.  * 0.0.6.2 Kis kommentezést teszünk bele 1. lépésként (hogy a kicsit lemaradt
  54.  * hallgatóknak is ;
  55.  * könnyebb legyen, jól megtűzdeljük további olvasmányokkal) ;
  56.  * http://progpater.blog.hu/2011/04/14/egyutt_tamadjuk_meg ;
  57.  * (majd a 2. lépésben "beletesszük a d.c-t", majd s 3. lépésben a
  58.  * parancssorsor argok feldolgozását) ;
  59.  * 0.0.6.3 z3a2.c: Fejlesztgetjük a forrást:
  60.  * http://progpater.blog.hu/2011/04/17/a_tizedik_tizenegyedik_labor ;
  61.  * 0.0.6.4 SVN-beli,
  62.  * http://www.inf.unideb.hu/~nbatfai/p1/forrasok-SVN/bevezetes/vedes/ ;
  63.  * 0.0.6.5 2012.03.20, z3a4.cpp: N betűk (hiányok), sorvégek, vezető komment
  64.  * figyelmen kívül: http://progpater.blog.hu/2012/03/20/a_vedes_elokeszitese ;
  65.  * 0.0.6.6 z3a5.cpp: mamenyaka kolléga észrevételére a több komment sor
  66.  * figyelmen kívül hagyása ;
  67.  * http://progpater.blog.hu/2012/03/20/a_vedes_elokeszitese/fullcommentlist/1#c16150365
  68.  * ;
  69.  * 0.0.6.7 Javaslom ezt a verziót választani védendő programnak ;
  70.  * 0.0.6.8 z3a7.cpp: pár kisebb javítás, illetve a védések támogatásához
  71.  * további komment a << ;
  72.  * eltoló operátort tagfüggvényként, illetve globális függvényként
  73.  * túlterhelő részekhez. ;
  74.  * http://progpater.blog.hu/2012/04/10/imadni_fogjak_a_c_t_egy_emberkent_tiszta_szivbol_4/fullcommentlist/1#c16341099
  75.  * ;
  76.  */
  77. #include <iostream> /* mert olvassuk a std::cin, írjuk a std::cout csatornákat */
  78. #include <cmath>    /* mert vonunk gyököt a szóráshoz: std::sqrt */
  79. #include <fstream>  /* fájlból olvasunk, írunk majd */
  80.  
  81. /*
  82.  =======================================================================================================================
  83.     Az LZWBinFa osztályban absztraháljuk az LZW algoritmus bináris fa építését. Az osztály definíciójába
  84.     beágyazzuk a fa egy csomópontjának az absztrakt jellemzését, ez lesz a beágyazott Csomopont osztály. Miért
  85.     ágyazzuk be? Mert külön nem szánunk neki szerepet, ezzel is jelezzük, hogy csak a fa részeként számiolunk
  86.     vele.
  87.  =======================================================================================================================
  88.  */
  89. class   LZWBinFa
  90. {
  91. /*
  92.  -----------------------------------------------------------------------------------------------------------------------
  93.  -----------------------------------------------------------------------------------------------------------------------
  94.  */
  95. public:
  96.  
  97.     /*
  98.      ===================================================================================================================
  99.         Szemben a bináris keresőfánkkal (BinFa osztály)
  100.         http://progpater.blog.hu/2011/04/12/imadni_fogjak_a_c_t_egy_emberkent_tiszta_szivbol_3 itt (LZWBinFa osztály) a fa
  101.         gyökere nem pointer, hanem a '/' betüt tartalmazó objektum, lásd majd a védett tagok között lent: Csomopont
  102.         gyoker;
  103.         A fa viszont már pointer, mindig az épülő LZW-fánk azon csomópontjára mutat, amit az input feldolgozása
  104.         során az LZW algoritmus logikája diktál: http://progpater.blog.hu/2011/02/19/gyonyor_a_tomor Ez a konstruktor
  105.         annyit csinál, hogy a fa mutatót ráállítja a gyökérre. (Mert ugye laboron, blogon, előadásban tisztáztuk,
  106.         hogy a tartalmazott tagok, most "Csomopont gyoker" konstruktora előbb lefut, mint a tagot tartalmazó LZWBinFa
  107.         osztály konstruktora, éppen a következő, azaz a fa=&gyoker OK.)
  108.      ===================================================================================================================
  109.      */
  110.     LZWBinFa() :
  111.     fa(&gyoker)
  112.     { }
  113.  
  114.     /*
  115.      ===================================================================================================================
  116.      ===================================================================================================================
  117.      */
  118.     ~   LZWBinFa()  { szabadit(gyoker.egyesGyermek()); szabadit(gyoker.nullasGyermek()); }
  119.  
  120.     /*
  121.      ===================================================================================================================
  122.         Tagfüggvényként túlterheljük a << operátort, ezzel a célunk, hogy felkeltsük a hallgató érdeklődését,
  123.         mert ekkor így nyomhatjuk a fába az inputot: binFa << b;
  124.         ahol a b egy '0' vagy '1'-es betű. Mivel tagfüggvény, így van rá "értelmezve" az aktuális (this "rejtett
  125.         paraméterként" kapott ) példány, azaz annak a fának amibe éppen be akarjuk nyomni a b betűt a tagjai (pl.:
  126.         "fa", "gyoker") használhatóak a függvényben. A függvénybe programoztuk az LZW fa építésének algoritmusát
  127.         tk.: http://progpater.blog.hu/2011/02/19/gyonyor_a_tomor a b formális param az a betű, amit éppen be kell nyomni
  128.         a fába. a binFa << b (ahol a b majd a végén látszik, hogy már az '1' vagy a '0') azt jelenti
  129.         tagfüggvényként, hogy binFa.operator<<(b) (globálisként így festene: operator<<(binFa, b) )
  130.      ===================================================================================================================
  131.      */
  132.     void operator<<(char b)
  133.     {
  134.  
  135.         /* Mit kell betenni éppen, '0'-t? */
  136.         if(b == '0')
  137.         {
  138.  
  139.             /*
  140.              * Van '0'-s gyermeke az aktuális csomópontnak? megkérdezzük Tőle, a "fa"
  141.              * mutató éppen reá mutat
  142.              */
  143.             if(!fa->nullasGyermek())    /* ha nincs, hát akkor csinálunk */
  144.             {
  145.  
  146.                 /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
  147.                 /* elkészítjük, azaz páldányosítunk a '0' betű akt. parammal */
  148.                 Csomopont   *uj = new Csomopont('0');
  149.                 /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
  150.  
  151.                 /*
  152.                  * az aktuális csomópontnak, ahol állunk azt üzenjük, hogy ;
  153.                  * jegyezze már be magának, hogy nullás gyereke mostantól van ;
  154.                  * küldjük is Neki a gyerek címét:
  155.                  */
  156.                 fa->ujNullasGyermek(uj);
  157.  
  158.                 /* és visszaállunk a gyökérre (mert ezt diktálja az alg.) */
  159.                 fa = &gyoker;
  160.             }
  161.             else    /* ha van, arra rálépünk */
  162.             {
  163.  
  164.                 /* azaz a "fa" pointer már majd a szóban forgó gyermekre mutat: */
  165.                 fa = fa->nullasGyermek();
  166.             }
  167.         }
  168.  
  169.         /* Mit kell betenni éppen, vagy '1'-et? */
  170.         else
  171.         {
  172.             if(!fa->egyesGyermek())
  173.             {
  174.                 /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
  175.                 Csomopont   *uj = new Csomopont('1');
  176.                 /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
  177.  
  178.                 fa->ujEgyesGyermek(uj);
  179.                 fa = &gyoker;
  180.             }
  181.             else
  182.             {
  183.                 fa = fa->egyesGyermek();
  184.             }
  185.         }
  186.     }
  187.  
  188.     /*
  189.      ===================================================================================================================
  190.         A bejárással kapcsolatos függvényeink (túlterhelt kiir-ók, atlag, ratlag stb.) rekurzívak, tk. a rekurzív
  191.         fabejárást valósítják meg (lásd a 3. előadás "Fabejárás" c. fóliáját és társait) (Ha a rekurzív
  192.         függvénnyel általában gondod van => K&R könyv megfelelő része: a 3. ea. izometrikus részében ezt
  193.         "letáncoltuk" :) és külön idéztük a K&R álláspontját::)
  194.      ===================================================================================================================
  195.      */
  196.     void kiir(void)
  197.     {
  198.  
  199.         /*
  200.          * Sokkal elegánsabb lenne (és más, a bevezetésben nem kibontandó reentráns
  201.          * kérdések miatt is, mert ;
  202.          * ugye ha most két helyről hívják meg az objektum ilyen függvényeit, tahát
  203.          * ha kétszer kezd futni az ;
  204.          * objektum kiir() fgv.-e pl., az komoly hiba, mert elromlana a mélység...
  205.          * tehát a mostani megoldásunk ;
  206.          * nem reentráns) ha nem használnánk a C verzióban globális változókat, a
  207.          * C++ változatban példánytagot a ;
  208.          * mélység kezelésére: http://progpater.blog.hu/2011/03/05/there_is_no_spoon
  209.          */
  210.         melyseg = 0;
  211.  
  212.         /*
  213.          * ha nem mondta meg a hívó az üzenetben, hogy hova írjuk ki a fát, akkor a ;
  214.          * sztenderd out-ra nyomjuk
  215.          */
  216.         kiir(&gyoker, std::cout);
  217.     }
  218.  
  219.     /*
  220.      * már nem használjuk, tartalmát a dtor hívja void szabadit (void) { szabadit
  221.      * (gyoker.egyesGyermek ());
  222.      * szabadit (gyoker.nullasGyermek ());
  223.      * // magát a gyökeret nem szabadítjuk, hiszen azt nem mi foglaltuk a szabad
  224.      * tárban (halmon). } ;
  225.      * A változatosság kedvéért ezeket az osztálydefiníció (class LZWBinFa {...};
  226.      * ) után definiáljuk, hogy kénytelen légy az LZWBinFa és a :: hatókör
  227.      * operátorral minősítve definiálni :) l. lentebb
  228.      */
  229.     int     getMelyseg(void);
  230.     double  getAtlag(void);
  231.     double  getSzoras(void);
  232.  
  233.     /*
  234.      * Vágyunk, hogy a felépített LZW fát ki tudjuk nyomni ilyenformán: std::cout
  235.      * << binFa;
  236.      * de mivel a << operátor is a sztenderd névtérben van, de a using namespace
  237.      * std-t elvből nem használjuk bevezető kurzusban, így ez a konstrukció csak
  238.      * az argfüggő névfeloldás miatt fordul le (B&L könyv 185. o. teteje) ám itt
  239.      * nem az a lényeg, hanem, hogy a cout ostream osztálybeli, így abban az
  240.      * osztályban kéne módosítani, hogy tudjon kiírni LZWBinFa
  241.      * osztálybelieket... e helyett a globális << operátort terheljük túl, a
  242.      * kiFile << binFa azt jelenti, hogy - tagfüggvényként:
  243.      * kiFile.operator<<(binFa) de ehhez a kiFile valamilyen std::ostream stream
  244.      * osztály forrásába kellene beleírni ezt a tagfüggvényt, amely ismeri a mi
  245.      * LZW binfánkat... - globális függvényként: operator<<(kiFile, binFa) és
  246.      * pont ez látszik a következő sorban:
  247.      */
  248.     friend std::ostream & operator <<(std::ostream & os, LZWBinFa & bf)
  249.     {
  250.         bf.kiir(os);
  251.         return os;
  252.     }
  253.  
  254.     /*
  255.      ===================================================================================================================
  256.      ===================================================================================================================
  257.      */
  258.     void    kiir(std::ostream & os)     { melyseg = 0; kiir(&gyoker, os); }
  259.  
  260. /*
  261.  -----------------------------------------------------------------------------------------------------------------------
  262.  -----------------------------------------------------------------------------------------------------------------------
  263.  */
  264. private:
  265.     class   Csomopont
  266.     {
  267.     public:
  268.  
  269.         /*
  270.          * A paraméter nélküli konstruktor az elepértelmezett '/' "gyökér-betűvel"
  271.          * hozza létre a csomópontot, ilyet hívunk a fából, aki tagként tartalmazza
  272.          * a gyökeret. Máskülönben, ha valami betűvel hívjuk, akkor azt teszi a
  273.          * "betu" tagba, a két gyermekre mutató mutatót pedig nullra állítjuk,
  274.          * C++-ban a 0 is megteszi.
  275.          */
  276.         Csomopont (char b = '/')
  277.         :
  278.         betu(b),
  279.         balNulla(0),
  280.         jobbEgy(0)
  281.         { };
  282.         ~Csomopont()
  283.         { };
  284.  
  285.         /*
  286.          ===============================================================================================================
  287.             Aktuális csomópont, mondd meg nékem, ki a bal oldali gyermeked ;
  288.             (a C verzió logikájával műxik ez is: ha nincs, akkor a null megy vissza)
  289.          ===============================================================================================================
  290.          */
  291.         Csomopont *nullasGyermek() const
  292.         {
  293.             return balNulla;
  294.         }
  295.  
  296.         /*
  297.          ===============================================================================================================
  298.             Aktuális csomópon,t mondd meg nékem, ki a jobb oldali gyermeked?
  299.          ===============================================================================================================
  300.          */
  301.         Csomopont *egyesGyermek() const
  302.         {
  303.             return jobbEgy;
  304.         }
  305.  
  306.         /*
  307.          ===============================================================================================================
  308.             Aktuális csomópont, ímhol legyen a "gy" mutatta csomópont a bal oldali gyereked!
  309.          ===============================================================================================================
  310.          */
  311.         void    ujNullasGyermek(Csomopont *gy)  { balNulla = gy; }
  312.  
  313.         /*
  314.          ===============================================================================================================
  315.             Aktuális csomópont, ímhol legyen a "gy" mutatta csomópont a jobb oldali gyereked!
  316.          ===============================================================================================================
  317.          */
  318.         void    ujEgyesGyermek(Csomopont *gy)   { jobbEgy = gy; }
  319.  
  320.         /*
  321.          ===============================================================================================================
  322.             Aktuális csomópont: Te milyen betűt hordozol? ;
  323.             (a const kulcsszóval jelezzük, hogy nem bántjuk a példányt)
  324.          ===============================================================================================================
  325.          */
  326.         char getBetu() const
  327.         {
  328.             return betu;
  329.         }
  330.  
  331.     private:
  332.  
  333.         /*
  334.          * friend class LZWBinFa;
  335.          * /* mert ebben a valtozatban az LZWBinFa metódusai nem közvetlenül ;
  336.          * a Csomopont tagjaival dolgoznak, hanem beállító/lekérdező üzenetekkel
  337.          * érik el azokat ;
  338.          * Milyen betűt hordoz a csomópont
  339.          */
  340.         char        betu;
  341.  
  342.         /*
  343.          * Melyik másik csomópont a bal oldali gyermeke? (a C változatból "örökölt"
  344.          * logika: ;
  345.          * ha hincs ilyen csermek, akkor balNulla == null) igaz
  346.          */
  347.         Csomopont   *balNulla;
  348.         Csomopont   *jobbEgy;
  349.  
  350.         /*
  351.          * nem másolható a csomópont (ökörszabály: ha van valamilye a szabad
  352.          * tárban, ;
  353.          * letiltjuk a másoló konstruktort, meg a másoló értékadást)
  354.          */
  355.         Csomopont (const Csomopont &);
  356.         Csomopont &operator =(const Csomopont &);
  357.     };
  358.  
  359.     /* Mindig a fa "LZW algoritmus logikája szerinti aktuális" csomópontjára mutat */
  360.     Csomopont           *fa;
  361.  
  362.     /* technikai */
  363.     int                 melyseg, atlagosszeg, atlagdb;
  364.     double              szorasosszeg;
  365.  
  366.     /* szokásosan: nocopyable */
  367.     LZWBinFa(const LZWBinFa &);
  368.     LZWBinFa &operator  =(const LZWBinFa &);
  369.  
  370.     /*-
  371.      ==-=================================================================================================================
  372.        - Kiírja a csomópontot az os csatornára. A rekurzió kapcsán lásd a korábbi K&R-es utalást...
  373.      ==-=================================================================================================================
  374.      */
  375.     void kiir(Csomopont * elem, std::ostream & os)
  376.     {
  377.  
  378.         /* Nem létező csomóponttal nem foglalkozunk... azaz ez a rekurzió leállítása */
  379.         if(elem != NULL)
  380.         {
  381.             ++melyseg;
  382.             kiir(elem->egyesGyermek(), os);
  383.  
  384.             /*
  385.              * ez a postorder bejáráshoz képest ;
  386.              * 1-el nagyobb mélység, ezért -1
  387.              */
  388.             for(int i = 0; i < melyseg; ++i) os << "---";
  389.             os << elem->getBetu() << "(" << melyseg - 1 << ")" << std::endl;
  390.             kiir(elem->nullasGyermek(), os);
  391.             --melyseg;
  392.         }
  393.     }
  394.  
  395.     /*
  396.      ===================================================================================================================
  397.      ===================================================================================================================
  398.      */
  399.     void szabadit(Csomopont *elem)
  400.     {
  401.  
  402.         /* Nem létező csomóponttal nem foglalkozunk... azaz ez a rekurzió leállítása */
  403.         if(elem != NULL)
  404.         {
  405.             szabadit(elem->egyesGyermek());
  406.             szabadit(elem->nullasGyermek());
  407.  
  408.             /*
  409.              * ha a csomópont mindkét gyermekét felszabadítottuk ;
  410.              * azután szabadítjuk magát a csomópontot:
  411.              */
  412.             delete elem;
  413.         }
  414.     }
  415.  
  416. /*
  417.  -----------------------------------------------------------------------------------------------------------------------
  418.  -----------------------------------------------------------------------------------------------------------------------
  419.  */
  420. protected:  /* ha esetleg egyszer majd kiterjesztjük az osztályt, mert */
  421.     /*
  422.      * akarunk benne valami újdonságot csinálni, vagy meglévő tevékenységet
  423.      * máshogy... stb. ;
  424.      * akkor ezek látszanak majd a gyerek osztályban is ;
  425.      * A fában tagként benne van egy csomópont, ez erősen ki van tüntetve, Ő a
  426.      * gyökér:
  427.      */
  428.     Csomopont   gyoker;
  429.     int         maxMelyseg;
  430.     double      atlag, szoras;
  431.  
  432.     void        rmelyseg(Csomopont *elem);
  433.     void        ratlag(Csomopont *elem);
  434.     void        rszoras(Csomopont *elem);
  435. };
  436.  
  437. /*
  438.  =======================================================================================================================
  439.     Néhány függvényt az osztálydefiníció után definiálunk, hogy lássunk ilyet is ... :) ;
  440.     Nem erőltetjük viszont a külön fájlba szedést, mert a sablonosztályosított tovább ;
  441.     fejlesztésben az linkelési gondot okozna, de ez a téma már kivezet a laborteljesítés ;
  442.     szükséges feladatából: http://progpater.blog.hu/2011/04/12/imadni_fogjak_a_c_t_egy_emberkent_tiszta_szivbol_3 ;
  443.     Egyébként a melyseg, atlag és szoras fgv.-ek a kiir fgv.-el teljesen egy kaptafa.
  444.  =======================================================================================================================
  445.  */
  446. int LZWBinFa::getMelyseg(void)
  447. {
  448.     melyseg = maxMelyseg = 0;   //változók resetelése
  449.     rmelyseg(&gyoker);          //számítás
  450.     return maxMelyseg - 1;
  451. }
  452.  
  453. /*
  454.  =======================================================================================================================
  455.  =======================================================================================================================
  456.  */
  457. double LZWBinFa::getAtlag(void)
  458. {
  459.     melyseg = atlagosszeg = atlagdb = 0;
  460.     ratlag(&gyoker);
  461.     atlag = ((double) atlagosszeg) / atlagdb;
  462.     return atlag;
  463. }
  464.  
  465. /*
  466.  =======================================================================================================================
  467.  =======================================================================================================================
  468.  */
  469. double LZWBinFa::getSzoras(void)
  470. {
  471.     atlag = getAtlag();
  472.     szorasosszeg = 0.0;
  473.     melyseg = atlagdb = 0;
  474.  
  475.     rszoras(&gyoker);
  476.  
  477.     if(atlagdb - 1 > 0)
  478.         szoras = std::sqrt(szorasosszeg / (atlagdb - 1));
  479.     else
  480.         szoras = std::sqrt(szorasosszeg);
  481.  
  482.     return szoras;
  483. }
  484.  
  485. /*
  486.  =======================================================================================================================
  487.  =======================================================================================================================
  488.  */
  489. void LZWBinFa::rmelyseg(Csomopont *elem)
  490. {
  491.     if(elem != NULL)
  492.     {
  493.         ++melyseg;  //rekurzió mieatt beljebb lépünk
  494.         if(melyseg > maxMelyseg) maxMelyseg = melyseg;
  495.         rmelyseg(elem->egyesGyermek());
  496.  
  497.         /*
  498.          * ez a postorder bejáráshoz képest ;
  499.          * 1-el nagyobb mélység, ezért -1
  500.          */
  501.         rmelyseg(elem->nullasGyermek());
  502.         --melyseg;  //majd visszalépünk a rekurzív hívás után
  503.     }
  504. }
  505.  
  506. /*
  507.  =======================================================================================================================
  508.  =======================================================================================================================
  509.  */
  510. void LZWBinFa::ratlag(Csomopont *elem)
  511. {
  512.     if(elem != NULL)
  513.     {
  514.         ++melyseg;
  515.         ratlag(elem->egyesGyermek());
  516.         ratlag(elem->nullasGyermek());
  517.         --melyseg;
  518.         if(elem->egyesGyermek() == NULL && elem->nullasGyermek() == NULL)
  519.         {
  520.             ++atlagdb;
  521.             atlagosszeg += melyseg;
  522.         }
  523.     }
  524. }
  525.  
  526. /*
  527.  =======================================================================================================================
  528.  =======================================================================================================================
  529.  */
  530. void LZWBinFa::rszoras(Csomopont *elem)
  531. {
  532.     if(elem != NULL)
  533.     {
  534.         ++melyseg;
  535.         rszoras(elem->egyesGyermek());
  536.         rszoras(elem->nullasGyermek());
  537.         --melyseg;
  538.         if(elem->egyesGyermek() == NULL && elem->nullasGyermek() == NULL)
  539.         {
  540.             ++atlagdb;
  541.             szorasosszeg += ((melyseg - atlag) * (melyseg - atlag));   
  542.             /*  szórás számítása:
  543.              *  1. Kiszámítjuk az adatok számtani közepét.
  544.              *  2. Kiszámítjuk az adatok eltérését a számtani középtől (adat - számtani közép)
  545.              *  3. Vesszük ezeknek az eltéréseknek a négyzetét.
  546.              *  4. Kiszámítjuk ezeknek az "eltérés négyzeteknek" a számtani közepét.
  547.              *  5. Végül ebből négyzetgyököt vonunk.
  548.              */
  549.         }
  550.     }
  551. }
  552.  
  553. /*
  554.  =======================================================================================================================
  555.     teszt pl.: http://progpater.blog.hu/2011/03/05/labormeres_otthon_avagy_hogyan_dolgozok_fel_egy_pedat ;
  556.     [norbi@sgu ~]$ echo "01111001001001000111"|./z3a2 ;
  557.     ------------1(3)
  558.     ---------1(2)
  559.     ------1(1)
  560.     ---------0(2)
  561.     ------------0(3)
  562.     ---------------0(4)
  563.     ---/(0)
  564.     ---------1(2)
  565.     ------0(1)
  566.     ---------0(2)
  567.     depth = 4 ;
  568.     mean = 2.75 ;
  569.     var = 0.957427 ;
  570.     a laborvédéshez majd ezt a tesztelést használjuk: ;
  571.     http:// ;
  572.     Ez volt eddig a main, de most komplexebb kell, mert explicite bejövő, kimenő fájlokkal kell dolgozni int main
  573.     () { char b;
  574.     LZWBinFa binFa;
  575.     while (std::cin >> b) { binFa << b;
  576.     } //std::cout << binFa.kiir ();
  577.     // így rajzolt ki a fát a korábbi verziókban de, hogy izgalmasabb legyen // a példa, azaz ki lehessen tolni az
  578.     LZWBinFa-t kimeneti csatornára: std::cout << binFa;
  579.     // ehhez kell a globális operator<< túlterhelése, lásd fentebb std::cout << "depth = " << binFa.getMelyseg ()
  580.     << std::endl;
  581.     std::cout << "mean = " << binFa.getAtlag () << std::endl;
  582.     std::cout << "var = " << binFa.getSzoras () << std::endl;
  583.     binFa.szabadit ();
  584.     return 0;
  585.     } ;
  586.     A parancssor arg. kezelést egyszerűen bedolgozzuk a 2. hullám kapcsolódó feladatából:
  587.     http://progpater.blog.hu/2011/03/12/hey_mikey_he_likes_it_ready_for_more_3 de mivel nekünk sokkal egyszerűbb is
  588.     elég, alig hagyunk meg belőle valamit...
  589.  =======================================================================================================================
  590.  */
  591. void usage(void)
  592. {
  593.     std::cout << "Usage: lzwtree in_file -<switch> out_file" << std::endl << "Switches: -o: no draw; -d: draw; -p:print to screen (no draw)";
  594. }
  595.  
  596. /*
  597.  =======================================================================================================================
  598.  =======================================================================================================================
  599.  */
  600. int main(int argc, char *argv[])
  601. {
  602.    
  603.     /*
  604.      * http://progpater.blog.hu/2011/03/12/hey_mikey_he_likes_it_ready_for_more_3 ;
  605.      * alapján a parancssor argok ottani elegáns feldolgozásából kb. ennyi marad: ;
  606.      * "*((*++argv)+1)"... ;
  607.      * a kiírás szerint ./lzwtree in_file -o out_file alakra kell mennie, ez 4 db
  608.      * arg:
  609.      */
  610.  
  611.      /*Kirajzoljuk-e a fát?*/
  612.      bool drawMe = false;
  613.  
  614.     if(argc != 4)
  615.     {
  616.  
  617.         /* ha nem annyit kapott a program, akkor felhomályosítjuk erről a júzetr: */
  618.         usage();
  619.  
  620.         /* és jelezzük az operációs rendszer felé, hogy valami gáz volt... */
  621.         return -1;
  622.     }
  623.  
  624.     /*~~~~~~~~~~~~~~~~~~~~~~*/
  625.     /* "Megjegyezzük" a bemenő fájl nevét */
  626.     char    *inFile = *++argv;
  627.     /*~~~~~~~~~~~~~~~~~~~~~~*/
  628.  
  629.     /* a -o kapcsoló jön? */
  630.     char oSwitch = *((*++argv) + 1);
  631.     if(oSwitch != 'o' && oSwitch != 'd' )
  632.     {
  633.         std::cout << oSwitch;
  634.         usage();
  635.         return -2;
  636.     }
  637.  
  638.     if (oSwitch == 'd' )
  639.         drawMe = true;
  640.  
  641.     /* ha igen, akkor az 5. előadásból kimásoljuk a fájlkezelés C++ változatát: */
  642.     std::fstream beFile(inFile, std::ios_base::in);
  643.  
  644.     /*
  645.      * fejlesztgetjük a forrást:
  646.      * http://progpater.blog.hu/2011/04/17/a_tizedik_tizenegyedik_labor
  647.      */
  648.     if(!beFile)
  649.     {
  650.         std::cout << inFile << " nem letezik..." << std::endl;
  651.         usage();
  652.         return -3;
  653.     }
  654.  
  655.     std::fstream kiFile(*++argv, std::ios_base::out);
  656.  
  657.     /*~~~~~~~~~~~~~~~~~~*/
  658.     unsigned char   b;      /* ide olvassik majd a bejövő fájl bájtjait */
  659.     LZWBinFa        binFa;  /* s nyomjuk majd be az LZW fa objektumunkba */
  660.     /*~~~~~~~~~~~~~~~~~~*/
  661.  
  662.     /*
  663.      * a bemenetet binárisan olvassuk, de a kimenő fájlt már karakteresen írjuk,
  664.      * hogy meg tudjuk ;
  665.      * majd nézni... :) l. az említett 5. ea. C -> C++ gyökkettes átírási
  666.      * példáit
  667.      */
  668.     while(beFile.read((char *) &b, sizeof(unsigned char)))
  669.         if(b == 0x0a) break;
  670.  
  671.     /*~~~~~~~~~~~~~~~~~~~~~~~*/
  672.     bool    kommentben = false;
  673.     /*~~~~~~~~~~~~~~~~~~~~~~~*/
  674.  
  675.     while(beFile.read((char *) &b, sizeof(unsigned char)))
  676.     {
  677.         if(b == 0x3e)
  678.         {   /* > karakter */
  679.             kommentben = true;
  680.             continue;
  681.         }
  682.  
  683.         if(b == 0x0a)
  684.         {   /* újsor */
  685.             kommentben = false;
  686.             continue;
  687.         }
  688.  
  689.         if(kommentben) continue;
  690.         if(b == 0x4e)   /* N betű */
  691.             continue;
  692.  
  693.         /*
  694.          * egyszerűen a korábbi d.c kódját bemásoljuk ;
  695.          * laboron többször lerajzoltuk ezt a bit-tologatást: ;
  696.          * a b-ben lévő bájt bitjeit egyenként megnézzük
  697.          */
  698.         for(int i = 0; i < 8; ++i)
  699.         {
  700.  
  701.             /*
  702.              * maszkolunk eddig..., most már simán írjuk az if fejébe a legmagasabb
  703.              * helyiértékű bit vizsgálatát ;
  704.              * csupa 0 lesz benne a végén pedig a vizsgált 0 vagy 1, az if megmondja
  705.              * melyik:
  706.              */
  707.             if(b & 0x80)
  708.  
  709.                 /* ha a vizsgált bit 1, akkor az '1' betűt nyomjuk az LZW fa objektumunkba */
  710.                 binFa << '1';
  711.             else
  712.                 /* különben meg a '0' betűt: */
  713.                 binFa << '0';
  714.             b <<= 1;
  715.         }
  716.     }
  717.  
  718.     /*
  719.      * std::cout << binFa.kiir ();
  720.      * // így rajzolt ki a fát a korábbi verziókban de, hogy izgalmasabb legyen ;
  721.      * a példa, azaz ki lehessen tolni az LZWBinFa-t kimeneti csatornára:
  722.      */
  723.     if (drawMe == true)
  724.         kiFile << binFa;    /* ehhez kell a globális operator<< túlterhelése, lásd fentebb */
  725.  
  726.     /*
  727.      * (jó ez az OO, mert mi ugye nem igazán erre gondoltunk, amikor írtuk, mégis
  728.      * megy, hurrá)
  729.      */
  730.     kiFile << "depth = " << binFa.getMelyseg() << std::endl;
  731.     kiFile << "mean = " << binFa.getAtlag() << std::endl;
  732.     kiFile << "var = " << binFa.getSzoras() << std::endl;
  733.  
  734.     kiFile.close();
  735.     beFile.close();
  736.  
  737.     return 0;
  738. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!