1
我對Heap.h和cpp文件以及PQ中的前面的代碼做了一些更改，並添加了PQ.cpp。我正在嘗試創建一個堆ADT，它將成爲一個優先級隊列的堆實現。我只是試圖添加一個peek函數堆說明，但我不能沒有收到錯誤。 其中包含這些錯誤。如何添加peek函數到我的堆類？
爲架構x86_64的未定義符號： 「PrecondViolatedExcep :: PrecondViolatedExcep（STD :: __ 1 :: basic_string的，性病:: __ 1 ::分配器>常量&）」，從引用： pqClass :: PEEK（）const的在PQ.o Heap.o中的heapClass :: peekTop（）const 「itemClass :: GetDirection（）const」，引用來自： enqRequest（int，int，int，bool，itemClass &，pqClass，pqClass）in main。 o ld：找不到架構x86_64的符號 clang：錯誤：連接器命令失敗，退出代碼1（使用-v查看調用）
Heap.h
// *********************************************************
// Header file Heap.h for the ADT heap.
// *********************************************************
#include "Data.h" // definition of itemClass
#pragma once
const int MAX_HEAP = 20;
typedef itemClass keyType;
typedef itemClass heapItemType;
class heapClass
{
public:
heapClass(); // default constructor
// copy constructor and destructor are
// supplied by the compiler
// heap operations:
virtual bool HeapIsEmpty() const;
// Determines whether a heap is empty.
// Precondition: None.
// Postcondition: Returns true if the heap is empty;
// otherwise returns false.
virtual void HeapInsert(const heapItemType& NewItem,
bool& Success);
// Inserts an item into a heap.
// Precondition: NewItem is the item to be inserted.
// Postcondition: If the heap was not full, NewItem is
// in its proper position and Success is true;
// otherwise Success is false.
virtual void HeapDelete(heapItemType& RootItem,
bool& Success);
// Retrieves and deletes the item in the root of a heap.
// This item has the largest search key in the heap.
// Precondition: None.
// Postcondition: If the heap was not empty, RootItem
// is the retrieved item, the item is deleted from the
// heap, and Success is true. However, if the heap was
// empty, removal is impossible and Success is false.
heapItemType peekTop() const throw(PrecondViolatedExcep);
protected:
void RebuildHeap(int Root);
// Converts the semiheap rooted at index Root
// into a heap.
private:
heapItemType Items[MAX_HEAP]; // array of heap items
int Size; // number of heap items
}; // end class
// End of header file.
Heap.cpp
// *********************************************************
// Implementation file Heap.cpp for the ADT heap.
// *********************************************************
#include "Heap.h" // header file for heap
heapClass::heapClass() : Size(0)
{
} // end default constructor
bool heapClass::HeapIsEmpty() const
{
return bool(Size == 0);
} // end HeapIsEmpty
void heapClass::HeapInsert(const heapItemType& NewItem,
bool& Success)
// Method: Inserts the new item after the last item in the
// heap and trickles it up to its proper position. The
// heap is full when it contains MAX_HEAP items.
{
Success = bool(Size < MAX_HEAP);
if (Success)
{ // place the new item at the end of the heap
Items[Size] = NewItem;
// trickle new item up to its proper position
int Place = Size;
int Parent = (Place - 1)/2;
while ((Parent >= 0) &&
(Items[Place].Key() > Items[Parent].Key()))
{ // swap Items[Place] and Items[Parent]
heapItemType Temp = Items[Parent];
Items[Parent] = Items[Place];
Items[Place] = Temp;
Place = Parent;
Parent = (Place -1)/2;
} // end while
++Size;
} // end if
} // end HeapInsert
void heapClass::HeapDelete(heapItemType& RootItem,
bool& Success)
// Method: Swaps the last item in the heap with the root
// and trickles it down to its proper position.
{
Success = bool(!HeapIsEmpty());
if (Success)
{ RootItem = Items[0];
Items[0] = Items[--Size];
RebuildHeap(0);
} // end if
} // end HeapDelete
void heapClass::RebuildHeap(int Root)
{
// if the root is not a leaf and the root's search key
// is less than the larger of the search keys in the
// root's children
int Child = 2 * Root + 1; // index of root's left
// child, if any
if (Child < Size)
{ // root is not a leaf, so it has a left child at Child
int RightChild = Child + 1; // index of right child,
// if any
// if root has a right child, find larger child
if ((RightChild < Size) &&
(Items[RightChild].Key() > Items[Child].Key()))
Child = RightChild; // index of larger child
// if the root's value is smaller than the
// value in the larger child, swap values
if (Items[Root].Key() < Items[Child].Key())
{ heapItemType Temp = Items[Root];
Items[Root] = Items[Child];
Items[Child] = Temp;
// transform the new subtree into a heap
RebuildHeap(Child);
} // end if
} // end if
// if root is a leaf, do nothing
} // end RebuildHeap
heapItemType heapClass::peekTop() const throw(PrecondViolatedExcep)
{
if (HeapIsEmpty())
throw PrecondViolatedExcep("Attempted peek into an empty heap.");
return Items[0];
} // end peekTop
優先級隊列 PQ.h
// *********************************************************
// Header file PQ.h for the ADT priority queue.
// Heap implementation.
// *********************************************************
#include "Heap.h" // ADT heap operations
typedef heapItemType pqItemType;
class pqClass
{
public:
// default constructor, copy constructor, and
// destructor are supplied by the compiler
// priority-queue operations:
virtual bool PQueueIsEmpty() const;
virtual void PQueueInsert(const pqItemType& NewItem,
bool& Success);
virtual void PQueueDelete(pqItemType& PriorityItem,
bool& Success);
pqItemType peek() const throw(PrecondViolatedExcep);
private:
heapClass H;
}; // end class
// End of header file.
PQ.cpp
#include <stdio.h>
// *********************************************************
// Implementation file PQ.cpp for the ADT priority queue.
// A heap represents the priority queue.
// *********************************************************
#include "PQ.h" // header file for priority queue
bool pqClass::PQueueIsEmpty() const
{
return H.HeapIsEmpty();
} // end PQueueIsEmpty
void pqClass::PQueueInsert(const pqItemType& NewItem,
bool& Success)
{
H.HeapInsert(NewItem, Success);
} // end PQueueInsert
void pqClass::PQueueDelete(pqItemType& PriorityItem,
bool& Success)
{
H.HeapDelete(PriorityItem, Success);
} // end PQueueDelete
pqItemType pqClass::peek() const throw(PrecondViolatedExcep) {
try
{
return H.peekTop();
}
catch (PrecondViolatedExcep e) {
throw PrecondViolatedExcep("Attempted peek into an empty priority queue."); } // end try/catch
} // end peek
// End of implementation file.
此外，請參閱有關如何改進功能實現的其他答案。 –