So i have been banging my head against a wall with this problem for awhile. I have also copy and pasted direct examples from the internet but nothing seems to sort it right. So can someone please just post what im doing wrong. Or just give me code to do it correctly.
Node Header
Code:
#ifndef _NODE_H
#define _NODE_H
#include <stdio.h>
class Node
{
public:
Node();
Node(int weight, char value, Node* left = NULL, Node* right = NULL);
~Node();
int GetWeight() const { return mWeight; }
char GetValue() const { return mValue; }
#ifdef _DEBUG
void Print() { printf("Weight: %d Value: %c", mWeight, mValue); }
#endif
private:
Node* pLeft;
Node* pRight;
int mWeight;
char mValue;
};
#endif
Node CPP
Code:
#include "Node.h"
Node::Node()
:pLeft(NULL)
,pRight(NULL)
,mWeight(0)
,mValue('\0')
{
}
// Left and right are default parameters of NULL
Node::Node(int weight, char value, Node* left , Node* right)
:pLeft(left)
,pRight(right)
,mWeight(weight)
,mValue(value)
{
}
Node::~Node()
{
}
Main
Code:
#include <stdio.h>
#include "Node.h"
#include <queue>
using namespace std;
/* Building a Tree
Step 1. Create a parentless node for each symbol. Each node should include the symbol and its probability.
Step 2. Select the two parentless nodes with the lowest probabilities.
Step 3. Create a new node which is the parent of the two lowest probability nodes.
Step 4. Assign the new node a probability equal to the sum of its children's probabilities.
Step 5. Repeat from Step 2 until there is only one parentless node left.
*/
struct CompareNodes
{
bool operator() (Node* weight1, Node* weight2)
{
return (weight1->GetWeight() > weight2->GetWeight());
}
};
void main()
{
// 1 Count the characters
int counts[256];
for(int a = 0; a < 256; ++a)
{
counts[a] = 0;
}
FILE* pFile = fopen("Data.txt", "rb");
if(pFile)
{
char temp = '\0';
while(temp != EOF)
{
temp = (char)fgetc(pFile);
// So we dont assign a -1 spot as we are reading temp after the while check
if(temp != EOF)
{
++counts[temp];
}
}
}
// Create a priority queue to sort are nodes
//priority_queue<Node*> nodeQueue;
priority_queue<Node*, vector<Node*>, CompareNodes> nodeQueue;
// Create all the nodes with values. But do not connect them
for(int a = 0; a < 256; ++a)
{
if(counts[a] != 0)
{
Node* temp = new Node(counts[a], a);
nodeQueue.push( temp );
}
}
fclose(pFile);
}
Would greatly appreciate any help. Thanks.