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
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 ?
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;
}
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 :)
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.
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 :)
To samo, co wcześniej:
temp.push_back((node*) & kolejka.top());
...
kolejka.pop();
Może niech kolejka trzyma wskaźniki na obiekty klasy node.
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ć :)
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);
}
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;
}
int n = ilosc_z[100];
node* tab[n]; //<--- to jest niestandardowe.
int i = 0;
tab[i]->znak = znaki[i];
tab[i]->wartosc = ilosc_z[i];
tab[i]->left = 0;
tab[i]->right = 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;
}
O co tu chodzi?
for (int i = 0; i < ilosc_z[100]; ++i)
tab[i] = new node; // <--- (1)
...
for (int i = 0; i < n; ++i)
a.push_back(*(tab[i])); // <--- (2)
for (i = 0; i < n; ++i)
kolejka.push(&a[i]); // <--- (3)
Po co tworzysz n obiektów node (1), jeśli i tak je kopiujesz do vectora (2), a kolejce przypisujesz adresy kopii (3)? Nigdzie nie widzę, żebyś zwalniał te obiekty.
A przecież można to zrobić tak:
void Huffman::huffman()
{
a.resize(ilosc_z[100]);
for (int i = 0; i < a.size(); ++i)
{
a[i]->znak = znaki[i];
a[i]->wartosc = ilosc_z[i];
a[i]->left = 0;
a[i]->right = 0;
}
for (i = 0; i < a.size(); ++i)
kolejka.push(&a[i]);
while (kolejka.size() > 1) // <--- nie wiem, czy dobrze zrozumiałem sens tej pętli
{
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);
}
...
i na jedno wyjdzie.
no racja, wielkie dzieki
napisalem teraz przechodzenie, ale wyrzuca segmentation fault i znowu nie mam pojecia dlaczego debugger podkresla ta linijke (w komentarzu), bo przeciez w kodzie wyraznie jest wskaznik nastepnego elementu liscia na 0
wywolanie: inorder(z, c,0)
gdzie z i c to skladowe klasy (inorder jest wywolane z wewnatrz metody)
void inorder(node * n, char c[], int lenc)
{
using std::cout;
if (!(n->left)) // tutaj debugger podgresla, ze cos nie tak
{
cout << n->znak << " : ";
for (int i = 0; i < lenc; i++) cout << c[i];
cout << std::endl;
}
else
{
c[lenc] = '0';
inorder(n->left, c, lenc + 1);
c[lenc] = '1';
inorder(n->right, c, lenc + 1);
}
}
if (!(n->left))
{
...
}
else
{
...
inorder(n->left, c, lenc + 1); //<--- OK, 'left' na coś wskazuje
...
inorder(n->right, c, lenc + 1); //<--- w przypadku 'right' nie wiadomo...
}
nie wiem, mi sie wydawalo, ze nie trzeba sprawdzac "prawego" w ten sposob, ale nawet przy zrobieniu takiej "prowizorki" wyrzuca Segmentation
void inorder(node * n, char c[], int lenc)
{
using std::cout;
if (!(n->left))
{
cout << n->znak << " : ";
for (int i = 0; i < lenc; i++) cout << c[i];
cout << std::endl;
}
else
{
c[lenc] = '0';
inorder(n->left, c, lenc + 1);
if ((n->right))
{
c[lenc] = '1';
inorder(n->right, c, lenc + 1);
}
else if (!(n->right))
{
return;
}
}
}
Ja tu błędu nie widzę, widocznie coś nie tak z samym drzewem. Kiedy Ci się to sypie, od razu przy pierwszym odwołaniu?
Zakładam, że od czasu zbudowania drzewa funkcją huffman nie robiłeś nic z vectorem a.
if ((n->right))
{
...
}
else if (!(n->right)) //<--- przecież ten warunek wynika z tego wyżej ;)
{
...
}
nic nie ruszalem wektora a, od razu po wywolaniu tej metody wypisujacej drzewo segmentation (zadnego wierzcholka nie wypisuje)
Schrzaniłem jedną rzecz w metodzie huffman, w sumie dość idiotyczny błąd:
void Huffman::huffman()
{
for (int i = 0; i < ilosc_z[100]; ++i)
{
node* n = new node;
n->znak = znaki[i];
n->wartosc = ilosc_z[i];
n->left = 0;
n->right = 0;
kolejka.push(n);
}
while (kolejka.size() > 1)
{
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);
}
...
Wszystkie obiekty klasy node muszą być alokowane pojedynczo, w przeciwnym wypadku byłby problem z ich zwalnianiem. Definicję a możesz usunąć, bo nie jest już potrzebna.
od razu po wywolaniu tej metody wypisujacej drzewo segmentation (zadnego wierzcholka nie wypisuje)
No to z korzeniem coś nie tak. Sprawdź, czy go dobrze ustawiłeś/przypisałeś.
dzieki, teraz wszystko dziala :D
tylko musze zrobic druga kolejke o odwrotnym sortowaniu...
bo nie wiedziec czemu, znaki najczesciej wystepujace maja najdluzsze prefixy ? (a wydawalo mi sie ze taka kolejka zrobi to ok)