daily pastebin goal
27%
SHARE
TWEET

Untitled

a guest Jun 13th, 2018 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <string>
  2. #include <iostream>
  3. #include <queue>
  4. #include <stack>
  5.  
  6. using namespace std;
  7.  
  8. int frecv[256];
  9. class Iterator;
  10.  
  11. class NodA {
  12. private:
  13.     NodA * st;
  14.     NodA *dr;
  15.     char e;
  16. public:
  17.     friend class AB;
  18.     NodA(char c, NodA* st, NodA* dr) : e{ c }, st{ st }, dr{ dr } {}
  19.  
  20.     char getCaracter() {
  21.         return e;
  22.     }
  23.     NodA* getDr() {
  24.         return dr;
  25.     }
  26.     NodA* getSt() {
  27.         return st;
  28.     }
  29. };
  30.  
  31. queue< string> q;
  32.  
  33.  
  34.  
  35. class AB {
  36. private:
  37.     NodA * rad;
  38. public:
  39.     friend class Iterator;
  40.  
  41.  
  42.  
  43.     AB() {
  44.         rad = NULL;
  45.     }
  46.  
  47.  
  48.     NodA* getRad() {
  49.         return rad;
  50.     }
  51.  
  52.     void creeazaArb(NodA *dr, NodA *st, char e) {
  53.         rad->dr = dr;
  54.         rad->st = st;
  55.         rad->e = e;
  56.     }
  57.  
  58.     void creeazaFrunza(char e) {
  59.         this->rad = new NodA(e, NULL, NULL);
  60.     }
  61.  
  62.     void creeazaAB(const AB& st, char e, const AB& dr) {
  63.         //distrug vechiul arbore
  64.         distruge(this->rad);
  65.         //creez radacina
  66.         this->rad = new NodA(e, NULL, NULL);
  67.         //copiez subarborii
  68.         this->rad->st = copiere(st.rad);
  69.         this->rad->dr = copiere(dr.rad);
  70.     }
  71.  
  72.     NodA* copiere(NodA* p) const {
  73.         if (p != NULL) {
  74.             //creez radacina
  75.             NodA* pNew = new NodA(p->e, NULL, NULL);
  76.             pNew->st = copiere(p->st);
  77.             pNew->dr = copiere(p->dr);
  78.             return pNew;
  79.         }
  80.         return NULL;
  81.     }
  82.  
  83.     void distrugeSubarbori(NodA* p) {
  84.         if (p != NULL) {
  85.             distruge(p->st);
  86.             distruge(p->dr);
  87.         }
  88.     }
  89.  
  90.     void adaugaSubSt(const AB& st) {
  91.         //distrug vechii subarbori ai subarborelui stang
  92.         distrugeSubarbori(this->rad->st);
  93.         //copiez noul subarbore
  94.         this->rad->st = copiere(st.rad);
  95.     }
  96.  
  97.     void adaugaSubDr(const AB& dr) {
  98.         //distrug vechii subarbori ai subarborelui drept
  99.         distrugeSubarbori(this->rad->dr);
  100.         //copiez noul subarbore
  101.         this->rad->dr = copiere(dr.rad);
  102.     }
  103.  
  104.     char element() const {
  105.         return this->rad->e;
  106.     }
  107.  
  108.     AB stang() const {
  109.         AB ab;
  110.         ab.rad = copiere(rad->st);
  111.         return ab;
  112.     }
  113.  
  114.     AB drept() const {
  115.         AB ab;
  116.         ab.rad = copiere(rad->dr);
  117.         return ab;
  118.     }
  119.  
  120.     void distruge(NodA* p) {
  121.         if (p != NULL) {
  122.             distruge(p->st);
  123.             distruge(p->dr);
  124.             delete p;
  125.         }
  126.     }
  127.  
  128.     Iterator iterator();
  129.    
  130.  
  131. };
  132.  
  133. class Iterator {
  134. private:
  135.     AB a;
  136.     NodA* current;
  137.     std::stack<NodA*> st;
  138. public:
  139.  
  140.     friend class AB;
  141.  
  142.     explicit Iterator(AB& a) : a{ a } {
  143.         this->current = this->a.getRad();
  144.     }
  145.  
  146.     bool valid() {
  147.         return this->current != nullptr || !st.empty();
  148.     }
  149.  
  150.     char element() {
  151.         while (this->current != nullptr) {
  152.             this->st.push(this->current);
  153.             this->current = this->current->getSt();
  154.         }
  155.  
  156.         auto elem = this->st.top();
  157.         current = st.top();
  158.         st.pop();
  159.         return elem->getCaracter();
  160.  
  161.     }
  162.  
  163.     void urmator() {
  164.         this->current = this->current->getDr();
  165.     }
  166.  
  167. };
  168.  
  169.  
  170. inline Iterator AB::iterator() {
  171.     return Iterator(*this);
  172. }
  173.  
  174. class Nod {
  175. private:
  176.     int prioritate;
  177.     Nod *urm;
  178.     Nod *ant;
  179.     AB ab;
  180. public:
  181.     friend class CoadaPrioritati;
  182.     Nod(int prioritate, AB a) :prioritate{ prioritate }, ab{ a }, urm{ NULL }, ant{ NULL } {}
  183.  
  184.     AB getArbore() {
  185.         return ab;
  186.     }
  187.  
  188.     int getPrioritate() {
  189.         return prioritate;
  190.     }
  191. };
  192.  
  193.  
  194.  
  195. class CoadaPrioritati
  196. {
  197. private:
  198.     Nod * prim;
  199.     Nod *ultim;
  200. public:
  201.     CoadaPrioritati() {
  202.         prim = ultim = nullptr;
  203.     }
  204.  
  205.     void adaugaC(int p, AB a) {
  206.         Nod *nodNou = new Nod(p, a);
  207.         Nod *curent = prim;
  208.  
  209.         if (curent == nullptr) {
  210.             prim = ultim = nodNou;
  211.         }
  212.         else
  213.         {
  214.             while (curent != nullptr && curent->prioritate <= p) {
  215.                 curent = curent->urm;
  216.             }
  217.             if (curent == nullptr) {
  218.                 ultim->urm = nodNou;
  219.                 ultim = nodNou;
  220.             }
  221.             else if (curent == prim) {
  222.                 curent->ant = nodNou;
  223.                 nodNou->urm = curent;
  224.                 prim = nodNou;
  225.             }
  226.             else {
  227.                 curent->ant->urm = nodNou;
  228.                 nodNou->ant = curent->ant;
  229.                 nodNou->urm = curent;
  230.                 curent->ant = nodNou;
  231.             }
  232.         }
  233.     }
  234.  
  235.     Nod* sterge() {
  236.         Nod* nod = prim;
  237.         prim = prim->urm;
  238.         return  nod;
  239.     }
  240.  
  241.     size_t dim() {
  242.         Nod* p = prim;
  243.         size_t len = 0;
  244.         while (p != NULL) {
  245.             len++;
  246.             p = p->urm;
  247.         }
  248.         return len;
  249.     }
  250.     bool vida() {
  251.         if (prim = ultim = nullptr)
  252.             return true;
  253.         else
  254.             return false;
  255.     }
  256.     ~CoadaPrioritati() {
  257.         Nod *nod = prim;
  258.         while (nod != NULL)
  259.         {
  260.             Nod* p = nod;
  261.             nod = nod->urm;
  262.             delete p;
  263.         }
  264.     }
  265. };
  266.  
  267. void construireCod(string s, int frecv[]) {
  268.     for (int i = 0; i < 256; i++)
  269.         frecv[i] = 0;
  270.     for (const auto& elem : s) {
  271.         frecv[int(elem)] ++;
  272.     }
  273. }
  274.  
  275.  
  276. vector<string> coduri;
  277. vector<char> car;
  278.  
  279. void stocheazaCod(NodA* rad, string str)
  280. {
  281.     if (rad == NULL)
  282.         return;
  283.     if (rad->getCaracter() != '$') {
  284.         q.push(str);
  285.         coduri.push_back(str);
  286.         car.push_back(rad->getCaracter());
  287.     }
  288.     stocheazaCod(rad->getSt(), str + "0");
  289.     stocheazaCod(rad->getDr(), str + "1");
  290. }
  291. void codificaHuffman(string s, CoadaPrioritati& coada, AB& arb) {
  292.     construireCod(s, frecv);
  293.     for (int i = 0; i<256; i++) {
  294.         if (frecv[i] != 0) {
  295.         //  cout << char(i) << " " << frecv[i] << endl;
  296.             AB a;
  297.             a.creeazaFrunza(char(i));
  298.             coada.adaugaC(frecv[i], a);
  299.         }
  300.     }
  301.  
  302.     while (coada.dim() != 1) {
  303.         auto left = coada.sterge();
  304.         auto right = coada.sterge();
  305.         auto frecventa = left->getPrioritate() + right->getPrioritate();
  306.         arb.creeazaFrunza('$');
  307.         arb.creeazaAB(left->getArbore(), '$', right->getArbore());
  308.         coada.adaugaC(frecventa, arb);
  309.     }
  310.  
  311.     //stocheazaCod(coada.sterge()->getArbore().getRad(), "");
  312. }
  313.  
  314.  
  315.  
  316. /*string decodareHuffman(NodA* rad, string s)
  317. {
  318.     string ans = "";
  319.     NodA* curr = rad;
  320.     for (int i = 0; i < s.size(); i++)
  321.     {
  322.         if (s[i] == '0')
  323.             curr = curr->getSt();
  324.         else
  325.             curr = curr->getDr();
  326.  
  327.         // reached leaf node
  328.         if (curr->getSt() == nullptr and curr->getDr() == nullptr)
  329.         {
  330.             ans += curr->getCaracter();
  331.             curr = rad;
  332.         }
  333.     }
  334.     // cout<<ans<<endl;
  335.     return ans + '\0';
  336. }*/
  337.  
  338.  
  339. string decodareHuffman(string s)
  340. {
  341.     int ok = 0;
  342.     string ans = "";
  343.     string caracter = "";
  344.     for (int i = 0; i < s.size(); i++) {
  345.         ok = 0;
  346.         for (int j = 0; j < coduri.size(); j++)
  347.             if (caracter == coduri[j]) {
  348.                 caracter = "";
  349.                 ans += car[j];
  350.                 ok = 1;
  351.             }
  352.         if (ok == 0)
  353.             caracter += s[i];
  354.     }
  355.     return ans;
  356. }
  357.  
  358.  
  359. int main() {
  360.     CoadaPrioritati coada;
  361.     string str = "rog";
  362.     string codare, decodare;
  363.     AB ab;
  364.     codificaHuffman(str, coada, ab);
  365.     auto nd = coada.sterge();
  366.     stocheazaCod(nd->getArbore().getRad(), "");
  367.  
  368.     Iterator it = ab.iterator();
  369.     while (it.valid()) {
  370.         auto elem = it.element();
  371.         if (elem != '$') {
  372.             std::cout << elem << "  " << q.front() << endl;
  373.             q.pop();
  374.         }
  375.         it.urmator();
  376.     }
  377.     string a = decodareHuffman("010001011");
  378.     cout << a;
  379.     return 0;
  380. }
RAW Paste Data
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
 
Top