[C++] priority queue huffman tree

[Verwijderd]

Ik ben voor school bezig aan een opdracht voor c++. Het is de bedoeling dat de huffman encoding geïmplementeerd wordt. Nu ben ik bezig met de HuffmanTree klasse die er als volgt uit ziet:

C++: HuffmanTree.cpp

#include <iostream.h>
#include <vector.h>
#include <stack.h>
#include <queue.h>

#include "HuffmanTree.h"
#include "Node.h"

Node _rootNode;
priority_queue<Node> pq;

HuffmanTree::HuffmanTree(){

}

bool operator<(Node a, Node b)
{
  return a.GetOccurence() < b.GetOccurence();
}

void HuffmanTree::CreateHuffmanTree(int *charOccurrence, int charsInEncoding)
{
    for(int i = 0; i < charsInEncoding; i++)
    {
        if(charOccurrence[i])
        {
            Node node((char)i, charOccurrence[i]);
            pq.push(node);
        }
    }

    //Test of het goed gaat.
    while(!pq.empty())
    {
        cout << "peek read: " << pq.top().GetChar() << endl;
        pq.pop();
    }
}

HuffmanTree::~HuffmanTree() {
}

C++: Node.cpp

#include <iostream.h>

#include "Node.h"

char _c;
int _occurrence;

Node::Node() {
}

Node::Node(char c, int occurrence) {
    _c = c;
    _occurrence = occurrence;
}

char Node::GetChar() const {
    return _c;
}

int Node::GetOccurence() const {
    //cout << "node occurence: " << _occurrence << endl;
    return _occurrence;
}

Node::~Node() {
}

Nu gaat er iets niet het helemaal lekker met de priority queue. Het lijkt wel of er niet ge-popt wordt. Voor het aantal nodes dat in de queue zit, krijg ik alleen het char van de laatste node te zien. Heeft iemand een idee hoe dit komt? Sorry als het een echte beginners vraag is, maar het is mijn eerste programma in c++.

Aanvulling:
Een node met de juiste waardes gaat er wel in, maar als ik de volgende code toevoeg in de while loop:

Node node = pq.top();
char c = node.GetChar();

blijft c de hele tijd y als ik na deze code een breakpoint neerzet.

Ik vraag btw niet om code. Ik vraag om een hint.

[ Voor 7% gewijzigd door Verwijderd op 17-02-2010 16:44 ]

[RobIII]

Verwijderd schreef op woensdag 17 februari 2010 @ 16:19:
Sorry als het een echte beginners vraag is, maar het is mijn eerste programma in c++.

Beginnersvraag of niet: heb je al gedebugged? (Debuggen: Hoe doe ik dat?).

Verwijderd schreef op woensdag 17 februari 2010 @ 16:19:
Het lijkt wel of er niet ge-popt wordt.

Dan is dat een goed punt om eens te gaan verifiëren

Ik mis dus een beetje wat we in onze Quickstart omschrijven; ik zie niet wat je al hebt geprobeerd (behalve de code die je nu hebt) om zelf tot een oplossing voor je probleem te komen. Je topic is dan al snel een scriptrequest en daar doen we hier niet aan. Dus bij deze zou ik graag alsnog de informatie die we in onze Quickstart van je verlangen in je topicstart zien Gebruik de edit knop ( ) daarvoor.

[ Voor 57% gewijzigd door RobIII op 17-02-2010 16:25 ]

[Soultaker]

Je probleem heeft niets met priority queues te maken. Je Node klasse werkt niet goed (en ja, het is een erg basic probleem). Ik zal je een grote hint geven, daar mag je zelf mee gaan debuggen, zoals RobIII ook suggereert:

C++:

Node n('a', 123), m('b', 456);
std::cout << n.GetChar() << ' ' << n.GetOccurence() << std::endl;
std::cout << m.GetChar() << ' ' << m.GetOccurence() << std::endl;

Aanvulling:
Een node met de juiste waardes gaat er wel in, maar als ik de volgende code toevoeg in de while loop: [..] blijft c de hele tijd y als ik na deze code een breakpoint neerzet.

y? of ÿ? Ik vermoed het laatste. Als je enig succes hoopt te boeken als programmeur, zul je nauwgezetter moeten werken dan je nu bezig bent. Dit verschil is wel relevant voor de verklaring van je probleem.

[Verwijderd]

[...]
y? of ÿ? Ik vermoed het laatste. Als je enig succes hoopt te boeken als programmeur, zul je nauwgezetter moeten werken dan je nu bezig bent. Dit verschil is wel relevant voor de verklaring van je probleem.

Nee het is niet een ÿ. Dan had ik dat uiteraard gezegd. Want zo nauwkeurig ben ik wel. Mss dat de rest van mijn programma een hoop verklaard.

C++: main.cpp

#include <stdlib.h>
#include <iostream.h>

#include "Counter.h"
#include "HuffmanTree.h"

//The number of different chars occurring in the text encoding used.
const int CHARS_IN_ENCODING = 127;

int main(int argc, char** argv)
{
    //Pointer to the array where the occurence is stored in.
    int *occurrenceArray;

    //Count the charoccurrence and display them.
    occurrenceArray = Counter::CountCharOccurence("SUSIE SAYS IT IS EASY.", CHARS_IN_ENCODING);
    Counter::DisplayCharOccurence(occurrenceArray, CHARS_IN_ENCODING);

    //Create the huffmantree using the occurence.
    HuffmanTree::CreateHuffmanTree(occurrenceArray, CHARS_IN_ENCODING);

    delete[] occurrenceArray;

    return 0;
}

C++:

int *Counter::CountCharOccurence(string text, int charsInEncoding)
{
    int *charOccurrence = new int[charsInEncoding];

    for(int i = 0; i < text.length(); i++)
    {
        charOccurrence[text[i]]++;
    }

    return charOccurrence;
}

[NC83]

Nog een hint heb je ook een .h file voor je node.cpp en kijk daar eens naar.

[user109731]

Soultaker schreef op woensdag 17 februari 2010 @ 17:05:
Je Node klasse werkt niet goed (en ja, het is een erg basic probleem).

De HuffmanTree class werkt ook niet goed, al heb je daar nu toevallig geen last van

[Verwijderd]

JanDM schreef op woensdag 17 februari 2010 @ 19:54:
[...]

De HuffmanTree class werkt ook niet goed, al heb je daar nu toevallig geen last van

Gaat het om hetzelfde probleem bij de twee klassen?

[RobIII]

Verwijderd schreef op woensdag 17 februari 2010 @ 20:21:
[...]


Gaat het om hetzelfde probleem bij de twee klassen?

Ga nou eerst eens debuggen. Jij hebt huiswerk. Jij moet er van leren. Niet wij
We zeggen met reden niet "daar zit de fout en zo los je 'm op"

[ Voor 57% gewijzigd door RobIII op 17-02-2010 20:22 ]

[Soultaker]

Verwijderd schreef op woensdag 17 februari 2010 @ 18:17:
Nee het is niet een ÿ. Dan had ik dat uiteraard gezegd. Want zo nauwkeurig ben ik wel. Mss dat de rest van mijn programma een hoop verklaard.

Vreemd; een ÿ had ik kunnen verklaren, maar een y niet. Anyway, heb je al naar de testcase gekeken die ik eerder postte? Naar mijn idee zul je daar toch echt mee moeten beginnen.

JanDM schreef op woensdag 17 februari 2010 @ 19:54:
De HuffmanTree class werkt ook niet goed, al heb je daar nu toevallig geen last van

Ongetwijfeld, maar laat de TS eerst maar eens de meest basale klasse die 'ie heeft debuggen voor je 'm er complexere datastructuren mee laat bouwen.

[NC83]

Soultaker schreef op woensdag 17 februari 2010 @ 21:38:
[...]

Vreemd; een ÿ had ik kunnen verklaren, maar een y niet. Anyway, heb je al naar de testcase gekeken die ik eerder postte? Naar mijn idee zul je daar toch echt mee moeten beginnen.

Die Y is heel makkelijk te verklaren als je naar de input string kijkt trouwens.

[Soultaker]

Oh, hoe dan? (Het is niet het laatste letter in de string, als je dat soms denkt!) En hebben we het nu over 'Y' of over 'y'? (Dat zijn precies het soort belangrijke verschillen waar ik het eerder over had!)

[ Voor 20% gewijzigd door Soultaker op 17-02-2010 23:03 ]

[matthijsln]

Soultaker schreef op woensdag 17 februari 2010 @ 23:02:
Oh, hoe dan? (Het is niet het laatste letter in de string, als je dat soms denkt!) En hebben we het nu over 'Y' of over 'y'? (Dat zijn precies het soort belangrijke verschillen waar ik het eerder over had!)

'Y' is de char in de input string met de hoogste ASCII waarde...

[Soultaker]

Ok, goed gezien. Maar dan hebben we het dus over 'Y' en niet over 'y', en ik zie ook niet zo 1-2-3 in waarom het grootste karakter speciaal zou zijn, want de priority queue sorteert op occurrence (niet op het karakter) en 'Y' komt niet als minste en ook niet als vaakste voor.

Het blijft giswerk natuurlijk, tot de TS al zijn code bij elkaar heeft gezet, en eindelijk wat gedebugt heeft.

* Soultaker neemt zich voor dit topic te negeren tot dat gebeurd is.

@mathijsln: je hebt helemaal gelijk.

[ Voor 29% gewijzigd door Soultaker op 18-02-2010 16:51 ]

[matthijsln]

'Y' is de parameter voor de aanroep van Node::Node() in de laatste iteratie van de for loop in HuffmanTree::CreateHuffmanTree() die loopt van 0 tot 126 waarbij alleen een Node wordt geconstrueerd indien de ascii waarde voorkomt in de input string

De grap is dat zelfs als de TS de bug fixt waardoor jouw stukje voorbeeldcode wel werkt als verwacht de door JanDM aangehaalde andere bug nog steeds roet in het eten gooit en mogelijk tot ditzelfde resultaat leidt (een beetje afhankelijk van de compiler)

[ Voor 33% gewijzigd door matthijsln op 18-02-2010 08:21 ]

[Verwijderd]

Beginnersvraag of niet: heb je al gedebugged? (Debuggen: Hoe doe ik dat?).

niet elke beginnersvraag komt van een beginner af. Er zitten ook programmeurs op dit forum die al jaren ervaring hebben maar nu voor het eerst met een andere taal in contact komen.

y? of ÿ? Ik vermoed het laatste. Als je enig succes hoopt te boeken als programmeur, zul je nauwgezetter moeten werken dan je nu bezig bent. Dit verschil is wel relevant voor de verklaring van je probleem.

zie jij ergens een y in de code erboven? hij bedoelt hier welk character dan ook.

Ga nou eerst eens debuggen. Jij hebt huiswerk. Jij moet er van leren. Niet wij
We zeggen met reden niet "daar zit de fout en zo los je 'm op"

als we op dit niveau van helpen blijven zitten komt die gozer er nooit al zal hij vast al een antwoord hebben gevonden na zoveel tijd.

als er bij dit forum geen zinnig antwoord wordt gegeven kan je net zo goed stackoverflow.com erbij pakken . ik zal hierbij mijn mond verder dichtsnoeren dit was alleen mijn commentaar op de situatie. tot ziens.

[NC83]

Gezien dit nu al te lang aan het duren is, het antwoord is dat de encapsulatie van je klasse niet goed is.

Je definieert variable als globals ipv member variables in node and huffman.

[matthijsln]

En een referentie naar een automatische variabele is niet meer geldig als die automatische variabele niet meer bestaat (priority_queue::top()).

[Verwijderd]

Hey Bedankt. Wist niet dat mijn topic nog in leven was. Verder ook nog niet aan mijn opdracht toegekomen. Ga er zo snel mogelijk naar kijken en weer in de C++ boeken duiken.

[.oisyn]

matthijsln schreef op dinsdag 23 februari 2010 @ 15:24:
En een referentie naar een automatische variabele is niet meer geldig als die automatische variabele niet meer bestaat (priority_queue::top()).

Even nittpicken, maar vergeet de term "automatic", het keyword "auto" krijgt in C++0x een andere betekenis. Noem het in plaats daarvan een lokale variabele.