1
Ich arbeite an einem Projekt, das ich eine Header-Datei zu meiner main.cpp enthalten muss. Die Headerdatei ist ein Heap, der eine Vorlagendatei verwendet. Aus Gründen, die mir entgehen, können die Funktionen zum Einfügen und Entfernen nicht in der Hauptdatei "gesehen" werden. Ich bekomme eine Fehlermeldung: C: /Users/Tito/Documents/C++proj/cs3304/Homework2_2/Homework10/main.cpp: 58: 17: Fehler: Anfrage für Mitglied 'Entfernen' in 'enter1', was ist des Nicht-Klassen-Typs 'priority_queue_heap()'. Kann mir bitte jemand sagen, wo ich falsch liege? Ich werde es wirklich zu schätzen wissen.Nicht auf Funktionen von Objekt
Dank
Hier sind die Codezeilen:
Main.cpp:
/**
* Insert a few elements into a heap and the remove them
* one by one and see if we get them in the right.
*/
#include "priority_queue_heap.h"
#include "heap.h"
#include <iostream>
#include <ctime>
using namespace std;
int test1() {
heap<int> hp;
hp.insert(1);
hp.insert(2);
hp.insert(3);
hp.insert(4);
hp.insert(5);
hp.check_heap();
int x = hp.remove();
cout << "removed " << x << endl;
x = hp.remove();
cout << "removed " << x << endl;
x = hp.remove();
cout << "removed " << x << endl;
x = hp.remove();
cout << "removed " << x << endl;
x = hp.remove();
cout << "removed " << x << endl;
cout << "empty? " << hp.is_empty() << endl;
}
void test2() {
srand(time(NULL));
heap<int> hp;
for(int i = 0; i < 30; i++) {
hp.insert(rand());
}
while(!hp.is_empty()) {
int x = hp.remove();
cout << x << endl;
}
}
int main() {
/*test1();
test2();*/
priority_queue_heap<int> enter1();
enter1.insert(135);
enter1.insert(909);
enter1.insert(203);
cout<<endl;
cout<< "values to be removed" << endl;
cout << enter1.remove() << endl;
}
heap.h:
#ifndef HEAP_H
#define HEAP_H
/**
* This class implements a heap as described in the text.
* We will treat it as a priority queue.
*/
template <class T>
class heap {
public:
static const int CAPACITY = 10;
heap() {
size = 0;
}
bool is_empty() const { return size == 0;}
bool is_full() const { return size == CAPACITY; }
/**
* Remove the largest value from this heap and return it.
*
* Precondition: heap is not empty.
*/
T remove();
/**
* Inserts the 'value' into the heap.
*
* Precondition: heap is not full
*/
void insert(const T& value);
/**
* Check if the heap is valid.
* Prints out each parent and its children (for all nodes with children)
* Stops when a parent is less than one or both of its children
* Prints 'check' for each parent that is greater than or equal to its
children
*/
bool check_heap();
private:
T data[CAPACITY];
int size;
};
#include "heap.template"
#endif // HEAP_H
heap.template:
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <iomanip>
/*
* parent index is p, children are at indices 2*p+1 and 2*p+2
* You must check that those are in range
*
* child index is c, parent index is (c-1)/2 (integer division)
*/
/**
* Inserts the 'value' into the heap.
*
* Precondition: heap is not full
*/
template <class T>
void heap<T>::insert(const T& value) {
assert(!is_full());
//std::cout << size << std::endl;
// add the value to a new node in proper position
data[size] = value;
size++;
// move the value up the tree as needed
int child = size-1; // index of the new 'node'
int parent = (child-1)/2; // index of the parent
while((child > 0) && (data[parent] < data[child])) {
// swap parent and child values
T tmp = data[parent];
data[parent] = data[child];
data[child] = tmp;
// update parent and child
child = parent; // this is where new value is!
parent = (child-1)/2;
}
// it's a heap!
}
/**
* Remove the largest value from this heap and return it.
*
* Precondition: heap is not empty.
*/
template <class T>
T heap<T>::remove() {
assert(!is_empty());
// grab first element, save it for return later
T save = data[0];
// copy last value in list to the beginning
// decrement size
data[0] = data[size-1];
size--;
// size--;
// data[0] = data[size];
// sift the new first element down until it finds its place
int parent = 0;
int left_child = 2*parent+1;
int right_child = 2*parent+2;
bool still_working = true;
while(still_working && left_child < size) { // while the parent has at
least one child
if(right_child >= size) {
// only the left child to worry about
if(data[parent] < data[left_child]) {
// out of order, so swap them
T t = data[parent];
data[parent] = data[left_child];
data[left_child] = t;
parent = left_child;
still_working = false; // we must be done!
} else {
still_working = false;
}
} else {
// two children
if(data[left_child] > data[right_child]) {
//left child larger
if(data[parent] < data[left_child]) {
// out of order, so swap them
T t = data[parent];
data[parent] = data[left_child];
data[left_child] = t;
parent = left_child;
} else {
still_working = false;
}
} else {
// right child larger
if(data[parent] < data[right_child]) {
// out of order, so swap them
T t = data[parent];
data[parent] = data[right_child];
data[right_child] = t;
parent = right_child;
} else {
still_working = false;
}
}
left_child = 2*parent + 1;
right_child = 2*parent + 2;
}
}
return save;
}
/**
* Check if the heap is valid.
* Prints out each parent and its children (for all nodes with children)
* Stops when a parent is less than one or both of its children
* Prints 'check' for each parent that is greater than or equal to its
children
*/
template <class T>
bool heap<T>::check_heap() {
for(int p = 0; p < size; p++) {
int cl = 2*p+1;
int cr = 2*p+2;
std::cout << std::setw(5) << p << std::setw(10) << data[p];
if(cl < size) { // p has a left child?
std::cout << std::setw(10) << data[cl];
if(data[p] < data[cl]) {
std:exit(1);
}
}
if(cr < size) { // p has a right child?
std::cout << std::setw(10) << data[cr];
if(data[p] < data[cr])
std::exit(1);
}
std::cout << std::endl;
}
return true;
}
priority_queue_simple.template:
#include <cassert>
/**
* Remove the largest value from this priority queue and return it.
*
* Precondition: priority queue is not empty.
*/
template <class T>
T priority_queue_simple<T>::remove() {
assert(size > 0);
int imax = 0;
for(int i = 1; i < size; i++) {
if(data[i] > data[imax])
imax = i;
}
T tmp = data[imax];
data[imax] = data[size-1];
size--;
return tmp;
}
/**
* Inserts the 'value' into the priority queue.
*
* Precondition: priority queue is not full
*/
template <class T>
void priority_queue_simple<T>::insert(const T& value) {
assert(size < CAPACITY);
size++;
data[size-1] = value;
}
priority_queue_heap.h:
#ifndef PRIORITY_QUEUE_HEAP_H
#define PRIORITY_QUEUE_HEAP_H
//#include "heap.h"
template <class T>
class priority_queue_heap {
priority_queue_heap();
bool is_empty() const;
bool is_full() const;
/**
* Remove the largest value from this priority queue and return it.
*
* Precondition: priority queue is not empty.
*/
T remove();
/**
* Inserts the 'value' into the priority queue.
*
* Precondition: priority queue is not full
*/
void insert(const T& value);
private:
heap<T> pri_que;
};
#include "priority_queue_heap.template"
#endif // PRIORITY_QUEUE_HEAP_H
template <class T>
T priority_queue_heap<T>::remove()
{
return pri_que.remove();
}
priority_queue_heap.template:
template <class T>
T priority_queue_heap<T>::remove()
{
return pri_que.remove();
}
template <class T>
void priority_queue_heap<T>::insert(const T& value)
{
pri_que.insert(value);
}
priority_queue_simple.h:
#ifndef PRIORITY_QUEUE_SIMPLE_H
#define PRIORITY_QUEUE_SIMPLE_H
/**
* This class implements a priority queue using a very simple strategy:
* Store the values in an array.
* Add new values at the end.
* When asked to remove a value, search for the largest (linear search)
*
*/
template <class T>
class priority_queue_simple {
public:
static const int CAPACITY = 30;
priority_queue_simple() {
size = 0;
}
bool is_empty() const {
return size == 0;
}
bool is_full() const {
return size == CAPACITY;
}
/**
* Remove the largest value from this priority queue and return it.
*
* Precondition: priority queue is not empty.
*/
T remove();
/**
* Inserts the 'value' into the priority queue.
*
* Precondition: priority queue is not full
*/
void insert(const T& value);
private:
T data[CAPACITY];
int size;
};
#include "priority_queue_simple.template"
#endif // PRIORITY_QUEUE_SIMPLE_H