obejscie consta z push z priority_queue

0

        node * z = new node;

        node * x=z->left = kolejka.top();   // tutaj blad: Huffman.cpp:170: error: cannot convert ‘const Huffman::node’ to ‘Huffman::node*’ in assignment
        kolejka.pop();
        node * y = z->right = kolejka.top();
        kolejka.pop();

        z->wartosc = x->wartosc + y->wartosc;

        kolejka.push(z);

jak to obejsc ?

z gory dzieki za pomoc

0

poradzilem sobie, ale mam kolejny problem - ta metoda dziala blednie, dlaczego ? (dokladny opis w komentarzu)


Huffman::node * Huffman::huffman()
{
    int n = ilosc_z[100];   // w vector ilosc_z zapisano liczbe roznych znakow

    node * tab[n];
    for (int i = 0; i < ilosc_z[100]; ++i)
        tab[i] = new node;

    int i = 0;
    tab[i]->znak = znaki[i];
    tab[i]->wartosc = ilosc_z[i];
    tab[i]->left = tab[i + 1];
    tab[i]->right = tab[i + 2];
    tab[i]->parent = 0;

    for (int i = 1; i < n; ++i)
    {
        tab[i]->znak = znaki[i];
        tab[i]->wartosc = ilosc_z[i];
        tab[i]->left = tab[i + 1];
        tab[i]->right = tab[i + 2];
        tab[i]->parent = tab[i - 1];

    }

    std::vector<node> a;

    for (int i = 0; i < n; ++i)
        a.push_back(*(tab[i]));

    for (int i = 0; i < n; ++i)
        kolejka.push(a[i]);

    for (int i = 0; i < n; ++i)
    {
        node * z = new node;

        node * x = z->left = (node*) & kolejka.top();
        kolejka.pop();
        node * y = z->right = (node*) & kolejka.top();
        kolejka.pop();

        z->wartosc = x->wartosc + y->wartosc;

        kolejka.push(*z);

    }
    /*z -< allocate_node();
    x <- left[z] <- extract_min(q);
    y <- right[z] <- extract_min(q);
    f[z] <- f[x] + f[y];
    INSERT (Q, z);

    return EXTRACT_MIN(q)*/
    node * t = (node*) & kolejka.top();
    kolejka.pop();
    return t;

} 

pozniej gdy przechodze to drzewo to mam wszedzie:
(zamiast liczby wystapien) 0 i zamiast litery jakas losowo duza liczbe
jak to naprawic ?

0

zawezilem miejsce w ktorym jest blad, do mojej implementacji alg z Cormena

Huffman::node * Huffman::huffman()
{
    int n = ilosc_z[100];

    node * tab[n];
    for (int i = 0; i < ilosc_z[100]; ++i)
        tab[i] = new node;

    int i = 0;
    tab[i]->znak = znaki[i];
    tab[i]->wartosc = ilosc_z[i];
    tab[i]->left = tab[i + 1];
    tab[i]->right = tab[i + 2];
    tab[i]->parent = 0;

    for (int i = 1; i < n; ++i)
    {
        tab[i]->znak = znaki[i];
        tab[i]->wartosc = ilosc_z[i];
        tab[i]->left = tab[i + 1];
        tab[i]->right = tab[i + 2];
        tab[i]->parent = tab[i - 1];

    }

    std::vector<node> a;

    for (int i = 0; i < n; ++i)
        a.push_back(*(tab[i]));

    for (i = 0; i < n; ++i)
        kolejka.push(a[i]);

std::cout<<"rffd"<<(char)a[5].znak<<a[5].wartosc;  //do tad jest dobrze, 

//Ewidentnie nie dziala, moja implementacja huffmana z Cormena, tylko gdzie sa bledy?

    for (int i = 0; i < n; ++i)
    {
        node * z = new node;

        node * x = z->left = (node*) & kolejka.top();
        kolejka.pop();
        node * y = z->right = (node*) & kolejka.top();
        kolejka.pop();

        z->wartosc = x->wartosc + y->wartosc;

        kolejka.push(*z);

    }
    /*z -< allocate_node();
    x <- left[z] <- extract_min(q);
    y <- right[z] <- extract_min(q);
    f[z] <- f[x] + f[y];
    INSERT (Q, z);

    return EXTRACT_MIN(q)*/
    node * t = (node*) & kolejka.top();

    kolejka.pop();
    return t;

} 
0

zapomnialem podac mojego funktora z kolejki:


     struct Porownaj
    {

        bool operator()(const node& w1, const node & w2)

        {

            if (w1.wartosc < w2.wartosc) return true;
            if (w1.wartosc > w2.wartosc) return false;

            return false;
        }
    };

    std::priority_queue<node, std::vector<node>, Porownaj> kolejka;

moze ktos rzucic na to oko, wazne to dla mnie :)

0

A nie można po prostu:

bool operator()(const node& w1, const node & w2)
{
        return w1.wartosc < w2.wartosc;
}
node * x = z->left = (node*) & kolejka.top();
kolejka.pop();

Przypisujesz wskaźnik na obiekt, który w następnej linii usuwasz.

0

ok, rzeczywiscie, dzieki, poprawilem tak (ale teraz rzuca jakis glibc - zawartosc ponizej):

std::vector<node*> temp;

    for (int i = 0; i < n; ++i)
    {

        temp.push_back((node*) & kolejka.top());
        x = z->left = temp[i];
        kolejka.pop();
         temp.push_back((node*) & kolejka.top());
         y = z->right = temp[i+1];
        kolejka.pop();

        z->wartosc = x->wartosc + y->wartosc;

        kolejka.push(*z);

    } 

glibc:


*** glibc detected *** .../huffman: double free or corruption (!prev): 0x08113510 ***
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6(+0x6b591)[0x26d591]
/lib/tls/i686/cmov/libc.so.6(+0x6cde8)[0x26ede8]
/lib/tls/i686/cmov/libc.so.6(cfree+0x6d)[0x271ecd]
/usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0xaad741]
ulpit/c++/huffman/dist/Debug/GNU-Linux-x86/huffman[0x804bfcf]
Pulpit/c++/huffman/dist/Debug/GNU-Linux-x86/huffman[0x804b2ff]
/Pulpit/c++/huffman/dist/Debug/GNU-Linux-x86/huffman[0x804a120]
/Pulpit/c++/huffman/dist/Debug/GNU-Linux-x86/huffman[0x8049ae5]
/Pulpit/c++/huffman/dist/Debug/GNU-Linux-x86/huffman[0x80499ba]
/Pulpit/c++/huffman/dist/Debug/GNU-Linux-x86/huffman[0x804cac2]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe6)[0x218bd6]
Pulpit/c++/huffman/dist/Debug/GNU-Linux-x86/huffman[0x8048fa1]
======= Memory map: ========
00121000-00123000 r-xp 00000000 08:03 999445     /lib/tls/i686/cmov/libdl-2.11.1.so
00123000-00124000 r--p 00001000 08:03 999445     /lib/tls/i686/cmov/libdl-2.11.1.so
00124000-00125000 rw-p 00002000 08:03 999445     /lib/tls/i686/cmov/libdl-2.11.1.so
0018b000-001a6000 r-xp 00000000 08:03 1581077    /lib/ld-2.11.1.so
001a6000-001a7000 r--p 0001a000 08:03 1581077    /lib/ld-2.11.1.so
001a7000-001a8000 rw-p 0001b000 08:03 1581077    /lib/ld-2.11.1.so

jak to naprawic ? bo szczerze nie mam pojecia co to w ogóle jest :)

0

To samo, co wcześniej:

temp.push_back((node*) & kolejka.top());
...
kolejka.pop();

Może niech kolejka trzyma wskaźniki na obiekty klasy node.

0

przerobilem na wskazniki na elementy kolejki (dalej Segmentation Fault):

 for (int i = 0; i < n; ++i)
    {

        node ** z = (node **)new node;

        (*z)->left = (node *)kolejka.top();   //tutaj debugger wyrzuca Segmentation...
         node ** x = &(*z)->left;
        kolejka.pop();

        (*z)->right = (node*) kolejka.top();
        node ** y = &(*z)->right;
        kolejka.pop();

        (*z)->wartosc = (*x)->wartosc + (*y)->wartosc;

        kolejka.push(*z);

    }

fragment private z pliku deklaracji:


  struct Porownaj
  {

        bool operator()(const node* w1, const node * w2)
        {
                return (*w1).wartosc < (*w2).wartosc;
        }
};
   std::priority_queue<node*, std::vector<node*>, Porownaj> kolejka;

co tu dalej jest nie tak ? :) strasznie już długo na tym siedzę i nie mogę dalej ruszyć :)

0
for (int i = 0; i < n; ++i)
{
    node* z = new node;

    z->left = kolejka.top();
    kolejka.pop();

    z->right = kolejka.top();
    kolejka.pop();

    node* x = z->left;
    node* y = z->right;
    z->wartosc = x->wartosc + y->wartosc;

    kolejka.push(z);
}
0

dalej segmentation fault ;/ wrzuce caly projekt (zakomentowane rzeczy w sumie niewazne)

plik h

#ifndef _HUFFMAN_H
#define _HUFFMAN_H
#include <iostream>
#include <vector>
#include <map>
#include <fstream>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <climits>
#include <cstring>

//struct Porownaj;
//class Huffman;
//class node;
//node * head;

class Huffman
{
public:

    struct node
    {
        wchar_t znak;
        int wartosc;
        node * left;
        node * right;
        //node * parent;

    };
    //node * z;
private:

    struct Porownaj
    {

        bool operator()(const node* w1, const node * w2)
        {
            return (*w1).wartosc < (*w2).wartosc;
        }
    };
    std::wstring kopia;
    // std::map<char, int> mymap;
    std::vector<wchar_t> znaki;
    std::vector<int> ilosc_z;

    int liczba_liter;
    unsigned long long int licznik;
    std::priority_queue<node*, std::vector<node*>, Porownaj> kolejka;
    std::vector<node> a;

public:

    //node * head;

    //node **tab;

    void zlicz_liczbe_roznych_znakow();
    void otworz_txt();
    void huffman();

    void test()
    {
        // std::cout<<z->znak<<"  "<<z->wartosc<<std::endl;

        // inorder_tree_walk(1,z);

    }

        /*
      void inorder_tree_walk(int level,node *head)
    {
            node *tmp=head;
            if (tmp!=0)
            {
                    inorder_tree_walk(level+1,tmp->left);
                    node_out(level,tmp);
                    inorder_tree_walk(level+1,tmp->right);
            }
    }
    void node_out(int level, node *nd)
    {
            int i;
            for (i=1; i<level; ++i)
                    printf(" ");

            //printf("adres: %p, key: %d, left->%p, right->%p\n", nd, nd->znak, nd->left, nd->right);
            std::cout<<"  "<<nd->wartosc<<std::endl;
    }*/

    const int & get_liczba_liter()const
    {
        return liczba_liter;
    }

    void get_kopia() const
    {
        //std::cout<<kopia;
        for (int i = 0; i < kopia.size(); i++)
            std::cout << kopia[i];
    }

    const long long int & get_licznik()const
    {
        return licznik;
    }

};

#endif  /* _HUFFMAN_H */

plik cpp


#include "Huffman.h"
//#include "BST_tree.h"

void Huffman::otworz_txt()
{
    std::ifstream FILE;
    char name[20];
    //std::cout << "Podaj nazwe pliku (wraz z rozszerzeniem txt): ";
    //std::cin.getline(name, 20);
    FILE.open("plik.txt");
    if (!FILE.is_open())
    {
        std::cout << "Blad otwarcia pliku!\n";
        exit(EXIT_FAILURE);
    }

    unsigned long long int i = 0;

    wchar_t ch = FILE.get();
    while (FILE.good())
    {
        kopia.resize(10 + i);

        std::cout << "*";
        kopia[i] = ch;
        ch = FILE.get();
        ++i;

    }

    if (FILE.eof())
        std::cout << "Odczytano caly plik\n";

    else if (FILE.fail())
        std::cout << "NIe udalo sie odczytac pomyslnie plkiu :(\n";

    else
        std::cout << "Nieznany blad\n";

    FILE.close();

}

void Huffman::zlicz_liczbe_roznych_znakow()
{
    using namespace std;

    // map<char,int> mymap;
    // map<char,int>::iterator it;
    // pair < map<char, int>::iterator, bool> ret;
    vector<wchar_t>::iterator it;
    vector<int>::iterator t;

    liczba_liter = 0;
    licznik = 0;

    ilosc_z.reserve(102);

    while (kopia[licznik])
    {
        //char a=kopia[i];
        it = find(znaki.begin(), znaki.end(), kopia[licznik]);

        // it = znaki.find(kopia[licznik]);
        // char a = *it;

        if (it != znaki.end())
        {
            licznik++;

            //mymap.insert((*it).first, (*it).second +1);

            /* unsigned long long int t = it->second;
             map<char,int>::iterator copy;
             copy=it;*/
            // mymap.erase(copy);
            //mymap.insert ( pair<char,int>((*it).first,it->second + 1));
            // znaki. ( pair<char,int>(kopia[licznik],t+1));

            vector<wchar_t>::iterator t = it;
            int k = t - znaki.begin();

            ilosc_z[k] += 1;
            continue;

        }
        else
        {
            // char a=plik[i];
            //mymap.push_back (plik[i]);
            // mymap.insert ( pair<char,int>(kopia[licznik],1));

            znaki.push_back(kopia[licznik]);
            ilosc_z.push_back(1);
            ++liczba_liter;
            ++licznik;

        }

        ilosc_z[100] = liczba_liter; //a tak sobie wruce liczbe wsyzstkich znakow a oc :D

    }

    for (int i = 0; i < liczba_liter; ++i)
        cout << (char) znaki[i] << " => " << ilosc_z[i] << endl;

}

void Huffman::huffman()
{
    int n = ilosc_z[100];

    node * tab[n];
    for (int i = 0; i < ilosc_z[100]; ++i)
        tab[i] = new node;

    int i = 0;
    tab[i]->znak = znaki[i];
    tab[i]->wartosc = ilosc_z[i];
    tab[i]->left = 0;
    tab[i]->right = 0;
    // tab[i]->parent = 0;

    for (int i = 1; i < n; ++i)
    {
        tab[i]->znak = znaki[i];
        tab[i]->wartosc = ilosc_z[i];
        tab[i]->left = 0;
        tab[i]->right = 0;
        //   tab[i]->parent = 0;

    }

    // std::vector<node> a;

    for (int i = 0; i < n; ++i)
        a.push_back(*(tab[i]));

    for (i = 0; i < n; ++i)
        kolejka.push(&a[i]);

    // std::cout << "rffd" << (char) a[5].znak << a[5].wartosc; //do tad jest dobrze,
    // std::cout << "rffd" << kolejka.top()->znak << kolejka.top()->wartosc;
    //  z = new node;

    //Ewidentnie nie dziala, moja implementacja huffmana z Cormena, tylko gdzie sa bledy?

    /*  for (int i = 0; i <n; ++i)
      {
          z->left = kolejka.top();
          node * x = z->left;
  //       kolejka.pop();

          z->right = kolejka.top();
          node * y = z->right;
        //  kolejka.pop();

          z->wartosc = x->wartosc + y->wartosc;
          z->znak=-1;

          kolejka.push(z);

      }*/
    for (int i = 0; i < n; ++i)
    {
        node* z = new node;

        z->left = kolejka.top();
        kolejka.pop();

        z->right = kolejka.top();
        kolejka.pop();

        node* x = z->left;
        node* y = z->right;
        z->wartosc = x->wartosc + y->wartosc;

        kolejka.push(z);
    }
    // std::cout << "rffd" << (char) a[5].znak << a[5].wartosc; //do tad jest dobrze,
    /*z -< allocate_node();
    x <- left[z] <- extract_min(q);
    y <- right[z] <- extract_min(q);
    f[z] <- f[x] + f[y];
    INSERT (Q, z);

    return EXTRACT_MIN(q)*/
    //node * t = (node*) & kolejka.top();

    // kolejka.pop();
    // return t;

}

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0