CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Sep 2008
    Posts
    70

    [RESOLVED] Priority Queue Sorting Incorrectly

    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.

  2. #2
    Join Date
    Sep 2008
    Posts
    70

    Re: [RESOLVED] Priority Queue Sorting Incorrectly

    nm, i misunderstood what the sort function does.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured