C++ Απορία σε Δυαδικό Σωρό

[sp_steve]

Γεια σας,

 

Προσπαθώ να φτιάξω ένα δυαδικό σωρό και στο σώμα της main αντιμετωπίζω ένα πρόβλημα. Μου εμφανίζει το εξής μήνυμα : "istantiated from here" και μου μαρκάρει την εντολή heap.insert(i); όπως θα δείτε στον παρακάτω κώδικα.

 

>int main( )

{

int numItems = 1000;


BinaryHeap<class Comparable> heap( numItems );

int i = 37;

int x;

//try

//{

for( i = 37; i != 0; i = ( i + 37 ) % numItems ) 
{heap.insert( i );}

for( i = 1; i < numItems; i++ )

{

heap.deleteMin( x );

if( x != i ) cout << "Oops! " << i << endl;

}

for( i = 37; i != 0; i = ( i + 37 ) % numItems )

{heap.insert( i );}

heap.insert( 0 );

heap.insert( i = 999999 ); // Should overflow

//}

/*catch(Overflow )

{ cout << "Overflow (expected)! " << i << endl; }

catch(BinaryHeap::Underflow& s )

{ cout << "Underflow (expected)! " << i << endl; }*/

return 0;
system("PAUSE");
}

 

 

Μήπως μπορείτε να με βοηθήσετε?

Ευχαριστώ!

[warchief]

Εισαι σίγουρος οτι στο ακολουθο σημείο δεν παραπονιέται ο compiler:

 

>
BinaryHeap<class Comparable> heap( numItems );

[παπι]

Εισαι σίγουρος οτι στο ακολουθο σημείο δεν παραπονιέται ο compiler:

 

>
BinaryHeap<class Comparable> heap( numItems );

 

Κανενα προβλημα. (αν και δεν ειναι οτι πιο ομορφο )

Το προβλημα (λογικα) ειναι οτι το heap.insert παιρνει Τ (δλδ Comparable) ενω εσυ βαζεις int... Δυο πραγματα παιζουν.

1) Δεν εχεις καταλαβαει τι ακριβος κανεις

2) Ξεχασες να κανεις overload τον cast operator για int στο Comparable

[sp_steve]

Κανενα προβλημα. (αν και δεν ειναι οτι πιο ομορφο )

Το προβλημα (λογικα) ειναι οτι το heap.insert παιρνει Τ (δλδ Comparable) ενω εσυ βαζεις int... Δυο πραγματα παιζουν.

1) Δεν εχεις καταλαβαει τι ακριβος κανεις

2) Ξεχασες να κανεις overload τον cast operator για int στο Comparable

 

Θέλω να πιστεύω οτι ξέρω τι κάνω... Σορρυ αν κάνω χαζές ερωτήσεις αλλά δεν είμαι και έμπειρος προγραμματιστής. Μπορείς να μου πείς τι εννοείς στο 2)? Με ποιόν τρόπο το κάνω αυτό?

[παπι]

Θέλω να πιστεύω οτι ξέρω τι κάνω... Σορρυ αν κάνω χαζές ερωτήσεις αλλά δεν είμαι και έμπειρος προγραμματιστής. Μπορείς να μου πείς τι εννοείς στο 2)? Με ποιόν τρόπο το κάνω αυτό?

 

Ποσταρε το κωδικα του BinaryHrap και του Comparable

[sp_steve]

Ποσταρε το κωδικα του BinaryHrap και του Comparable

 

Ο Κώδικάς μου είναι αυτός :

 

>#ifndef BINARY_HEAP_H_
#define BINARY_HEAP_H_

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

template <class Comparable>
class BinaryHeap{
            
public:

explicit BinaryHeap( int capacity = 100 );

bool isEmpty( ) const ;

bool isFull( ) const ;

const Comparable & findMin( ) const;

void insert( int x );

void deleteMin( );

void deleteMin( int minItem );

void makeEmpty( );

//int currentSize; // Number of elements in heap max_size

void buildHeap( );

void percolateDown( int hole );
private:
   int currentSize;
   vector<Comparable> array;
   //const vector<Comparable> v;
};
#endif


///////////////////////////////////////////////


#include "BinaryHeap.h"
#include "dsexceptions.h"

// Construct the binary heap.
template <class Comparable>
BinaryHeap<Comparable>::BinaryHeap(int capacity )
 : array( capacity + 1 ), currentSize( 0 )
{
}

/* Construct the binary heap.
// v is a vector containing the initial items.
template <class Comparable>
BinaryHeap<Comparable>::BinaryHeap(const vector<Comparable> & v )
 : array( v.size( ) + 1 ), currentSize( v.size( ) )
{
   for( int i = 0; i < v.size( ); i++ )
       array[ i + 1 ] = v[ i ];
   buildHeap( );
}*/

// Insert item x into the priority queue, maintaining heap order.
// Duplicates are allowed.
template <class Comparable>
void BinaryHeap<Comparable>::insert( int x ) 
{
   array[ 0 ] = x;   // initialize sentinel
   if( currentSize + 1 == array.size( ) )
       array.resize( array.size( ) * 2 + 1 );

     // Percolate up
   int hole = ++currentSize;
   for( ; x < array[ hole / 2 ]; hole /= 2 )
       array[ hole ] = array[ hole / 2 ];
   array[ hole ] = x;
}

// Find the smallest item in the priority queue.
// Return the smallest item, or throw UnderflowException if empty.
template <class Comparable>
const Comparable & BinaryHeap<Comparable>::findMin( ) const
{
   if( isEmpty( ) )
       //throw Underflow( );
   return array[ 1 ];
}

// Remove the smallest item from the priority queue.
// Throw UnderflowException if empty.
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( )
{
   if( isEmpty( ) )
       //throw Underflow( );

   array[ 1 ] = array[ currentSize-- ];
   percolateDown( 1 );
}

// Remove the smallest item from the priority queue
// and place it in minItem. Throw UnderflowException if empty.
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( int minItem )
{
   minItem = findMin( );
   array[ 1 ] = array[ currentSize-- ];
   percolateDown( 1 );
}

// Establish heap-order property from an arbitrary
// arrangement of items. Runs in linear time.
template <class Comparable>
void BinaryHeap<Comparable>::buildHeap( )
{
   for( int i = currentSize / 2; i > 0; i-- )
       percolateDown( i );
}

// Test if the priority queue is logically empty.
// Return true if empty, false otherwise.
template <class Comparable>
bool BinaryHeap<Comparable>::isEmpty( ) const
{
   return currentSize == 0;
}

// Make the priority queue logically empty.
template <class Comparable>
void BinaryHeap<Comparable>::makeEmpty( )
{
   currentSize = 0;
}

// Internal method to percolate down in the heap.
// hole is the index at which the percolate begins.
template <class Comparable>
void BinaryHeap<Comparable>::percolateDown( int hole )
{
   int child;
   Comparable tmp = array[ hole ];

   for( ; hole * 2 <= currentSize; hole = child )
   {
       child = hole * 2;
       if( child != currentSize && array[ child + 1 ] < array[ child ] )
           child++;
       if( array[ child ] < tmp )
           array[ hole ] = array[ child ];
       else
           break;
   }
   array[ hole ] = tmp;
}



//////////////////////////////////////////////

int main( )

{

int numItems = 1000;


BinaryHeap<class Comparable> heap[numItems];

int i = 37;

int x;

//try

//{

for( i = 37; i != 0; i = ( i + 37 ) % numItems ) 
{heap.insert( i );}

for( i = 1; i < numItems; i++ )

{

heap.deleteMin( x );

if( x != i ) cout << "Oops! " << i << endl;

}

for( i = 37; i != 0; i = ( i + 37 ) % numItems )

{heap.insert( i );}

heap.insert( 0 );

heap.insert( i = 999999 ); // Should overflow

//}

/*catch(Overflow )

{ cout << "Overflow (expected)! " << i << endl; }

*/

return 0;
system("PAUSE");
}

 

Φαίνεται λίγο "άτσαλος" γιατί άλλα κομμάτια κώδικα τα έχω βρεί και τα έχω ενώσει και άλλα τα έχω γράψει μόνος μου.

[παπι]

Στη main αντι για

BinaryHeap<class Comparable> heap[numItems];

βαλεBinaryHeap<char> heap(numItems);

[sp_steve]

Στη main αντι για

BinaryHeap<class Comparable> heap[numItems];

βαλεBinaryHeap<char> heap(numItems);

 

Έτσι όντως λειτουργεί... σ'ευχαριστώ..

 

Να ρωτήσω και κάτι άλλο που προέκυψε...Φτιάχνω το σώμα του δημιουργού BinaryHeap(int) και θέλω να περάσω σαν όρισμα εναν vector που τον δηλώνω σαν private ως εξής : const vector<Comparable> v;

 

O Constructor εχει την μορφή:

 

>template <class Comparable>
BinaryHeap<Comparable>::BinaryHeap(const vector<Comparable> &v)
 : array( v.size( ) + 1 ), currentSize( v.size( ) )
{
   for( int i = 0; i < v.size( ); i++ )
       array[ i + 1 ] = v[ i ];
   buildHeap( );
}

 

και μου βγάζει πρόβλημα στην 3η γραμμή.

** και το array ειναι δηλωμένο ως vector...

 

Είναι συντακτικό το λάθος μου? ή κατι άλλο?