i need help in this code
Author |
Message |
babyman
|
Posted: Tue Dec 09, 2008 12:55 pm Post subject: i need help in this code |
|
|
Hi,
I have not used c++ for long time as i am just minoring in computer science.
I had an assignment in which i was required to do the following:
You are asked to provide a C++ class to implement a MAX heap of integers.
Your class should have the appropriate constructors (including a copy-constructor)
and destructor. In addition, your class should provide the following operators and
functions:
(a) operator+ to allow for adding of two heaps (e.g., heap3 = heap1 +
heap2 results in heap3 contacting the element of heap1 and heap2).
(b) operator+ to allow for adding a single integer to a heap (e.g., heap2 =
heap1 + 5 results in heap2 containing the elements of heap and the value
5)
(c) operator[] to allow for accessing the individual elements of the heap as
they were stored in a sorted array (e.g., heap[5] accesses the 5th largest
element in the heap).
(d) operator= to allow heap assignments (e.g. heap1 = heap2 = heap3)
(e) operator+= to allow heap assignments (e.g. heap1 += heap2 and
heap3 += 5)
(f) operator<< to allow for printing heaps on cout (e.g. cout << heap1
prints heap1 on cout).
Note: for an example of a basic MAX heap class see:
http://www.cise.ufl.edu/~raj/Pgm2.11
http://www.cise.ufl.edu/~raj/Pgm2.12
http://www.cise.ufl.edu/~raj/Pgm2.13
I built this code and need somebody to refer me 2 my mistakes. i really appreciate ur help.
header file:
c++: |
#ifndef HEAP_H
#define HEAP_H
class heap
{
friend ostream &operator<<( ostream&, const heap & );
private:
Type *array;
int MaxSize, Nel;
// Max. size of the heap, no. of elements
void Adjust(Type a[], int i, int n);
public:
heap(int MSize):
heap (const heap &);
~heap();
heap &operator+ (const heap &);
heap &operator+=(const heap &);
heap &operator+ (int );
operator=( const heap &);
operator[]( int);
bool Insert(Type item);
// Insert item.
bool DelMax(Type& item);
// Delete the maximum.
};
#endif
|
cpp file:
c++: |
#include <iostream>
#include "heap.h"
using namespace std;
heap:: heap(int size)
MaxSize(MSize)
{
array = new Type[MaxSize+1];
Nel=0;
};
heap::~heap()
{
delete []array;
};
heap::heap (const heap &a)
{
array=new Type [MaxSize+1];
for (int i=0;i=MaxSize;i++)
array[i]=a[i];
}
friend ostream &operator<<( ostream &output, const heap &a)
{
int i;
// output private ptr-based array
for ( i = 0; i = a.MaxSize; i++ ) {
output << setw( 12 ) << a.array[ i ];
if ( ( i + 1 ) % 4 == 0 ) // 4 numbers per row of output
output << endl;
} // end for
if ( i % 4 != 0 ) // end last line of output
output << endl;
return output; // enables cout << x << y;
} // end function operator<<
const heap::heap &operator+ (const heap &heap1)
{
Type *array1;
int x=sizeof(heap1)/4;
array1=new[Maxsize+2+x];
for (int i=0;i=MaxSize;i++)
array1[i]=array[i];
for (i=Maxsize;i=x+MaxSize;i++)
array1[i]=heap1.array[i-MaxSize];
delete []array1;
};
const heap::heap &operator+=(const heap &right)
{
Type *array1;
MaxSize1=MaxSize;
array=new Type[MaxSize+1];
for (int i=0;i=MaxSize;i++)
array1[i]=array[i];
delete []array;
MaxSize=MaxSize1+sizeof(right.array)/4;
Type *array;
array=new Type[MaxSize+1];
for (i=0;i=MaxSize1;i++)
array[i]=array1[i];
for (i=MaxSize1+1;i=MaxSize;i++)
array[i]=right.array[i-MaxSize-1];
}
const heap::heap &operator+ (int x)
{
MaxSize=Maxsize+1;
array[MaxSize]=x;
}
const heap &heap::operator=( const heap &right )
{
if ( &right != this ) // check for self-assignment
{
// for arrays of different sizes, deallocate original
// left-side array, then allocate new left-side array
if ( MaxSize != right.size )
{
delete [] array; // reclaim space
MaxSize = right.MaxSize; // resize this object
array = new int[ MaxSize ]; // create space for array copy
} // end inner if
for ( int i = 0; i < MaxSize; i++ )
array[ i ] = right.array[ i ]; // copy array into object
} // end outer if
return *this; // enables x = y = z, for example
} // end function operator=
int &heap::operator[]( int subscript )
{
// check for subscript out of range error
if ( subscript < 0 || subscript >= MaxSize ) {
cout << "\nError: Subscript " << subscript
<< " out of range" << endl;
exit( 1 ); // terminate program; subscript out of range
} // end if
return array[ subscript ]; // reference return
} // end function operator[]
bool heap::Insert(Type item)
{ // Inserts item.
int i = ++Nel;
if (i==MaxSize)
{
cout << "heap size exceeded"
<< endl;
return false;
}
while ((i>1) && (array[i/2]<item))
{
array[i] = array[i/2];
i /= 2;
}
array[i] = item;
return true;
}
void heap::Adjust(Type a[], int i, int n)
// The complete binary trees with roots 2*i and 2*i+1 are
// combined with node i to form a heap rooted at i. No
// node has an address greater than n or less than 1.
{
int j = 2*i, item = a[i];
while (j <= n)
{
if ((j<n) && (a[j]<a[j+1]))
j++;
// Compare left and right child
// and let j be the larger child.
if (item >= a[j])
break;
// A position for item is found.
a[j/2] = a[j];
j *= 2;
}
a[j/2] = item;
}
bool heap::DelMax(Type& item)
{
if (!Nel)
{ cout << "heap is empty"<< endl;
return false;
}
item=array[1];
array[1]=array[Nel--];
Adjust(array, 1, Nel);
return true;
};
|
Mod Edit: Remember syntax tags! Thanks code: | [syntax="cpp"]Code Here[/syntax] |
|
|
|
|
|
|
Sponsor Sponsor
|
|
|
|
|