如何向我的堆 Class 添加一个 peek 函数？

Question

我对 Heap.h 和 cpp 文件以及 PQ.. 中的先前代码进行了一些更改，并添加了一个 PQ.cpp。我正在尝试创建一个堆 ADT，它将成为优先级队列的堆实现。我只是想在堆声明中添加一个 peek 函数，但我不能不收到错误。其中包括这些错误。

未定义的体系结构符号x86_64： "PrecondViolatedExcep::PrecondViolatedExcep(std::__1::basic_string, std::__1::allocator > const&)"，引用自： pqClass::peek() PQ.o 中的常量 heapClass::peekTop() Heap.o 中的常量 "itemClass::GetDirection() const"，引用自： main.o 中的 enqRequest(int, int, int, bool, itemClass&, pqClass, pqClass) 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.

Answer 1

您需要在 .cpp 文件中的函数签名中添加一个 const，以便它与您的 .h 文件中的签名匹配。

Answer 2

您正在 PQ.h 中创建抽象对象 class:

heapClass H;

您还试图仅在堆为空时才访问元素

heapItemType heapClass::peekTop(){
  if (HeapIsEmpty())

  return heapItemType[0];
}

你需要这样的东西（以防你的类型是指针）：

heapItemType heapClass::peekTop(){
  if (HeapIsEmpty()) {
    return nullptr;
  }

  return heapItemType[0];
}

或者你需要某种无效的对象你可以return在空堆的情况下

Answer 3

通过查看您的代码，我可以看出您已经定义了 heapClass 的方法：

virtual heapItemType peekTop() const =0;

这被声明为纯虚函数，因为您在 class 中的声明中将其设置为等于 0。这将导致您的 heapClass 变得抽象。我从你的 pqClass 中看到的是你正在存储一个 heapClass 类型的对象。我在这里看不到任何继承，这是您可能会遇到构建或编译器错误的原因之一。您不能将 class 中的方法或函数声明为纯虚函数而不继承它。我不知道这是不是你想要的。但就目前而言，您的 heapClass 对这种类型的方法声明是抽象的！

您需要从其声明中删除 = 0 或继承此 class，派生的 class 将使用 override 指令实现此功能。此外 Anon Mail 是正确的，您还需要在实现文件中将方法声明为 const，Andrew Lavq 对函数的实际实现有一个有效的观点。

如何向我的堆 Class 添加一个 peek 函数？

How do I add a peek function to my heap Class?

c++

debugging

heap

data-structures

c++11